У нас есть решение - обработчик 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
