Note: This website is archived. For up-to-date information about D projects and development, please visit wiki.dlang.org.

Changes from Version 1 of MetaSwitchBench

Show
Ignore:
Author:
Cyborg16 (IP: 82.2.114.66)
Timestamp:
03/15/08 12:57:21 (13 years ago)
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • MetaSwitchBench

    v0 v1  
     1= Switch vs Coded Binary Search = 
     2 
     3This 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. 
     4 
     5Be 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. 
     6 
     7== Benchmarking code == 
     8 
     9{{{ 
     10#!d 
     11/** Test speed of switch (...) statements verse a binary search using if (...) ... else ... 
     12* 
     13* The results speak for themselves, but bear in mind the rather large number of possible cases 
     14* (i.e. vals) in the latter results. 
     15* 
     16* vals is the number of possible values (so number of case statements). 
     17* N is the number of variables to look up the value of. 
     18* 
     19* Result (vals = 0x10, N = 0x1000000): 
     20* 
     21* Init... done (time 0.74) 
     22* Binary search...done (time 1.20) 
     23* Switch search...done (time 1.80) 
     24* 
     25* Result (vals = 0x100, N = 0x1000000): 
     26* 
     27* Init... done (time 0.87) 
     28* Binary search...done (time 1.66) 
     29* Switch search...done (time 4.33) 
     30* 
     31* Result (vals = 0x1000, N = 0x1000000): 
     32* 
     33* Init... done (time 0.78) 
     34* Binary search...done (time 2.08) 
     35* Switch search...done (time 38.99) 
     36*/ 
     37module meta_switchBench; 
     38 
     39import tango.time.StopWatch; 
     40import tango.io.Stdout; 
     41import tango.math.Random; 
     42 
     43const uint vals = 0x100;    // must be no more than type.max+1 
     44alias ubyte type; 
     45 
     46// Simple inefficient int-to-string converter 
     47char[] itoa (uint x) { 
     48    if (x == 0) return "0"; 
     49    else { 
     50        char[] ret; 
     51        while (x > 0) { 
     52            ret = cast(char)((x % 10) + '0') ~ ret; 
     53            x /= 10; 
     54        } 
     55        return ret; 
     56    } 
     57} 
     58 
     59// Generates the "number string" 
     60char[][] genNumbers () { 
     61    char[][] ret; 
     62     
     63    for (ushort i = 0; i < vals; ++i) { 
     64        ret ~= itoa (i); 
     65    } 
     66     
     67    return ret; 
     68} 
     69 
     70// Purely to add indentation. Could just return "" without affecting functionality. 
     71char[] indent (uint i) { 
     72    char[] ret; 
     73    for (; i > 0; --i) ret ~= "  "; 
     74    // This is not executable at compile time: 
     75    //ret.length = i * 4;               // number of characters for each indentation 
     76    //ret[] = ' ';              // character to indent with 
     77    return ret; 
     78} 
     79     
     80/* Generates a binary search algorithm. 
     81* 
     82* Currently this is tailored to it's particular use (switchBench). */ 
     83char[] binarySearch (char[] var, char[][] consts, int indents = 0) { 
     84    if (consts.length > 3) { 
     85        return indent(indents) ~ "if (" ~ var ~ " <= " ~ consts[$/2 - 1] ~ ") {\n" ~ 
     86            binarySearch (var, consts[0 .. $/2], indents + 1) ~ 
     87        indent(indents) ~ "} else {\n" ~ 
     88            binarySearch (var, consts[$/2 .. $], indents + 1) ~ 
     89        indent(indents) ~ "}\n"; 
     90    } else { 
     91        char[] ret; 
     92        ret ~= indent(indents); 
     93        foreach (c; consts) { 
     94            ret ~= "if (" ~ var ~ " == " ~ c ~ ") {\n" ~ 
     95                indent(indents+1) ~ "++dOut["~c~"];\n" ~ 
     96            indent(indents) ~ "} else "; 
     97        } 
     98        ret = ret[0..$-6] ~ '\n';  // remove last else 
     99        return ret; 
     100    } 
     101} 
     102 
     103char[] switchSearch (char[] var, char[][] consts) { 
     104    char[] ret; 
     105     
     106    ret ~= "switch ("~var~") {\n"; 
     107        foreach (c; consts) { 
     108            ret ~= indent(1) ~ "case "~c~":\n"~ 
     109                indent(2) ~ "++dOut["~c~"];\n"~ 
     110            indent(2) ~ "break;\n"; 
     111        } 
     112    ret ~= "}\n"; 
     113     
     114    return ret; 
     115} 
     116 
     117const char[][] nums = genNumbers(); 
     118 
     119void main() { 
     120    const N = 0x1000000; 
     121    type[] dIn = new type[N]; 
     122    ubyte[vals] dOut; 
     123    float t; 
     124     
     125    StopWatch sw; 
     126    Random rand = new Random; 
     127     
     128    Stdout ("Init... ").flush; 
     129    sw.start; 
     130    foreach (inout i; dIn) i = rand.next(vals); 
     131    t = sw.stop; 
     132    Stdout.format ("done (time {})", t).newline; 
     133     
     134    Stdout ("Binary search...").flush; 
     135    foreach (x; dIn) { 
     136        mixin (binarySearch ("x", nums)); 
     137    } 
     138    t = sw.stop; 
     139    Stdout.format ("done (time {})", t).newline; 
     140     
     141    Stdout ("Switch search...").flush; 
     142    foreach (x; dIn) { 
     143        mixin (switchSearch ("x", nums)); 
     144    } 
     145    t = sw.stop; 
     146    Stdout.format ("done (time {})", t).newline; 
     147     
     148} 
     149}}} 
     150 
     151= Source = 
     152|| Author || Cyborg16 || 
     153|| Date || March 15, 2008 ||