Bitmap実装のちょっとした前フリ

前にまつもとさんがtrunkに合わせていたbitmapのパッチが古くなっていたので(早いなぁ)
今のバージョンに合わせて、GC::Profilerで計測してみた。
 

Bitmap適用前

nari@nari-laptop ~/s/r/ruby-trunk> ./miniruby -e "GC::Profiler.enable; a = []; 2000000.times {a << [1, 2]}; GC::Profiler.report"
GC 11 invokes.
Index    Invoke Time(sec)       Use Size(byte)     Total Size(byte)         Total Object                    GC Time(ms)
    1               0.004               193940               212940                10647         0.00000000000000000000
    2               0.008               343720               360360                18018         0.00000000000000000000
    3               0.012               605560               622440                31122         0.40009999999999995568
    4               0.028              1080040              1097460                54873         0.40010000000000001119
    5               0.048              1930760              1949220                97461         0.40000000000000007772
    6               0.080              3468640              3488940               174447         0.80000000000000037748
    7               0.140              6233480              6257160               312858         1.60009999999999985576
    8               0.240             11206920             11236680               561834         2.80010000000000092157
    9               0.388             19052060             19099080               954954         4.80030000000000001137
   10               0.528             24457900             24504480              1225224         6.40040000000000031122
   11               0.788             36612760             36674820              1833741        10.00059999999999504894


More detail.
Index Allocate Increase    Allocate Limit  Use Slot  Have Finalize             Mark Time(ms)            Sweep Time(ms)
    1            808485           8000000        13           true    0.00000000000000000000    0.00000000000000000000
    2            195240           8000000        22          false    0.00000000000000000000    0.00000000000000000000
    3            315524           8000000        38          false    0.40009999999999995568    0.00000000000000014129
    4            379500           8000000        67          false    0.40010000000000001119    0.00000000000000028257
    5           1051688           8000000       119          false    0.40000000000000007772    0.00000000000000000000
    6           2215800           8000000       213          false    0.80000000000000037748    0.00000000000000000000
    7           2546516           8000000       382          false    1.20009999999999994458    0.39999999999999880096
    8           7391544           8000000       686          false    2.00010000000000065512    0.80000000000000193179
    9           7999996           8000000      1166          false    3.60020000000000006679    1.20010000000000216502
   10           9455256           8000000      1496          false    4.80030000000000001137    1.60009999999999807940
   11          15801324           9455217      2239          false    6.80039999999999711378    3.20020000000000104379

 

Bitmap適用後

nari@nari-laptop ~/s/r/ruby1.9_org> ./miniruby -e "GC::Profiler.enable; a = []; 2000000.times {a << [1, 2]}; GC::Profiler.report"
GC 11 invokes.
Index    Invoke Time(sec)       Use Size(byte)     Total Size(byte)         Total Object                    GC Time(ms)
    1               0.000               193880               212940                10647         0.00000000000000000000
    2               0.004               343700               360360                18018         0.39999999999999991118
    3               0.012               605580               622440                31122         0.40009999999999995568
    4               0.028              1080260              1097460                54873         0.80009999999999992237
    5               0.052              1931480              1949220                97461         3.20019999999999971152
    6               0.108              3470240              3488940               174447         6.80049999999999954525
    7               0.216              6236760              6257160               312858        18.00110000000000098908
    8               0.472             11213240             11236680               561834        49.60309999999999774900
    9               1.100             19058380             19099080               954954       134.80850000000000932232
   10               2.536             24459420             24504480              1225224       221.21379999999999199645
   11               4.960             36614280             36658440              1832922       516.83230000000003201421


More detail.
Index Allocate Increase    Allocate Limit  Use Slot  Have Finalize             Mark Time(ms)            Sweep Time(ms)
    1            810547           8000000        13           true    0.00000000000000000000    0.00000000000000000000
    2            195256           8000000        22          false    0.39999999999999991118    0.00000000000000000000
    3            315540           8000000        38          false    0.40009999999999995568    0.00000000000000014129
    4            379580           8000000        67          false    0.80009999999999992237    0.00000000000000000000
    5           1051888           8000000       119          false    2.80019999999999935625    0.40000000000000035527
    6           2216152           8000000       213          false    6.40040000000000031122    0.40009999999999956710
    7           2547188           8000000       382          false   17.60109999999999885745    0.39999999999999985567
    8           7392760           8000000       686          false   48.80310000000000059117    0.80000000000000437428
    9           7999996           8000000      1166          false  133.60839999999998894964    1.20010000000001060272
   10           9453336           8000000      1496          false  219.21370000000001709850    2.00009999999998289155
   11          15801324           9453336      2238          false  513.23199999999997089617    3.60030000000002292637

やっぱり凄く時間がかかってるみたい。特にMark。
数十倍時間がかかってますね。
 

秘蔵bitmapパッチの蔵出し

まぁ、ここからが本題なんだけども、私の秘蔵bitmapパッチを使うと。これだけ速くなりますよと。

nari@nari-laptop ~/s/r/ruby1.9_work> ./miniruby -e "GC::Profiler.enable; a = []; 2000000.times {a << [1, 2]}; GC::Profiler.report"
GC 11 invokes.
Index    Invoke Time(sec)       Use Size(byte)     Total Size(byte)         Total Object                    GC Time(ms)
    1               0.004               194080               213200                10660         0.00000000000000000000
    2               0.004               343980               360800                18040         0.39999999999999991118
    3               0.012               606060               623200                31160         0.40009999999999995568
    4               0.020              1081080              1098800                54940         0.40000000000000007772
    5               0.036              1932840              1951600                97580         0.79999999999999982236
    6               0.068              3472560              3493200               174660         1.20010000000000016662
    7               0.124              6240780              6264800               313240         2.00020000000000042206
    8               0.232             11220300             11250400               562520         3.60019999999999917861
    9               0.400             19065440             19106000               955300         6.40040000000000208757
   10               0.560             24457820             24518000              1225900         8.00050000000000238742
   11               0.828             36612680             36686800              1834340        12.00079999999999813554


More detail.
Index Allocate Increase    Allocate Limit  Use Slot  Have Finalize             Mark Time(ms)            Sweep Time(ms)
    1            808465           8000000        13           true    0.00000000000000000000    0.00000000000000000000
    2            195288           8000000        22          false    0.39999999999999991118    0.00000000000000000000
    3            315620           8000000        38          false    0.40009999999999995568    0.00000000000000014129
    4            379716           8000000        67          false    0.40000000000000007772    0.00000000000000008843
    5           1052104           8000000       119          false    0.39999999999999991118    0.40000000000000018874
    6           2216536           8000000       213          false    0.80000000000000015543    0.40009999999999940057
    7           2547868           8000000       382          false    2.00020000000000042206    0.00000000000000000000
    8           7393976           8000000       686          false    3.20019999999999882334    0.40000000000000146549
    9           7999996           8000000      1165          false    5.60030000000000161009    0.80009999999999903419
   10           9449872           8000000      1495          false    6.80040000000000244285    1.20009999999999572573
   11          15801324           9447281      2237          false   10.40069999999999694751    1.60010000000000163212

Mark時間を2倍くらいで何とか抑えている。
これはBitmapを見つける所を高速化しているおかげ。
Sweepが速くなっているのはmarkを消すのを一括で行っている為だと思われる。
 
ただ、
GC、今よりも1.2倍時間かかりますけど、どうですかっ」
「それ、却下で!」
の流れになる可能性がある。
 
早く投稿したいのだけど、本当にcopy-on-writeに効いてるのか確かめてない。
確かめたら報告としてまとめようかと。
ちょっと最近忙しいので、誰か確かめてくれると嬉しいなぁ。
あと、Markもう少し速くならんだろうか。。。

パッチ