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

Re: Robin Hood Hashing for the perl core

Thread Previous | Thread Next
From:
Tomasz Konojacki
Date:
September 10, 2021 14:31
Subject:
Re: Robin Hood Hashing for the perl core
Message ID:
20210910163138.0090.5C4F47F8@xenu.pl
On Fri, 10 Sep 2021 12:21:06 +0000
Nicholas Clark <nick@ccl4.org> wrote:

> 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

Valgrind's branch prediction numbers are almost completely made up and
shouldn't be trusted. According to their documentation, valgrind's
simulated branch predictor is based on early Pentium 4. Modern CPUs work
completely differently!

https://valgrind.org/docs/manual/cg-manual.html#branch-sim

I'm also sceptical about its cache simulation. The only metrics I trust
are instruction and branch counts.

perf and AMD uProf are better tools for measuring those things.
Unfortunately, they aren't nearly as pleasant to use as valgrind.

BTW, while branch prediction numbers are very useful for figuring out
what the CPU is doing, it's important to remember that, in the end,
wall-clock time is the only metric that actually matters.

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