Darren Cook wrote:
Here are results for cvs head version with your modification, which show that your analysis was correct:
It would be interesting to see how your results compare to Google's (open source) hash map: http://goog-sparsehash.sourceforge.net/ http://goog-sparsehash.sourceforge.net/doc/performance.html
I've not used them but they seem to give some good improvements (memory or speed, but not both) over std_hash and std_map.
Surprisingly google::dense_hash_set often outperforms all other containers in both speed and memory usage. I've run the test on Centrino 1.86Mhz, Linux Fedora Core 5, gcc 4.1.1 (-O3 -march=pentium-m -fearly-inlining -fomit-frame-pointer). legend: [mi_set], [mi_hash] boost::multi_index ordered, hashed index [gd_hash] google::dense_hash_set [gs_hash] google::sparse_hash_set [std_set] std::set [std_hash] std::tr1::unordered_set 100 elements; 10000 iterations insert test (lower is better) gd_hash [ 18.56%] OOOOOOO 69837 usec std_hash [ 37.96%] OOOOOOOOOOOOOOO 142828 usec ext_hash [ 40.08%] OOOOOOOOOOOOOOOO 150781 usec mi_hash [ 46.10%] OOOOOOOOOOOOOOOOOO 173466 usec mi_set [ 59.62%] OOOOOOOOOOOOOOOOOOOOOOO 224312 usec std_set [ 65.12%] OOOOOOOOOOOOOOOOOOOOOOOOOO 245003 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 376244 usec find hit test (lower is better) gd_hash [ 28.41%] OOOOOOOOOOO 53315 usec std_hash [ 34.29%] OOOOOOOOOOOOO 64354 usec ext_hash [ 34.45%] OOOOOOOOOOOOO 64659 usec mi_hash [ 37.26%] OOOOOOOOOOOOOO 69928 usec std_set [ 49.18%] OOOOOOOOOOOOOOOOOOO 92299 usec mi_set [ 55.42%] OOOOOOOOOOOOOOOOOOOOOO 104011 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 187677 usec find miss test (lower is better) std_set [ 23.93%] OOOOOOOOO 50217 usec gd_hash [ 27.99%] OOOOOOOOOOO 58739 usec mi_set [ 30.23%] OOOOOOOOOOOO 63441 usec ext_hash [ 31.94%] OOOOOOOOOOOO 67013 usec mi_hash [ 33.42%] OOOOOOOOOOOOO 70119 usec std_hash [ 34.12%] OOOOOOOOOOOOO 71605 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 209833 usec iterate test (lower is better) std_hash [ 66.77%] OOOOOOOOOOOOOOOOOOOOOOOOOO 44699 usec mi_hash [ 75.28%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 50395 usec mi_set [ 75.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 50426 usec gd_hash [ 83.61%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 55977 usec gs_hash [ 87.26%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 58421 usec std_set [ 93.77%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 62774 usec ext_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 66947 usec erase test (lower is better) gd_hash [ 19.63%] OOOOOOO 59340 usec std_hash [ 42.69%] OOOOOOOOOOOOOOOOO 129042 usec ext_hash [ 44.60%] OOOOOOOOOOOOOOOOO 134816 usec mi_hash [ 46.43%] OOOOOOOOOOOOOOOOOO 140338 usec gs_hash [ 60.22%] OOOOOOOOOOOOOOOOOOOOOOOO 182015 usec std_set [ 91.81%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 277477 usec mi_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 302245 usec memory test (lower is better) gs_hash [ 21.80%] OOOOOOOO 436 bytes gd_hash [ 51.20%] OOOOOOOOOOOOOOOOOOOO 1024 bytes std_hash [ 60.80%] OOOOOOOOOOOOOOOOOOOOOOOO 1216 bytes ext_hash [ 78.60%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1572 bytes mi_hash [ 79.20%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1584 bytes mi_set [ 80.80%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1616 bytes std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 2000 bytes 1000 elements; 1000 iterations insert test (lower is better) gd_hash [ 10.38%] OOOO 33393 usec ext_hash [ 37.89%] OOOOOOOOOOOOOOO 121921 usec mi_hash [ 40.47%] OOOOOOOOOOOOOOOO 130227 usec std_hash [ 44.19%] OOOOOOOOOOOOOOOOO 142183 usec mi_set [ 71.75%] OOOOOOOOOOOOOOOOOOOOOOOOOOOO 230863 usec std_set [ 72.74%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOO 234033 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 321755 usec find hit test (lower is better) gd_hash [ 16.87%] OOOOOO 22701 usec ext_hash [ 22.73%] OOOOOOOOO 30578 usec std_hash [ 25.22%] OOOOOOOOOO 33935 usec mi_hash [ 26.18%] OOOOOOOOOO 35221 usec std_set [ 60.36%] OOOOOOOOOOOOOOOOOOOOOOOO 81207 usec mi_set [ 69.59%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 93627 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 134542 usec find miss test (lower is better) std_set [ 27.38%] OOOOOOOOOO 24405 usec gd_hash [ 32.99%] OOOOOOOOOOOOO 29408 usec ext_hash [ 41.25%] OOOOOOOOOOOOOOOO 36771 usec mi_hash [ 44.97%] OOOOOOOOOOOOOOOOO 40082 usec std_hash [ 45.57%] OOOOOOOOOOOOOOOOOO 40622 usec mi_set [ 45.91%] OOOOOOOOOOOOOOOOOO 40925 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 89137 usec iterate test (lower is better) std_hash [ 41.72%] OOOOOOOOOOOOOOOO 13996 usec mi_set [ 54.50%] OOOOOOOOOOOOOOOOOOOOO 18283 usec mi_hash [ 56.89%] OOOOOOOOOOOOOOOOOOOOOO 19084 usec gd_hash [ 58.35%] OOOOOOOOOOOOOOOOOOOOOOO 19576 usec gs_hash [ 70.96%] OOOOOOOOOOOOOOOOOOOOOOOOOOOO 23804 usec std_set [ 96.28%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 32301 usec ext_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 33548 usec erase test (lower is better) gd_hash [ 8.71%] OOO 29415 usec std_hash [ 28.92%] OOOOOOOOOOO 97642 usec ext_hash [ 29.87%] OOOOOOOOOOO 100855 usec mi_hash [ 31.00%] OOOOOOOOOOOO 104666 usec gs_hash [ 38.51%] OOOOOOOOOOOOOOO 130033 usec std_set [ 87.57%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 295700 usec mi_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 337675 usec memory test (lower is better) gs_hash [ 22.58%] OOOOOOOOO 4516 bytes gd_hash [ 40.96%] OOOOOOOOOOOOOOOO 8192 bytes std_hash [ 60.64%] OOOOOOOOOOOOOOOOOOOOOOOO 12128 bytes ext_hash [ 70.86%] OOOOOOOOOOOOOOOOOOOOOOOOOOOO 14172 bytes mi_hash [ 70.92%] OOOOOOOOOOOOOOOOOOOOOOOOOOOO 14184 bytes mi_set [ 80.08%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 16016 bytes std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 20000 bytes 10000 elements; 100 iterations insert test (lower is better) gd_hash [ 8.28%] OOO 27523 usec ext_hash [ 36.62%] OOOOOOOOOOOOOO 121660 usec mi_hash [ 39.58%] OOOOOOOOOOOOOOO 131527 usec std_hash [ 43.43%] OOOOOOOOOOOOOOOOO 144319 usec mi_set [ 82.65%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 274601 usec std_set [ 84.13%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 279531 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 332265 usec find hit test (lower is better) gd_hash [ 12.77%] OOOOO 17580 usec ext_hash [ 22.61%] OOOOOOOOO 31127 usec std_hash [ 24.03%] OOOOOOOOO 33077 usec mi_hash [ 26.68%] OOOOOOOOOO 36721 usec std_set [ 88.99%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 122490 usec mi_set [ 99.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 136709 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 137646 usec find miss test (lower is better) gd_hash [ 19.62%] OOOOOOO 21992 usec std_set [ 26.10%] OOOOOOOOOO 29253 usec ext_hash [ 34.17%] OOOOOOOOOOOOO 38306 usec mi_hash [ 35.73%] OOOOOOOOOOOOOO 40047 usec std_hash [ 36.21%] OOOOOOOOOOOOOO 40588 usec mi_set [ 40.72%] OOOOOOOOOOOOOOOO 45644 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 112088 usec iterate test (lower is better) std_hash [ 43.10%] OOOOOOOOOOOOOOOOO 13476 usec mi_set [ 52.92%] OOOOOOOOOOOOOOOOOOOOO 16546 usec mi_hash [ 58.97%] OOOOOOOOOOOOOOOOOOOOOOO 18436 usec gs_hash [ 65.69%] OOOOOOOOOOOOOOOOOOOOOOOOOO 20539 usec gd_hash [ 69.76%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 21812 usec std_set [ 94.60%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 29576 usec ext_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 31265 usec erase test (lower is better) gd_hash [ 5.44%] OO 23497 usec std_hash [ 22.81%] OOOOOOOOO 98480 usec ext_hash [ 23.94%] OOOOOOOOO 103380 usec mi_hash [ 24.78%] OOOOOOOOO 106985 usec gs_hash [ 30.88%] OOOOOOOOOOOO 133356 usec std_set [ 84.98%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 366960 usec mi_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 431809 usec memory test (lower is better) gs_hash [ 22.05%] OOOOOOOO 44104 bytes std_hash [ 60.55%] OOOOOOOOOOOOOOOOOOOOOOOO 121096 bytes ext_hash [ 64.58%] OOOOOOOOOOOOOOOOOOOOOOOOO 129156 bytes mi_hash [ 64.58%] OOOOOOOOOOOOOOOOOOOOOOOOO 129168 bytes gd_hash [ 65.54%] OOOOOOOOOOOOOOOOOOOOOOOOOO 131072 bytes mi_set [ 80.01%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 160016 bytes std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 200000 bytes 99997 elements; 10 iterations insert test (lower is better) gd_hash [ 7.94%] OOO 34089 usec mi_hash [ 30.89%] OOOOOOOOOOOO 132547 usec ext_hash [ 34.77%] OOOOOOOOOOOOO 149230 usec std_hash [ 37.89%] OOOOOOOOOOOOOOO 162617 usec gs_hash [ 84.58%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 362965 usec mi_set [ 95.61%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 410326 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 429163 usec find hit test (lower is better) gd_hash [ 5.87%] OO 21290 usec ext_hash [ 12.52%] OOOOO 45377 usec std_hash [ 13.35%] OOOOO 48396 usec mi_hash [ 14.81%] OOOOO 53685 usec gs_hash [ 42.55%] OOOOOOOOOOOOOOOOO 154215 usec mi_set [ 91.53%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 331696 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 362392 usec find miss test (lower is better) gd_hash [ 15.53%] OOOOOO 28542 usec std_set [ 22.84%] OOOOOOOOO 41969 usec mi_set [ 30.00%] OOOOOOOOOOO 55134 usec ext_hash [ 31.45%] OOOOOOOOOOOO 57798 usec mi_hash [ 31.79%] OOOOOOOOOOOO 58434 usec std_hash [ 38.45%] OOOOOOOOOOOOOOO 70665 usec gs_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 183790 usec iterate test (lower is better) gd_hash [ 22.00%] OOOOOOOO 19308 usec gs_hash [ 22.89%] OOOOOOOOO 20095 usec std_hash [ 48.80%] OOOOOOOOOOOOOOOOOOO 42834 usec mi_hash [ 73.03%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOO 64106 usec ext_hash [ 81.72%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 71735 usec mi_set [ 82.35%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 72286 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 87783 usec erase test (lower is better) gd_hash [ 4.19%] O 27369 usec std_hash [ 18.74%] OOOOOOO 122516 usec ext_hash [ 20.00%] OOOOOOOO 130774 usec mi_hash [ 20.49%] OOOOOOOO 133954 usec gs_hash [ 23.12%] OOOOOOOOO 151108 usec std_set [ 89.08%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 582334 usec mi_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 653718 usec memory test (lower is better) gs_hash [ 21.64%] OOOOOOOO 432760 bytes gd_hash [ 52.43%] OOOOOOOOOOOOOOOOOOOO 1048576 bytes std_hash [ 61.58%] OOOOOOOOOOOOOOOOOOOOOOOO 1231568 bytes ext_hash [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586428 bytes mi_hash [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586440 bytes mi_set [ 80.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1599968 bytes std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1999940 bytes dir := $(CURDIR) bin_dir := $(dir)/bin obj_dir := $(dir)/obj src_dir := $(CURDIR) all : test_obj := ${addprefix $(obj_dir)/,test.o} $(bin_dir)/test : $(test_obj) bin_targets += $(bin_dir)/test CPPFLAGS := -isystem ../boost.head CXXCOMMON := -fmessage-length=0 -Wall -Wextra -Wno-missing-field-initializers ifndef DEBUG CXXFLAGS := $(CXXCOMMON) -O3 -march=pentium-m -fearly-inlining -fomit-frame-pointer else CXXFLAGS := $(CXXCOMMON) -ggdb endif LDDIRS := LDFLAGS := # allow -l in prerequisites VPATH := $(LDDIRS) all : $(bin_dir) $(obj_dir) $(bin_targets) $(bin_dir)/% : $(CXX) $(LDFLAGS) -o $@ $+ $(obj_dir)/%.o : %.cc $(CXX) -c $< $(CPPFLAGS) $(CXXFLAGS) -MMD -MF $(@:.o=.d) -o $@ $(bin_dir) $(obj_dir) $(lib_dir) : mkdir -p $@ # suppress built-in rules for the following targets Makefile : ; make.% : ; $(obj_dir)/%.d : ; %.hpp %.h %.cc %.cpp : ; %:: s.% ; .PHONY: all clean clean : rm -rf $(obj_dir) $(bin_dir) objs := $($(bin_targets:$(bin_dir)/%=%_obj)) deps := $(objs:.o=.d) -include $(deps) #! /bin/bash out=${1:-out} rm -rf $out.log $out.csv $out.txt for n in 100 1000 10000 100000; do (( x = 1000000 / $n )); bin/test -q -n $n -x $x -a $out.txt &>$out.log done