From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
 id 3A881386F46E; Tue, 12 May 2020 11:00:57 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3A881386F46E
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
 s=default; t=1589281257;
 bh=LVxHIyZW39qqf0gEyx0qViQ2Ntll3Zti45TrEsN2GZQ=;
 h=From:To:Subject:Date:From;
 b=NuiybQjdx3tyw61q9x1l+rADAU9UBIVro7eqCcyQRuZclRskhJsbfKr0oaInOGVYA
 KLIgpnULeCAWA5vTcvv+ZRwQQpi2Uuu6YI6YjJ5Hoqh3izz2eOEzOiySx8LfmGFWTl
 ykf5W96JmPf31BdeXIMmn7B95Lx78JHfNGKoKYEA=
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
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 10.1.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: normal
X-Bugzilla-Who: redbeard0531 at gmail dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-95079-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-BeenThere: gcc-bugs@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-bugs mailing list <gcc-bugs.gcc.gnu.org>
List-Unsubscribe: <http://gcc.gnu.org/mailman/options/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-request@gcc.gnu.org?subject=help>
List-Subscribe: <http://gcc.gnu.org/mailman/listinfo/gcc-bugs>,
 <mailto:gcc-bugs-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Tue, 12 May 2020 11:00:57 -0000

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

            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 optimizat=
ion
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...)=