/*
Idea from:
http://www.reddit.com/r/programming/comments/asqml/whats_the_difference_between_if_else_and_switch/
Perfect hash computed with:
http://www.ibiblio.org/pub/Linux/devel/lang/c/mph-1.2.tar.gz
Constants:
NDATA=10_000, NLOOPS=4_000, random seed=10
Compiled with:
LDC based on DMD v1.051 and llvm 2.6 (Fri Nov 27 12:54:12 2009)
ldc -O3 -release -inline
dmd -O -release -inline
Timings, ldc, seconds:
test1: 4.48
test2: 2.98
test3: 2.09
test4: 2.07
test5: 5.44 // Tango AA opIn_r is bug-slow
Timings, dmd, seconds:
test1: 5.55
test2: 5.35
test3: 4.73
test4: 4.79
test5: 3.61
*/
version (Tango) {
import tango.stdc.stdio: printf;
import tango.stdc.stdlib: rand, srand;
} else {
import std.c.stdio: printf;
import std.c.stdlib: rand, srand;
}
int test1(char[][] strings) {
int result;
foreach (txt; strings) {
switch (txt) {
case "__alignof": result += 1; break; // do something
case "__alignof__": result += 2; break;
case "__asm": result += 3; break;
case "__asm__": result += 4; break;
case "__attribute": result += 5; break;
case "__attribute__": result += 6; break;
case "__const": result += 7; break;
case "__const__": result += 8; break;
case "__inline": result += 9; break;
case "__inline__": result += 10; break;
case "__signed": result += 11; break;
case "__signed__": result += 12; break;
case "__typeof": result += 13; break;
case "__typeof__": result += 14; break;
case "__volatile": result += 15; break;
case "__volatile__": result += 16; break;
case "all": result += 17; break;
case "asm": result += 18; break;
case "auto": result += 19; break;
case "break": result += 20; break;
case "case": result += 21; break;
case "catch": result += 22; break;
case "char": result += 23; break;
case "class": result += 24; break;
case "const": result += 25; break;
case "continue": result += 26; break;
case "default": result += 27; break;
case "delete": result += 28; break;
case "do": result += 29; break;
case "double": result += 30; break;
case "dynamic": result += 31; break;
case "else": result += 32; break;
case "enum": result += 33; break;
case "except": result += 34; break;
case "exception": result += 35; break;
case "extern": result += 36; break;
case "float": result += 37; break;
case "for": result += 38; break;
case "friend": result += 39; break;
case "goto": result += 40; break;
case "if": result += 41; break;
case "inline": result += 42; break;
case "int": result += 43; break;
case "long": result += 44; break;
case "new": result += 45; break;
case "operator": result += 46; break;
case "overload": result += 47; break;
case "private": result += 48; break;
case "protected": result += 49; break;
case "public": result += 50; break;
case "raise": result += 51; break;
case "raises": result += 52; break;
case "register": result += 53; break;
case "reraise": result += 54; break;
case "return": result += 55; break;
case "short": result += 56; break;
case "signed": result += 57; break;
case "sizeof": result += 58; break;
case "static": result += 59; break;
case "struct": result += 60; break;
case "switch": result += 61; break;
case "this": result += 62; break;
case "try": result += 63; break;
case "typedef": result += 64; break;
case "typeof": result += 65; break;
case "union": result += 66; break;
case "unsigned": result += 67; break;
case "virtual": result += 68; break;
case "void": result += 69; break;
case "volatile": result += 70; break;
case "while": result += 71; break;
default: result += 72; break;
}
}
return result;
}
int perfectHash(char[] key) {
static const int[] g = [56, 11, 41, 15, 43, 41, 37, 46, -1, 27,
41, 39, 28, 26, 70, 59, 32, 4, 45, 59,
21, 58, 12, 30, 47, -1, 63, 70, 33, 66,
31, 0, 8, -1, 49, 47, 62, 39, 34, 24,
-1, 21, 64, 40, 37, 2, 34, 12, 1, 44,
9, 60, 8, 0, 36, 52, 37, 25, 23, 37,
52, 65, 28, 57, 32, 65, 38, 33, 50, 45,
66, 66, -1, 31, 57, 61, 12, 0, 45, 0];
static const int[] T0 = [38, 67, 16, 59, 2, 14, 3, 16, 32, 46,
76, 33, 30, 65, 29, 4, 1, 35, 39, 18,
28, 67, 9, 38, 67, 7, 70, 26];
static const int[] T1 = [74, 33, 4, 1, 46, 32, 15, 32, 71, 58,
70, 19, 28, 15, 31, 13, 11, 6, 79, 32,
39, 47, 44, 6, 73, 16, 49, 29];
uint f0, f1;
if (key.length < 2 || key.length > 13)
return -1;
foreach (c; key) {
if (c < 95 || c > 122)
return -1;
f0 += T0[-95 + c];
f1 += T1[-95 + c];
}
f0 %= 80;
f1 %= 80;
return (g[f0] + g[f1]) % 71;
}
int test2(char[][] strings) {
int result;
foreach (txt; strings) {
switch (perfectHash(txt)) {
case perfectHash("__alignof"): // compile-time run!
if (txt == "__alignof") result += 1; // do something
else goto default; // hash collision with wrong string
break;
case perfectHash("__alignof__"):
if (txt == "__alignof__") result += 2;
else goto default;
break;
case perfectHash("__asm"):
if (txt == "__asm") result += 3;
else goto default;
break;
case perfectHash("__asm__"):
if (txt == "__asm__") result += 4;
else goto default;
break;
case perfectHash("__attribute"):
if (txt == "__attribute") result += 5;
else goto default;
break;
case perfectHash("__attribute__"):
if (txt == "__attribute__") result += 6;
else goto default;
break;
case perfectHash("__const"):
if (txt == "__const") result += 7;
else goto default;
break;
case perfectHash("__const__"):
if (txt == "__const__") result += 8;
else goto default;
break;
case perfectHash("__inline"):
if (txt == "__inline") result += 9;
else goto default;
break;
case perfectHash("__inline__"):
if (txt == "__inline__") result += 10;
else goto default;
break;
case perfectHash("__signed"):
if (txt == "__signed") result += 11;
else goto default;
break;
case perfectHash("__signed__"):
if (txt == "__signed__") result += 12;
else goto default;
break;
case perfectHash("__typeof"):
if (txt == "__typeof") result += 13;
else goto default;
break;
case perfectHash("__typeof__"):
if (txt == "__typeof__") result += 14;
else goto default;
break;
case perfectHash("__volatile"):
if (txt == "__volatile") result += 15;
else goto default;
break;
case perfectHash("__volatile__"):
if (txt == "__volatile__") result += 16;
else goto default;
break;
case perfectHash("all"):
if (txt == "all") result += 17;
else goto default;
break;
case perfectHash("asm"):
if (txt == "asm") result += 18;
else goto default;
break;
case perfectHash("auto"):
if (txt == "auto") result += 19;
else goto default;
break;
case perfectHash("break"):
if (txt == "break") result += 20;
else goto default;
break;
case perfectHash("case"):
if (txt == "case") result += 21;
else goto default;
break;
case perfectHash("catch"):
if (txt == "catch") result += 22;
else goto default;
break;
case perfectHash("char"):
if (txt == "char") result += 23;
else goto default;
break;
case perfectHash("class"):
if (txt == "class") result += 24;
else goto default;
break;
case perfectHash("const"):
if (txt == "const") result += 25;
else goto default;
break;
case perfectHash("continue"):
if (txt == "continue") result += 26;
else goto default;
break;
case perfectHash("default"):
if (txt == "default") result += 27;
else goto default;
break;
case perfectHash("delete"):
if (txt == "delete") result += 28;
else goto default;
break;
case perfectHash("do"):
if (txt == "do") result += 29;
else goto default;
break;
case perfectHash("double"):
if (txt == "double") result += 30;
else goto default;
break;
case perfectHash("dynamic"):
if (txt == "dynamic") result += 31;
else goto default;
break;
case perfectHash("else"):
if (txt == "else") result += 32;
else goto default;
break;
case perfectHash("enum"):
if (txt == "enum") result += 33;
else goto default;
break;
case perfectHash("except"):
if (txt == "except") result += 34;
else goto default;
break;
case perfectHash("exception"):
if (txt == "exception") result += 35;
else goto default;
break;
case perfectHash("extern"):
if (txt == "extern") result += 36;
else goto default;
break;
case perfectHash("float"):
if (txt == "float") result += 37;
else goto default;
break;
case perfectHash("for"):
if (txt == "for") result += 38;
else goto default;
break;
case perfectHash("friend"):
if (txt == "friend") result += 39;
else goto default;
break;
case perfectHash("goto"):
if (txt == "goto") result += 40;
else goto default;
break;
case perfectHash("if"):
if (txt == "if") result += 41;
else goto default;
break;
case perfectHash("inline"):
if (txt == "inline") result += 42;
else goto default;
break;
case perfectHash("int"):
if (txt == "int") result += 43;
else goto default;
break;
case perfectHash("long"):
if (txt == "long") result += 44;
else goto default;
break;
case perfectHash("new"):
if (txt == "new") result += 45;
else goto default;
break;
case perfectHash("operator"):
if (txt == "operator") result += 46;
else goto default;
break;
case perfectHash("overload"):
if (txt == "overload") result += 47;
else goto default;
break;
case perfectHash("private"):
if (txt == "private") result += 48;
else goto default;
break;
case perfectHash("protected"):
if (txt == "protected") result += 49;
else goto default;
break;
case perfectHash("public"):
if (txt == "public") result += 50;
else goto default;
break;
case perfectHash("raise"):
if (txt == "raise") result += 51;
else goto default;
break;
case perfectHash("raises"):
if (txt == "raises") result += 52;
else goto default;
break;
case perfectHash("register"):
if (txt == "register") result += 53;
else goto default;
break;
case perfectHash("reraise"):
if (txt == "reraise") result += 54;
else goto default;
break;
case perfectHash("return"):
if (txt == "return") result += 55;
else goto default;
break;
case perfectHash("short"):
if (txt == "short") result += 56;
else goto default;
break;
case perfectHash("signed"):
if (txt == "signed") result += 57;
else goto default;
break;
case perfectHash("sizeof"):
if (txt == "sizeof") result += 58;
else goto default;
break;
case perfectHash("static"):
if (txt == "static") result += 59;
else goto default;
break;
case perfectHash("struct"):
if (txt == "struct") result += 60;
else goto default;
break;
case perfectHash("switch"):
if (txt == "switch") result += 61;
else goto default;
break;
case perfectHash("this"):
if (txt == "this") result += 62;
else goto default;
break;
case perfectHash("try"):
if (txt == "try") result += 63;
else goto default;
break;
case perfectHash("typedef"):
if (txt == "typedef") result += 64;
else goto default;
break;
case perfectHash("typeof"):
if (txt == "typeof") result += 65;
else goto default;
break;
case perfectHash("union"):
if (txt == "union") result += 66;
else goto default;
break;
case perfectHash("unsigned"):
if (txt == "unsigned") result += 67;
else goto default;
break;
case perfectHash("virtual"):
if (txt == "virtual") result += 68;
else goto default;
break;
case perfectHash("void"):
if (txt == "void") result += 69;
else goto default;
break;
case perfectHash("volatile"):
if (txt == "volatile") result += 70;
else goto default;
break;
case perfectHash("while"):
if (txt == "while") result += 71;
else goto default;
break;
default:
result += 72;
}
}
return result;
}
const char[][] keywords = [
// right keywords
"__alignof", "__alignof__", "__asm", "__asm__", "__attribute",
"__attribute__", "__const", "__const__", "__inline", "__inline__",
"__signed", "__signed__", "__typeof", "__typeof__", "__volatile",
"__volatile__", "all", "asm", "auto", "break", "case", "catch",
"char", "class", "const", "continue", "default", "delete", "do",
"double", "dynamic", "else", "enum", "except", "exception",
"extern", "float", "for", "friend", "goto", "if", "inline", "int",
"long", "new", "operator", "overload", "private", "protected",
"public", "raise", "raises", "register", "reraise", "return",
"short", "signed", "sizeof", "static", "struct", "switch", "this",
"try", "typedef", "typeof", "union", "unsigned", "virtual", "void",
"volatile", "while"
];
int test3(char[][] strings) {
static const int[] map = [72,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
62, 63, 64, 65, 66, 67, 68, 69, 70, 71];
int result;
foreach (txt; strings) {
int h = perfectHash(txt);
if (h != -1 && txt == keywords[h])
result += map[h + 1];
else
result += map[0]; // default
}
return result;
}
int test4(char[][] strings) {
int result;
foreach (txt; strings) {
int h = perfectHash(txt);
if (h != -1 && txt == keywords[h])
result += h + 1;
else
result += 72; // default
}
return result;
}
int[char[]] keymap;
static this() {
foreach (i, key; keywords)
keymap[key] = i + 1;
keymap.rehash;
}
int test5(char[][] strings) {
int result;
foreach (txt; strings) {
int* p = txt in keymap;
if (p != null)
result += *p;
else
result += 72; // default
}
return result;
}
void main() {
const int NDATA = 10_000;
const int NLOOPS = 4_000;
const int USE_ALGO = 1;
srand(10);
const char[][] words = [
// right keywords
"__alignof", "__alignof__", "__asm", "__asm__", "__attribute",
"__attribute__", "__const", "__const__", "__inline", "__inline__",
"__signed", "__signed__", "__typeof", "__typeof__", "__volatile",
"__volatile__", "all", "asm", "auto", "break", "case", "catch",
"char", "class", "const", "continue", "default", "delete", "do",
"double", "dynamic", "else", "enum", "except", "exception",
"extern", "float", "for", "friend", "goto", "if", "inline", "int",
"long", "new", "operator", "overload", "private", "protected",
"public", "raise", "raises", "register", "reraise", "return",
"short", "signed", "sizeof", "static", "struct", "switch", "this",
"try", "typedef", "typeof", "union", "unsigned", "virtual", "void",
"volatile", "while",
// wrong keywords
"the", "of", "and", "a", "to", "in", "is", "you", "that", "it",
"he", "was", "for", "on", "are", "as", "with", "his", "they", "I ",
"at", "be", "this", "have", "from", "or", "one", "had", "by",
]; // std.string.split() not used here to use the C std lib only
// generate test data
char[][] testData = new char[][](NDATA);
foreach (ref word; testData)
word = words[rand() % words.length];
int tot;
for (int i; i < NLOOPS; i++) {
static if (USE_ALGO == 1) tot += test1(testData);
static if (USE_ALGO == 2) tot += test2(testData);
static if (USE_ALGO == 3) tot += test3(testData);
static if (USE_ALGO == 4) tot += test4(testData);
static if (USE_ALGO == 5) tot += test5(testData);
}
printf("%d\n", tot);
}