[PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Huanghui Nie]

[-- Attachment #1: Type: text/plain, Size: 4246 bytes --]

Hi.

When I implemented a hash table with reference to the C++ STL, I found that
when the hash table in the C++ STL deletes elements, if the first element
deleted is the begin element, the before begin node is repeatedly assigned.
This creates unnecessary performance overhead.


First, let’s see the code implementation:

In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when
&_M_before_begin == _M_buckets[__bkt]. That also means
_M_buckets[__bkt]->_M_nxt is assigned under some conditions.

_M_remove_bucket_begin is called by _M_erase and _M_extract_node:

   1. Case _M_erase a range: _M_remove_bucket_begin is called in a for loop
   when __is_bucket_begin is true. And if __is_bucket_begin is true and
   &_M_before_begin == _M_buckets[__bkt], __prev_n must be &_M_before_begin.
   __prev_n->_M_nxt is always assigned in _M_erase. That means
   _M_before_begin._M_nxt is always assigned, if _M_remove_bucket_begin is
   called and &_M_before_begin == _M_buckets[__bkt]. So there’s no need to
   assign _M_before_begin._M_nxt in _M_remove_bucket_begin.
   2. Other cases: _M_remove_bucket_begin is called when __prev_n ==
   _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in _M_erase and
   _M_before_begin. That means _M_buckets[__bkt]->_M_nxt is always assigned.
   So there's no need to assign _M_buckets[__bkt]->_M_nxt in
   _M_remove_bucket_begin.

In summary, there’s no need to check &_M_before_begin == _M_buckets[__bkt]
and assign _M_before_begin._M_nxt in _M_remove_bucket_begin.


Then let’s see the responsibility of each method:

The hash table in the C++ STL is composed of hash buckets and a node list.
The update of the node list is responsible for _M_erase and _M_extract_node
method. _M_remove_bucket_begin method only needs to update the hash
buckets. The update of _M_before_begin belongs to the update of the node
list. So _M_remove_bucket_begin doesn’t need to update _M_before_begin.


Existing tests listed below cover this change:

23_containers/unordered_set/allocator/copy.cc

23_containers/unordered_set/allocator/copy_assign.cc

23_containers/unordered_set/allocator/move.cc

23_containers/unordered_set/allocator/move_assign.cc

23_containers/unordered_set/allocator/swap.cc

23_containers/unordered_set/erase/1.cc

23_containers/unordered_set/erase/24061-set.cc

23_containers/unordered_set/modifiers/extract.cc

23_containers/unordered_set/operations/count.cc

23_containers/unordered_set/requirements/exception/basic.cc

23_containers/unordered_map/allocator/copy.cc

23_containers/unordered_map/allocator/copy_assign.cc

23_containers/unordered_map/allocator/move.cc

23_containers/unordered_map/allocator/move_assign.cc

23_containers/unordered_map/allocator/swap.cc

23_containers/unordered_map/erase/1.cc

23_containers/unordered_map/erase/24061-map.cc

23_containers/unordered_map/modifiers/extract.cc

23_containers/unordered_map/modifiers/move_assign.cc

23_containers/unordered_map/operations/count.cc

23_containers/unordered_map/requirements/exception/basic.cc


Regression tested on x86_64-pc-linux-gnu. Is it OK to commit?


---

ChangeLog:


libstdc++: hashtable: No need to update before begin node in
_M_remove_bucket_begin


2024-01-16  Huanghui Nie  <nnnjkk@gmail.com>


gcc/

* libstdc++-v3/include/bits/hashtable.h


---


diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h

index b48610036fa..6056639e663 100644

--- a/libstdc++-v3/include/bits/hashtable.h

+++ b/libstdc++-v3/include/bits/hashtable.h

@@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

        if (!__next_n || __next_bkt != __bkt)

          {

            // Bucket is now empty

-           // First update next bucket if any

+           // Update next bucket if any

            if (__next_n)

              _M_buckets[__next_bkt] = _M_buckets[__bkt];



-           // Second update before begin node if necessary

-           if (&_M_before_begin == _M_buckets[__bkt])

-             _M_before_begin._M_nxt = __next_n;

            _M_buckets[__bkt] = nullptr;

          }

       }

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 4694 bytes --]

Hi

Looks like a great finding to me, this is indeed a useless check, thanks!

Have you any figures on the performance enhancement ? It might help to 
get proper approval as gcc is currently in dev stage 4 that is to say 
only bug fixes normally.

François

