In this little essay we are going to discuss poisoned numbers (numbers we want to avoid) by looking at two simple problems. We complicate the problems by asking how to write code to solve with without branches (which modern processors don't like.)
Suppose we start with 3 predefined constant numbers (which may or may not be different -- but you don't necessarily know.) You are passed two of the numbers, and required to return the third. This actually comes up as an interesting practical problem when using the "triple buffer algorithm" to smooth a stream of multimedia data when the producer is asynchronous to the consumer. One buffer was just written to, the other consumed, which is the remaining buffer from which we can start a new write sequence? Well we can pose a trivial solution:
But of course, this code has a lot of conditional operations (the if(), the &&, and 8 == operations). This does not bode well for our modern deeply pipelined processor. The question is, can we solve this without any branches (no if()'s, loops, ?: or conditional operators)?
Suppose we have been handed an array of 32 unsigned integers (2s complement) that are 32 bits in length each. We wish to choose any number which is different from all these numbers (not necessarily from any given set of numbers as in the problem described above.) How might we do this?
Well the loops ought to be well predicted right? Yeah, but the two if() statements in there are going be bad news for the our deeply pipelined processor. So same as before, the question is, can we solve this without any branches (no if()'s, loops, ?: or conditional operators)?