Changes from Version 1 of MetaSwitchBench

Author:

Cyborg16 (IP: 82.2.114.66)

Timestamp:

03/15/08 12:57:21 (16 years ago)

Comment:

--

MetaSwitchBench

@@ +1 @@
+= 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 ||