Re: [boost][multi_index][hash][rfc] Hashed indices preview +Boost.Hash
Hi Howard, I'm glad you jumped into this discussion! ----- Mensaje original ----- De: Howard Hinnant <hinnant@twcny.rr.com> Fecha: Domingo, Febrero 20, 2005 5:31 pm Asunto: Re: [boost] [multi_index][hash][rfc] Hashed indices preview +Boost.Hash
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.
What strikes about the resolution is that it doesn't seem to address Bill Wade's concern: in a minimum overhead "classic" hash table implementation (one pointer per element + one pointer per bucket), iteration is not going to be amortized constant under low load conditions. This is in very strong disagreement with that the std requires about forward iterators. I think this cannot be just swept under the rug: if the committee is going to accept it, at least it should be noted somewhere. The implementation I adopted (2 pointers per node + 2 pointers per bucket) has O(1) iteration, insert() and erase(), whatever the load conditions (provided the hash function behaves, of course.) I agree with you bidirectional iteration is of little value, and my main motivation was to achieve O(1). So, I'll be happy to go for a lighter implementation if these issues can be solved in another way --or if there's consensum that costly iteration under low load conditions is acceptable. PS. The worst of all implementations seems to be Dinkum's, where iteration is O(1) but insertion will degrade to O(bucket_count()^2) when a previous rehashing is issued, as Wade points out. It also puzzled me that the comittee NADed the issue without at least a comment on this. Looking fwd to your comments, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Feb 20, 2005, at 12:57 PM, JOAQUIN LOPEZ MU?Z wrote:
What strikes about the resolution is that it doesn't seem to address Bill Wade's concern: in a minimum overhead "classic" hash table implementation (one pointer per element + one pointer per bucket), iteration is not going to be amortized constant under low load conditions. This is in very strong disagreement with that the std requires about forward iterators. I think this cannot be just swept under the rug: if the committee is going to accept it, at least it should be noted somewhere.
<nod> I would favor a resolution which stated that complexity requirements for hash containers assume a perfect distribution with a load factor of 1. Complexities under other conditions could be undefined, or perhaps implementation defined. -Howard
JOAQUIN LOPEZ MU?Z wrote:
The implementation I adopted (2 pointers per node + 2 pointers per bucket) has O(1) iteration, insert() and erase(), whatever the load conditions (provided the hash function behaves, of course.) I agree with you bidirectional iteration is of little value, and my main motivation was to achieve O(1). So, I'll be happy to go for a lighter implementation if these issues can be solved in another way --or if there's consensum that costly iteration under low load conditions is acceptable.
FWIW, if you can find a spare bit in a pointer, I've thought of a non-portable way to get something closer to O(1) without the extra memory load. The nodes are stored in a singly-linked list which includes the buckets, so the last node in a bucket points to the next bucket. The spare bit is used to indicate if a pointer is pointing to a node or a bucket. So the data structure is something like: struct node_or_bucket { node_or_bucket* next_; void set(node* x) { next_ = x; } void set(bucket* x) { next_ = x | 1; } bool is_next_bucket() const { return x & 1; } node_or_bucket* get() const { return x & -2; } }; struct node : node_or_bucket { T value_; }; struct bucket : node_or_bucket { }; bucket* buckets_; // Array of buckets. bucket* start_; // First bucket. You can tell when a bucket ends because the pointer will be to a bucket (or perhaps null, although a circular list would avoid that). This also means that the node that comes before any node is always from the same bucket, so erase only has to look at a single bucket. Unfortunately, this can leave an empty bucket in the linked list. As more empty buckets are left iteration gets slower, so they need to be cleaned up. It would probably be possible for insert & erase to remove any they chance across. And erase could do a complete clean up whenever the number of empty buckets reaches a certain percentage of the current size. I'm not going to do this for now, as it wouldn't be remotely appropriate for boost. And in many cases, this might end up slower than the current implementation. I expect that the majority of accesses of an unordered container are going to be by key. Daniel
participants (3)
-
Daniel James -
Howard Hinnant -
JOAQUIN LOPEZ MU?Z