Когда программисту нечего делать или оптимизируем код при помощи Linq.Expression

Так сложилось, что активно кодировать мне не удается уже лет пять. Так что каждый шанс залезть в код и напакостить там товарищам воспринимается с радостью, как возможность тряхнуть стариной и убедиться что есть еще “ягоды в ягодицах” (ака шило в жопе). Да, и сразу оговорюсь, что статья скорее туториал, не из серии "смотрите ух как круто я могу", а из серии "о, какой удачный вариант показать на простом примере применение технологии, которая у некоторых коллег вызывает затруднения". Моё глубокое убеждение что подобные решения должны входить в арсенал любого разработчика на C#.

Давеча я ревьювил код, который включает в себя многошаговый процесс аппроксимации, в который активно вовлечено постоянное получение коэффициента (Коэффициент выбирается для диапазона значений. Если кому важны детали - речь идет о моделировании движения тела оживальной формы, без собственного движителя, в атмосфере. А выбор идет из таблицы КСФ Игалла по текущей скорости тела (диапазон скоростей соответствует конкретному КСФ, порядка 300 элементов в таблице). 

Процесс многошаговый, операция поиска выполняется часто, и ребятишки-разработчики были молодцы, пошли даже дальше чем бинарный поиск, реализовали вычисление целочисленного ключа для диапазона значений и получение коэффициента по этому ключу через Dictionary А поскольку команда Agile, а я, гадкий, еще и SixSigma и очень люблю все видеть в цифрах - то ребята убедительно показали эффективность выбранного решения. На 1 расчет из 1000 точек аппроксимации затраты составляют:

Линейный поиск в таблице - 0.6ms
Линейный поиск цепочкой if-return - 0.1ms
Поиск делением пополам - 0.08ms
Поиск словарем - 0.018ms

На стол ко мне это попало в тот момент, когда проект дополз до этапа “а теперь делаем эти же расчеты еще и на микроконтроллере”. Оказалось что с переносом словаря как-то не очень (да, могли бы подумать и заранее, но они в первый раз столкнулись с микроконтроллерами, так что простим им это упущение). 

Спасибо команде, цифры для “думать” они уже посчитали, и я обратил внимание что выигрыш “чистого кода” против поиска в структуре данных - в 6 раз (первые строчки). А экономия словаря против деления пополам - чуть больше 4 раз. 

И тут как раз возник тот самый момент “чешутся ручки”, и совпало два фактора - во-первых, я большой поклонник data-driven архитектур, уже лет 20 как. А во-вторых .NET предоставляет совершенно уникальные средства для построения кода “на лету”. Так почему бы не попробовать построить цепочку операторов if для двоичного поиска из таблицы, и сделать это в виде Linq выражения? А ничего не препятствует, на самом деле. А главное, что та же логика потом хорошо подойдет для того, чтобы просто сгенерить код “табличной” функции для более примитивной архитектуры микроконтроллера. 

Сказано - сделано. Используем всё тоже старое доброе деление пополам исходного массива коэффициентов. Логика простая - если значение попал в диапазон среднего элемента таблицы - возвращаем коэффициент из среднего элемента. Если меньше диапазона - уходим по цепочке if, построенных из левой части таблицы коэффициентов, если больше диапазона - уходим по цепочке if, построенных из правой части таблицы. 

Начнем с оператора if, который проверяет попадание значения в диапазон и возвращает коэффициент, если мы попали. Код очень простой - функция получает параметры range (диапазон), коэффициент, который надо вернуть (value), ссылку на исходное значение (v) и ссылку на точку возврата.  Функция строит, соответственно, три Linq элемента - оператор возврата, условие для if и сам if. Получается аналог конструкции
If (v >= from && v < to) return value;

public Expression CreateSimpleIf(double from, double to, 
                      double value, 
                      Expression v, LabelTarget returnTarget)
{
    var returnStmt = Expression.Return(
      returnTarget, 
      Expression.Constant(value));
    var ifCondition = Expression.AndAlso(
        Expression.GreaterThanOrEqual(v, Expression.Constant(from)), 
        Expression.LessThan(v, Expression.Constant(to)));
    return Expression.IfThen(ifCondition, returnStmt);
}

Теперь построим цепочку операторов для массива диапазонов. Я отдельно обрабатываю ситуации в 1 и 2 элемента, это необязательно, но у меня чисто рефлекс чуть-чуть, но  ускорить код там, где можно. 

На входе нам нужен уже массив диапазаонов, и все те же значение для сравнения и указатель на точку возврата. 

Получается аналог конструкции

If (v >= mid.from && v < mid.to) return mid.value 
If (v < mid.from)
return search in (0...mid-1)
else
return search in (mid + 1...length - 1);

Span используется что бы избежать пересоздания массивов/списков в которых хранятся коэффициенты и/или чтобы не таскать за собой два дополнительных параметра “начало диапазона в таблице для поиска и конец диапазона в таблице для поиска”. 

public Expression CreateSpanExpression(Span<Coefficient> span, 
          Expression v, 
          LabelTarget returnTarget)
{
    if (span.Length == 1)
        return CreateSimpleIf(span[0].RangeFrom, 
                   span[0].RangeTo, 
                   span[0].Value, 
                   v, returnTarget);
    else if (span.Length == 2)
    {
        Expression[] ifs = new Expression[2];
        ifs[0] = CreateSimpleIf(span[0].RangeFrom, 
                   span[0].RangeTo, 
                   span[0].Value, 
                   v, returnTarget);
        ifs[1] = CreateSimpleIf(span[1].RangeFrom, 
                   span[1].RangeTo, 
                   span[1].Value, 
                   v, returnTarget);
        return Expression.Block(ifs);
    }
    else
    {
        int mid = span.Length / 2;
        Expression[] blocks = new Expression[2];
        blocks[0] = CreateSimpleIf(span[mid].RangeFrom, 
                       span[mid].RangeTo, 
                       span[mid].Value, 
                       v, returnTarget);

        var leftSide = 
          CreateSpanExpression(span.Slice(0, mid), 
                               v, returnTarget);
        var rightSide = 
          CreateSpanExpression(span.Slice(mid + 1, 
                               span.Length - mid - 1), 
                               v, returnTarget);

        Expression condition = 
          Expression.LessThan(v, 
                              Expression.Constant(span[mid].RangeFrom));
        blocks[1] = Expression.IfThenElse(condition, leftSide, rightSide);
        return Expression.Block(blocks);
     }
} 

Ну и осталось дело за малым - превратить это в функцию. Надо создать описание параметров, описание типа возвращаемого значения, создать lambda-выражение и скомпилировать все это в исполняемый код. 

public Func<double, double> CreateBTReeExpression()	
{
    var value = Expression.Parameter(typeof(double), "value");
    var returnTarget = Expression.Label(typeof(double));

    var ifs = CreateSpanExpression(mCoefficients.ToArray(), 
                                   value, returnTarget);
    var body = Expression.Block(typeof(double), 
                 new Expression[] 
                 { 
                   ifs, 
                   Expression.Label(returnTarget, 
                     Expression.Constant(0.0))
                 });

    var expression = Expression.Lambda(typeof(Func<double, double>), 
                       body, 
                       new ParameterExpression[] { value });
    var functionDelegate = expression.Compile();
    return (Func<double, double>) functionDelegate;        
}

Ок, проверяем, а стоило ли оно хлопот? По замерам у меня получилось 0.012ms, или в 1.5 раза быстрее использования Dictionary. Ну и плюс появившаяся возможность легко адаптировать код для генерация исходного кода функции для микроконтроллера. 

Главный недостаток этого метода, мешающий его внедрению, состоит в том, что программисту приходится думать “наоборот” - от действия к условию и писать не код, линейно отражающий процесс, который мы автоматизируем, а строить в голове “дерево” операций. Динозаврам типа меня, еще помнящим программирование в обратной польской записи на программируемых микрокалькуляторах и на языке Форт - в принципе привычно, а вот для более продвинутых коллег это может оказаться мозголомным знанием.  

Второй недостаток в том, что, к сожалению, “отладчиком в IDE” по такому коду не походишь, а значит надо возвращаться к старым добрым методам отладки по снятию контрольных показателей и сравнению с ожидаемым эталоном. 

Это сильно ограничивает популярность такого подхода, но, как мне кажется, он всё равно стоит внимания, все-таки выгоды по производительности в некоторых ситуациях, как в приведенной задаче, которая, увы, даже не может быть распараллелена в силу природы алгоритма (следующий шаг сильно зависит от того, что насчитали раньше). И для таких задач вопрос повышения производительности решается все теми же “старыми, добрыми методам”.  

Ну и лично я считаю это не недостатками, а скорее достоинствами – в итоге, не смотря на затраты времени, такие упражнения повышают эффективность команды и способность её решать новые и необычные задачи. Но навязывать это как silver bullet я конечно не решусь.

p.s. Ну и да, после того как потешил шаловливые ручки, то посмеялся от души над самой идеей необходимости поиска вообще. Все-таки потому у тела, движущегося по баллистической траектории, скорость хаотически не меняется, а значит надо всего лишь найти коэффициент соответствующий начальной скорости, а потом уныло ползти к началу таблицы, когда скорость падает до следующего диапазона. Но это уже совсем другая, не такая интересная история, о том, чем разработка отличается от кодирования. А так хочется иногда просто покодировать. :-)