Re: [boost] Please Help: Experienced very bad performance with Multi-index

Subject: Re: [boost] Please Help: Experienced very bad performance with Multi-index
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2009-07-30 16:06:03

Jarolin, Robert <Robert.Jarolin <at> trueposition.com> writes:

> 
> Actually, I found the issue.  I will try to explain it as follows:
> 
> Assume that I have data that needs to be hashed by 4 different keys
> (key1, key2, key3, key4).  If there are situations where key3 and key4
> are non unique and I make them the same value for every entry, when I
> remove an entry from my table that has a lot of entries (ex. 10000), it
> may take seconds to for the removal to take place.

Hashed non-unique indices have this problem, when deleting
an entry with a much repeated key performance can be linear.
On the other hand, several *seconds* to delete an entry on a
container with tens of thousands of entries is *way* too
long even taking this problem into account. Which compiler/
environment are you using? Did you manage to find how to activate
release settings?

> Is there a way to improve on this?  Something like be able to tell the
> multiindex to not always hash a key if the value is not set (example, if
> integer, value of -1 means not set)?

I see a number of possibilities (once you've ruled out
the debug vs. release issue, which I strongly suggest
you take a look at before going any further):

1. Replace the indices for key3 and key4 with ordered
indices. This is a trade-off, since some oeprations will
get slower (lookup), so you'll have to measure and decide.
2. If I understood you right, you don't always care about
the key3 or key4 value of a given element. When this is
the case, set them to a random value to avoid repetitions.
3. This is drastic, but a colleague recently modified
the lib source code so as to turn singly-linked hashed
indices into doubly-linked indices, which don't have the
deletion problem described above. Details can be found
at http://lists.boost.org/Archives/boost/2009/04/151184.php
(read the whole thread).

HTH,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo