Re: [boost] [multi_index][hash][rfc] Hashed indices preview +Boost.Hash

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-02-20 11:31:12

On Feb 20, 2005, at 10:21 AM, JOAQUIN LOPEZ MU?Z wrote:

>>> 1.4. Usual implementations use one pointer per bucket, whereas
>>> Boost.MultiIndex has two pointers per bucket. This addresses
>> potential> performance problems of insert() and erase() under low
>> load conditions,
>>> as discussed in
>>> http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
>>> issue 6.14. Is this convenient?
>>
>> Well it's not unreasonable, you need what you need.
>
> BTW, have you read the committee's resolution to this
> issue? It doesn't make any sense to me (Bill Wade's concern,
> OTOH, seems very rasonable.)

Imho the committee's resolution is quite logical.

The hash containers exist for one reason:  As an optimized solution, in 
both memory consumption and speed, compared to the tree-based 
containers.  The speed department especially concerns lookup, insert 
and erase (in that order), but not iteration (there are other 
containers which optimize iteration, vector being the extreme example).

The coder who carefully tunes his hash function and loading will be 
rewarded with significant optimization.  The coder who doesn't, may be 
presented with a solution that performs worse than the tree-based 
containers, and is better off sticking with the O(Log N) solution.

Imho, the committee should do absolutely nothing to penalize the coder 
who has carefully tuned his hash function and loading, either in memory 
consumption nor speed.  Of course if hash container writers would like 
to add safeguards which may also add such overhead, I see little 
rationale for the committee to object to that either.

Doubling the per element storage overhead for a perfect distribution 
with a loading of 1 is a serious hit in the memory consumption 
department, and may well lead to a performance hit due to more L2 cache 
misses.  Adding bidirectional iteration, again at the cost of doubling 
the per element overhead in a well tuned application makes little sense 
to me.  The container is unordered.  When you iterate in the forward 
direction, you access the elements in a generally unpredictable, 
unordered order.  What motivation is there (motivation high enough to 
double per element overhead), to iterate in the reverse of the 
generally unpredictable, unordered order?

Again, I have no wish for the committee to outlaw such hash containers. 
  But I strongly feel that neither should they outlaw the more 
traditional hash container design which favors uncompromising 
performance when everything is tuned just right.

-Howard