[multi_index] modify_key with an iterator to composite_key
Hi,
From what I've found on the net (here: http://groups.google.com/group/boost-list/browse_thread/thread/687ce9662a4c1...), about this problem, Joaquin explains that modify_key on a composite_key isn't supported.
Relevant part from that thread is: When you use modify_key, you modifier functor is passed
*the key* rather than the whole element as is the case with modify. In this particular situation, the key is a composite key; so the key object (defined privately by composite_key) is some entity that somehow references entry::m_x and entry::m_y. This object is not exposed to the public and you're not supposed to try to use it or modify it, hence the problems you're seeing. In short, when using composite_key you cannot use modify_key.
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. Maybe there's a better way to configure the index? I'm using Entry::m_State for an equal_range() search, while Entry::m_Timestamp is only for ordering (I bump the timestamp everytime I change m_State). I am using boost.1.35 btw Any response much appreciated, Christian
Christian Holmquist escribió:
Hi,
From what I've found on the net (here: http://groups.google.com/group/boost-list/browse_thread/thread/687ce9662a4c1...), 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
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
Christian Holmquist escribió:
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.
hashed_unique should be marginally better, but again you'd better profile that assumption. Thanks for using Boost.MultiIndex, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Wed, Jan 27, 2010 at 8:13 AM, <joaquin@tid.es> wrote:
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.)
Cool, that's a valuable tip about the implementation. Would make a great note in the doc. Boost docs tend to be quite dry, and your very insightful answer to Christian's question would be very appreciated in the doc, perhaps linked from modify()/modify_key(). My $0.02, and once again thanks for this fantastic library. --DD
participants (3)
-
Christian Holmquist -
Dominique Devienne -
joaquin＠tid.es