= Switch vs Coded Binary Search =

This is just an example to generate the extra performance of an if...else binary search algorithm over a switch statement. See [MetaBinarySearch] for more on how to generate binary search algorithms.

Be aware that although this example shows huge speed improvements in some cases, switch statements do still have many advantages, such as simpler, much clearer code, and probably slightly smaller binaries.

== Benchmarking code ==

{{{
#!d
/** Test speed of switch (...) statements verse a binary search using if (...) ... else ...
*
* The results speak for themselves, but bear in mind the rather large number of possible cases
* (i.e. vals) in the latter results.
*
* vals is the number of possible values (so number of case statements).
* N is the number of variables to look up the value of.
*
* Result (vals = 0x10, N = 0x1000000):
*
* Init... done (time 0.74)
* Binary search...done (time 1.20)
* Switch search...done (time 1.80)
*
* Result (vals = 0x100, N = 0x1000000):
*
* Init... done (time 0.87)
* Binary search...done (time 1.66)
* Switch search...done (time 4.33)
*
* Result (vals = 0x1000, N = 0x1000000):
*
* Init... done (time 0.78)
* Binary search...done (time 2.08)
* Switch search...done (time 38.99)
*/
module meta_switchBench;

import tango.time.StopWatch;
import tango.io.Stdout;
import tango.math.Random;

const uint vals = 0x100;    // must be no more than type.max+1
alias ubyte type;

// Simple inefficient int-to-string converter
char[] itoa (uint x) {
    if (x == 0) return "0";
    else {
        char[] ret;
        while (x > 0) {
            ret = cast(char)((x % 10) + '0') ~ ret;
            x /= 10;
        }
        return ret;
    }
}

// Generates the "number string"
char[][] genNumbers () {
    char[][] ret;
    
    for (ushort i = 0; i < vals; ++i) {
        ret ~= itoa (i);
    }
    
    return ret;
}

// Purely to add indentation. Could just return "" without affecting functionality.
char[] indent (uint i) {
    char[] ret;
    for (; i > 0; --i) ret ~= "  ";
    // This is not executable at compile time:
    //ret.length = i * 4;		// number of characters for each indentation
    //ret[] = ' ';		// character to indent with
    return ret;
}
    
/* Generates a binary search algorithm.
*
* Currently this is tailored to it's particular use (switchBench). */
char[] binarySearch (char[] var, char[][] consts, int indents = 0) {
    if (consts.length > 3) {
        return indent(indents) ~ "if (" ~ var ~ " <= " ~ consts[$/2 - 1] ~ ") {\n" ~
            binarySearch (var, consts[0 .. $/2], indents + 1) ~
        indent(indents) ~ "} else {\n" ~
            binarySearch (var, consts[$/2 .. $], indents + 1) ~
        indent(indents) ~ "}\n";
    } else {
        char[] ret;
        ret ~= indent(indents);
        foreach (c; consts) {
            ret ~= "if (" ~ var ~ " == " ~ c ~ ") {\n" ~
                indent(indents+1) ~ "++dOut["~c~"];\n" ~
            indent(indents) ~ "} else ";
        }
        ret = ret[0..$-6] ~ '\n';  // remove last else
        return ret;
    }
}

char[] switchSearch (char[] var, char[][] consts) {
    char[] ret;
    
    ret ~= "switch ("~var~") {\n";
        foreach (c; consts) {
            ret ~= indent(1) ~ "case "~c~":\n"~
                indent(2) ~ "++dOut["~c~"];\n"~
            indent(2) ~ "break;\n";
        }
    ret ~= "}\n";
    
    return ret;
}

const char[][] nums = genNumbers();

void main() {
    const N = 0x1000000;
    type[] dIn = new type[N];
    ubyte[vals] dOut;
    float t;
    
    StopWatch sw;
    Random rand = new Random;
    
    Stdout ("Init... ").flush;
    sw.start;
    foreach (inout i; dIn) i = rand.next(vals);
    t = sw.stop;
    Stdout.format ("done (time {})", t).newline;
    
    Stdout ("Binary search...").flush;
    foreach (x; dIn) {
        mixin (binarySearch ("x", nums));
    }
    t = sw.stop;
    Stdout.format ("done (time {})", t).newline;
    
    Stdout ("Switch search...").flush;
    foreach (x; dIn) {
        mixin (switchSearch ("x", nums));
    }
    t = sw.stop;
    Stdout.format ("done (time {})", t).newline;
    
}
}}}

= Source =
|| Author || Cyborg16 ||
|| Date || March 15, 2008 ||