Производительность вычисления формул

У нас есть решение - обработчик OLAP-запросов, для которого критичная скорость преобразования и загрузки данных в хранилище и вычисление формул в MDX-запросах. Достоверно известно ("британские ученые доказали"), что в типовом сценарии на вычисления уходит 90% времени процессора. Это и есть проблема.

Итак, исходная реализация: предварительно разбираем выражение и строим синтаксическое дерево (AST, но в своей объектной модели). Далее при выполнении кода просто просим дерево посчитать значение выражения для текущего контекста выполнения (контекст включает текущую строку данных и область видимости блоков агрегации данных, например в матричной группировке).

Варианты решения

Первая попытка решения - вместо собственного AST формируем функцию вычисления значения, аргументом которой является контекст. Например есть выражение:

(GetRecordValue(ctx,2) * 1024 + GetRecordValue(ctx,3))/3600/(Max(1, GetRecordValue(ctx,4))

Код построения функции даже проще кода построения AST. К сожалению, на каждом этапе построения функции приходится формировать лямбда функцию с аргументом контекста, что приводит к следующей результирующей функции:

ctx5 => (ctx4 => (ctx3 => (ctx2 => (ctx => 
    GetRecordValue(ctx,2))(ctx2) * (ctx => 1024)(ctx2))(ctx3)
    + (ctx2 => (ctx => GetRecordValue(ctx,2))(ctx2))(ctx3))(ctx4) / (ctx4 => 3600))(ctx5)
  / (ctx2 => Max(ctx2 => 1, (ctx => GetRecordValue(ctx,4)(ctx2)))(ctx5)

Кроме того, для каждой лямбда функции (точнее для ее замыкания) создается класс. Несмотря на это, результат - примерно двукратный рост скорости - хорош, но недостаточно. Хотелось чтобы скорость выполнения была такая же как и для кода написанного на C#.

Выражения, появившиеся в .NET 3.5 - это аналог исходного решения, но если метод Compile использует IL Emit, можно ожидать существенно лучший результат.

Для проверки решения на практике реализуем два парсера - первый возвращает лямбда-функцию вычисления, второй - Expression.

NParsec

Проще всего сделать парсер с помощью библиотеки NParsec (последовательный порт parsec => jparsec => nparsec).

Обобщенный код парсера занимает примерно 30 строк наглядного кода:

private static Parser<T> CreateParser<T>(Func<string, T> getVar,
 IDictionary<char,Map<T,T,T>> binaryOps, Map<string,T> parseValue, Map<T,T> unaryMinus)
{
 var patCharExt = Patterns.IsChar(Char.IsLetter).Or(Patterns.IsChar('_'));
 var patVar = patCharExt.Seq(Patterns.InRange('0', '9').Or(patCharExt).Many());
 var scannerVar = Scanners.IsPattern(patVar, "var");

 var lexerVal = Lexers.Lex(scannerVar, Tokenizers.ForString);

 var operators = Terms.GetOperatorsInstance("+", "-", "*", "/", "(", ")", "^");
 var ignored = Scanners.IsWhitespaces().Many_();
 var lexeme = Lexers.Lexeme(ignored, operators.Lexer | Lexers.LexDecimal() | lexerVal).FollowedBy(Parsers.Eof());

 var pPlus = GetOperator(operators, "+", binaryOps['+']);
 var pMinus = GetOperator(operators, "-", binaryOps['-']);
 var pMul = GetOperator(operators, "*", binaryOps['*']);
 var pDiv = GetOperator(operators, "/", binaryOps['/']);
 var pPower = GetOperator(operators, "^", binaryOps['^']);
 var pNeg = GetOperator(operators, "-", unaryMinus);
 var pVar = Terms.OnString((@from, len, data) => getVar(data));

 var pNumber = Terms.OnDecimal((_, __, s) => parseValue(s));
 var lazyExpr = new Parser<T>[1];
 var pLazyExpr = Parsers.Lazy(() => lazyExpr[0]);
 var pTerm = pLazyExpr.Between(operators.GetParser("("), operators.GetParser(")")) | pNumber | pVar;
 var optable = new OperatorTable<T>()
  .Infixl(pPlus, 10).Infixl(pMinus, 10)
  .Infixl(pMul, 20).Infixl(pDiv, 20)
  .Infixl(pPower, 25).Prefix(pNeg, 30);
 var pExpr = Expressions.BuildExpressionParser(pTerm, optable);
 lazyExpr[0] = pExpr;
 return Parsers.ParseTokens(lexeme, pExpr.FollowedBy(Parsers.Eof()), "calculator");
}

private static Parser<T> GetOperator<T>(Terms ops, string op, T v)
{
 return ops.GetParser(op).Seq(Parsers.Return(v));
}

Парсеры для лямбда-функций и Expressions на основе обобщенного парсера выглядят как:

private static Parser<Func<double>> CreateLambdaParser(Func<string, Func<double>> getVar)
{
 var binaryOps = new Dictionary<char, Map<Func<double>, Func<double>, Func<double>>>
  {
   {'+', (a, b) => () => a() + b()},
   {'/', (a, b) => () => a()/b()},
   {'-', (a, b) => () => a() - b()},
   {'*', (a, b) => () => a()*b()},
   {'^', (a, b) => () => Math.Pow(a(), b())}
  };
 Map<Func<double>, Func<double>> unaryMinus = v => () => -v();
 Map<string, Func<double>> parseDouble = s =>
  {
   var v = double.Parse(s);
   return () => v;
  };

 return CreateParser(getVar, binaryOps, parseDouble, unaryMinus);
}

private static Parser<Expression> CreateExpressionParser(Func<string, Expression> getVar)
{
 var binaryOps = new Dictionary<char, Map<Expression, Expression, Expression>>
  {
   {'+', Expression.Add},
   {'/', Expression.Divide},
   {'-', Expression.Subtract},
   {'*', Expression.Multiply},
   {'^', (a,b) => Expression.Call(typeof(Math).GetMethod("Pow"), a, b)}
  };
 Map<string, Expression> parseDouble = s => Expression.Constant(double.Parse(s));

 return CreateParser(getVar, binaryOps, parseDouble, Expression.Negate);
}

Ну и собственно:

Результаты замера производительности

Для замера скорости подойдет полином 20-й степени вида ((a1+1)*a2+1)*a3 + 1... Результат - примерно 200 кратное превосходство Expression - 120 секунд против 600 мс. Результат подозрительный, но причина в том что переменные a1..a20 - это по сути константы, так как компилятор выражений, обнаружив что в правой части выражения стоит константа, вероятно подставил значения в AST и произвел оптимизацию.

Для получения достоверного результата я заменил константу на вызов функции и получил вполне достоверный результат 5.58c для лямбда-функций против 1.17с для выражений. А при включенной оптимизации компилятора C# - 2.27с против 0.26с. В результате имеем 10-кратный выигрыш при соизмеримой сложности кода.

Исходный код и тесты доступны по в репозитарии на bitbucket