Re: [boost] [multi_index] benchmarking

From: Maxim Yegorushkin (maxim.yegorushkin_at_[hidden])
Date: 2006-05-29 07:41:39

JOAQUIN LOPEZ MU?Z wrote:
> Hello Maxim,
> 
> ----- Mensaje original -----
> De: Maxim Yegorushkin <maxim.yegorushkin_at_[hidden]>
> Fecha: Domingo, Mayo 28, 2006 12:54 pm
> Asunto: [boost] [multi_index] benchmarking
> 
>> 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.

[]

> * Which compiler/environment have you run this with?
> I guess GCC 4.x since you've got tr1 containers.

It was Linux Fedora Core 5 with a customized kernel, Centrino 1.86Ghz, gcc 
4.1.0.  I attached the results of a full run with 100-100000 elements. (I 
actually tested performance of an in-house hash vs. standard containers and 
B.MI, hence adapter<> level of indirection in the code).

> * From the figures on memory consumption of mi_set looks 
> like you're using Boost 1.33.1 (which still doesn't
> have the spatial optimization suggested by you and
> described at http://tinyurl.com/rwvvt), right?

[max_at_localhost ~]$ rpm -q boost boost-devel
boost-1.33.1-5
boost-devel-1.33.1-5

 > If so,
> I cannot find a reason why mi_set performs in general
> sensibly better than std_set, since the data structures
> and algorithms are basically equivalent, and B.MI
> introduces some metaprogramming overhead that the
> optimizer usually doesn't clean away entirely. I'd
> have hoped for a small decrease in performance
> for B.MI, though not as high as that observed in
> mi_hash wrt std_hash. Do you have an idea anout this?

The attached results show that B.MI is faster on insert and erase, but slightly 
slower on find hit/miss than std::set. My guesswork is that std::set probably 
does more(?) balancing on insert/erase.

> * I'd be grateful if you could rerun the tests for
> the RC_1_34_0 branch, since mi_set should perform
> quite better, and erase test(mi_hash) should also
> improve. If you do this, please report your results
> back.

Okay.

> I must say that B.MI does not intend to outperform
> single-index std containers since in general the
> data structures are equivalent; it is when
> multi-indexing comes into play that I expect a
> large impact in favor of B.MI.

I see nothing what could prevent B.MI from being as fast as the standard containers.

insert test (lower is better)
100 elements; 10000 iterations
std_hash  [ 28.38%] OOOOOOOOOOOOOOOOOOOOOO 145568 usec
ext_hash  [ 30.59%] OOOOOOOOOOOOOOOOOOOOOOOO 156928 usec
mi_set    [ 43.46%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 222920 usec
mi_hash   [ 43.70%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 224151 usec
std_set   [ 48.75%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 250070 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 512941 usec
1000 elements; 1000 iterations
ext_hash  [ 13.04%] OOOOOOOOOO 122660 usec
std_hash  [ 14.94%] OOOOOOOOOOO 140467 usec
mi_hash   [ 22.03%] OOOOOOOOOOOOOOOOO 207181 usec
mi_set    [ 24.21%] OOOOOOOOOOOOOOOOOOO 227659 usec
std_set   [ 25.68%] OOOOOOOOOOOOOOOOOOOO 241446 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 940323 usec
10000 elements; 100 iterations
ext_hash  [  8.33%] OOOOOO 123626 usec
std_hash  [  9.58%] OOOOOOO 142095 usec
mi_hash   [ 13.45%] OOOOOOOOOO 199450 usec
mi_set    [ 18.34%] OOOOOOOOOOOOOO 272109 usec
std_set   [ 18.80%] OOOOOOOOOOOOOOO 278875 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1483340 use
99994 elements; 10 iterations
ext_hash  [ 21.07%] OOOOOOOOOOOOOOOO 127191 usec
std_hash  [ 22.27%] OOOOOOOOOOOOOOOOO 134396 usec
mi_hash   [ 60.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 362156 usec
mi_set    [ 68.25%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 411952 usec
std_set   [ 70.45%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 425242 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 603597 usec

find hit test (lower is better)
100 elements; 10000 iterations
ext_hash  [ 58.82%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 64130 usec
std_hash  [ 61.57%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 67129 usec
mi_hash   [ 66.41%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 72410 usec
std_set   [ 84.48%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 92107 usec
mi_set    [ 94.66%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 103212 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 109032 usec
1000 elements; 1000 iterations
ext_hash  [ 33.93%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 31404 usec
std_hash  [ 35.10%] OOOOOOOOOOOOOOOOOOOOOOOOOOOO 32487 usec
mi_hash   [ 42.11%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 38979 usec
xxxx_hash [ 88.97%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 82352 usec
std_set   [ 91.38%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 84581 usec
mi_set    [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 92561 usec
10000 elements; 100 iterations
ext_hash  [ 20.95%] OOOOOOOOOOOOOOOO 32216 usec
std_hash  [ 21.09%] OOOOOOOOOOOOOOOO 32428 usec
mi_hash   [ 26.09%] OOOOOOOOOOOOOOOOOOOO 40108 usec
std_set   [ 79.52%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 122251 usec
mi_set    [ 89.92%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 138237 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 153741 usec
99994 elements; 10 iterations
ext_hash  [ 12.75%] OOOOOOOOOO 44765 usec
std_hash  [ 13.79%] OOOOOOOOOOO 48424 usec
mi_hash   [ 15.84%] OOOOOOOOOOOO 55602 usec
xxxx_hash [ 78.97%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 277269 usec
std_set   [ 94.81%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 332885 usec
mi_set    [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 351112 usec

find miss test (lower is better)
100 elements; 10000 iterations
std_set   [ 43.59%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 49964 usec
mi_set    [ 49.14%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 56326 usec
std_hash  [ 60.85%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 69748 usec
ext_hash  [ 61.10%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 70039 usec
mi_hash   [ 63.29%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 72547 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 114627 usec
1000 elements; 1000 iterations
std_set   [ 34.68%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 24622 usec
mi_set    [ 49.14%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 34884 usec
ext_hash  [ 50.11%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 35575 usec
mi_hash   [ 52.92%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 37572 usec
std_hash  [ 55.74%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 39576 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 70995 usec
10000 elements; 100 iterations
std_set   [ 24.84%] OOOOOOOOOOOOOOOOOOO 31275 usec
ext_hash  [ 29.78%] OOOOOOOOOOOOOOOOOOOOOOO 37486 usec
mi_set    [ 31.32%] OOOOOOOOOOOOOOOOOOOOOOOOO 39434 usec
std_hash  [ 31.71%] OOOOOOOOOOOOOOOOOOOOOOOOO 39915 usec
mi_hash   [ 31.75%] OOOOOOOOOOOOOOOOOOOOOOOOO 39967 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 125894 usec
99994 elements; 10 iterations
std_set   [ 14.94%] OOOOOOOOOOO 39139 usec
mi_set    [ 18.10%] OOOOOOOOOOOOOO 47425 usec
ext_hash  [ 22.09%] OOOOOOOOOOOOOOOOO 57875 usec
mi_hash   [ 23.40%] OOOOOOOOOOOOOOOOOO 61308 usec
std_hash  [ 26.92%] OOOOOOOOOOOOOOOOOOOOO 70522 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 262012 usec

iterate test (lower is better)
100 elements; 10000 iterations
std_hash  [ 63.89%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 44698 usec
mi_set    [ 70.80%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 49532 usec
mi_hash   [ 71.96%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 50344 usec
std_set   [ 91.67%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 64130 usec
ext_hash  [ 95.84%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 67048 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 69961 usec
1000 elements; 1000 iterations
std_hash  [ 18.00%] OOOOOOOOOOOOOO 14368 usec
mi_set    [ 22.76%] OOOOOOOOOOOOOOOOOO 18166 usec
mi_hash   [ 24.40%] OOOOOOOOOOOOOOOOOOO 19471 usec
std_set   [ 40.26%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 32134 usec
ext_hash  [ 41.80%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 33364 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 79812 usec
10000 elements; 100 iterations
std_hash  [  6.13%] OOOO 13501 usec
mi_set    [  7.56%] OOOOOO 16671 usec
mi_hash   [  7.85%] OOOOOO 17298 usec
std_set   [ 13.20%] OOOOOOOOOO 29103 usec
ext_hash  [ 14.05%] OOOOOOOOOOO 30972 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 220399 usec
99994 elements; 10 iterations
std_hash  [ 27.97%] OOOOOOOOOOOOOOOOOOOOOO 43076 usec
mi_hash   [ 42.22%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 65028 usec
mi_set    [ 47.84%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 73677 usec
ext_hash  [ 48.18%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 74202 usec
std_set   [ 55.96%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 86179 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 154010 usec

erase test (lower is better)
100 elements; 10000 iterations
std_hash  [ 34.73%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 134293 usec
ext_hash  [ 36.52%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOO 141223 usec
mi_hash   [ 43.46%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 168061 usec
mi_set    [ 65.67%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 253949 usec
std_set   [ 68.79%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 266012 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 386714 usec
1000 elements; 1000 iterations
std_hash  [ 28.01%] OOOOOOOOOOOOOOOOOOOOOO 100903 usec
ext_hash  [ 29.48%] OOOOOOOOOOOOOOOOOOOOOOO 106206 usec
mi_hash   [ 37.85%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 136369 usec
mi_set    [ 73.84%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 266049 usec
std_set   [ 85.05%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 306450 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 360301 usec
10000 elements; 100 iterations
std_hash  [ 23.15%] OOOOOOOOOOOOOOOOOO 101506 usec
ext_hash  [ 24.80%] OOOOOOOOOOOOOOOOOOO 108749 usec
mi_hash   [ 32.05%] OOOOOOOOOOOOOOOOOOOOOOOOO 140515 usec
mi_set    [ 78.13%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 342594 usec
std_set   [ 82.57%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 362052 usec
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 438492 usec
99994 elements; 10 iterations
std_hash  [ 21.54%] OOOOOOOOOOOOOOOOO 123883 usec
ext_hash  [ 23.34%] OOOOOOOOOOOOOOOOOO 134236 usec
mi_hash   [ 33.93%] OOOOOOOOOOOOOOOOOOOOOOOOOOO 195170 usec
xxxx_hash [ 88.76%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 510591 usec
mi_set    [ 96.24%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 553598 usec
std_set   [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 575251 usec

memory test (lower is better)
100 elements; 10000 iterations
std_hash  [ 11.40%] OOOOOOOOO 1216 bytes
ext_hash  [ 14.74%] OOOOOOOOOOO 1572 bytes
mi_hash   [ 14.85%] OOOOOOOOOOO 1584 bytes
std_set   [ 18.75%] OOOOOOOOOOOOOO 2000 bytes
mi_set    [ 18.94%] OOOOOOOOOOOOOOO 2020 bytes
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 10668 bytes
1000 elements; 1000 iterations
std_hash  [  4.09%] OOO 12128 bytes
ext_hash  [  4.79%] OOO 14172 bytes
mi_hash   [  4.79%] OOO 14184 bytes
std_set   [  6.75%] OOOOO 20000 bytes
mi_set    [  6.76%] OOOOO 20020 bytes
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 296172 bytes
10000 elements; 100 iterations
std_hash  [  4.09%] OOO 121096 bytes
ext_hash  [  4.36%] OOO 129156 bytes
mi_hash   [  4.36%] OOO 129168 bytes
std_set   [  6.76%] OOOOO 200000 bytes
mi_set    [  6.76%] OOOOO 200020 bytes
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 2960076 bytes
99994 elements; 10 iterations
std_hash  [ 15.39%] OOOOOOOOOOOO 1231544 bytes
ext_hash  [ 19.83%] OOOOOOOOOOOOOOO 1586404 bytes
mi_hash   [ 19.83%] OOOOOOOOOOOOOOO 1586416 bytes
std_set   [ 25.00%] OOOOOOOOOOOOOOOOOOO 1999880 bytes
mi_set    [ 25.00%] OOOOOOOOOOOOOOOOOOO 1999900 bytes
xxxx_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7999884 bytes