On 17/01/2024 09:11, Huanghui Nie wrote:
>
> Hi.
>
> When I implemented a hash table with reference to the C++ STL, I found 
> that when the hash table in the C++ STL deletes elements, if the first 
> element deleted is the begin element, the before begin node is 
> repeatedly assigned. This creates unnecessary performance overhead.
>
>
> First, let’s see the code implementation:
>
> In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when 
> &_M_before_begin == _M_buckets[__bkt]. That also means 
> _M_buckets[__bkt]->_M_nxt is assigned under some conditions.
>
> _M_remove_bucket_begin is called by _M_erase and _M_extract_node:
>
>  1. Case _M_erase a range: _M_remove_bucket_begin is called in a for
>     loop when __is_bucket_begin is true. And if __is_bucket_begin is
>     true and &_M_before_begin == _M_buckets[__bkt], __prev_n must be
>     &_M_before_begin. __prev_n->_M_nxt is always assigned in _M_erase.
>     That means _M_before_begin._M_nxt is always assigned, if
>     _M_remove_bucket_begin is called and &_M_before_begin ==
>     _M_buckets[__bkt]. So there’s no need to assign
>     _M_before_begin._M_nxt in _M_remove_bucket_begin.
>  2. Other cases: _M_remove_bucket_begin is called when __prev_n ==
>     _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in
>     _M_erase and _M_before_begin. That means _M_buckets[__bkt]->_M_nxt
>     is always assigned. So there's no need to assign
>     _M_buckets[__bkt]->_M_nxt in _M_remove_bucket_begin.
>
> In summary, there’s no need to check &_M_before_begin == 
> _M_buckets[__bkt] and assign _M_before_begin._M_nxt in 
> _M_remove_bucket_begin.
>
>
> Then let’s see the responsibility of each method:
>
> The hash table in the C++ STL is composed of hash buckets and a node 
> list. The update of the node list is responsible for _M_erase and 
> _M_extract_node method. _M_remove_bucket_begin method only needs to 
> update the hash buckets. The update of _M_before_begin belongs to the 
> update of the node list. So _M_remove_bucket_begin doesn’t need to 
> update _M_before_begin.
>
>
> Existing tests listed below cover this change:
>
> 23_containers/unordered_set/allocator/copy.cc
>
> 23_containers/unordered_set/allocator/copy_assign.cc
>
> 23_containers/unordered_set/allocator/move.cc
>
> 23_containers/unordered_set/allocator/move_assign.cc
>
> 23_containers/unordered_set/allocator/swap.cc
>
> 23_containers/unordered_set/erase/1.cc
>
> 23_containers/unordered_set/erase/24061-set.cc
>
> 23_containers/unordered_set/modifiers/extract.cc
>
> 23_containers/unordered_set/operations/count.cc
>
> 23_containers/unordered_set/requirements/exception/basic.cc
>
> 23_containers/unordered_map/allocator/copy.cc
>
> 23_containers/unordered_map/allocator/copy_assign.cc
>
> 23_containers/unordered_map/allocator/move.cc
>
> 23_containers/unordered_map/allocator/move_assign.cc
>
> 23_containers/unordered_map/allocator/swap.cc
>
> 23_containers/unordered_map/erase/1.cc
>
> 23_containers/unordered_map/erase/24061-map.cc
>
> 23_containers/unordered_map/modifiers/extract.cc
>
> 23_containers/unordered_map/modifiers/move_assign.cc
>
> 23_containers/unordered_map/operations/count.cc
>
> 23_containers/unordered_map/requirements/exception/basic.cc
>
>
> Regression tested on x86_64-pc-linux-gnu. Is it OK to commit?
>
>
> ---
>
> ChangeLog:
>
>
> libstdc++: hashtable: No need to update before begin node in 
> _M_remove_bucket_begin
>
>
> 2024-01-16Huanghui Nie<nnnjkk@gmail.com>
>
>
> gcc/
>
> * libstdc++-v3/include/bits/hashtable.h
>
>
> ---
>
>
> diff --git a/libstdc++-v3/include/bits/hashtable.h 
> b/libstdc++-v3/include/bits/hashtable.h
>
> index b48610036fa..6056639e663 100644
>
> --- a/libstdc++-v3/include/bits/hashtable.h
>
> +++ b/libstdc++-v3/include/bits/hashtable.h
>
> @@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>       if (!__next_n || __next_bkt != __bkt)
>
>         {
>
>           // Bucket is now empty
>
> -         // First update next bucket if any
>
> +         // Update next bucket if any
>
>           if (__next_n)
>
>             _M_buckets[__next_bkt] = _M_buckets[__bkt];
>
> -         // Second update before begin node if necessary
>
> -         if (&_M_before_begin == _M_buckets[__bkt])
>
> -           _M_before_begin._M_nxt = __next_n;
>
>           _M_buckets[__bkt] = nullptr;
>
>         }
>
>     }
>
>

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Huanghui Nie]

