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
>>> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk