[PATCH] hashtable insert enhancement

[François Dumont]

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: 35837 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20120107/ef8542c6/attachment.bin>