From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 2B64E385C31F; Tue, 12 Jul 2022 22:18:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2B64E385C31F From: "cuzdav at gmail dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/106275] New: unordered_map with std::string key, std::hash, and custom equality predicate weirdness Date: Tue, 12 Jul 2022 22:18:04 +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: 12.1.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: cuzdav 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: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 12 Jul 2022 22:18:05 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D106275 Bug ID: 106275 Summary: unordered_map with std::string key, std::hash, and custom equality predicate weirdness Product: gcc Version: 12.1.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ Assignee: unassigned at gcc dot gnu.org Reporter: cuzdav at gmail dot com Target Milestone: --- g++12.1 (on linux), Does not occur on GCC 11 or earlier. std::unordered_map, CustomPred> acts strangely such that finds do not seem to use the hasher properly, and seem = to use a linear search, invoking the equality predicate against every key.=20= =20 A custom hasher implemented in terms of std::hash fixes it, as does using the default equality predicate. It also does not happen with key type of, say, "int". I've only seen it for std::string (in my limited experimentation.) I added output to the predicate to indicate when it's called, and it shows excessive calls printed when "SHOWBUG" macro is defined. //////////////////////////////////////// #include #include #include #include struct EqualToWrapper{ bool operator()(const std::string& key1, const std::string& key2) const= { std::cout << "equal_to(key1=3D" << key1 << ", key2=3D" << key2 << "= )\n"; return std::equal_to<>{}(key1, key2); } }; #ifdef SHOWBUG using UsageMap =3D std::unordered_map, EqualToWrapper>; #else struct MyHash : public std::hash {}; using UsageMap =3D std::unordered_map; #endif int main() { UsageMap m; m.insert(std::make_pair("A", 111)); m.insert(std::make_pair("B", 222)); m.insert(std::make_pair("C", 333)); m.insert(std::make_pair("D", 444)); m.insert(std::make_pair("E", 555)); m.insert(std::make_pair("F", 666)); m.find("foo"); } //////////////////////////////// With a custom equality predicate and my derived-from-std::hash hasher, outp= ut on g++ 12 is: equal_to(key1=3DC, key2=3DA)=20=20=20 When run with -DSHOWBUG macro defined, output is: equal_to(key1=3DB, key2=3DA) equal_to(key1=3DC, key2=3DB) equal_to(key1=3DC, key2=3DA) equal_to(key1=3DD, key2=3DB) equal_to(key1=3DD, key2=3DC) equal_to(key1=3DD, key2=3DA) equal_to(key1=3DE, key2=3DB) equal_to(key1=3DE, key2=3DD) equal_to(key1=3DE, key2=3DC) equal_to(key1=3DE, key2=3DA) equal_to(key1=3DF, key2=3DE) equal_to(key1=3DF, key2=3DB) equal_to(key1=3DF, key2=3DD) equal_to(key1=3DF, key2=3DC) equal_to(key1=3DF, key2=3DA) equal_to(key1=3Dfoo, key2=3DF) equal_to(key1=3Dfoo, key2=3DE) equal_to(key1=3Dfoo, key2=3DB) equal_to(key1=3Dfoo, key2=3DD) equal_to(key1=3Dfoo, key2=3DC) equal_to(key1=3Dfoo, key2=3DA) On Godbolt: https://godbolt.org/z/GP5dox1qs $ g++ -v=20 Using built-in specs. COLLECT_GCC=3Dg++ COLLECT_LTO_WRAPPER=3D/opt/imc/gcc-12.1.0/libexec/gcc/x86_64-pc-linux-gnu/1= 2.1.0/lto-wrapper Target: x86_64-pc-linux-gnu Configured with: ../gcc-12.1.0/configure --prefix=3D/opt/imc/gcc-12.1.0 --enable-languages=3Dc,c++,fortran,lto --disable-multilib --with-build-time-tools=3D/build/INSTALLDIR//opt/imc/gcc-12.1.0/bin --enable-libstdcxx-time=3Drt Thread model: posix Supported LTO compression algorithms: zlib gcc version 12.1.0 (GCC)=