Re: [Boost-users] [multi_index] modify_key with an iterator to composite_key

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