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
