Google Sparse Hash Map - berupon’s diary

Google Sparse Hash Mapってどんなもんなんだろう？って思ってちょっと調べてみた。
http://goog-sparsehash.sourceforge.net/
documentがSGIのSTLに合わせてあるらしいんだけど、統一されると既にSGIのSTLを知っている人にはとても嬉しいんだろうなぁ。。

消費メモリが少ないけど処理速度が犠牲にしたのがsparse系で、
その逆で消費メモリは多めだけど、処理速度を追求したのがdense系。
濃い薄いっていうのは値を格納する骨組みの事をイメージしてるのかな？
setとmapの違いは、setはkeyとvalueが同じで、mapはpairで格納するkeyとvalueが異なる。
hash関数を使うので、要素の並び順を規定したい場合は、違うcontainerのが良いらしい。
sparsetableは、消費メモリをけちった配列という感じっぽい。

気になるのは標準のstd::mapと比較した時のperformanceで
http://goog-sparsehash.sourceforge.net/doc/performance.html
を見てみると、とっても良い感じ。

http://groups-beta.google.com/group/google-sparsehash/browse_thread/thread/a95daaf8769da17b/5403eeb8b1828349
を見てみるとVC7.1で使えるようにalexisさんという人が改造したようで、
それをちょっと自分の環境でもbuildしてbenchmarkを取ってみた。

自分の貧弱な環境では1千万回も回していたら動作がいつ終わるかわからないし、
Memoryも溢れてしまうので、5万回くらいにした。STANDARD MAPのところで、
benchmarkの時間以上に異様に長い時間止まってしまうのは謎。なんでだろう…。

[ WCPUID Version 3.3  (c) 1996-2004  By H.Oda! ]

  Processor #1 : AMD Athlon XP (Model 6) / 8253754B
      Platform : Socket A (Socket 462)     
 Vendor String : AuthenticAMD
      CPU Type : Original OEM Processor (0)
        Family : 6  (7)
         Model : 6  (6)
   Stepping ID : 2  (2)
      Brand ID : -  (-)
          APIC : ----
HT Log.CPU Cnt : ----
   Name String : AMD Athlon(tm) XP 1500+

Internal Clock : 1333.37 MHz
    System Bus :  266.67 MHz DDR
  System Clock :  133.34 MHz
    Multiplier :   10.0  

    L1 I-Cache :   64K Byte
    L1 D-Cache :   64K Byte
    L1 T-Cache :  ----
    L1  Cache  :  ----
    L2  Cache  :  256K Byte
    L2  Speed  : 1333.37 MHz (Full)

    MMX   Unit : Supported
    SSE   Unit : Supported
   SSE2   Unit : Not Supported
   SSE3   Unit : Not Supported
   MMX2   Unit : Supported
  3DNow!  Unit : Supported
  3DNow!+ Unit : Supported

   Host Bridge : 1022:700E.13 [AMD-761]
  South Bridge : 1106:0686.40 [VIA VT82C686B]
    VGA Device : 1002:4150.00 [ATI RADEON 9600 Series]
  Memory  Size : 512M Byte
  Memory Clock : ----

    OS Version : Windows XP  Version 5.1.2600 Service Pack 2

======
Hardware information:
  OEM ID: 0
  Number of processors: 1
  Page size: 4096
  Processor type: 586
  Minimum application address: 10000
  Maximum application address: 7ffeffff
  Active processor mask: 1
Average over 50000 iterations
2005/05/08

SPARSE_HASH_MAP:
map_grow              2175.42 ns
Memory used              1.5 Mb
map_predict/grow      1194.02 ns
map_replace            289.32 ns
map_fetch              260.88 ns
map_remove             370.25 ns

DENSE_HASH_MAP:
map_grow               269.91 ns
Memory used              2.1 Mb
map_predict/grow        57.10 ns
map_replace             44.37 ns
map_fetch               44.45 ns
map_remove              47.91 ns

STANDARD HASH_MAP:
map_grow             43102.15 ns
Memory used              3.1 Mb
map_predict/grow      2724.64 ns
map_replace            181.75 ns
map_fetch              172.35 ns
map_remove           27973.22 ns

STANDARD MAP:
map_grow              2512.32 ns
Memory used              3.4 Mb
map_predict/grow      2922.49 ns
map_replace            353.18 ns
map_fetch              319.60 ns
map_remove           20146.23 ns

標準のmapよりかなり良さげだけど、要素によってはhash関数を別途用意しなければ
いけないので、極端にデータ数が多い時じゃなければ普通のmapでいいやぁ。。
何だか比較する興味心はあるけど、実際やる気はあんまり無いという事だろうか。（汗
でもデータ件数がとっても多い本格的なデータ処理する時は使ってみよう。