Bitwise binary search

A binary search is not a very interesting topic as it is a well known and fairly simple algorithm. However, I have encountered an interesting variant of it lately – one that I would like to share.

The Linux Kernel defines one Jiffy as the period of time between two consecutive system timer interrupts, and keeps a “jiffies” counter. Having jiffies, the next handy parameter would be the amount of delay-loop iterations that the CPU is able to fit in a single jiffy. With this number at hand (and known timer frequency) the kernel is able to support fine-grained execution delays, for instance. How would you implement computation of said “loops_per_jiffy” parameter?

Obviously, a binary search for the right loops_per_jiffy value is plausible: define upper and lower bounds, and constantly check their average value to half the range with each iteration. However, the approach taken in the kernel (and presented in the book Essential linux device drivers) is slightly different and therefore worth mentioning here.

The whole idea is to work the right bits of loops_per_jiffy, starting with the most-significant-bit (MSB) which is leftmost:

loops_per_jiffy = (1 << 12);  /* Initial approximation */

while ((loops_per_jiffy <<= 1) != 0) {
    ticks = jiffies;
    while (ticks == jiffies); /* Wait for a fresh jiffy */
    ticks = jiffies;

    __delay(loops_per_jiffy); /* Delay loop */

    /* Did the wait outlast the current jiffy? */
    ticks = jiffies - ticks;
    if (ticks) break;
}

loops_per_jiffy >>= 1;

The given code snippet searches for the location of the MSB by performing shift-left on the loops_per_jiffy variable (which is equivalent to multiplication by two) in each iteration. The loop breaks when the current value exceeds the required delay, which means that the right delay should be shorter. Therefore the previous value is restored; The MSB is now found and we can move on to the rest of the bits.

required_precision = 5;       /* Desired precision (bits) */

loopbit = loops_per_jiffy;

while (required_precision-- && (loopbit >>= 1)) {
    loops_per_jiffy |= loopbit;

    ticks = jiffies;
    while (ticks == jiffies); /* Wait for a fresh jiffy */
    ticks = jiffies;

    __delay(loops_per_jiffy); /* Delay loop */

    if (jiffies != ticks)     /* Longer than 1 tick */
        loops_per_jiffy &= ~loopbit;
}

Working our way to the right from the MSB (up to the given precision), the same trick is carried out every time: the current bit is toggled on with a bitwise OR operation, and if the wait is too long it will be toggled off with a bitwise AND operation. Once the right value is set, the algorithm moves on to the next bit by shifting right the current loopbit.

Have you encountered any non-trivial manifestations of well known algorithms? Feel free to share.

2 thoughts on “Bitwise binary search

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>