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,
Main reason being that std::tr1::unordered containers are not generally available in current environments, although this seems to be improving fast.
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: [...]
Thank you for sharing your data. Figures show that hashed indices have ample room for improvement with respect to implementations of unordered containers. I have a question, an open question, a request and an invitation. * Which compiler/environment have you run this with? I guess GCC 4.x since you've got tr1 containers. * 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? 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? * 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. 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. That said, I do what I can in order to optimize the internal algorithms, and your data shows that there's room for improvement in hashed indices --I know you've got good knowledge of the internals of B.MI, so if you feel like contributing to this task or have some ideas to increase performance, you are most welcome. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
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
Maxim Yegorushkin ha escrito:
JOAQUIN LOPEZ MU?Z wrote:
[...]
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 doubt that. The basic RB-tree algorithms are based on SGI STL both in the case of B.MI and libstdc++. I might be wrong, of course, and libstdc++ might have changed a lot wrt to its SGI ancestor. [...]
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.
The metaprogramming scaffolding constructed by B.MI with the aim of allowing multi-indexing is not always completely optimized away by the compiler, basically, most operations go through a lot more (ideally inlined) functions. GCC is traditionally poorer at optimizing than say MSVC or ICC. But the range of degradation I expect is 0-10%, not as high as the 250+% on insert that your tests show for mi_hash... ...which has gotten me examining the test to determine what's going weird. I think I found it: your insert test consists of invocations of the form h.insert(begin, end); for which std_hash (and presumably ext_hash) are smart enough to pre-rehash based on n=std::distance(begin,end) when this distance's calculation is affordable. B.MI hashed indices don't do that, so the same call incurs several rehashing ops from size()=0 till size()=n. Could you do me a favor? Please replace your local copy of hashed indices range insert member function (at line 249 of the RC_1_34_0 version of boost/multi_index/hashed_index.hpp): template<typename InputIterator> void insert(InputIterator first,InputIterator last) { BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; iterator hint=end(); for(;first!=last;++first)hint=insert(hint,*first); } with the following: template<typename InputIterator> void insert(InputIterator first,InputIterator last) { BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; // WARNING: following line only for testing purposes. reserve(size()+std::distance(first,last)); iterator hint=end(); for(;first!=last;++first)hint=insert(hint,*first); } and rerun your tests? If my analysis is correct, figures for insert(mi_hash) should be then on par with or only slightly worse than std_hash and ext_hash. If this hunch proves right, it is certainly an opportunity for huge performance improvements and I will deal with it (in a proper way, the patch above is only a hack meant for testing purposes). Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquín Mª López Muñoz wrote: []
The metaprogramming scaffolding constructed by B.MI with the aim of allowing multi-indexing is not always completely optimized away by the compiler, basically, most operations go through a lot more (ideally inlined) functions. GCC is traditionally poorer at optimizing than say MSVC or ICC. But the range of degradation I expect is 0-10%, not as high as the 250+% on insert that your tests show for mi_hash...
...which has gotten me examining the test to determine what's going weird. I think I found it: your insert test consists of invocations of the form
h.insert(begin, end);
for which std_hash (and presumably ext_hash) are smart enough to pre-rehash based on n=std::distance(begin,end) when this distance's calculation is affordable. B.MI hashed indices don't do that, so the same call incurs several rehashing ops from size()=0 till size()=n. Could you do me a favor? Please replace your local copy of hashed indices range insert member function (at line 249 of the RC_1_34_0 version of boost/multi_index/hashed_index.hpp):
[code snipped]
and rerun your tests? If my analysis is correct, figures for insert(mi_hash) should be then on par with or only slightly worse than std_hash and ext_hash. If this hunch proves right, it is certainly an opportunity for huge performance improvements and I will deal with it (in a proper way, the patch above is only a hack meant for testing purposes).
Here are results for cvs head version, note the memory usage for mi_set: 99994 elements; 1 iterations insert test (lower is better) ext_hash [ 35.29%] OOOOOOOOOOOOOO 15105 usec std_hash [ 38.83%] OOOOOOOOOOOOOOO 16619 usec mi_hash [ 88.74%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 37984 usec mi_set [ 98.82%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 42299 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 42804 usec find hit test (lower is better) ext_hash [ 13.13%] OOOOO 4730 usec std_hash [ 14.15%] OOOOO 5096 usec mi_hash [ 15.56%] OOOOOO 5606 usec mi_set [ 93.48%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 33675 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 36024 usec find miss test (lower is better) std_set [ 56.75%] OOOOOOOOOOOOOOOOOOOOOO 4275 usec mi_set [ 61.10%] OOOOOOOOOOOOOOOOOOOOOOOO 4603 usec mi_hash [ 82.40%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6207 usec ext_hash [ 84.10%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6335 usec std_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7533 usec iterate test (lower is better) std_hash [ 51.22%] OOOOOOOOOOOOOOOOOOOO 4542 usec mi_hash [ 72.95%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6469 usec mi_set [ 83.39%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7395 usec ext_hash [ 84.66%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7508 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 8868 usec erase test (lower is better) std_hash [ 21.42%] OOOOOOOO 12797 usec ext_hash [ 22.85%] OOOOOOOOO 13650 usec mi_hash [ 22.93%] OOOOOOOOO 13699 usec mi_set [ 94.28%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 56324 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 59740 usec memory test (lower is better) std_hash [ 61.58%] OOOOOOOOOOOOOOOOOOOOOOOO 1231544 bytes ext_hash [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586404 bytes mi_hash [ 79.33%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586416 bytes mi_set [ 80.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1599920 bytes std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1999880 bytes Here are results for cvs head version with your modification, which show that your analysis was correct: 99994 elements; 1 iterations insert test (lower is better) mi_hash [ 31.71%] OOOOOOOOOOOO 13467 usec ext_hash [ 35.01%] OOOOOOOOOOOOOO 14871 usec std_hash [ 38.78%] OOOOOOOOOOOOOOO 16471 usec mi_set [ 97.50%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 41409 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 42471 usec find hit test (lower is better) ext_hash [ 12.83%] OOOOO 4604 usec std_hash [ 14.17%] OOOOO 5086 usec mi_hash [ 16.04%] OOOOOO 5757 usec mi_set [ 92.12%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 33056 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 35885 usec find miss test (lower is better) std_set [ 57.50%] OOOOOOOOOOOOOOOOOOOOOOO 4291 usec mi_set [ 62.88%] OOOOOOOOOOOOOOOOOOOOOOOOO 4692 usec mi_hash [ 81.33%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6069 usec ext_hash [ 83.49%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6230 usec std_hash [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7462 usec iterate test (lower is better) std_hash [ 50.29%] OOOOOOOOOOOOOOOOOOOO 4425 usec mi_hash [ 73.62%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOO 6478 usec mi_set [ 82.21%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7234 usec ext_hash [ 84.88%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 7469 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 8799 usec erase test (lower is better) std_hash [ 21.48%] OOOOOOOO 12728 usec ext_hash [ 22.77%] OOOOOOOOO 13492 usec mi_hash [ 23.35%] OOOOOOOOO 13837 usec mi_set [ 94.06%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 55744 usec std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 59264 usec memory test (lower is better) std_hash [ 61.58%] OOOOOOOOOOOOOOOOOOOOOOOO 1231544 bytes ext_hash [ 79.32%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586404 bytes mi_hash [ 79.33%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1586416 bytes mi_set [ 80.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1599920 bytes std_set [100.00%] OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 1999880 bytes BTW, the in-house container I tested originally missed the same optimization opportunity.
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. Darren
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
Maxim Yegorushkin wrote:
Joaquín Mª López Muñoz wrote:
[]
Please replace your local copy of hashed indices range insert member function (at line 249 of the RC_1_34_0 version of boost/multi_index/hashed_index.hpp):
[]
Here are results for cvs head version, note the memory usage for mi_set:
Oops, sorry I tested HEAD rather than RC_1_34_0. Should I retest it?
Maxim Yegorushkin ha escrito:
Maxim Yegorushkin wrote:
Joaquín Mª López Muñoz wrote:
[]
Please replace your local copy of hashed indices range insert member function (at line 249 of the RC_1_34_0 version of boost/multi_index/hashed_index.hpp):
[]
Here are results for cvs head version, note the memory usage for mi_set:
Oops, sorry I tested HEAD rather than RC_1_34_0. Should I retest it?
No, it's OK, both branches are currently in sync. Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ___________________________________________________________________________ Antes de imprimir este mensaje, asegúrese de que es necesario. La mejora del medio ambiente empieza en nuestro día a día. ___________________________________________________________________________
participants (4)
-
Darren Cook -
JOAQUIN LOPEZ MU?Z -
Joaquín Mª López Muñoz
-
Maxim Yegorushkin