トップ «前の日記(2010-07-05) 最新 次の日記(2010-07-08)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|12|
2022|01|02|03|04|05|06|07|08|09|10|11|12|
2023|01|02|03|04|05|06|07|08|09|10|11|12|
2024|01|02|03|

ToDo:


2010-07-06

_ 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)

本日のツッコミ(全7件) [ツッコミを入れる]
_ k.inaba (2014-05-24 01:33)

穴とか関係あるんかいな、というのは僕も思わなくもなかったんですが、適当にこんなの
#include <vector>
#include <iostream>
using namespace std;
int main() {
        vector<int> x(1, 0);
        vector< pair<int*,int*> > ranges;
        int change = 0, overlap = 0;
        for(int i=1; i<100000000; ++i) {
                int* p = &x[0];
                x.push_back(i);
                int* q = &x[0];
                if( p != q ) {
                        cerr << q << endl;
                        ++change;
                        int* qe = q + x.capacity();
                        for(int k=0; k<ranges.size(); ++k)
                                if( !(qe<=ranges[k].first || ranges[k].second<=q) )
                                        {++overlap; break;}
                        ranges.push_back( make_pair(q,qe) );
                }
        }
        cout << overlap << "/" << change << endl;
}
を書きつつvectorの実装を変えてだんだん倍率下げながら遊んでみると、確かにmsvcrtでもlibstdc++でも1.6〜1.7倍の辺りから再ヒットしだすようになるので、まあそんなものなのかなあと。「要素中くらいの時」のゾーンがそれなりにあるということになるんでしょうか。

アドレスが変わる時は失敗する realloc は欲しいですねえ。

_ mame (2014-05-24 01:33)

> ならし計算量どころか毎回 O(1) なんじゃね?

この現象は Linux の Ruby の String で実際に確認されてます。
mremap の恩恵にあずかれない JRuby や windows では困るらしいですが。
http://redmine.ruby-lang.org/issues/show/905#note-46

_ kosaki (2014-05-24 01:33)

なんかどこかで聞いたことある話だと思ったらmameさんがズバリ書いていてくれた。なんというエスパー

_ shinh (2014-05-24 01:33)

おおたしかに再ヒットしてますね面白い。ただ、 linux+glibc だと後半半分くらいの overlap 、つまりアドレスが急にでかくなって明らかに mmap しはじめてからは、 strace 見ても munmap 呼ばれてるのであまりメモリフラグメンテーションとかは関係ない世界ぽいですね。ただ結構序盤でも overlap してるので、あれーそういうもんかなという感がありました。

手元で 1.5 倍でやってみると、最初に再利用されるのは、

2: 0x12ba030
3: 0x12ba050
4: 0x12ba010
6: 0x12ba050 overlap! 6: 0x12ba050 < 0x12ba050 and 0x12ba05c < 0x12ba068

とかで、 12bytes の領域が 24bytes で再利用されてました。なんか僕のメモリアロケータの脳内モデルとあわない感があり。

_ Rui (2014-05-24 01:33)

CALLとRETをペアにするほうが速いというのはどこかで読んだなーと思ったらAMDの最適化マニュアルでした(*1)。しかし直後の命令にジャンプするCALLは特別扱いで最適化してるからRETとペアにしなくて問題ないとありました。Intelのほうはどうだったっけ、と調べてみると、特にパフォーマンスについて言及がない。まあ最適化してるような気がします。

*1 http://support.amd.com/us/Processor_TechDocs/40546-PUB-Optguide_3-11_5-21-09.pdf PDFの121ページ
*2 http://www.intel.com/Assets/PDF/manual/248966.pdf PDFのページ453

_ m.ukai (2014-05-24 01:33)

> call pop
今時は平気で最適予測できると思いますが、return stack buffer を実装した初期は予測できてなかったんではないかと思います。
古めの x86 processor のことも考えると call pop というコードよりは汎用コードとしてベター、という方針ではないですかね。(-march で CPU を特定すると call pop とか吐いたりするかもしれませんが知りません)

_ shinh (2014-05-24 01:33)

Rui さん m.ukai さんコメントありがとうございますです。

ご指摘の通り、 -mtune= で call/ret になったり call/pop になったりするっぽいです。

call/pop になるもの: native (@ core2 duo), i386, i486, i586, pentium, pentium-mmx, prescott, nocona, core2, winchip-c6, winchip2, c3
call/ret になるもの: pentiumpro, generic, generic32, i686, generic64, pentium2, pentium3, pentium3m, pentium-m, pentium4, pentium4m, k6, k6-2, k6-3, athlon, athlon-tbird, athlon-4, athlon-xp, athlon-mp, k8, k8-sse3, x86-64, c3-2, atom, geode, opteron, opteron-sse3, athlon64, athlon64-sse3, athlon-fx, amdfam10, barcelona, bdver1

これは、 gcc の gcc/config/i386/i386.c の

  /* X86_TUNE_DEEP_BRANCH_PREDICTION */
  m_ATOM | m_PPRO | m_K6_GEODE | m_AMD_MULTIPLE | m_PENT4 | m_GENERIC,

と対応してるみたいです。

ざっと見た感じ、 intel の方は

- 古いのは call/pop
- pentium になって call/ret がペアになってるやつは最適化してあって速くなった。で、 call/pop が相対的にイマイチになったので call/ret に
- さらに新しくなって prescott あたりから call/ret を特殊な扱いとしてくれるようになった

って感じなんですかね。 AMD は m_AMD_MULTIPLE が m_K8 を含んでて、最近の AMD の CPU は全部この分類なのでかわいそうなことになってる、って感じかもです。別のシンボル作って分離してやるといいのかもしれず。

nocona とか core2 で call/ret になったのはこれですかね。

http://gcc.gnu.org/viewcvs?view=revision&revision=124084

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2010年
7月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
1.shinh(2014-05-24 01:33) 2.Gimite(2014-05-24 01:33) 3.シンX(2014-05-24 01:33)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h