0
$\begingroup$

Consider for example the following recursive program:

function fibonacci(int n) {
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

The question is now, why recursive programs are problematic for branch predictors? I think that this is due to the fact that the branch-instruction inside these programs follows a very hard to predict pattern. When considering for example fibonacci(4), it holds that

fibonacci(4) = fibonacci(2) + fibonacci(3)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1).

Thus the following function calls will be performed in this order: fibonacci(2), fibonacci(3), fibonacci(0), fibonacci(1), fibonacci(1), fibonacci(2), fibonacci(1), fibonacci(0). This results in following sequence of Taken / Not Taken for the if-statement: NT NT T T T NT T T, which is quite irregular.

My question is now, if my answer and reasoning is correct?

$\endgroup$
  • 1
    $\begingroup$ Your statement sounds interesting and makes some sense. I'm curious though where you found the claim that recursion isn't very predictor-friendly, or why you thought originally that it's true. (I haven't come across it before.) $\endgroup$ – Omar Dec 9 '17 at 13:31
  • $\begingroup$ @Omar It's a question that was asked by the teacher on a test in our advanced computer architecture course, and I was curious if my answer makes sense $\endgroup$ – Pieter Verschaffelt Dec 9 '17 at 14:32
  • $\begingroup$ In terms of conditional branch prediction, recursion is not problematic. However, recursion can needlessly overflow a processor's return address stack (an address predictor in the front end), so no return address prediction will be available for older returns. Recursion can be converted to a looping structure by a sufficiently clever compiler, allowing the programmer to use recursion without performance loss. $\endgroup$ – Paul A. Clayton Dec 10 '17 at 13:00
  • $\begingroup$ @PaulA.Clayton I did not think about the Return Address Stack. This is indeed a very good remark and will definitely impact performance. Thank you $\endgroup$ – Pieter Verschaffelt Dec 10 '17 at 14:52
4
$\begingroup$

It would seem that recursion isn't the problem at all, but a pattern of branches that is hard to predict. For example, if you calculate n! using recursions (if n = 0 -> return 1 else return n * factorial (n-1)) that should play very nicely with branch prediction. For example 25! will start with 25 taken branches, followed by one branch not taken.

If you calculated fib (n) by simulating the recursion using a stack, you would have mostly a loop, with the exact same branches inside the loop, and as far as branch prediction is concerned, it would be just as good / bad with no recursion anywhere in sight.

PS. This was about predicting whether a branch is taken or not taken. Newer processors use other branch-related predictions: Predicting the target of a branch (for example for virtual functions, where a branch will lead to one of possibly many implementations of a virtual functions), and prediction of the target of a "return" instruction, where the processor predicts that a "return" instruction most likely branches to the instruction after the previous "call subroutine" instruction.

$\endgroup$
2
$\begingroup$

Along with the problem of unpredictable T/NT patterns (as explained by the other posts), there is a problem with the return addresses.

The prediction of the return address is done by using the RAS (return address stack), which is a circular buffer containing the last called addresses. When a return instruction is used, the last address of the RAS is used and the RAS pointer is decreased.

The problem with recursion is that the size of the RAS is limited (such as 64 addresses). If you use Fibonacci with a big N, we have more than 64 function calls and the older addresses in RAS are overwritten. Since the return address is hard to calculate, we can not use the prediction and speculative execution for these overwritten addresses, resulting in a lot of thrown away executions in the pipeline.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.