public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "redbeard0531 at gmail dot com" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/95079] New: unorderd_map::insert_or_assign and try_emplace should only hash and mod once unless there is a rehash. Date: Tue, 12 May 2020 11:00:56 +0000 [thread overview] Message-ID: <bug-95079-4@http.gcc.gnu.org/bugzilla/> (raw) 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...)
next reply other threads:[~2020-05-12 11:00 UTC|newest] Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top 2020-05-12 11:00 redbeard0531 at gmail dot com [this message] 2020-05-12 11:26 ` [Bug libstdc++/95079] " redi at gcc dot gnu.org 2020-05-24 10:00 ` fdumont at gcc dot gnu.org 2020-05-29 11:13 ` cvs-commit at gcc dot gnu.org 2021-02-28 14:39 ` fdumont at gcc dot gnu.org 2021-03-02 13:40 ` redbeard0531 at gmail dot com 2021-03-02 16:49 ` fdumont at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-95079-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).