libstdc++/41975

[François Dumont]

Here is an other step forward to fix this issue. In this step nodes are 
now doubly linked to each other. It avoids some loops on buckets but 
performance are still not ok. I have created a performance test, see 
attached 41975.cc. Before the patch the result was:

41975.cc                        Container generation               2r    
1u    0s  8452192mem    0pf
41975.cc                        Container erase                   21r   
21u    0s -6400096mem    0pf
41975.cc                        Container iteration               10r   
10u    0s       32mem    0pf

With the attached patch it is:

41975.cc                        Container generation               3r    
2u    0s 11652176mem    0pf
41975.cc                        Container erase                  185r  
182u    0s -9600080mem    0pf
41975.cc                        Container iteration                0r    
0u    0s       48mem    0pf

Of course there are more memory manipulated. Regarding operations CPU 
consumption iteration is much better but erase is much worst. I think 
the problem is in the invocation of std::fill that cost a lot as soon as 
we start having a lot of buckets to update. This is why I have already 
started to work on a last evolution to avoid those calls.

To be continued...

François

On 10/03/2011 09:30 PM, François Dumont wrote:
> 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: 30101 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111012/8b100b4e/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 41975.cc
Type: text/x-c
Size: 1794 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111012/8b100b4e/attachment-0001.bin>