JOAQUIN LOPEZ MU?Z wrote:
Hello Maxim,
----- Mensaje original ----- De: Maxim Yegorushkin <maxim.yegorushkin@gmail.com> 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@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