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
> 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
(read the whole thread).
JoaquÃn M LÃ³pez MuÃ±oz
TelefÃ³nica, InvestigaciÃ³n y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk