develooper Front page | perl.perl5.porters | Postings from September 2021

Re: Robin Hood Hashing for the perl core

Thread Previous | Thread Next
From:
Nicholas Clark
Date:
September 10, 2021 12:21
Subject:
Re: Robin Hood Hashing for the perl core
Message ID:
YTtNsmGyukWQ42YM@etla.org
On Fri, Sep 10, 2021 at 10:47:48AM +0100, Dave Mitchell wrote:
> On Fri, Sep 10, 2021 at 08:50:42AM +0000, Nicholas Clark wrote:
> > Lots more CPU instructions.
> > More CPU cache references, but far fewer last level read misses.
> 
> I'd be interested in seeing the changes in number of branches and numbers
> of failed branch predictions.  My unquantified intuition is that that is
> one of the most important performance factors in modern CPUs.

Aha, --branch-sim=yes

blead at 75595dd289

==9493== I   refs:      36,259,777,136
==9493== I1  misses:            34,365
==9493== LLi misses:             7,108
==9493== I1  miss rate:           0.00%
==9493== LLi miss rate:           0.00%
==9493==
==9493== D   refs:      16,768,164,534  (11,109,175,017 rd   + 5,658,989,517 wr)
==9493== D1  misses:       215,977,059  (   190,801,625 rd   +    25,175,434 wr)
==9493== LLd misses:       206,542,187  (   183,664,107 rd   +    22,878,080 wr)
==9493== D1  miss rate:            1.3% (           1.7%     +           0.4%  )
==9493== LLd miss rate:            1.2% (           1.7%     +           0.4%  )
==9493==
==9493== LL refs:          216,011,424  (   190,835,990 rd   +    25,175,434 wr)
==9493== LL misses:        206,549,295  (   183,671,215 rd   +    22,878,080 wr)
==9493== LL miss rate:             0.4% (           0.4%     +           0.4%  )
==9493==
==9493== Branches:       5,829,099,182  ( 5,326,755,821 cond +   502,343,361 ind)
==9493== Mispredicts:      429,396,239  (    89,391,173 cond +   340,005,066 ind)
==9493== Mispred rate:             7.4% (           1.7%     +          67.7%   )


ABH, load factor 0.625 (*not* 0.675 as I mis-reported earlier. Sorry)

==27112== I   refs:      41,942,836,004
==27112== I1  misses:            33,102
==27112== LLi misses:             6,921
==27112== I1  miss rate:           0.00%
==27112== LLi miss rate:           0.00%
==27112==
==27112== D   refs:      18,637,514,170  (12,273,187,422 rd   + 6,364,326,748 wr)
==27112== D1  misses:       222,136,637  (   182,252,838 rd   +    39,883,799 wr)
==27112== LLd misses:       181,543,299  (   145,196,987 rd   +    36,346,312 wr)
==27112== D1  miss rate:            1.2% (           1.5%     +           0.6%  )
==27112== LLd miss rate:            1.0% (           1.2%     +           0.6%  )
==27112==
==27112== LL refs:          222,169,739  (   182,285,940 rd   +    39,883,799 wr)
==27112== LL misses:        181,550,220  (   145,203,908 rd   +    36,346,312 wr)
==27112== LL miss rate:             0.3% (           0.3%     +           0.6%  )
==27112==
==27112== Branches:       6,629,846,443  ( 6,119,713,828 cond +   510,132,615 ind)
==27112== Mispredicts:      447,055,595  (   127,049,280 cond +   320,006,315 ind)
==27112== Mispred rate:             6.7% (           2.1%     +          62.7%   )


If I read that right

More branches.

In absolute numbers, more mispredicts for conditional branches, fewer for
indirect branches. (Where *are* the indirect branches we're hitting so much?),

In absolute numbers slightly more mispredicts over all, but proportionally
fewer.

(Burn more CPU work with the intent to reduce cache misses)

I'm not sure what can be tweaked to be better.
Or what actually matters, and what's fluff.
What is the benchmark?


Nicholas Clark

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About