[Bug libstdc++/95079] New: unorderd_map::insert_or_assign and try_emplace should only hash and mod once unless there is a rehash.

[redbeard0531 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95079

            Bug ID: 95079
           Summary: unorderd_map::insert_or_assign and try_emplace should
                    only hash and mod once unless there is a rehash.
           Product: gcc
           Version: 10.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redbeard0531 at gmail dot com
  Target Milestone: ---

Currently insert_or_assign() and try_emplace() call find(key) and fall back to
emplace(...) if that fails to find the key. The computed hash (and more
importantly in general) the modded bucket index computed by find() is thrown
away and recomputed by emplace(). Instead they should compute the hash once,
and unless there is a rehash, also only do the modulus once. This optimization
is already performed for operator[].

https://godbolt.org/z/cw82RC shows that the hasher is invoked once for
operator[] and twice for insert_or_assign().
http://quick-bench.com/ge8Suq7PcdRKm6IBQbjvwuXhW6Y shows that there is a
significant performance difference (20% in this test).

(I know std::unordered_map is always going to be less than fast on 64-bit
platforms, but it doesn't need to be slower than it needs to be...)