[-- Attachment #1.1: Type: text/plain, Size: 6190 bytes --]

Yes, I have. I did a benchmark today.

The conclusion is: the time consumption can be reduced by 0.4% ~ 1.2% when
unordered_set erase(begin()), and 1.2% ~ 2.4% when erase(begin(), end()).


My test environment:

CPU: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz, 2393.365 MHz, 56 CPUs

MEM: 256G

OS: CentOS-8.2

g++: gcc version 8.3.1 20191121 (Red Hat 8.3.1-5) (GCC)

Compile flags: -O3 -std=c++17


Test conclusion data (time taken to delete every 100 million elements):

erase(begin()):

|size of unordered_set   |100     |1,000   |10,000  |100,000
|1,000,000|10,000,000|

|base time consuming (ms)|3827.736|3807.725|3830.168|3807.373|3798.713
|3854.168  |

|test time consuming (ms)|3783.406|3789.460|3791.146|3778.033|3783.494
|3808.137  |

|Time-consuming reduction|1.16%   |0.48%   |1.02%   |0.77%   |0.40%    |1.19%
    |

erase(begin(),end()):

|size of unordered_set   |100     |1,000   |10,000  |100,000
|1,000,000|10,000,000|

|base time consuming (ms)|2779.229|2768.550|2795.778|2767.385|2761.521
|2804.099  |

|test time consuming (ms)|2712.759|2726.578|2752.224|2732.140|2718.953
|2739.727  |

|Time-consuming reduction|2.39%   |1.52%   |1.56%   |1.27%   |1.54%    |2.30%
    |


Please see the attachment for test code and detailed test result.

2024年1月18日(木) 4:04 François Dumont <frs.dumont@gmail.com>:

> Hi
>
> Looks like a great finding to me, this is indeed a useless check, thanks!
>
> Have you any figures on the performance enhancement ? It might help to get
> proper approval as gcc is currently in dev stage 4 that is to say only bug
> fixes normally.
>
> François
> On 17/01/2024 09:11, Huanghui Nie wrote:
>
> Hi.
>
> When I implemented a hash table with reference to the C++ STL, I found
> that when the hash table in the C++ STL deletes elements, if the first
> element deleted is the begin element, the before begin node is repeatedly
> assigned. This creates unnecessary performance overhead.
>
>
> First, let’s see the code implementation:
>
> In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when
> &_M_before_begin == _M_buckets[__bkt]. That also means
> _M_buckets[__bkt]->_M_nxt is assigned under some conditions.
>
> _M_remove_bucket_begin is called by _M_erase and _M_extract_node:
>
>    1. Case _M_erase a range: _M_remove_bucket_begin is called in a for
>    loop when __is_bucket_begin is true. And if __is_bucket_begin is true and
>    &_M_before_begin == _M_buckets[__bkt], __prev_n must be &_M_before_begin.
>    __prev_n->_M_nxt is always assigned in _M_erase. That means
>    _M_before_begin._M_nxt is always assigned, if _M_remove_bucket_begin is
>    called and &_M_before_begin == _M_buckets[__bkt]. So there’s no need to
>    assign _M_before_begin._M_nxt in _M_remove_bucket_begin.
>    2. Other cases: _M_remove_bucket_begin is called when __prev_n ==
>    _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in _M_erase and
>    _M_before_begin. That means _M_buckets[__bkt]->_M_nxt is always assigned.
>    So there's no need to assign _M_buckets[__bkt]->_M_nxt in
>    _M_remove_bucket_begin.
>
> In summary, there’s no need to check &_M_before_begin == _M_buckets[__bkt]
> and assign _M_before_begin._M_nxt in _M_remove_bucket_begin.
>
>
> Then let’s see the responsibility of each method:
>
> The hash table in the C++ STL is composed of hash buckets and a node list.
> The update of the node list is responsible for _M_erase and _M_extract_node
> method. _M_remove_bucket_begin method only needs to update the hash
> buckets. The update of _M_before_begin belongs to the update of the node
> list. So _M_remove_bucket_begin doesn’t need to update _M_before_begin.
>
>
> Existing tests listed below cover this change:
>
> 23_containers/unordered_set/allocator/copy.cc
>
> 23_containers/unordered_set/allocator/copy_assign.cc
>
> 23_containers/unordered_set/allocator/move.cc
>
> 23_containers/unordered_set/allocator/move_assign.cc
>
> 23_containers/unordered_set/allocator/swap.cc
>
> 23_containers/unordered_set/erase/1.cc
>
> 23_containers/unordered_set/erase/24061-set.cc
>
> 23_containers/unordered_set/modifiers/extract.cc
>
> 23_containers/unordered_set/operations/count.cc
>
> 23_containers/unordered_set/requirements/exception/basic.cc
>
> 23_containers/unordered_map/allocator/copy.cc
>
> 23_containers/unordered_map/allocator/copy_assign.cc
>
> 23_containers/unordered_map/allocator/move.cc
>
> 23_containers/unordered_map/allocator/move_assign.cc
>
> 23_containers/unordered_map/allocator/swap.cc
>
> 23_containers/unordered_map/erase/1.cc
>
> 23_containers/unordered_map/erase/24061-map.cc
>
> 23_containers/unordered_map/modifiers/extract.cc
>
> 23_containers/unordered_map/modifiers/move_assign.cc
>
> 23_containers/unordered_map/operations/count.cc
>
> 23_containers/unordered_map/requirements/exception/basic.cc
>
>
> Regression tested on x86_64-pc-linux-gnu. Is it OK to commit?
>
>
> ---
>
> ChangeLog:
>
>
> libstdc++: hashtable: No need to update before begin node in
> _M_remove_bucket_begin
>
>
> 2024-01-16  Huanghui Nie  <nnnjkk@gmail.com>
>
>
> gcc/
>
> * libstdc++-v3/include/bits/hashtable.h
>
>
> ---
>
>
> diff --git a/libstdc++-v3/include/bits/hashtable.h
> b/libstdc++-v3/include/bits/hashtable.h
>
> index b48610036fa..6056639e663 100644
>
> --- a/libstdc++-v3/include/bits/hashtable.h
>
> +++ b/libstdc++-v3/include/bits/hashtable.h
>
> @@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>         if (!__next_n || __next_bkt != __bkt)
>
>           {
>
>             // Bucket is now empty
>
> -           // First update next bucket if any
>
> +           // Update next bucket if any
>
>             if (__next_n)
>
>               _M_buckets[__next_bkt] = _M_buckets[__bkt];
>
>
>
> -           // Second update before begin node if necessary
>
> -           if (&_M_before_begin == _M_buckets[__bkt])
>
> -             _M_before_begin._M_nxt = __next_n;
>
>             _M_buckets[__bkt] = nullptr;
>
>           }
>
>        }
>
>

[-- Attachment #2: test1.cc --]
[-- Type: application/octet-stream, Size: 630 bytes --]

#include <cstdio>
#include <cstdlib>
#include <unordered_set>
#include <chrono>

int main(int argc, char** argv) {
  int size = ::atoi(argv[1]);
  int loop = ::atoi(argv[2]);

  std::unordered_set<int> data;
  data.reserve(size);
  double t;
  for (int k = 0; k < loop; ++k) {
    for (int i = 0; i < size; ++i) {
      data.emplace(i);
    }
    auto t1 = std::chrono::steady_clock::now();
    for (int i = 0; i < size; ++i) {
      data.erase(data.begin());
    }
    auto t2 = std::chrono::steady_clock::now();
    t += std::chrono::duration<double, std::micro>(t2 - t1).count();
  }
  printf("Cost: %lf\n", t);
  return 0;
}


[-- Attachment #3: test2.cc --]
[-- Type: application/octet-stream, Size: 597 bytes --]

#include <cstdio>
#include <cstdlib>
#include <unordered_set>
#include <chrono>

int main(int argc, char** argv) {
  int size = ::atoi(argv[1]);
  int loop = ::atoi(argv[2]);

  std::unordered_set<int> data;
  data.reserve(size);
  double t;
  for (int k = 0; k < loop; ++k) {
    for (int i = 0; i < size; ++i) {
      data.emplace(i);
    }
    auto t1 = std::chrono::steady_clock::now();
    data.erase(data.begin(), data.end());
    auto t2 = std::chrono::steady_clock::now();
    t += std::chrono::duration<double, std::micro>(t2 - t1).count();
  }
  printf("Cost: %lf\n", t);
  return 0;
}


[-- Attachment #4: result.csv --]
[-- Type: text/csv, Size: 6212 bytes --]

hashtable version,"test type(1=erase(begin() 2=erase(begin(), end())",size of unordered_set,loop,cost time1,cost time2,cost time3,cost time4,cost time5,cost time6,cost time7,cost time8,cost time9,cost time10,cost time11,cost time12,cost time13,cost time14,cost time15,cost time16,cost time17,cost time18,cost time19,cost time20,cost time21,cost time22,cost time23,cost time24,average costtime
base,1,100,1000000,3823.493,3822.681,3823.487,3826.009,3827.419,3815.043,3824.576,3827.587,3823.115,3822.625,3828.422,3823.058,3826.549,3873.806,3815.655,3853.773,3816.512,3826.372,3807.932,3852.067,3820.759,3824.035,3833.077,3827.616,3827.736
test,1,100,1000000,3771.571,3769.245,3784.259,3770.356,3799.412,3773.946,3811.564,3770.921,3776.988,3814.076,3782.95,3796.984,3770.042,3783.934,3822.614,3786.986,3799.942,3769.783,3771.954,3767.856,3771.71,3771.4,3787.584,3775.674,3783.406
base,2,100,1000000,2809.389,2778.206,2776.783,2806.46,2773.297,2753.868,2779.01,2782.715,2801.758,2776.475,2775.62,2786.181,2772.866,2779.171,2776.704,2779.79,2778.756,2780.544,2783.637,2754.423,2780.021,2778.152,2758.39,2779.289,2779.229
test,2,100,1000000,2695.99,2706.163,2741.074,2702.181,2711.039,2697.633,2706.972,2734.776,2705.539,2704.209,2709.499,2727.339,2737.397,2748.108,2737.865,2705.216,2709.018,2706.612,2712.392,2702.284,2707.86,2685.334,2711.586,2700.123,2712.759
base,1,1000,100000,3797.022,3801.701,3845.955,3800.277,3799.269,3804.899,3798.337,3797.996,3803.812,3797.084,3799.005,3803.165,3795.779,3886.368,3805.567,3801.1,3796.808,3799.167,3801.139,3824.756,3797.933,3824.186,3799.616,3804.458,3807.725
test,1,1000,100000,3791.256,3790.226,3787.149,3787.383,3842.439,3787.531,3789.466,3788.159,3790.282,3777.703,3788.607,3788.634,3789.289,3783.478,3785.203,3796.558,3787.165,3789.253,3739.095,3809.067,3790.257,3789.134,3788.45,3791.262,3789.46
base,2,1000,100000,2770.653,2766.165,2766.432,2771.019,2764.841,2773.394,2768.809,2771.287,2766.246,2777.166,2769.634,2765.984,2766.127,2754.672,2768.229,2772.901,2769.123,2773.159,2774.906,2764.569,2766.496,2765.35,2767.608,2770.423,2768.55
test,2,1000,100000,2716.778,2714.804,2715.655,2720.923,2719.634,2731.495,2718.936,2742.902,2699.984,2723.99,2720.647,2724.48,2738.964,2720.266,2733.468,2715.76,2718.717,2716.562,2725.198,2717.34,2825.85,2732.884,2720.978,2721.668,2726.578
base,1,10000,10000,3822.724,3822.136,3832.718,3823.444,3822.066,3824.938,3845.033,3823.653,3825.097,3821.607,3856.073,3821.575,3821.405,3824.923,3821.77,3823.008,3821.993,3839.306,3820.877,3925.253,3817.731,3821.818,3821.173,3823.716,3830.168
test,1,10000,10000,3799.764,3785.985,3788.534,3789.304,3786.5,3788.131,3825.623,3785.362,3784.366,3801.078,3784.956,3784.937,3822.219,3785.595,3785.953,3788.438,3784.868,3791.152,3786.138,3786.018,3790.52,3790.296,3786.592,3785.18,3791.146
base,2,10000,10000,2792.236,2792.593,2793.781,2794.741,2794.203,2805.638,2795.744,2791.699,2816.771,2792.745,2791.476,2797.161,2790.68,2805.948,2790.781,2790.321,2790.225,2807.69,2790.333,2788.867,2796.099,2796.358,2795.142,2797.44,2795.778
test,2,10000,10000,2746.432,2742.164,2745.393,2768.938,2770.194,2747.573,2747.745,2745.096,2743.483,2744.135,2743.616,2811.89,2749.38,2745.868,2745.868,2744.948,2760.844,2743.756,2746.124,2745.905,2746.125,2774.749,2745.862,2747.297,2752.224
base,1,100000,1000,3803.815,3801.374,3805.723,3838.825,3807.848,3804.506,3809.31,3808.968,3809.804,3803.585,3804.104,3803.752,3833.906,3801.922,3801.311,3808.528,3801.909,3809.198,3800.951,3807.704,3802.195,3808.516,3806.399,3792.792,3807.373
test,1,100000,1000,3772.25,3773.281,3775.894,3773.233,3779.474,3776.377,3772.346,3776.045,3774.53,3777.022,3771.48,3774.368,3774.361,3774.061,3776.991,3784.857,3793.553,3773.227,3773.481,3806.12,3780.02,3791.458,3776.513,3771.853,3778.033
base,2,100000,1000,2774.227,2765.314,2770.277,2767.069,2763.217,2760.879,2770.374,2768.014,2765.732,2773.391,2765.237,2764.888,2766.775,2768.556,2772.143,2766.144,2765.849,2759.546,2768.855,2766.845,2766.124,2769.056,2768.17,2770.565,2767.385
test,2,100000,1000,2762.534,2688.875,2727.942,2732.512,2731.866,2730.009,2732.819,2731.785,2726.283,2730.371,2725.973,2737.078,2731.83,2730.165,2734.018,2727.441,2730.356,2729.162,2729.638,2781.079,2729.196,2730.84,2728.868,2730.714,2732.14
base,1,1000000,100,3795.995,3794.453,3798.35,3795.408,3797.449,3793.136,3799.852,3799.073,3795.84,3794.06,3796.174,3792.995,3795.656,3808.393,3795.261,3796.692,3794.845,3794.827,3793.469,3834.264,3796.209,3792.741,3816.559,3797.411,3798.713
test,1,1000000,100,3731.346,3779.127,3787.058,3763.331,3782.874,3787.526,3783.998,3794.579,3787.743,3780.275,3780.013,3778.24,3779.863,3785.267,3782.577,3795.678,3868.659,3782.761,3781.478,3781.01,3781.462,3780.29,3781.546,3767.153,3783.494
base,2,1000000,100,2761.417,2764.684,2761.706,2749.641,2759.581,2764.313,2760.867,2754.61,2760.823,2768.231,2759.123,2759.991,2759.151,2758.963,2765.045,2760.949,2762.091,2762.359,2770.512,2761.514,2759.618,2758.706,2769.368,2763.245,2761.521
test,2,1000000,100,2713.671,2715.116,2723.414,2713.218,2713.316,2726.65,2714.696,2688.076,2789.947,2712.222,2710.506,2691.592,2713.17,2712.399,2714.737,2713.679,2713.862,2713.766,2712.854,2724.32,2713.091,2713.861,2781.472,2715.245,2718.953
base,1,10000000,10,3840.799,3822.04,3823.061,3823.658,3822.138,4065.106,3836.565,3826.96,3821.787,3819.953,3822.437,3823.611,3823.497,4050.641,3820.995,3827.454,4061.5,3820.556,3824.042,3822.966,3822.598,3828.905,3822.462,3826.311,3854.168
test,1,10000000,10,3794.528,3794.328,3795.333,3798.696,3769.481,3793.053,3873.152,3799.613,3796.982,3798.711,3795.175,3795.941,4031.049,3809.053,3793.369,3793.605,3793.4,3793.058,3795.602,3794.969,3796.661,3797.499,3794.753,3797.278,3808.137
base,2,10000000,10,2789.121,2788.516,2776.764,2787.776,2789.507,2790.068,2777.693,2792.21,2790.414,2802.279,2789.662,2789.86,2785.881,2975.997,2788.857,2959.528,2784.704,2789.618,2790.713,2788.469,2788.762,2793.355,2797.491,2791.119,2804.099
test,2,10000000,10,2736.393,2740.613,2738.415,2736.739,2746.083,2750.259,2739.898,2736.715,2756.323,2740.862,2738.368,2717.114,2750.023,2739.277,2736.757,2737.928,2734.841,2736.417,2740.543,2739.228,2741.903,2740.973,2738.099,2739.668,2739.727

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 6868 bytes --]

Thanks, nice result, I'll try to run the performance benchmarks that are 
coming with libstdc++ to see if they spot anything.

That's tests in testsuite/performance folder in case you want to have a 
try yourself.

François


On 18/01/2024 10:26, Huanghui Nie wrote:
>
> Yes, I have. I did a benchmark today.
>
> The conclusion is: the time consumption can be reduced by 0.4% ~ 1.2% 
> when unordered_set erase(begin()), and 1.2% ~ 2.4% when erase(begin(), 
> end()).
>
>
> My test environment:
>
> CPU: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz, 2393.365 MHz, 56 CPUs
>
> MEM: 256G
>
> OS: CentOS-8.2
>
> g++: gcc version 8.3.1 20191121 (Red Hat 8.3.1-5) (GCC)
>
> Compile flags: -O3 -std=c++17
>
>
> Test conclusion data (time taken to delete every 100 million elements):
>
> erase(begin()):
>
> |size of unordered_set |100 |1,000 |10,000|100,000 |1,000,000|10,000,000|
>
> |base time consuming (ms)|3827.736|3807.725|3830.168|3807.373|3798.713 
> |3854.168|
>
> |test time consuming (ms)|3783.406|3789.460|3791.146|3778.033|3783.494 
> |3808.137|
>
> |Time-consuming reduction|1.16% |0.48% |1.02% |0.77% |0.40%|1.19% |
>
> erase(begin(),end()):
>
> |size of unordered_set |100 |1,000 |10,000|100,000 |1,000,000|10,000,000|
>
> |base time consuming (ms)|2779.229|2768.550|2795.778|2767.385|2761.521 
> |2804.099|
>
> |test time consuming (ms)|2712.759|2726.578|2752.224|2732.140|2718.953 
> |2739.727|
>
> |Time-consuming reduction|2.39% |1.52% |1.56% |1.27% |1.54%|2.30% |
>
>
> Please see the attachment for test code and detailed test result.
>
>
> 2024年1月18日(木) 4:04 François Dumont <frs.dumont@gmail.com>:
>
>     Hi
>
>     Looks like a great finding to me, this is indeed a useless check,
>     thanks!
>
>     Have you any figures on the performance enhancement ? It might
>     help to get proper approval as gcc is currently in dev stage 4
>     that is to say only bug fixes normally.
>
>     François
>
>     On 17/01/2024 09:11, Huanghui Nie wrote:
>>
>>     Hi.
>>
>>     When I implemented a hash table with reference to the C++ STL, I
>>     found that when the hash table in the C++ STL deletes elements,
>>     if the first element deleted is the begin element, the before
>>     begin node is repeatedly assigned. This creates unnecessary
>>     performance overhead.
>>
>>
>>     First, let’s see the code implementation:
>>
>>     In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned
>>     when &_M_before_begin == _M_buckets[__bkt]. That also means
>>     _M_buckets[__bkt]->_M_nxt is assigned under some conditions.
>>
>>     _M_remove_bucket_begin is called by _M_erase and _M_extract_node:
>>
>>      1. Case _M_erase a range: _M_remove_bucket_begin is called in a
>>         for loop when __is_bucket_begin is true. And if
>>         __is_bucket_begin is true and &_M_before_begin ==
>>         _M_buckets[__bkt], __prev_n must be &_M_before_begin.
>>         __prev_n->_M_nxt is always assigned in _M_erase. That means
>>         _M_before_begin._M_nxt is always assigned, if
>>         _M_remove_bucket_begin is called and &_M_before_begin ==
>>         _M_buckets[__bkt]. So there’s no need to assign
>>         _M_before_begin._M_nxt in _M_remove_bucket_begin.
>>      2. Other cases: _M_remove_bucket_begin is called when __prev_n
>>         == _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned
>>         in _M_erase and _M_before_begin. That means
>>         _M_buckets[__bkt]->_M_nxt is always assigned. So there's no
>>         need to assign _M_buckets[__bkt]->_M_nxt in
>>         _M_remove_bucket_begin.
>>
>>     In summary, there’s no need to check &_M_before_begin ==
>>     _M_buckets[__bkt] and assign _M_before_begin._M_nxt in
>>     _M_remove_bucket_begin.
>>
>>
>>     Then let’s see the responsibility of each method:
>>
>>     The hash table in the C++ STL is composed of hash buckets and a
>>     node list. The update of the node list is responsible for
>>     _M_erase and _M_extract_node method. _M_remove_bucket_begin
>>     method only needs to update the hash buckets. The update of
>>     _M_before_begin belongs to the update of the node list. So
>>     _M_remove_bucket_begin doesn’t need to update _M_before_begin.
>>
>>
>>     Existing tests listed below cover this change:
>>
>>     23_containers/unordered_set/allocator/copy.cc
>>
>>     23_containers/unordered_set/allocator/copy_assign.cc
>>
>>     23_containers/unordered_set/allocator/move.cc
>>
>>     23_containers/unordered_set/allocator/move_assign.cc
>>
>>     23_containers/unordered_set/allocator/swap.cc
>>
>>     23_containers/unordered_set/erase/1.cc
>>
>>     23_containers/unordered_set/erase/24061-set.cc
>>
>>     23_containers/unordered_set/modifiers/extract.cc
>>
>>     23_containers/unordered_set/operations/count.cc
>>
>>     23_containers/unordered_set/requirements/exception/basic.cc
>>
>>     23_containers/unordered_map/allocator/copy.cc
>>
>>     23_containers/unordered_map/allocator/copy_assign.cc
>>
>>     23_containers/unordered_map/allocator/move.cc
>>
>>     23_containers/unordered_map/allocator/move_assign.cc
>>
>>     23_containers/unordered_map/allocator/swap.cc
>>
>>     23_containers/unordered_map/erase/1.cc
>>
>>     23_containers/unordered_map/erase/24061-map.cc
>>
>>     23_containers/unordered_map/modifiers/extract.cc
>>
>>     23_containers/unordered_map/modifiers/move_assign.cc
>>
>>     23_containers/unordered_map/operations/count.cc
>>
>>     23_containers/unordered_map/requirements/exception/basic.cc
>>
>>
>>     Regression tested on x86_64-pc-linux-gnu. Is it OK to commit?
>>
>>
>>     ---
>>
>>     ChangeLog:
>>
>>
>>     libstdc++: hashtable: No need to update before begin node in
>>     _M_remove_bucket_begin
>>
>>
>>     2024-01-16Huanghui Nie<nnnjkk@gmail.com>
>>
>>
>>     gcc/
>>
>>     * libstdc++-v3/include/bits/hashtable.h
>>
>>
>>     ---
>>
>>
>>     diff --git a/libstdc++-v3/include/bits/hashtable.h
>>     b/libstdc++-v3/include/bits/hashtable.h
>>
>>     index b48610036fa..6056639e663 100644
>>
>>     --- a/libstdc++-v3/include/bits/hashtable.h
>>
>>     +++ b/libstdc++-v3/include/bits/hashtable.h
>>
>>     @@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>           if (!__next_n || __next_bkt != __bkt)
>>
>>             {
>>
>>               // Bucket is now empty
>>
>>     -         // First update next bucket if any
>>
>>     +         // Update next bucket if any
>>
>>               if (__next_n)
>>
>>                 _M_buckets[__next_bkt] = _M_buckets[__bkt];
>>
>>     -         // Second update before begin node if necessary
>>
>>     -         if (&_M_before_begin == _M_buckets[__bkt])
>>
>>     -           _M_before_begin._M_nxt = __next_n;
>>
>>               _M_buckets[__bkt] = nullptr;
>>
>>             }
>>
>>         }
>>
>>

[PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Huanghui Nie]

[-- Attachment #1.1: Type: text/plain, Size: 4030 bytes --]

Hi.

When I implemented a hash table with reference to the C++ STL, I found that
when the hash table in the C++ STL deletes elements, if the first element
deleted is the begin element, the before begin node is repeatedly assigned.
This creates unnecessary performance overhead.


First, let’s see the code implementation:

In _M_remove_bucket_begin, _M_before_begin._M_nxt is assigned when
&_M_before_begin == _M_buckets[__bkt]. That also means
_M_buckets[__bkt]->_M_nxt is assigned under some conditions.

_M_remove_bucket_begin is called by _M_erase and _M_extract_node:

   1. Case _M_erase a range: _M_remove_bucket_begin is called in a for loop
   when __is_bucket_begin is true. And if __is_bucket_begin is true and
   &_M_before_begin == _M_buckets[__bkt], __prev_n must be &_M_before_begin.
   __prev_n->_M_nxt is always assigned in _M_erase. That means
   _M_before_begin._M_nxt is always assigned, if _M_remove_bucket_begin is
   called and &_M_before_begin == _M_buckets[__bkt]. So there’s no need to
   assign _M_before_begin._M_nxt in _M_remove_bucket_begin.
   2. Other cases: _M_remove_bucket_begin is called when __prev_n ==
   _M_buckets[__bkt]. And __prev_n->_M_nxt is always assigned in _M_erase and
   _M_before_begin. That means _M_buckets[__bkt]->_M_nxt is always assigned.
   So there's no need to assign _M_buckets[__bkt]->_M_nxt in
   _M_remove_bucket_begin.

In summary, there’s no need to check &_M_before_begin == _M_buckets[__bkt]
and assign _M_before_begin._M_nxt in _M_remove_bucket_begin.


Then let’s see the responsibility of each method:

The hash table in the C++ STL is composed of hash buckets and a node list.
The update of the node list is responsible for _M_erase and _M_extract_node
method. _M_remove_bucket_begin method only needs to update the hash
buckets. The update of _M_before_begin belongs to the update of the node
list. So _M_remove_bucket_begin doesn’t need to update _M_before_begin.


Existing tests listed below cover this change:

23_containers/unordered_set/allocator/copy.cc

23_containers/unordered_set/allocator/copy_assign.cc

23_containers/unordered_set/allocator/move.cc

23_containers/unordered_set/allocator/move_assign.cc

23_containers/unordered_set/allocator/swap.cc

23_containers/unordered_set/erase/1.cc

23_containers/unordered_set/erase/24061-set.cc

23_containers/unordered_set/modifiers/extract.cc

23_containers/unordered_set/operations/count.cc

23_containers/unordered_set/requirements/exception/basic.cc

23_containers/unordered_map/allocator/copy.cc

23_containers/unordered_map/allocator/copy_assign.cc

23_containers/unordered_map/allocator/move.cc

23_containers/unordered_map/allocator/move_assign.cc

23_containers/unordered_map/allocator/swap.cc

23_containers/unordered_map/erase/1.cc

23_containers/unordered_map/erase/24061-map.cc

23_containers/unordered_map/modifiers/extract.cc

23_containers/unordered_map/modifiers/move_assign.cc

23_containers/unordered_map/operations/count.cc

23_containers/unordered_map/requirements/exception/basic.cc


Regression tested on x86_64-pc-linux-gnu. Is it OK to commit?


---


diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h

index b48610036fa..6056639e663 100644

--- a/libstdc++-v3/include/bits/hashtable.h

+++ b/libstdc++-v3/include/bits/hashtable.h

@@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

        if (!__next_n || __next_bkt != __bkt)

          {

            // Bucket is now empty

-           // First update next bucket if any

+           // Update next bucket if any

            if (__next_n)

              _M_buckets[__next_bkt] = _M_buckets[__bkt];



-           // Second update before begin node if necessary

-           if (&_M_before_begin == _M_buckets[__bkt])

-             _M_before_begin._M_nxt = __next_n;

            _M_buckets[__bkt] = nullptr;

          }

       }

[-- Attachment #2: no-need-to-update-before-begin-node.diff --]
[-- Type: application/octet-stream, Size: 693 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index b48610036fa..6056639e663 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -872,13 +872,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	if (!__next_n || __next_bkt != __bkt)
 	  {
 	    // Bucket is now empty
-	    // First update next bucket if any
+	    // Update next bucket if any
 	    if (__next_n)
 	      _M_buckets[__next_bkt] = _M_buckets[__bkt];
 
-	    // Second update before begin node if necessary
-	    if (&_M_before_begin == _M_buckets[__bkt])
-	      _M_before_begin._M_nxt = __next_n;
 	    _M_buckets[__bkt] = nullptr;
 	  }
       }

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Sam James]

Huanghui Nie <nnnjkk@gmail.com> writes:

> Hi.

Please CC the libstdc++ LM for libstdc++ patches, per
https://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html#list.patches.

> [...]

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Huanghui Nie]

