はじめてのにき

_ 1.5倍とか

http://www.kmonos.net/wlog/111.html#_2334100705

なんかこの話は gus さんと何度かしたのでなんか書く。

結論としてはなんか C++ が残念な気がするという話なんだけど、 メモリアロケータの実際とか自信無い面があるので少しあやしい。 全く測定とかはしてないし。

まず、要素数が少ない時。

この時はどうせメモリアロケータ的に 穴もへったくれもなくてサイズごとのプール使ってるんじゃないのか。 そしてキリのいい数字の方がサイズごとのプールにちょっきり入りそうだし、 倍々でいいんじゃないの。

次に要素数多い時。

なんか mmap しはじめるはず。 ということで使い捨てたメモリは munmap されるだろうし やはり依然として穴とか関係ない感がある。

ただやはり瞬間的に要素数 * 3 のメモリが必要になるわけだし、 このへんになると直感的に 1.5 倍とか少なめな方が良さげな気もする。

そもそも要素数が大きくなってくると realloc が mremap になっていって、 mremap ならそもそも アドレスが移動しようがコピーいらなくなるんじゃね？ ならし計算量どころか毎回 O(1) なんじゃね？ という話を gus さんにした。

すると C++ の allocator は realloc しないと教えてもらった。 kinaba さんが引用している comp.lang.c++ の 議論にもあるけど、 C++ の vector は、 必ず、次の領域の allocate => コピー => free って感じでやる、らしい。

さて、仮に C++ の allocator に realloc があったらいいのかっていうと、 どうも realloc ではうまくいかない気がする。 というのは non-POD な型の場合、 アドレスの移動が起きた場合、 適切にコピーコンストラクタ呼んでやらないといけなくて、 しかし realloc でアドレスが変わった時って、 前の pointer は既に free されているのよね。

なんか話としては

• is_pod とかを駆使して pod が vector に入ってる時くらいは realloc にする
• あるいは user がアドレス移動 OK だよ、と vector に policy として伝える
• デフォルトでは何もしない move_address とかいう関数を全てのクラスに暗黙で定義されるようにしておいて、アドレスの変化が重要な子はそれを定義
• そもそも realloc がアドレス変える時に古い address が free されてるのが悪くて、 address が変わる時は user が free しなければならない realloc があればいい
• あるいは、アドレスが変わる時は失敗する realloc があればいい
• mremap ならそれはできるはずなので、サイズが大きくなった時用の allocator だけは自分で…

などなど。なんか C++ ダメなんじゃないかと思った。 0x とかで解決されてるよ! とかだったらすいません。

(02:22)

_ コピーコンストラクタ

でその議論の結論としては

#include <stdio.h>

struct S {
    S(const S& s) {
    }
};

int main() {
    // copy コンストラクタを定義たせいでデフォルトコンストラクタが無い時は
    //S s;

    // こうすればいいよ!
    S s(s);
}

(02:32)

_ RIP相対

http://twitter.com/kazuho/status/17851784436

x86-64 の場合、無いと大変なことになる系かなと

何故でしょうか!!!

とかいうのはめんどいので書く。

x86-64 さんは、こうアドレス空間が広いです。 64bit 。 x86 と同じ 32bit 絶対でデータを mov とかしようとすると、 届かないことがあったりします。 つまりどういうことかというと、

void foo() {
    puts("foo");
}

をコンパイルして objdump する。

> gcc -c -g rip.c
> objdump -Sr rip.o

rip.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <foo>:
void foo() {
   0:   55                    push   %rbp
   1:   48 89 e5              mov    %rsp,%rbp
    puts("foo");
   4:   bf 00 00 00 00        mov    $0x0,%edi
        5: R_X86_64_32 .rodata
   9:   e8 00 00 00 00        callq  e <foo+0xe>
        a: R_X86_64_PC32 puts+0xfffffffffffffffc
}
   e:   c9                    leaveq
   f:   c3                    retq

とかすると、まぁ callq の引数部分が 32bit 相対になっていて、 ここがその、 so とかになった時に loader が解決できない可能性があるわけ。

で、それが理由で普通に -shared とかすると、

> gcc -g rip.c -shared -o rip.so
/usr/bin/ld: /tmp/ccbHkebh.o: relocation R_X86_64_32 against `.rodata' can not be used when making a shared object; recompile with -fPIC
/tmp/ccbHkebh.o: could not read symbols: Bad value
collect2: ld returned 1 exit status
zsh: exit 1     gcc -g rip.c -shared -o rip.so

とまぁ怒られるわけです。つまりどこにでも置けるように PIC (position independent code) にしやがれ、と。

で言われた通りに -fPIC とかつけるとどうなるかっつーと、

0000000000000000 <foo>:
void foo() {
   0:   55                    push   %rbp
   1:   48 89 e5              mov    %rsp,%rbp
    puts("foo");
   4:   48 8d 3d 00 00 00 00  lea    0x0(%rip),%rdi        # b <foo+0xb>
        7: R_X86_64_PC32 .rodata+0xfffffffffffffffc
   b:   e8 00 00 00 00        callq  10 <foo+0x10>
        c: R_X86_64_PLT32  puts+0xfffffffffffffffc
}
  10:   c9                    leaveq
  11:   c3                    retq

こうなる。 ここに rip 相対が登場して、 .text と .rodata の相対的な位置は変わらんようにしてある (っていうかまとめて mmap するって話だと思う) のでちゃんと relocation できますめでたしめでたしというような。

ちなみに x86 だとどうなるかというと、

00000000 <foo>:
void foo() {
   0:   55                    push   %ebp
   1:   89 e5                 mov    %esp,%ebp
   3:   53                    push   %ebx
   4:   83 ec 14              sub    $0x14,%esp
   7:   e8 fc ff ff ff        call   8 <foo+0x8>
        8: R_386_PC32 __i686.get_pc_thunk.bx
   c:   81 c3 02 00 00 00     add    $0x2,%ebx
        e: R_386_GOTPC _GLOBAL_OFFSET_TABLE_
    puts("foo");
  12:   8d 83 00 00 00 00     lea    0x0(%ebx),%eax
        14: R_386_GOTOFF .rodata
  18:   89 04 24              mov    %eax,(%esp)
  1b:   e8 fc ff ff ff        call   1c <foo+0x1c>
        1c: R_386_PLT32 puts
}
  20:   83 c4 14              add    $0x14,%esp
  23:   5b                    pop    %ebx
  24:   5d                    pop    %ebp
  25:   c3                    ret

なんか call が増えて大変なことになる。 __i686.get_pc_thunk.bx の定義は

08048416 <__i686.get_pc_thunk.bx>:
 8048416:       8b 1c 24                mov    (%esp),%ebx
 8048419:       c3                      ret

という感じで、まぁ要は call で eip 取ってくるテクニック。

ところで、 なんで call pop じゃダメなのかは知らない。 intel さんが call があると ret やーというような解析を もりっとしていて、 call したのに ret しないと遅くなるとか そいうことだったりとかかなーとか妄想するが知らない。

あと、たしか、 x86-64 は 64bit 絶対 call とか、 64bit 絶対参照とかあったと思う。 このへん使えばどこにでも届くわけだけど、 やらないのは、どうせ PIC の方がいいじゃん (リロケーションのコストとか的に) ってことなのかなぁ。知らない。

(23:33)

_ ↑

こいう話は TCC の時に色々 考えたりしたので、 どっかで話したりする機会ないかなぁとか思いつつ今に至ってる気がする。

謎のメモが出てきた。

http://shinh.skr.jp/m/?date=20090331#p06

(23:36)