Branch prediction about randomx HOT 7 CLOSED

I've done some testing.

In tests/branch_prediction, there is a RandomX program translated into C. Only CALL and RET instructions are implemented, the rest is NOP. The program contains 128 CALL/RET instructions and 896 NOPs.

The program has 4 versions with different branching patterns:

• branch_always - CALL/RET is always taken.
• branch_predictably - One global counter is used to make random regular branching patterns for all CALL/RET instructions.
• branch_randomly - CALL/RET is randomly taken/not taken (each instruction has a different probability). An inline LCG is used for random number generation.
• branch_mixed - there are 2 types of CALL instructions: first type has the "predictable" branching pattern and a small number of CALL instructions have the "random" branching pattern.

The program uses the perf_event_open syscall to measure the number of hardware branch mispredictions.

> ./branch_mixed 1000000
0       1364014
1       16404
2       2807174
VM branches: 131967

Index 0 is the number of hardware branch instructions executed, index 1 is the number of mispredictions and index 3 is the runtime measured by the CPU timer.

As expected, the results vary a lot depending the CPU architecture. I have tested Intel Ivy Bridge (Core i3-3220) and AMD Ryzen (R7-1700).

Intel Ivy Bridge

AMD Ryzen

The performance difference between the predictable and random strategies is < 10%, which will become even smaller once the remaining (non-branching) instruction are taken into account.

If someone has access to a Linux machine with another CPU architecture, please test the 4 strategies and report results. Makefile is included to build the 4 tests. Run with 1000000 instructions like the example above. Beware that in some cases, the results vary widely between runs, so it's best to run multiple times and calculate the average.

Summary

Implementing any kind of branch-prediction-friendly patterns in RandomX is probably not worth the effort and risk of ASIC optimization.

from randomx.

Intel Core i5-8250U CPU @ 1.60GHz, average over 10 runs

./branch_always 1000000
0	1185262
1	84
2	4956039
VM branches: 111110

./branch_predictably 1000000
0	1262030
1	2454
2	4745556
VM branches: 134598

./branch_randomly 1000000
0	1304653
1	49918
2	5590118
VM branches: 139093

./branch_mixed 1000000
0	1364016
1	8635
2	4717666
VM branches: 131967

from randomx.

@wowario Can you please repeat branch_predictably and branch_mixed with the latest commit? There was a bug in the predictable algorithm that made it never branch.

from randomx.

How is "runtime per VMB" calculated?

from randomx.

Ryzen 2200G

from randomx.

@fuwa0529 It's the runtime divided by VMB scaled so that branch_randomly = 100%.

For you, it's ~126%, ~101%, 100% and ~104%. Strangely, random is the fastest.

from randomx.

I did notice some variation of the result, yet I was being lazy and only ran each test once ...

from randomx.