Fly Without Branches

Your boss comes running up to you and says:

“We have a stream with billions of integers, I want you to filter out the ones between 5 and 25!”

“That sounds easy enough. No probl–”

“One slight problem, you can’t sort the numbers in the stream and it has to be as fast as possible.”

You start coding away and come up with the below pseudo python code like a champ:

output = [0]*100000000000000000000000000000000

for num in stream:
  if num >= 5 and num <= 25:

Your boss comes back, his eyes glear down at your IDE.

“This is too slow; the branch prediction is poor!”

“The bra– what-a-what?”

“The CPU is boring as hell and it likes when life is predictable with it’s branch predictor! When it knows what’s coming, it can fill up the pipeline with the right instructions! Change it so that “if” statement is out!”

Are ternary operators still ok? Sure they are, they can be rewritten by the compiler.

The result is an unreadable chunk of code, but at least the CPU and your boss are happy!

output = [0]*100000000000000000000000000000000
i = 0

for num in stream:
  output[i] = num
  i += (1 if num >= 5 else 0) & (1 if num <= 25 else 0)