|
|
Boost : |
From: Maxim Yegorushkin (maxim.yegorushkin_at_[hidden])
Date: 2006-05-30 16:25:26
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk