[PATCH] hashtable insert enhancement

[François Dumont]

     Same patch proposition as the previous one except that I have 
revisited the _M_rehash method that was still trying to keep nodes 
ordered by their bucket index. The result is 1 loop on nodes rather than 
a loop on nodes and a loop on buckets, simpler and faster code:

41975.cc                        unordered_set<int> without cache: first 
insert     5r    3u    1s  8022176mem    0pf
41975.cc                        unordered_set<int> without cache: erase 
from iterator      1r    1u    0s -6400160mem    0pf
41975.cc                        unordered_set<int> without cache: second 
insert    4r    4u    0s  6397472mem    0pf
41975.cc                        unordered_set<int> without cache: erase 
from key           1r    1u    0s -6400208mem    0pf
41975.cc                        unordered_set<int> with cache: first 
insert        5r    4u    1s  8019488mem    0pf
41975.cc                        unordered_set<int> with cache: erase 
from iterator         1r    2u    0s -6400208mem    0pf
41975.cc                        unordered_set<int> with cache: second 
insert       5r    4u    0s  6400256mem    0pf
41975.cc                        unordered_set<int> with cache: erase 
from key      1r    1u    0s -6400256mem    0pf
41975.cc                        unordered_set<string> without cache: 
first insert         44r   43u    1s  8019472mem    0pf
41975.cc                        unordered_set<string> without cache: 
erase from iterator           7r    7u    0s -6400192mem    0pf
41975.cc                        unordered_set<string> without cache: 
second insert        44r   42u    1s  6400208mem    0pf
41975.cc                        unordered_set<string> without cache: 
erase from key        6r    7u    0s -6400208mem    0pf
41975.cc                        unordered_set<string> with cache: first 
insert    15r   14u    0s  8019472mem    0pf
41975.cc                        unordered_set<string> with cache: erase 
from iterator      3r    3u    0s -6400192mem    0pf
41975.cc                        unordered_set<string> with cache: second 
insert   14r   14u    1s  6400240mem    0pf
41975.cc                        unordered_set<string> with cache: erase 
from key           4r    4u    0s -6400240mem    0pf


François


On 01/07/2012 11:09 PM, François Dumont wrote:
> Hello
>
>     Here is a patchfor the hashtable implementation, the last 
> modifying hashtable data model I swear :-). Here are the important 
> points of this patch:
> - _M_begin_bucket_index that used to be the index of the first 
> non-empty bucket has been replaced by _M_before_begin which a node 
> before the hashtable begin node. Thanks to this modification the 
> hashtable implementation is much more consistent because now all 
> non-empty buckets are containing their before-begin node; previously 
> the first non-empty bucket was containing its begin node rather than 
> the before-begin. It is a rather logical modification because, as 
> documented, the hashtable is the aggregation of a std::forward_list 
> and a std::vector<std::forward_list::iterator>. A std::forward_list 
> contains its before begin node, so does the hashtable now.
> - I used to consider that hashtable nodes had to be ordered according 
> to their bucket index. This is in fact useless and worst a performance 
> issue because previously, when I had to add a node in an empty bucket, 
> I need to look for the previous not-empty bucket to find the node to 
> link after. With this patch, when inserting in an empty bucket, the 
> new node is simply inserted at the beginning of the forward_list and 
> the bucket then contain the forward_list before-begin. This is a 
> constant time operation while previously it was O(N) with N the number 
> of empty buckets before the targeted bucket.
> - I have introduced a _M_find_before_node method, called by 
> _M_find_node, that returns the node before an equivalent one. This way 
> I can insert node after it without taking care of computing the next 
> node bucket to potentially update it, see what was done in 
> _M_insert_after for additional details.
>
> Here is the result on the performance test 
> performance/23_containers/insert_erase/41975.cc:
>
> Before patch:
>
> 41975.cc                     unordered_set<int> without cache: first 
> insert       9r    7u    0s  8022176mem    0pf
> 41975.cc                     unordered_set<int> without cache: erase 
> from iterator       1r    1u    0s -6400160mem    0pf
> 41975.cc                     unordered_set<int> without cache: second 
> insert      95r   94u    0s  6397600mem    0pf
> 41975.cc                     unordered_set<int> without cache: erase 
> from key       1r    1u    0s -6400320mem    0pf
> 41975.cc                     unordered_set<int> with cache: first 
> insert       7r    7u    0s  8019552mem    0pf
> 41975.cc                     unordered_set<int> with cache: erase from 
> iterator       1r    1u    0s -6400256mem    0pf
> 41975.cc                     unordered_set<int> with cache: second 
> insert      95r   95u    0s  6400304mem    0pf
> 41975.cc                     unordered_set<int> with cache: erase from 
> key       1r    0u    0s -6400304mem    0pf
> 41975.cc                     unordered_set<string> without cache: 
> first insert      55r   54u    0s  8019536mem    0pf
> 41975.cc                     unordered_set<string> without cache: 
> erase from iterator       7r    7u    0s -6400240mem    0pf
> 41975.cc                     unordered_set<string> without cache: 
> second insert      56r   55u    1s  6400272mem    0pf
> 41975.cc                     unordered_set<string> without cache: 
> erase from key       6r    7u    0s -6400272mem    0pf
> 41975.cc                     unordered_set<string> with cache: first 
> insert      22r   20u    0s  8019536mem    0pf
> 41975.cc                     unordered_set<string> with cache: erase 
> from iterator       4r    4u    0s -6400240mem    0pf
> 41975.cc                     unordered_set<string> with cache: second 
> insert      22r   21u    1s  6400288mem    0pf
> 41975.cc                     unordered_set<string> with cache: erase 
> from key       3r    4u    0s -6400288mem    0pf
>
> After patch:
>
> 41975.cc                        unordered_set<int> without cache: 
> first insert     9r    6u    1s  8022176mem    0pf
> 41975.cc                        unordered_set<int> without cache: 
> erase from iterator      1r    1u    0s -6400160mem    0pf
> 41975.cc                        unordered_set<int> without cache: 
> second insert    7r    6u    0s  6397472mem    0pf
> 41975.cc                        unordered_set<int> without cache: 
> erase from key           1r    1u    0s -6400208mem    0pf
> 41975.cc                        unordered_set<int> with cache: first 
> insert        8r    6u    1s  8019488mem    0pf
> 41975.cc                        unordered_set<int> with cache: erase 
> from iterator         1r    2u    0s -6400208mem    0pf
> 41975.cc                        unordered_set<int> with cache: second 
> insert       8r    7u    0s  6400256mem    0pf
> 41975.cc                        unordered_set<int> with cache: erase 
> from key      1r    1u    0s -6400256mem    0pf
> 41975.cc                        unordered_set<string> without cache: 
> first insert         51r   51u    0s  8019472mem    0pf
> 41975.cc                        unordered_set<string> without cache: 
> erase from iterator           7r    7u    0s -6400192mem    0pf
> 41975.cc                        unordered_set<string> without cache: 
> second insert        50r   49u    0s  6400208mem    0pf
> 41975.cc                        unordered_set<string> without cache: 
> erase from key        7r    7u    0s -6400208mem    0pf
> 41975.cc                        unordered_set<string> with cache: 
> first insert    20r   20u    1s  8019472mem    0pf
> 41975.cc                        unordered_set<string> with cache: 
> erase from iterator      4r    4u    0s -6400192mem    0pf
> 41975.cc                        unordered_set<string> with cache: 
> second insert   20r   20u    0s  6400240mem    0pf
> 41975.cc                        unordered_set<string> with cache: 
> erase from key           4r    4u    0s -6400240mem    0pf
>
> You can see the very good impact on the 'second insert' test case 
> which is a worst case insertion for the current implementation. It 
> could even be worst if the hash policy was not reducing the number of 
> buckets when too high. I don't understand however why the difference 
> is so small on string type...
>
> 2012-01-07  François Dumont <fdumont@gcc.gnu.org>
>
>         * include/bits/hashtable_policy.h (_Hash_node_base): New, use 
> it as
>         base class of ...
>         (_Hash_node<Value, true>, _Hash_node<Value, false>): ... those.
>         * include/bits/hashtable.h (_Hashtable): Replace 
> _M_begin_bucket_index
>         by _M_before_begin. Review implementation so that we do not 
> need to
>         look for previous non-empty bucket when inserting nodes.
>
> Tested under linux x86_64 normal, debug, profile modes.
>
> Ok to commit ?
>
> François
>

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