[Bug libstdc++/96088] New: Range insertion into unordered_map is less effective than a loop with insertion

[Bug libstdc++/96088] New: Range insertion into unordered_map is less effective than a loop with insertion

[antoshkka at gmail dot com]

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

            Bug ID: 96088
           Summary: Range insertion into unordered_map is less effective
                    than a loop with insertion
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: antoshkka at gmail dot com
  Target Milestone: ---

Consider the function f1:

static constexpr std::initializer_list<std::pair<const char*, int>> lst = {
    {"long_str_for_dynamic_allocating", 1}};

void f1() {
    std::unordered_map<std::string, int> m(1);
    m.insert(lst.begin(), lst.end());
}


It creates a temporary and as a result makes 4 allocations. Meanwhile f2 does
not create a temporary and does aonly 3 allocations:

void f2() {
    std::unordered_map<std::string, int> m(1);
    for (const auto& x : lst) {
        m.insert(x);
    }
}


Godbolt playground: https://godbolt.org/z/VapmBU

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[fdumont at gcc dot gnu.org]

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

--- Comment #1 from François Dumont <fdumont at gcc dot gnu.org> ---
The core issue here is that unordered_map key type is std::string while you
insert const char* which explains the temporary.

In f2 you use insert(Pair&&) method so a temporary is generated but then moved
into the container. In f1 we try to check for insertion before generating the
value_type and to do so we use hash<std::string> that generates an additional
temporary.

I'll check if we can be smarter here. A nice improvement would be to change
std::hash<std::string> operator signature to:

      size_t
      operator()(const string_view& __str) const noexcept

but that's a Standard modification.

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to François Dumont from comment #1)
> I'll check if we can be smarter here. A nice improvement would be to change
> std::hash<std::string> operator signature to:
> 
>       size_t
>       operator()(const string_view& __str) const noexcept
> 
> but that's a Standard modification.

Or use unordered_map<string, int, hash<string_view>, equal_to<>> which should
perform better.

We haven't implemented http://wg21.link/p0919r3 and http://wg21.link/p1690r1
yet, I wonder if those would help, especially if we make the internal helpers
available pre-C++20. That could allow the range insertion to use the
heteregenous lookup, to avoid creating temporaries. I'm not sure if that would
be conforming though. Heterogeneous lookup is observably different, and not
conforming in C++17.

Adding hash<string>::operator()(string_view) is an interesting idea for the
standard though.

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[glisse at gcc dot gnu.org]

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

--- Comment #3 from Marc Glisse <glisse at gcc dot gnu.org> ---

(In reply to Jonathan Wakely from comment #2)
> Or use unordered_map<string, int, hash<string_view>, equal_to<>> which
> should perform better.

Good idea.

> We haven't implemented http://wg21.link/p0919r3 and http://wg21.link/p1690r1
> yet, I wonder if those would help, especially if we make the internal
> helpers available pre-C++20. That could allow the range insertion to use the
> heteregenous lookup, to avoid creating temporaries. I'm not sure if that
> would be conforming though. Heterogeneous lookup is observably different,
> and not conforming in C++17.

Restricting it to a few standard types like string should not be observable.

> Adding hash<string>::operator()(string_view) is an interesting idea for the
> standard though.

Indeed. If we want to, I think it is possible to add some overloads for when
the argument is exactly const char* or string_view, which should remain
conforming and provide a significant part of the benefits.

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #3)
> > Adding hash<string>::operator()(string_view) is an interesting idea for the
> > standard though.
> 
> Indeed. If we want to, I think it is possible to add some overloads for when
> the argument is exactly const char* or string_view, which should remain
> conforming and provide a significant part of the benefits.

It would probably have to be:

  template<typename T>
    requires same_as<T, basic_string_view<Char,Traits>>
    size_t
    operator()(T) const;

otherwise it can introduce ambiguities for things convertible to both string
and string_view. But that annoyance aside, it seems worth exploring.

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[fdumont at gcc dot gnu.org]

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

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-08-04
           Assignee|unassigned at gcc dot gnu.org      |fdumont at gcc dot gnu.org

--- Comment #5 from François Dumont <fdumont at gcc dot gnu.org> ---
After further investigation the unordered containers are also suffering from a
problem similar to libstdc++/87194. There are several places where we
constraint the iterator value_type to be an instance of container key_type
forcing the compiler to generate temporaries.

I'll fix that so that the nice enhancements already proposed can indeed work.

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[fdumont at gcc dot gnu.org]

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

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #6 from François Dumont <fdumont at gcc dot gnu.org> ---
Fix with this commit:
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=2c43f5ec9db163696de8691eb529df06c4999bcc

libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088]

When inserting into unordered_multiset or unordered_multimap first instantiate
the node to store and compute the hash code from it to avoid a potential
intermediate key_type instantiation.

When inserting into unordered_set or unordered_map check if invoking the hash
functor with container key_type is noexcept and invoking the same hash functor
with key part of the iterator value_type can throw. In this case create a
temporary key_type instance at Hashtable level and use it to compute the hash
code. This temporary instance is moved to the final storage location if needed.

libstdc++-v3/ChangeLog:

PR libstdc++/96088
* include/bits/hashtable_policy.h (_Select2nd): New.
(_NodeBuilder<>): New.
(_ReuseOrAllocNode<>::operator()): Use variadic template args.
(_AllocNode<>::operator()): Likewise.
* include/bits/hashtable.h
(_Hashtable<>::__node_builder_t): New.
(_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)):
 New.
(_Hashtable<>::_S_forward_key): New.
(_Hashtable<>::_M_insert): Use latter.
(_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&,
false_type)):
Instantiate node first, compute hash code second.
* testsuite/23_containers/unordered_map/96088.cc: New test.
* testsuite/23_containers/unordered_multimap/96088.cc: New test.
* testsuite/23_containers/unordered_multiset/96088.cc: New test.
* testsuite/23_containers/unordered_set/96088.cc: New test.
* testsuite/util/replacement_memory_operators.h
(counter::_M_increment): New.
(counter::_M_decrement): New.
(counter::reset()): New.

[Bug libstdc++/96088] Range insertion into unordered_map is less effective than a loop with insertion

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:81eab204a56dcd8acb1ca5d7df277437ca07b51a

commit r12-1162-g81eab204a56dcd8acb1ca5d7df277437ca07b51a
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jun 2 12:33:38 2021 +0100

    libstdc++: Fix tests for COW std::string [PR 96088]

    The expected number of allocations is different when copying COW
    strings.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/96088
            * testsuite/23_containers/unordered_map/96088.cc: Adjust
            expected number of allocations.
            * testsuite/23_containers/unordered_set/96088.cc: Likewise.