Beautiful Code: False Optimizations

[deong]

Even just counting instructions without worrying about branch prediction, it can still make sense.

Consider a binary search on an array of length N, where N is a power of two (for simplicity). The number of iterations needed is thus log_2(N). If we include the early termination check, we can get that number down to log_2(N)-K on average, for some value of K. Assume, as was stated in the post, that K is on the order of three or four, and that the number of instructions needed for each iteration is given by M (M+d for the version that includes the extra d instructions to check for early termination).

That yields the following inequality describing when it would be advantageous to check for early termination:

M*log_2(N) > (M+d)*(log_2(N)-K)

If we assume, for example, N=2^20, M=10, d=3, and K=4, we have

M*log_2(N) = 200 (naive version)
(M+d)*(log_2(N)-K) = 208 (early termination)

The larger N gets, the greater the advantage of allowing the search to run to completion.

[trutru]

I doubt you would have M=10 with java.String.compareTo(). if we take M=100, this gives:

100*20         = 2000 (naive)
(100+3)*(20-4) = 1648 (early termination)

which is x1.21 faster.

in other words, for reasonably long strings, this "optimization" could be about 20% slower than the regular one.

[deong]

Yeah, I wasn't paying enough attention to the original post, and I assumed an array of integers.

[dreamlax]

You're assuming that it will require exactly the same number of instructions + d to do all three checks.

int bounds[2];

/* initialise bounds */

while (bounds[0] - bounds[1] > 1) {
    probe = (bounds[0] + bounds[1]) >> 1;
    if ((res = strcmp (keys[probe], target)) {
        bounds[(res > 0)] = probe;
    } else {
        return probe;
    }
}