libstdc++/41975

[François Dumont]

     Here is as promise my latest proposal. This time there is no memory 
overhead except that hash code are now cached per default because we 
need it much more often than with the previous version and moreover we 
need it to implement erase in a robust way.

Without the patch the performance are:

41975.cc                        unordered_set<int> without cache: first 
insert     3r    2u    0s  8452192mem    0pf
41975.cc                        unordered_set<int> without cache: erase 
from iterator   2812r 2804u    1s -6400096mem    0pf
41975.cc                        unordered_set<int> without cache: second 
insert    1r    1u    0s  6400032mem    0pf
41975.cc                        unordered_set<int> without cache: erase 
from key           1r    1u    0s -6400032mem    0pf
41975.cc                        unordered_set<int> with cache: first 
insert        2r    2u    0s 11652192mem    0pf
41975.cc                        unordered_set<int> with cache: erase 
from iterator      2809r 2804u    0s -9600096mem    0pf
41975.cc                        unordered_set<int> with cache: second 
insert       2r    1u    0s  9600016mem    0pf
41975.cc                        unordered_set<int> with cache: erase 
from key      1r    2u    0s -9600016mem    0pf
41975.cc                        unordered_set<string> without cache: 
first insert          9r    8u    1s  8452192mem    0pf
41975.cc                        unordered_set<string> without cache: 
erase from iterator           3r    3u    0s -6400096mem    0pf
41975.cc                        unordered_set<string> without cache: 
second insert         4r    3u    0s  6400016mem    0pf
41975.cc                        unordered_set<string> without cache: 
erase from key        4r    5u    0s -6400016mem    0pf
41975.cc                        unordered_set<string> with cache: first 
insert     6r    5u    1s 11652176mem    0pf
41975.cc                        unordered_set<string> with cache: erase 
from iterator      2r    3u    0s -9600080mem    0pf
41975.cc                        unordered_set<string> with cache: second 
insert    3r    4u    0s  9600016mem    0pf
41975.cc                        unordered_set<string> with cache: erase 
from key           4r    3u    0s -9600016mem    0pf

with it it is:

41975.cc                        unordered_set<int> without cache: first 
insert     9r    7u    0s  8022160mem    0pf
41975.cc                        unordered_set<int> without cache: erase 
from iterator      1r    2u    0s -6400144mem    0pf
41975.cc                        unordered_set<int> without cache: second 
insert   97r   96u    1s  6400272mem    0pf
41975.cc                        unordered_set<int> without cache: erase 
from key           1r    1u    0s -6400272mem    0pf
41975.cc                        unordered_set<int> with cache: first 
insert       11r   10u    1s 11222224mem    0pf
41975.cc                        unordered_set<int> with cache: erase 
from iterator         2r    1u    0s -9600208mem    0pf
41975.cc                        unordered_set<int> with cache: second 
insert     100r   99u    0s  9600240mem    0pf
41975.cc                        unordered_set<int> with cache: erase 
from key      2r    1u    0s -9600240mem    0pf
41975.cc                        unordered_set<string> without cache: 
first insert         57r   56u    2s  8022160mem    0pf
41975.cc                        unordered_set<string> without cache: 
erase from iterator           8r    8u    0s -6400144mem    0pf
41975.cc                        unordered_set<string> without cache: 
second insert        57r   55u    1s  6400144mem    0pf
41975.cc                        unordered_set<string> without cache: 
erase from key        8r    8u    0s -6400144mem    0pf
41975.cc                        unordered_set<string> with cache: first 
insert    29r   27u    1s 11222176mem    0pf
41975.cc                        unordered_set<string> with cache: erase 
from iterator      5r    5u    0s -9600160mem    0pf
41975.cc                        unordered_set<string> with cache: second 
insert   27r   27u    0s  9600240mem    0pf
41975.cc                        unordered_set<string> with cache: erase 
from key           6r    5u    0s -9600240mem    0pf


There are however still 2 similar testsuite failures:

PASS: 23_containers/unordered_multimap/requirements/exception/basic.cc 
(test for excess errors)
N10__gnu_test12functor_base19iterator_operationsISt18unordered_multimapIN9__gnu_cxx17throw_value_limitES4_St4hashIS4_ESt8equal_toIS4_ENS3_21throw_allocator_limitIS4_EEEEE
end count 1
N10__gnu_test12functor_base25const_iterator_operationsISt18unordered_multimapIN9__gnu_cxx17throw_value_limitES4_St4hashIS4_ESt8equal_toIS4_ENS3_21throw_allocator_limitIS4_EEEEE
end count 1
N10__gnu_test12functor_base11erase_pointISt18unordered_multimapIN9__gnu_cxx17throw_value_limitES4_St4hashIS4_ESt8equal_toIS4_ENS3_21throw_allocator_limitIS4_EEELb1ELb0EEE
end count 1
N10__gnu_test12functor_base11erase_rangeISt18unordered_multimapIN9__gnu_cxx17throw_value_limitES4_St4hashIS4_ESt8equal_toIS4_ENS3_21throw_allocator_limitIS4_EEELb1ELb0EEE
end count 1
terminate called after throwing an instance of 'std::logic_error'
   what():  annotate_base::check_allocated by label
label: 5        size: 304       address: 0x11ae400

and the same for unordered_multiset.

     Looks like the problem is in erase range because when I remove it 
from the tested methods the test is passing. However I don't understand 
that unordered_set and unordered_map do not have the same issue. If 
anyone could help I would greatly appreciate.

2 remarks about this new implementation:
- iterator and local_iterator are aliases, should we introduce a 
distinct type just to forbid assignment between the 2 (like we have in 
debug mode)
- I fail to write the static_assert checking that if hash code is not 
cached then hash functor should be noexcept qualified, help on this 
point would be appreciated too

François
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 57280 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111114/a48696e5/attachment.bin>