Re: [boost] [multi_index] benchmarking

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2006-05-28 17:49:34

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,

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