Re: [PATCH 5/5][_Hashtable] Prefer to insert after last node

[Jonathan Wakely <jwakely@redhat.com>]

I think this should wait for the next stage 1. It's a big patch
affecting the default -std mode (not just experimental C++20/23/26
material), and was first posted after the end of stage 1.

Do we really need the changes for versioned namespace? How much
difference does that extra member make to performance, compared with
the version for the default config?

On Wed, 20 Dec 2023 at 06:10, François Dumont <frs.dumont@gmail.com> wrote:
>
> Here is a new version of this patch.
>
> The previous one had some flaws that were unnoticed by testsuite tests,
> only the performance tests were spotting it. So I'm adding checks on the
> consistency of the unordered containers in this patch.
>
> I also forget to signal that after this patch gnu versioned namespace
> version is supposed to be bump. But I hope it's already the plan because
> of the move to the cxx11 abi in this mode.
>
> Note for reviewer, after application of the patch, a 'git diff -b' is
> much more readable.
>
> And some benches results:
>
> before:
>
> unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000
> inserts individually 19999990 calls      44r   44u    0s 95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000
> inserts in range 20000000 calls      43r   43u    0s 95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X
> inserts individually 19999990 calls      44r   44u 0s  95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X
> inserts in range 20000000 calls      43r   43u    0s 95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000
> inserts individually 10000000 calls      30r   30u    0s 111999328mem
> 0pf
> unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000
> inserts in range 10000010 calls      33r   32u    0s 111999328mem    0pf
> unordered_set_range_insert.cc-thread    hash code cached 1000000 X
> inserts individually 10000000 calls      30r   31u    0s 111999328mem
> 0pf
> unordered_set_range_insert.cc-thread    hash code cached 1000000 X
> inserts in range 10000010 calls      32r   32u    0s 111999328mem    0pf
>
> after:
>
> unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000
> inserts individually 19999990 calls      44r   44u    0s 95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000
> inserts in range 10000020 calls      26r   25u    0s 95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X
> inserts individually 19999990 calls      43r   44u 0s  95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X
> inserts in range 10000020 calls      26r   26u    0s 95999760mem    0pf
> unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000
> inserts individually 10000000 calls      35r   35u    0s 111999328mem
> 0pf
> unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000
> inserts in range 10000010 calls      32r   33u    0s 111999328mem    0pf
> unordered_set_range_insert.cc-thread    hash code cached 1000000 X
> inserts individually 10000000 calls      31r   32u    0s 111999328mem
> 0pf
> unordered_set_range_insert.cc-thread    hash code cached 1000000 X
> inserts in range 10000010 calls      31r   31u    0s 111999328mem    0pf
>
>
>      libstdc++: [_Hashtable] Prefer to insert after last node
>
>      When inserting an element into an empty bucket we currently insert
> the new node
>      after the before-begin node so in first position. The drawback of
> doing this is
>      that we are forced to update the bucket that was containing this
> before-begin
>      node to point to the newly inserted node. To do so we need at best
> to do a modulo
>      to find this bucket and at worst, when hash code is not cached,
> also compute it.
>
>      To avoid this side effect it is better to insert after the last
> node. To do so
>      we are introducing a helper type _HintPolicy that has 3
> resposibilities.
>
>      1. When the gnu versioned namespace is used we add a _M_last member
> to _Hashtable,
>      _HintPolicy is then in charge of maintaining it. For this purpose
> _HintPolicy is
>      using the RAII pattern, it resets the _M_last at destruction level.
> It also maintain
>      its own _M_last, all mutable operations are updating it when needed.
>
>      2. When the gnu versioned namespace is not used _HintPolicy will
> still maintain its
>      _M_last member using initially the user provided hint if any and if
> it is actually
>      the container last node that is to say a dereferenceable node with
> its next node being
>      null. All mutable operations can also update the contextual
> _HintPolicy instance
>      whenever they detect the last node during their process.
>
>      3. As long as we haven't been able to detect the container last
> node, _HintPolicy
>      is used to keep a cache of the before-begin bucket index so that we
> do not need to
>      compute it afterward for example in the context of range insertion.
>
>      libstdc++-v3/ChangeLog:
>
>              * include/bits/hashtable.h
> [_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container
> last node.
>              (_Hashtable<>::_LastNodeManager): New.
>              (_Hashtable<>::_M_get_last(__node_ptr)): New.
> (_Hashtable<>::_M_get_last_node_mgr(__node_ptr)): New.
> (_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.
>              (_Hashtable<>::_M_set_last(__node_ptr)): New.
>              (_Hashtable<>::_M_compute_hash_code(__node_ptr, const
> key_type&)): Remove.
> (_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a
> _HintPolicy.
>              (_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy&
> parameter and use it
>              to optimize insertion in an empty bucket.
>              (_Hashtable<>::_M_insert_unique_node): Add _HintPolicy&
> parameter.
>              (_Hashtable<>::_M_insert_multi_node(__node_ptr,
> __hash_code, __node_ptr)): Replace by...
> (_Hashtable<>::_M_insert_multi_node(_HintPolicy&, const key_type&,
>              __node_ptr, __node_ptr)): ... this.
> (_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New.
> (_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.
>              (_Hashtable<>::_M_emplace): Adapt to use latters.
>              (_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.
>              (_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy&
> parameter.
>              (_Hashtable<>::_M_insert): Adapt to use latter.
>              (_Hashtable<>::emplace_hint(const_iterator, _Args&&...)):
> Adapt.
>              (_hashtable<>::rehash(size_type)): Adapt.
>              (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):
>              Add hint parameter, adapt to use it for _HintPolicy
> instantiation.
>              (_Hashtable<>::_M_reinsert_node_multi): Likewise.
>              (_Hashtable<>::_M_merge_unique): Adapt.
>              (_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.
>              (_Hashtable<>::_Hashtable<_InputIte>()): Adapt.
>              (_Hashtable<>::_M_assign): Call _M_set_last.
>              (_Hashtable<>::_M_reset()): Reset _M_last.
> (_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.
>              (_Hashtable<>(_Hashtable&&, __node_alloc_type&&,
> true_type)): Copy _M_last.
>              (_Hashtable<>(_Hashtable&&, __node_alloc_type&&,
> false_type)): Copy _M_last.
>              (_Hashtable<>::_M_insert_range): Adapt.
>              (_Hashtable<>::_M_erase): Call _M_check_for_last.
>              (_Hashtable<>::erase): Likewise.
>              * include/bits/hashtable_policy.h:
>              (_Map_base<>::operator[](const key_type&)): Use hint policy.
>              (_Map_base<>::operator[](key_type&&)): Likewise.
>              (_Insert_base<>::insert(const_iterator, const
> value_type&)): Likewise using hint.
>              (_Insert_base<>::try_emplace): Likewise.
> (_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)):
> Use hint policy.
> (_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)):
> Use hint policy.
>              (_Insert<>::insert(const_iterator, value_type&&)): Likewise.
>              * include/bits/unordered_map.h
> (unordered_map<>::insert(node_type&&)): Pass cend as
>              hint.
>              (unordered_map<>::insert(const_iterator, node_type&&)):
> Adapt to use hint.
>              * include/bits/unordered_set.h
> (unordered_set<>::insert(node_type&&)): Pass cend as
>              hint.
>              (unordered_set<>::insert(const_iterator, node_type&&)):
> Adapt to use hint.
>              *
> testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt
> implementation
>              specific tests.
>              *
> testsuite/23_containers/unordered_map/consistency_check.cc: New test case.
>              *
> testsuite/23_containers/unordered_multimap/consistency_check.cc: New
> test case.
>              *
> testsuite/23_containers/unordered_multiset/consistency_check.cc: New
> test case.
>              *
> testsuite/23_containers/unordered_set/consistency_check.cc: New test case.
>              * testsuite/libstdc++-prettyprinters/cxx11.cc (main): Adapt
> expectations on element
>              order in unordered_map instance.
>