[boost] [multi_index] benchmarking

From: Maxim Yegorushkin (maxim.yegorushkin_at_[hidden])
Date: 2006-05-28 06:54:48

As a part of a project I needed to compare performances of boost::multi_index 
hashed_unique/ordered_unique indexes with those of std::tr1::unordered_set, 
__gnu_cxx::hash_set, std::set. multi_index performance documentation page does 
not provide this kind of information, so I had to write my own test. I thought 
it might be a good idea to add the results to the documentation page. Source 
code for the test is provided.

Here is a sample run:

[max_at_localhost cont]$ sudo bin/test -q -n 10000 -x 10
10000 elements; 10 iterations
insert test (lower is better)
ext_hash  [ 44.43%] OOOOOOOOOOOOOOOOO 29714 usec
std_hash  [ 50.90%] OOOOOOOOOOOOOOOOOOOO 34042 usec
mi_hash   [ 69.61%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 46561 usec
mi_set    [ 97.17%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 64990 usec
std_set   [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 66885 usec
find hit test (lower is better)
ext_hash  [ 22.54%] OOOOOOOOO 7266 usec
std_hash  [ 23.87%] OOOOOOOOO 7694 usec
mi_hash   [ 29.09%] OOOOOOOOOOO 9378 usec
std_set   [ 87.99%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 28364 usec
mi_set    [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 32235 usec
find miss test (lower is better)
std_set   [ 85.09%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 8027 usec
ext_hash  [ 93.33%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 8805 usec
mi_set    [ 93.69%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 8839 usec
std_hash  [ 97.62%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 9209 usec
mi_hash   [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 9434 usec
iterate test (lower is better)
std_hash  [ 43.66%] OOOOOOOOOOOOOOOOO 3129 usec
mi_hash   [ 55.60%] OOOOOOOOOOOOOOOOOOOOOO 3984 usec
mi_set    [ 57.26%] OOOOOOOOOOOOOOOOOOOOOO 4103 usec
std_set   [ 93.54%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6703 usec
ext_hash  [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7166 usec
erase test (lower is better)
std_hash  [ 27.31%] OOOOOOOOOO 23914 usec
ext_hash  [ 28.68%] OOOOOOOOOOO 25117 usec
mi_hash   [ 38.02%] OOOOOOOOOOOOOOO 33299 usec
mi_set    [ 92.56%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 81057 usec
std_set   [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 87573 usec
memory test (lower is better)
std_hash  [ 60.54%] OOOOOOOOOOOOOOOOOOOOOOOO 121096 bytes
ext_hash  [ 64.57%] OOOOOOOOOOOOOOOOOOOOOOOOO 129156 bytes
mi_hash   [ 64.58%] OOOOOOOOOOOOOOOOOOOOOOOOO 129168 bytes
std_set   [ 99.99%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 200000 bytes
mi_set    [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 200020 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 := 
CXXCOMMON := -fmessage-length=0 -Wall -Wextra -Wno-missing-field-initializers
ifndef DEBUG
CXXFLAGS := $(CXXCOMMON) -O3 -march=pentium-m -fearly-inlining
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)