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,