https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115285
--- Comment #18 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Jonathan Wakely <r...@gcc.gnu.org>: https://gcc.gnu.org/g:ce2cf1f03295b7992a8e3eae3c703845f045db27 commit r15-5213-gce2cf1f03295b7992a8e3eae3c703845f045db27 Author: Jonathan Wakely <jwak...@redhat.com> Date: Thu Oct 31 19:53:55 2024 +0000 libstdc++: Refactor Hashtable insertion [PR115285] This completely reworks the internal member functions for insertion into unordered containers. Currently we use a mixture of tag dispatching (for unique vs non-unique keys) and template specialization (for maps vs sets) to correctly implement insert and emplace members. This removes a lot of complexity and indirection by using 'if constexpr' to select the appropriate member function to call. Previously there were four overloads of _M_emplace, for unique keys and non-unique keys, and for hinted insertion and non-hinted. However two of those were redundant, because we always ignore the hint for unique keys and always use a hint for non-unique keys. Those four overloads have been replaced by two new non-overloaded function templates: _M_emplace_uniq and _M_emplace_multi. The former is for unique keys and doesn't take a hint, and the latter is for non-unique keys and takes a hint. In the body of _M_emplace_uniq there are special cases to handle emplacing values from which a key_type can be extracted directly. This means we don't need to allocate a node and construct a value_type that might be discarded if an equivalent key is already present. The special case applies when emplacing the key_type into std::unordered_set, or when emplacing std::pair<cv key_type, X> into std::unordered_map, or when emplacing two values into std::unordered_map where the first has type cv key_type. For the std::unordered_set case, obviously if we're inserting something that's already the key_type, we can look it up directly. For the std::unordered_map cases, we know that the inserted std::pair<const key_type, mapped_type> would have its first element initialized from first member of a std::pair value, or from the first of two values, so if that is a key_type, we can look that up directly. All the _M_insert overloads used a node generator parameter, but apart from the one case where _M_insert_range was called from _Hashtable::operator=(initializer_list<value_type>), that parameter was always the _AllocNode type, never the _ReuseOrAllocNode type. Because operator=(initializer_list<value_type>) was rewritten in an earlier commit, all calls to _M_insert now use _AllocNode, so there's no reason to pass the generator as a template parameter when inserting. The multiple overloads of _Hashtable::_M_insert can all be removed now, because the _Insert_base::insert members now call either _M_emplace_uniq or _M_emplace_multi directly, only passing a hint to the latter. Which one to call is decided using 'if constexpr (__unique_keys::value)' so there is no unnecessary code instantiation, and overload resolution is much simpler. The partial specializations of the _Insert class template can be entirely removed, moving the minor differences in 'insert' member functions into the common _Insert_base base class. The different behaviour for maps and sets can be implemented using enable_if constraints and 'if constexpr'. With the _Insert class template no longer needed, the _Insert_base class template can be renamed to _Insert. This is a minor simplification for the complex inheritance hierarchy used by _Hashtable, removing one base class. It also means one less class template instantiation, and no need to match the right partial specialization of _Insert. The _Insert base class could be removed entirely by moving all its 'insert' members into _Hashtable, because without any variation in specializations of _Insert there is no reason to use a base class to define those members. That is left for a later commit. Consistently using _M_emplace_uniq or _M_emplace_multi for insertion means we no longer attempt to avoid constructing a value_type object to find its key, removing the PR libstdc++/96088 optimizations. This fixes the bugs caused by those optimizations, such as PR libstdc++/115285, but causes regressions in the expected number of allocations and temporary objects constructed for the PR 96088 tests. It should be noted that the "regressions" in the 96088 tests put us exactly level with the number of allocations done by libc++ for those same tests. To mitigate this to some extent, _M_emplace_uniq detects when the emplace arguments already contain a key_type (either as the sole argument, for unordered_set, or as the first part of a pair of arguments, for unordered_map). In that specific case we don't need to allocate a node and construct a value type to check for an existing element with equivalent key. The remaining regressions in the number of allocations and temporaries should be addressed separately, with more conservative optimizations specific to std::string. That is not part of this commit. libstdc++-v3/ChangeLog: PR libstdc++/115285 * include/bits/hashtable.h (_Hashtable::_M_emplace): Replace with _M_emplace_uniq and _M_emplace_multi. (_Hashtable::_S_forward_key, _Hashtable::_M_insert_unique) (_Hashtable::_M_insert_unique_aux, _Hashtable::_M_insert): Remove. * include/bits/hashtable_policy.h (_ConvertToValueType): Remove. (_Insert_base::_M_insert_range): Remove overload for unique keys and rename overload for non-unique keys to ... (_Insert_base::_M_insert_range_multi): ... this. (_Insert_base::insert): Call _M_emplace_uniq or _M_emplace_multi instead of _M_insert. Add insert overloads from _Insert. (_Insert_base): Rename to _Insert. (_Insert): Remove * testsuite/23_containers/unordered_map/96088.cc: Adjust expected number of allocations. * testsuite/23_containers/unordered_set/96088.cc: Likewise.
