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: Christian Holmquist (c.holmquist_at_[hidden])
Date: 2010-01-27 10:03:04

> 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?)
>
>
Ah, obviously.. I was thinking along these lines, but didn't come up with a
definite answer by myself.
Thanks for clarifying.

> 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.)
>
>
Excellent, this is definitely good enough. Will I gain anything by choosing
hashed_non_unique over hashed_unique in this case?
Outer code guarantees that duplicates won't be inserted anyway, so this
constraint is implicit in my case.

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

I'm sure it will be.

> Hope this helps,
>
>
It certainly does, thanks a lot for the information. And for a great library
:)

/ Christian