Optimization attempt of findPeriod using binary search

[rveilleux]

Optimized findPeriod to use a binary search into the 36 elements period table O(log N) instead of O(N) lookups

[rveilleux]

Note: Even while it performs less lookup in average, the loop is more complex, so perhaps real-world gain will be small.

[tehKaiN]

It's a funny thing - I've done something similar in the past, emailed Frank W. about it and he told me he's unsure that the optimization is worth it. I've checked my code again by running it in release mode (-O3 compiler option) and it was horribly slower than his trivial array traversal.

Have you done some measurements with Bartman's profiler and/or setting custom.color[0] to fixed color during the function run? Lemme know how's the performance before/after.

My code looked like this:

static inline UBYTE findPeriod(UWORD *pPeriods, UWORD uwNote) {
    // Find nearest period for a note value
    // https://stackoverflow.com/questions/6553970/
    UBYTE ubLow = 0, ubHigh = MOD_PERIOD_TABLE_LENGTH;
    while (ubLow != ubHigh) {
        UBYTE ubMid = (ubLow + ubHigh) / 2;
        if (uwNote < pPeriods[ubMid]) {
            // This index, and everything below it, is not the first element
            // greater/equal than what we're looking for because
            // this element is no greater/equal than the element.
            ubLow = ubMid + 1;
        }
        else {
            // This element is at least as large as the element, so anything after it can't
            // be the first element that's at least as large.
            ubHigh = ubMid;
        }
    }
}