From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 37921 invoked by alias); 2 May 2015 18:35:58 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 37873 invoked by uid 48); 2 May 2015 18:35:53 -0000 From: "glisse at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/65641] unordered_map - __detail::_Mod_range_hashing is slow Date: Sat, 02 May 2015 18:35:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Version: unknown X-Bugzilla-Keywords: X-Bugzilla-Severity: enhancement X-Bugzilla-Who: glisse at gcc dot gnu.org X-Bugzilla-Status: NEW 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: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-SW-Source: 2015-05/txt/msg00101.txt.bz2 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65641 --- Comment #4 from Marc Glisse --- Currently, the only implemented policy uses primes from a hard-coded list for the number of buckets. This makes it easy to precompute (and hard-code in the library) anything that may be helpful to speed-up modulo computation. With a number of buckets that is a power of 2, modulo computation becomes trivial (masking). However, the simplistic specialization of std::hash for pointers in libstdc++ means that all double* hash to a multiple of 8. So we would need to add some scrambling somewhere to avoid leaving most buckets empty in unordered_set.