[-- Attachment #1: Type: text/plain, Size: 313 bytes --]

Thanks. Done.

2024年1月17日(水) 12:39 Sam James <sam@gentoo.org>:

>
> Huanghui Nie <nnnjkk@gmail.com> writes:
>
> > Hi.
>
> Please CC the libstdc++ LM for libstdc++ patches, per
>
> https://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html#list.patches
> .
>
> > [...]
>
>

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 655 bytes --]

On Wed, 17 Jan 2024, 08:14 Huanghui Nie via Gcc, <gcc@gcc.gnu.org> wrote:

> Thanks. Done.
>

And don't CC the main gcc@ list, that's not for patch discussion. And if
you CC the right list, you don't need to CC the individual maintainers.

Anyway, it's on the right list now so we'll review it there, thanks.



> 2024年1月17日(水) 12:39 Sam James <sam@gentoo.org>:
>
> >
> > Huanghui Nie <nnnjkk@gmail.com> writes:
> >
> > > Hi.
> >
> > Please CC the libstdc++ LM for libstdc++ patches, per
> >
> >
> https://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html#list.patches
> > .
> >
> > > [...]
> >
> >
>

Re: [PATCH] libstdc++: hashtable: No need to update before begin node in _M_remove_bucket_begin

[Huanghui Nie]

[-- Attachment #1: Type: text/plain, Size: 852 bytes --]

I'm sorry for CC the gcc@ list. Waiting for your review results there.
Thanks.

2024年1月17日(水) 16:18 Jonathan Wakely <jwakely.gcc@gmail.com>:

>
>
> On Wed, 17 Jan 2024, 08:14 Huanghui Nie via Gcc, <gcc@gcc.gnu.org> wrote:
>
>> Thanks. Done.
>>
>
> And don't CC the main gcc@ list, that's not for patch discussion. And if
> you CC the right list, you don't need to CC the individual maintainers.
>
> Anyway, it's on the right list now so we'll review it there, thanks.
>
>
>
>> 2024年1月17日(水) 12:39 Sam James <sam@gentoo.org>:
>>
>> >
>> > Huanghui Nie <nnnjkk@gmail.com> writes:
>> >
>> > > Hi.
>> >
>> > Please CC the libstdc++ LM for libstdc++ patches, per
>> >
>> >
>> https://gcc.gnu.org/onlinedocs/libstdc++/manual/appendix_contributing.html#list.patches
>> > .
>> >
>> > > [...]
>> >
>> >
>>
>