Re: Hashtable Small size optimization

[Jonathan Wakely <jwakely at redhat dot com>]

Re https://gcc.gnu.org/ml/gcc-patches/2018-10/msg00903.html


On 15/10/18 22:46 +0200, François Dumont wrote:
> I started considering PR libstdc++/68303.
>
> First thing was to write a dedicated performance test case, it is the 
> unordered_small_size.cc I'd like to add with this patch.

Great, more performance tests are always good.

> The first runs show a major difference between tr1 and std 
> implementations, tr1 being much better:
>
> std::tr1::unordered_set<int> without hash code cached: 1st insert    
>    9r    9u    1s  14725920mem    0pf
> std::tr1::unordered_set<int> with hash code cached: 1st insert       
> 8r    9u    0s  14719680mem    0pf
> std::unordered_set<int> without hash code cached: 1st insert      
> 17r   17u    0s  16640080mem    0pf
> std::unordered_set<int> with hash code cached: 1st insert      14r   
> 14u    0s  16638656mem    0pf
>
> I had a look in gdb to find out why and the answer was quite obvious. 
> For 20 insertions tr1 implementation bucket count goes through [11, 
> 23] whereas for std it is [2, 5, 11, 23], so 2 more expensive rehash.
>
> As unordered containers are dedicated to rather important number of 
> elements I propose to review the rehash policy with this patch so that 
> std also starts at 11 on the 1st insertion. After the patch figures 
> are:
>
> std::tr1::unordered_set<int> without hash code cached: 1st insert    
>    9r    9u    0s  14725920mem    0pf
> std::tr1::unordered_set<int> with hash code cached: 1st insert       
> 8r    8u    0s  14719680mem    0pf
> std::unordered_set<int> without hash code cached: 1st insert      
> 15r   15u    0s  16640128mem    0pf
> std::unordered_set<int> with hash code cached: 1st insert      12r   
> 12u    0s  16638688mem    0pf

OK, that seems worthwhile then.

> Moreover I noticed that performance tests are built with -O2, is that 
> intentional ? The std implementation uses more abstractions than tr1, 
> looks like building with -O3 optimizes away most of those abstractions 
> making tr1 and std implementation much closer:

Yes, I think it's intentional that -O2 is used, because I think
that's the most commonly-used optimisation level. We don't want to 

> std::tr1::unordered_set<int> without hash code cached: 1st insert    
>    2r    1u    1s  14725952mem    0pf
> std::tr1::unordered_set<int> with hash code cached: 1st insert       
> 2r    1u    0s  14719536mem    0pf
> std::unordered_set<int> without hash code cached: 1st insert       
> 2r    2u    0s  16640064mem    0pf
> std::unordered_set<int> with hash code cached: 1st insert       2r    
> 2u    0s  16638608mem    0pf

Hmm, interesting. I wonder if we can determine what is not being
optimized at -O2, and either tweak the code or improve the compiler.

> Note that this patch also rework the alternative rehash policy based 
> on powers of 2 so that it also starts with a larger number of bucket 
> (16) and respects LWG2156.
>
> Last I had to wider the memory column so that alignment is preserved 
> even when memory diff is negative.
>
> Tested under Linux x86_64.
>
> Ok to commit ?

Does this patch still apply cleanly? I think it would be good to
commit it now, early in stage 1.