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でいいやぁ。。
何だか比較する興味心はあるけど、実際やる気はあんまり無いという事だろうか。（汗
でもデータ件数がとっても多い本格的なデータ処理する時は使ってみよう。
