Boost logo

Boost Users :

Subject: Re: [Boost-users] [multi_index] modify_key with an iterator to composite_key
From: joaquin_at_[hidden]
Date: 2010-01-27 09:13:08


Christian Holmquist escribió:
> Hi,
>
> From what I've found on the net (here:
> http://groups.google.com/group/boost-list/browse_thread/thread/687ce9662a4c1c68?pli=1),
> about this problem, Joaquin explains that modify_key on a
> composite_key isn't supported.
>
> [...]
>
> The alternative must be to use modify() instead, so I'd like to know
> how to get the best
> performance in the following scenario:
>
> My index is specified as.
>
> namespace bmi = boost::multi_index;
>
> struct Index : boost::mpl::vector2
> <
> bmi::hashed_unique<bmi::member<Entry, std::string,
> &Entry::m_Name> >,
> bmi::ordered_non_unique
> <
> bmi::composite_key
> <
> Entry,
> bmi::member<Entry, int, &Entry::m_State>,
> bmi::member<Entry, int, &Entry::m_Timestamp>
> >
> >
> >
> {};
>
> I frequently updated Entry::m_State and Entry::m_Timestamp, but never
> Entry::m_Name
> during the lifetime of an entry, thus I expected modify_key to be
> faster since the expensive
> hash index don't need to be updated.
> Since I cannot tell modify() which parts of the Entry I'm about to update,
> I don't see how I can avoid the rehashing.

Alas you can't avoid it: all indices are updated upon modify(), no
matter what part of
the element you've modified. The same is true of modify_key(), which is
merely a
lightweight wrapper of modify(). To understand why things are like this,
take into
account that the lib cannot know wether a given key interacts or not
with the rest
(for instance, what if your first index in the example had used
Entry::m_Timestamp?)

On the bright side, index updating has been implemented so as to be as fast
as possible: before relocating an element indices check internally whether
the element remains in place after modification, which is usually a cheaper
operation than brute relocation. In the particular case of a hashed
index, if modify()
hasn't touched its key then updating merely invokes a hash call and a
couple of
pointer comparisons (not even equality comparison is needed.)

I'd recommend some profiling to see whether the provided performance is OK
for your needs.

Hope this helps,

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net