Когда программисту нечего делать или оптимизируем код при помощи 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.: Ну и да, после того как потешил шаловливые ручки, то посмеялся от души над самой идеей необходимости поиска вообще. Все-таки потому у тела, движущегося по баллистической траектории, скорость хаотически не меняется, а значит надо всего лишь найти коэффициент соответствующий начальной скорости, а потом уныло ползти к началу таблицы, когда скорость падает до следующего диапазона. Но это уже совсем другая, не такая интересная история, о том, чем разработка отличается от кодирования. А так хочется иногда просто покодировать.

    Комментарии 19

      +1

      Чисто из спортивного интереса: любопытно, какое место по производительности заняли бы switch-expressions из девятого C#.

        0
        Кстати да, их же тоже можно в дерево выстроить. Буду обратно у компа — замерю и напишу.
          0

          switch-expressions это сахар для обычного switch и перед компиляцией преобразуется в него

            0

            В сишарпе что классический switch, что новый switch expression, что блок последовательных if + return — абсолютно одно и то же. Байт-код генерируется практически идентичный, производительность абсолютно не отличается.

              +1
              А у Dictionary внутри хеш таблица, или что-то типа дерева?
                0
                массивы
                  +1
                  Ну не линейный же там поиск по ключу в массиве?

                  Я почему спросил — меня несколько смущает намеренный автором результат, что набор if быстрее словаря в полтора раза. Набор if — это скорее всего аналог бинарного поиска. В определенных условиях хеш таблица выигрывает у бинарного поиска (и сильно), в каких-то — проигрывает, но как правило не сильно.

                  Да и вообще, правильно померять быстродействие — дело тонкое, не учесть какой-то фактор — это бывало многократно, у людей с любым уровнем квалификации и опыта.
                    0
                    Конечно там не перебор, но вы ведь спросили что внутри. Внутри два массива. Хэш используется только что бы подсчитать правильный индекс в одном из них.
                      0
                      Сорри, я нечетко сформулировал, конечно имелось в виду, что за поиск там.
                      0
                      правильно померять быстродействие
                      Это правильное замечание, но в данном случае не зря sixsigma. В данном случае за финальными цифрами стоит и планирование эксперимента показывающее что условия измерения соответствуют реальному использованию, и учет размера кванта измерения, и проверка серией запусков с доказательством n-test что отклонение результатов одного запуска от среднеквадратичного значения меньше статистически значимого.

                      Выигрыш хэш таблицы дело вполне себе предсказуемое если знать как она устроена внутри.

                      1) выигрыш по сравнению сложных ключей за счет того что тяжелая операция сравнения заменяется на одноразовое вычисление хеш и серию легких сравнений хеш-значения и вызов тяжелого сравнения значений уже только на небольшую корзину (как правило размер выбирается такой, где линейный поиск оказывается не дольше двоичного дерева, до 6-8 элементов в bucket.

                      2) Ну и поиск в значительных объемах данных — после N > 10000 никаким сокращением одного O преодолеть разницу между 1 условной операцией и пусть логарифмическим, но ростом в другой — нельзя.

                      Но статья не про структуры данных, а про то что возможность динамического создания кода открывает возможность воспользоваться динамической модификацией, реализовав выигрыш, который возникает от набора данных, а не заложен изначально в алгоритм. В данном случае, как я и написал в начале — задача просто оказалась возможностью показать на простом примере, обычно кейсы применения Linq генерации кода куда запутаннее, там только на несколько страниц контекст объяснять пришлось бы.
                        0
                        >Это правильное замечание, но в данном случае не зря sixsigma.
                        Я в общем и не имел в виду, что вы что-то неверно померяли. Просто этот процесс измерения не был тут достаточно подробно описан, а допустить в нем ошибку — ну это вполне типично. Хотя бы — описать данные, на которых меряли, много ли их было или мало.

                        А сам процесс генерации кода из Expression — он без сомнения интересный (хотя такие статьи тут уже и были), и тема в целом неисчерпаемая.
                          0
                          Так вроде первом абзаце, прошу прощения что не акцентировал на этом внимание. 300 значений в таблице, значения вида
                          range (double, double)->drag. Поиск drag по попаданию значения ключа внутрь range.
                            0
                            Ну т.е. таблица — 300 строк?
                              0
                              Да.
                    +1
                    Хеш-таблица, просто они для небольшого ускорения перераспределения по buckets используют не массив массивов как в книжке, а массив entries и массив указателей на позиции buckets.

                    Исходный код можно посмотреть тут
                    github.com/microsoft/referencesource/blob/master/mscorlib/system/collections/generic/dictionary.cs

                    Ваш вопрос в другом комментарии по поводу сравнения хэш-таблицы с двоичным деревом правильный. Но чтобы понять логику надо учесть один момент — у словаря поиск O(1), у дерева O(log2). Это все помнят и знают, но вот что O говорит только о количестве неких попугаев в которых мериться операция, а не о длительность в выраженной в единицах времени — забывают.

                    Собственно на размышления как раз и наводят цифры что по O соотношение количество операций 1 к log2(300) примерно 8, а реальное исполнение всего в 4. Именно более тяжелое O словаря и возможность ускорить O двоичного дерева за счет исключения обращения к памяти и открывают окно возможности для оптимизации здесь.
                0

                Я правильно понял, что заменили поиск по хэш-таблице с линейной памятью (300 элементов) и константным количеством случайного доступа на код линейного объёма (хотя бы 300 ифов) и логарифмическим количеством операций, но как бы без доступа к памяти? И при этом стало сильно быстрее?


                Если да, то это немного удивительно. Возможно, конечно, лучше работает условный branch prediction или кэш для кода больше, чем для данных, или просто так данные уложились компактнее, чем в хэш-таблице.

                  0
                  Я бы не сказал что «сильно», всего в 1.5 раза. Что сравнимо со словарем мы получили структуру легко реализуемую на микроконтроллере.

                  А чем удивительно? Обращение к памяти всегда стоило дорого, по сравнению с теми же самыми операциями, но с аргументами в виде константы с команде. Посмотрите первые две строки в таблице, которые натолкнули меня на мысль — там тоже сравнение совершенно аналогичное, только сравнивается линейный поиск в массиве с линейной же цепочкой if.
                  +2
                  к сожалению, “отладчиком в IDE” по такому коду не походишь

                  Это не совсем так. Если добавить код для сохранения отладочной информации, то становится возможной пошаговая отладка в псевдокоде. Пример кода. Конечно, вручную привязывать выражения к номерам строк — сомнительное удовольствие, но это вполне поддаётся автоматизации. Не так давно появилась библиотека ExpressionDebugger, позволяющая добавить отладку одной строкой кода.

                    0
                    О, спасибо!

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое