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?

  • 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

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.


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.