using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.Reflection.Emit;
namespace ParserJitting
{
public class Program
{
// a few sample predicates, we will use these in a loop to simulate more of them
private static string[] predicates = {
"fact1",
"fact2",
"fact3",
"fact2 & fact1",
"fact3 & fact2",
"fact4 | fact5",
"!fact4 & fact5",
"!(fact1 & fact2) | !fact5",
};
// it ain't object oriented but it's only a benchmark :)
private static int ichInput = 0;
private static string strInput = null;
private static string strLookaheadToken = null;
private static Dictionary<String, int> dictFacts = new Dictionary<String,int>();
public static bool[] truthTable = null;
static void Main(string[] args)
{
int len = predicates.Length;
int i;
List<BooleanDelegate> compList = new List<BooleanDelegate>();
// compile the predicates
for (i = 0; i< len; i++)
{
compList.Add(CompilePredicate(predicates[i]));
}
BooleanDelegate[] compiledPredicates = compList.ToArray();
truthTable = new bool[dictFacts.Count];
// these few prime numbered facts are in the fact table
// therefore they are "true"
SetFact("fact2");
SetFact("fact3");
SetFact("fact5");
SetFact("fact7");
SetFact("fact11");
SetFact("fact13");
SetFact("fact17");
SetFact("fact19");
// dump some test evaluations so we can be sure things are working ok
for (i = 0; i< len; i++)
Console.WriteLine("{0} => {1}", predicates[i], compiledPredicates[i]());
System.Diagnostics.Stopwatch clock = new System.Diagnostics.Stopwatch();
clock.Start();
// the real benchmark
for (int j = 0; j < 1000000; j++)
for (i = 0; i< len; i++)
compiledPredicates[i]();
clock.Stop();
Console.WriteLine("time {0:n0}ms", clock.ElapsedMilliseconds);
}
// ultra lame exception class, please do better than this in your code :)
class ParseException : Exception
{
public ParseException() : base("Syntax Error")
{
}
}
static int predCount = 0;
static ILGenerator il;
delegate bool BooleanDelegate();
// Compile a simple boolean predicate
static BooleanDelegate CompilePredicate(string predicate)
{
strInput = predicate;
ichInput = 0;
strLookaheadToken = null;
string strName = String.Format("pred{0}", predCount++);
DynamicMethod dm = new DynamicMethod(strName , typeof(bool), new Type[] {}, typeof(Program), true);
il = dm.GetILGenerator();
CompileOr();
il.Emit(OpCodes.Ret);
return (BooleanDelegate)dm.CreateDelegate(typeof(BooleanDelegate));
}
// this starts the recursive descent parser -- or is the outer clause
// the other clauses happen in the natural order (outermost first)
static void CompileOr()
{
CompileAnd();
for (; ;)
{
string s = PeekToken();
if (s == null)
break;
if (s != "|")
break;
ReadToken();
CompileAnd();
il.Emit(OpCodes.Or);
}
}
static void CompileAnd()
{
CompileOptionalNot();
for (; ; )
{
string s = PeekToken();
if (s == null)
break;
if (s != "&")
break;
ReadToken();
CompileOptionalNot();
il.Emit(OpCodes.And);
}
}
static void CompileOptionalNot()
{
bool invert = false;
string s = PeekToken();
while (s == "!")
{
invert = !invert;
ReadToken();
s = PeekToken();
}
CompileFact();
if (invert)
il.Emit(OpCodes.Not);
}
static void CompileFact()
{
string s = ReadToken();
if (s == null)
throw new ParseException();
if (s == "(")
{
CompileOr();
s = ReadToken();
if (s != ")")
throw new ParseException();
}
else
{
string fact = s;
if (fact == null)
throw new ParseException();
int ifact = GetFactNumber(fact);
il.Emit(OpCodes.Ldsfld, typeof(Program).GetField("truthTable"));
il.Emit(OpCodes.Ldc_I4, ifact);
il.Emit(OpCodes.Ldelem_I1);
}
}
// reuse the lookahead if there is one, this consumes a token
static string ReadToken()
{
if (strLookaheadToken == null)
{
PeekToken();
}
string ret = strLookaheadToken;
strLookaheadToken = null;
return ret;
}
// this sets up the lookahead token without actually consuming it
static string PeekToken()
{
// give back the lookahead token again if we already computed it
if (strLookaheadToken != null)
return strLookaheadToken;
strLookaheadToken = GetToken();
return strLookaheadToken;
}
// this reads a token from the input stream and is unaware of lookahead concerns
static string GetToken()
{
if (ichInput >= strInput.Length)
return null;
char ch = '\0';
for (; ; )
{
ch = getc();
if (ch != ' ' && ch != '\t')
break;
}
int idx = ichInput - 1;
if (ch >= 'a' && ch <= 'z' ||
ch >= 'A' && ch <= 'Z' ||
ch == '_')
{
while ('\0' != (ch = getc()))
if (ch >= 'a' && ch <= 'z' ||
ch >= 'A' && ch <= 'Z' ||
ch >= '0' && ch <= '9' ||
ch == '_')
continue;
else
break;
if (ch != '\0') ichInput--;
return strInput.Substring(idx, ichInput - idx);
}
// the single character tokens for valid operators
switch (ch)
{
case '!': case '&': case '|': case '(': case ')':
return strInput.Substring(idx, 1);
}
// error token
return null;
}
// fetch the next character from the input stream
static char getc()
{
if (ichInput >= strInput.Length)
return '\0';
return strInput[ichInput++];
}
// fixed size stack -- we could do better if we needed to but
// this is good enough for this test
static bool[] evalStack = new bool[16];
static int GetFactNumber(string fact)
{
if (!dictFacts.ContainsKey(fact))
dictFacts.Add(fact, dictFacts.Count);
return dictFacts[fact];
}
static void SetFact(string fact)
{
// facts that are mentioned in no predicates may be disregarded
if (!dictFacts.ContainsKey(fact))
return;
truthTable[dictFacts[fact]] = true;
}
}
}
