[NSWI131] 03-counter-spinner: Weird branch missprediction counter behavior

[Petr Tůma]

Hi Pavel,

interesting, isn't it ? :-) The answer can be found by looking at how GCC compiles your code, in particular the two possible returns:

>         if (arr[idx]) {
>             return 1;
>         } else {
>             return 2;
>         }

movzbl  8(%rdi,%rax), %eax    ;Read bool from array position, extend to entire EAX
testb   %al, %al              ;Check if bottom byte of EAX is zero or not
sete    %al                   ;If previous check was zero, set low byte of EAX to 1, otherwise to 0
movzbl  %al, %eax             ;Extend low byte of EAX to entire EAX
addl    $1, %eax              ;Add one to EAX

So you see, the compiler converted your IF construct into something that, written in C++, would be "return (1+!arr[idx])". Same behavior, but no conditional jump.

Petr


On 19/03/2020 19:00, Pavel Marek wrote:
> Hello,
> 
> I am working on 03-counter-spinner assignment and I am confused from the way how my CPU predicts/miss predicts branches (PAPI_BR_MSP, and PAPI_BR_PRC counters).
> 
> Here is the particular example: I have quite a huge array of booleans (100MB), initialize it to a random values, and then in `execute` just increase the index and conditionally jump based on the content of the array. Here is the code:
> 
> ```c++
> class branch_misspredictions : public workload {
> private:
>     static constexpr size_t arr_size = 100*1024*1024; // 100MB
>     volatile bool arr[arr_size];
>     size_t idx;
> 
> public:
>     void before() {
>         idx = 0;
>         srand(42);
>         for (size_t i = 0; i < arr_size; i++) {
>             arr[i] = rand() % 2 == 0 ? true : false;
>         }
>     }
> 
>     int execute() {
>         idx = (idx < arr_size - 1) ? idx + 1 : 0;
>         if (arr[idx]) {
>             return 1;
>         } else {
>             return 2;
>         }
>     }
> };
> ```
> 
> The score (ratio events/instructions) for correct predictions (PAPI_BR_PRC) is: 0.09 and for miss predictions (PAPI_BR_MSP) is: 0.00007
> 
> My intuition tells me that the scores should be other way around ie. there should be a lot of miss predictions and few correct predictions.
> 
> Can you provide some insight of what I am doing wrong here? It seems really weird to me, but maybe I missed something trivial..
> 
> Type of my CPU: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
> 
> 
> Thanks for any comments.
> Pavel Marek
> _______________________________________________
> NSWI131 mailing list
> NSWI131 at d3s.mff.cuni.cz
> https://d3s.mff.cuni.cz/mailman/listinfo/nswi131