libstdc++/41975

[François Dumont]

Hi

     Here is some news about my attempt to fix 41975 issue.

     For the moment I have made 2 modifications to the hashtable 
implementation:
- The nodes are all linked together, there is no more null node at the 
end of each bucket list
- Bucket N+1 point to Bucket N past-the-end node

     With those modifications:
- Iterate on the hashtable is faster, it is not impacted anymore by big 
holes in the buckets. I have been able to use only 1 type of iterator 
for both iterator and local_iterator. sizeof(iterator) is limited to the 
size of a pointer which is good as iterators are most of the time passed 
by value.
- To find an element is equivalent to the previous version, it is the 
reason why I have stored bucket N past-the-end node in bucket N + 1
- To insert require an additional cost when the insert is done in an 
empty bucket because we have to find out what is the previous node and 
we need to update bucket entries to have bucket N+1 pointing to bucket N 
past-the-end node.
- To erase also require the same overhead as for insert. Also 
erase(iterator) now needs to access erased element hash code to find out 
what buckets will need to be updated. It might generate an exception 
which is forbidden by Standard so we will have to force the hash code to 
be stored or at least add a static assertion that if hash code is not 
stored then the hash functor has to be noexcept qualified.

     So for the moment I haven't made progress to fix 41975. Now I plan 
to look at the benefit of using a doubly linked list, insert and erase 
could find the previous bucket more easily. Regarding the update of 
bucket values on insert and erase I still believe that the overhead 
could be limited if we keep load factor big enough. Even if it is 
forbidden to rehash the container in erase(iterator) and erase(iterator, 
iterator) methods it is still possible to do so in erase(const 
key_type&) and insert overloads.

      Any thoughts regarding those evolutions ?

      I have also plan to play with the performance tests to validate 
the impact of those evolutions.

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 27827 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111003/ecd121a8/attachment.bin>