Does every pure function have a branchless equivalent?

By pure function I understand a function that uses only its input values and no global state to produce the output.

By branchless function I understand a function that does not use if/else during its execution. A loop contains a branch with and unconditional jump. Constant loops can be unrolled.

As an example, here is the signum function:

function signum(x):
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;

And here is a branchless version of the same function:

function signum(x):
  return (x > 0) - (x < 0);

The general answer to your question is no. Consider a function which measures the length of a linked list. How would you implement that without a branch?

But if you just stick with functions which (say) take a machine word and return a machine word (which your example does) then the answer is "yes, sort of". In fact, when analysing algorithms in the word-RAM model, we conventionally assume that any function which takes a fixed number of machine words and returns a fixed number of machine words is constant-time, because it could (in principle, at least) be implemented with a lookup table or a new CPU instruction.

Whether the branch-free version is more practical or not depends partly on the function and partly on the CPU's instruction set.

Don't forget, by the way, that pretty much all modern CPUs have a conditional move instruction. Some ISAs (e.g. ARM) can do conditional execution of all, or almost all, instructions. So there's even more ways to implement branch-free code there.

  • $\begingroup$ Certainly, measuring the length of a linked list branchlessly is impossible, yet I can combine it with your second paragraph to achieve some success, by picturing the linked list as a array of machine words. My main question lies with the lookup table you mentioned: is it possible to represent each lookup table as a set of branchless instructions? $\endgroup$ Nov 26 '15 at 5:14
  • $\begingroup$ Does using a precomputed array of results and replacing the function with a single (branch-free!) load instruction count as cheating? It's not global "state", in the sense that you can't modify it. It's not part of the state of the program. $\endgroup$
    – Pseudonym
    Nov 26 '15 at 5:16
  • $\begingroup$ Now thats a very clever cheat :D I might try to narrow down my thinking: the mapping between the input and output values forms (usually) some pattern, such as f(x) = x*2 mod 256 and therefore its possible to derive the instruction sequence and luckily enough, it is branch-free (this is becoming a buzzword by now). If the input/output is a perfectly random pair, my best guess is that no sequence exists, let alone branch-free. The question that I am still puzzled by, is if any pattern can be represented without conditional execution. $\endgroup$ Nov 26 '15 at 5:29
  • $\begingroup$ Yes it can. However, if your machine word size is $w$ bits, it might require $O(2^w)$ instructions to implement the function in general. This is both a necessary condition (since you can't do better than the Kolmogorov complexity of the function), and a sufficient condition (since you could implement the lookup table with a large number of conditional move instructions). So while it's possible in principle, in practice you may not be able to fit the code in the computer that you want to run it on. $\endgroup$
    – Pseudonym
    Nov 26 '15 at 5:42

Here is a pure function which cannot be written without if/else. It takes one number and if the number is even it returns "EVEN" string or else it returns "ODD" string.

Also, in your second code sample the expression (x > 0) is internally a branching and it returns a boolean value and you cannot subtract boolean values.

  • 3
    $\begingroup$ Nope, that is pretty easy to do without a branch. In C: unsigned even_or_odd(int x) { unsigned t = x & 1; return 0x4556454e * (1-t) + 0x4f444400 * t; } /* Making this return a C string wouldn't format well in this little comment box, but you get the idea. */ $\endgroup$
    – Pseudonym
    Nov 26 '15 at 5:14
  • $\begingroup$ Brilliant, reminds me of this. $\endgroup$ Nov 26 '15 at 5:32
  • $\begingroup$ Well in general computation is all about if else isn't it. A transistor is if/else, logic gates are if/else and all the arithmetic (which was used in the tricky C code) is in the end if/else :) $\endgroup$
    – Ankur
    Nov 26 '15 at 5:40

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.