[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

["fdumont at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57885

--- Comment #7 from FranÃois Dumont <fdumont at gcc dot gnu.org> ---
I had a try and the result is not good. I attached the modified implementation
if you want to have a try even if it is not perfect cause there are some
exception safety issue.

With the current implementation on my device I have the following result:

Container:std::unordered_map<int,int>  Key:int
Insertion: 23521 13329 13899 13544 13870  min=13329 max=23521
Lookup:    29246 29120 32406 29524 29065  min=29065 max=32406

Container:std::tr1::unordered_map<int,int>  Key:int
Insertion: 24410 10392 10404 10226 10180  min=10180 max=24410
Lookup:    22728 19985 20314 19918 20741  min=19918 max=22728

With the modified solution using empty nodes to mark end of bucket I had:

Container:std::unordered_map<int,int>  Key:int
Insertion: 30080 19250 17861 18955 18350  min=17861 max=30080
Lookup:    35884 36518 38623 35896 36661  min=35884 max=38623

Container:std::tr1::unordered_map<int,int>  Key:int
Insertion: 28912 10112 10046 10447 13026  min=10046 max=28912
Lookup:    22515 20114 19517 20400 19543  min=19517 max=22515

I fear that the memory overhead is not only impacting memory. It is surely not
good for memory cache. If you want to give it a try and check generated
assembly, additional testq should have vanish.

FranÃois