О бедном LINQ’е замолвите слово

Все свое недлинное бытие в роли c# программиста я считал, что LINQ — это в первую очередь не про производительность кода, а про производительность программиста, как быстро он пишет код, а не как быстро сей код выполняет процессор. А проблемы с производительностью и кода и программиста, решаются после выявления «узких» мест. Посему, я часто пишу var groupedByDate = lst.GroupBy(item => item.IssueTime.Date).Select(…).ToList() и делаю так не из-за вредности или злого умысла, а просто так легче отлаживать код. Для списка достаточно поместить курсор мыши на текст переменной и сразу видно есть ли там что-то или нет.


Начало


После прочтения статьи «Неудачная статья про ускорение рефлексии» и утихания эмоций по поводу «в интернете кто-то не прав», я задался вопросом, а можно сделать «LINQ to Objects» код близким по производительности к «ручному». Почему именно «LINQ to Objects»? В своей работе я часто использую только поставщики «LINQ to Objects» и «LINQ to Entities». Производительность «LINQ to Entities», для меня не критична; критично насколько оптимальным для целевого сервера БД будет сгенерированный SQL-запрос и как быстро его выполнит сервер.


За основу я решил использовать проект автора статьи. В отличии от примеров из интернета, где в основном сравнивается код наподобие integerList.Where(item => item > 5).Sum() с «ручным» кодом, содержащим foreach, if и так далее, пример из статьи показался мне интересным и жизненным.


Первое что было мной сделано — это использование единой функции сравнения строк. В коде-первоисточнике, в методах выполняющих одну и ту же функцию, но находящихся в противоположных углах ринга, используются разные способы, в одном случае variable0.Equals(constant0, StringComparison.InvariantCultureIgnoreCase), а в другом variable0.ToUpperInvariant() ==constant0.ToUpperInvariant(). Особенно обидно за константу, которую переводят в верхний регистр каждый вызов метода. Я выбрал третий вариант с использованием в обеих случаях variable0.ToUpperInvariant() ==constant0InUpperCaseInvariant.


Далее был «выкинут» весь код, который напрямую не связан со сравнением производительности LINQ и «ручного» кода. Первым под горячую руку попался код, создающий и инициализирующий объект класса Mock<HabraDbContext>. Какой смысл создавать соединения с БД для каждого теста, один раз достаточно? Он был вынесен за рамки тестов производительности.


IStorage _db;

[GlobalSetup]
public void Setup()
{
    _db = MockHelper.InstanceDb();
}

private IStorage DBInstance => _db;

Для проформы запустился модифицированный тест… И — о, чудо! Метод с суффиксом Linq занимает первое место во всех «весовых» категориях!


image


Малюсенький червячок сомнения «а может все таки в интернете кто-то не прав» отправился к праотцам. Реноме LINQ восстановлено. Новые тесты можно не писать, но рубикон перейден — продолжаем.


Цели меняются


Было решено написать свой тест производительности с нуля, перенеся туда только самое необходимое, непосредственно относящееся к противостоянию LINQ vs «ручной» код. Подробно описывать процесс написания теста не имеет смысла. Далее следуют наиболее интересные с моей точки зрения моменты. Ссылка на код будет приведена ниже.


Мне показалось, что для данного теста неудобно использовать среднеквадратическое отклонение для оценки разброса результатов, принимая во внимание, что средние величины отличаются на порядок для каждой категории ([Params(1, 10, 100, 1000)]). Захотелось увидеть колонку с коэффициентами вариации. С наскоку не удалось найти способ как добавить ее в отчет. Поиск в интернете так же не дал ответа. Был написан свой класс StatisticColumnRelStdDev.


Теперь перейдем непосредственно к задаче — переписать код класса FastHydrationLinq, так что бы его производительность приблизилась к ManualHydrationLinq — победителю исправленного теста из статьи. Как видно, цель статьи изменилась, вместо (Fast)(Manual)(Slow)HydrationLinq vs (Fast)(Manual)(Slow)Hydration, целью стала задача потягаться со скоростью исполнения ManualHydrationLinq. Тест FastHydrationLinq был выбран из-за его префикса в названии. Он просто обязан быть быстрым.


Оптимизация этого теста в основном свелась к избавлению от вызовов методов ToArray, ToDictionary и использованию универсальных шаблонов IEnumerable<T> в качестве типов возвращаемых значений различных методов. Незамысловатым путем копирования, был создан новый класс FastContactHydrator2. В нем был изменен тип хранилища списка пар ключ-объект класса Action<Contact, string> c ConcurrentDictionary<string, Action<Contact, string>> на IEnumerable<KeyValuePair<string, Action<Contact, string>>>. Был добавлен метод GetContact2, где вызов метода Sum, в завершении вызывает всю цепочку отложенных операций.


protected override Contact GetContact2(IEnumerable<PropertyToValueCorrelation> correlations)
{
    var contact = new Contact();
    int dummySum = _propertySettersArray.Join(correlations, propItem => propItem.Key, corrItem => corrItem.PropertyName, (prop, corr) => { prop.Value(contact, corr.Value); return 1; }).Sum();
    return contact;
}

Метод ParseWithLinq был переписан как


public static IEnumerable<KeyValuePair<string, string>> ParseWithLinq2(string rawData, string keyValueDelimiter = ":", string pairDelimiter = ";")
    => rawData.Split(pairDelimiter)
    .Select(x => x.Split(keyValueDelimiter, StringSplitOptions.RemoveEmptyEntries))
    .Select(x => x.Length == 2 ? new KeyValuePair<string, string>(x[0].Trim(), x[1].Trim())
                                : new KeyValuePair<string, string>(_unrecognizedKey, x[0].Trim()));

Вот и вся оптимизация.


В время разработки кода класса FastContactHydrator2, в оригинальных тестах автора статьи, находились места, которые выглядели не логичными или не нужными в контексте цели моего теста и в общем, как например использование словаря как хранилища пар ключ-значение, но поиск происходит полным перебором (функции ParseWithLinq и ParseWithoutLinq). В этих местах словарь был заменен на список. В другом месте удален не нужный, в моем тесте, вызов метода ToArray. Так же было удалено магическое число 10 в коде var result = new List<PropertyToValueCorrelation>(10). Почему 10? Число 42 я бы понял, а вот 10 не могу. Так появилась серия тестов имеющих постфикс Fair в названии.


Еще пара слов об общих изменениях. Типы хранилищ исходных данных были приведены к массивам в обеих случаях. Данные возвращаемые методом GetFakeData расширены новыми ключевыми словами. Так сделано преднамеренно, что бы увеличить объем исходных данных.
Скомпилированный исполняемый файл был запущен несколько раз, и для анализа были взяты результаты тестов, которые имеют наименьший разброс значений в колонке «Коэффициент Вариации» (RelStdDev). Ими оказались тесты для N=1000.


Краткая аннотация к таблице ниже:


- Строки `ManualHydration`, `SlowHydration`, `FastHydration`, `ManualHydrationLinq`, `SlowHydrationLinq`, `FastHydrationLinq` - это тесты из первоначальной статьи, без изменений;

  • Строки ManualHydrationFair, ManualHydrationFairLinq, FastHydrationFairLinq — это тесты из первоначальной статьи, из которых удалены нелогичности и ненужности;
  • Строка FastHydrationLinq2 — моя версия быстрого теста с использованием отложенного исполнения, которые, по-моему мнению, должны помочь компилятору произвести наиболее быстрый код для LINQ;
  • Колонка N имеет такое же назначение, что и в оригинальной статье;
  • Колонка Ratio показывает отношение времени исполнения теста в строке к времени исполнения FastHydrationLinq2.

image
Linq-тесты в первых рядах


И что мы видим? Цель достигнута — тест FastHydrationLinq2 имеет паритет с ManualHydrationLinq в колонке Ratio. Абсолютное время исполнения 26,361.37 μs и 26,422.17 μs соответственно для N=1000. Оба теста делят третье/четверное место при всех значениях N. Абсолютным победителем стал тест ManualHydrationFairLinq, его производительность на 8% лучше, чем у теста ради которого и затеялась статья. Второе место занимает тест FastHydrationFairLinq, он выполняется примерно на 1% быстрее теста-протагониста.


Пару слов про производительность оптимизированных Fair-тестов. Как уже было указано выше, тест ManualHydrationFairLinq на 8% быстрее его не оптимизированного собрата. А FastHydrationFairLinq выигрывает у FastHydrationLinq 12%. Тесты без суффикса Linq занимают почетные три места в подвале таблицы.


Вот вроде бы и сказке конец, но постойте. Автор статьи упоминал о сборщике мусора и его отрицательное влияние на производительность. Оглядываясь назад видно, что я оптимизировал оригинальный тест путем переноса вызова метода MockHelper.InstanceDb() в метод Setup, а так же не перенес его в свой тест. Хотя этот вызов можно удалить и в оригинальном тесте — результат его исполнения нигде не используется, а данные для тестов генерируются методом GetFakeData, он все таки планомерно вызывается для каждого теста. Складывается впечатление, что единственная его цель — сгенерировать в памяти мусор. Что ж добавим MockHelper.InstanceDb() и в мой тест.


К колонке с заголовком N, добавилась колонка MakeGarbage. Для значений False мусор в памяти не генерируется, True — мусор должен присутствовать в изрядном количестве.


image
Сборщик мусора принялся за дело


Полная версия таблицы для всех значений N

image


Voilà, кроме размеров таблицы с результатами ничего удивительного, в тестах с мусором места разделились точно так же как и без него. Единственное значимое изменение — уменьшение разницы времени исполнения между самым быстрым и самым медленным тестами для N=1. Эта разница составляет 10% для тестов с мусором и 82% для тестов без него.


Выводы… Выводы будут немного позже.


В погоне за неуловимым Джо


После приведения моего исходного кода в опрятный вид, например были удалены тесты отдельных функций, или методы расположены в порядке «ручной» тест — Linq-тест, я запустил исполняемый файл и получил результаты похожие на результаты из оригинальной статьи:


image
Для N=1 и MakeGarbage=True на первое место выходят «ручные» тесты


Я очень обрадовался, наконец то забрезжил лучик надежды, что удастся разобраться, с изменениями производительности LINQ при присутствии мусора в памяти.
Значения колонок «Gen X» и «Allocated» для N=1 и MakeGarbage=True в двух предыдущих таблицах примернo одинаковы, для теста FastHydrationLinq2 это


|                                |      Gen 0 |   Gen 1 | Gen 2 |   Allocated |
|«Ручные» методы на первом месте |    20.5078 |  0.4883 |     - |    63.95 KB |
|Linq-методы на первом месте     |    20.7520 |       - |     - |    63.69 KB |

Эти же значения для теста ManualHydrationFairLinq полностью одинаковые.


Количество выделенной памяти и количество вызовов сборщика мусора примерно одинаковы в обеих ситуациях. Не знаю верно ли это в действительности, но мое мнение, что в подобных случаях сборщик мусора должен влиять на производительность также — примерно одинаково.
Так что же так влияет на производительность одинакового кода, с одинаковыми объемами выделенной памяти и прочее? Под подозрение пал порядок вызова тестов. Для скорости выполнения, я исправляю аттрибут для N как [Params(1, 100)] и MakeGargabe=True. Начинаю пробовать различные комбинации «ручной» — Linq-код, все они давали результаты схожие с результатами на изображении выше. Опробовались различные вариации — сначала вызываются все ручные методы, второй вариант — сначала вызываются все Linq-методы, далее была комбинация Linq — Ручной — Ручной — Linq. Все без изменений — ручные тесты впереди. Значит источник проблемы не в порядке вызова.


На следующее утро, я запускаю тот же исполняемый файл для сокращенного теста, и вижу стандартную картину — Linq-тесты снова лидеры. На колу мочало, начинай сначала. Под подозрение падает запущенная программа работы с графическими изображениями paint.net, в которой я подготавливал изображения для статьи. Несколько запусков тестов с запущенным параллельно paint.net и без него — есть стойкая корреляция между тестом на первом месте и фактом нахождения paint.net в оперативной памяти. Запущен paint.net — «ручной» тест впереди, не запущен — Linq-тест впереди планеты всей.


Возвращаю тест в исходное состояние — значения N варьируются как 1, 10, 100, 1000 и переменной MakeGarbage возвращается атрибут [ParamsAllValues]. Запускаю paint.net, запускаю тест — «ручной» метод впереди. Запускаю тест еще три раза — теперь Linq-метод на первом месте. В дополнение к paint.net запускаю Visual Studio — «ручные» тесты снова на коне. Тут мне стало жалко своего времени, каждый прогон всех 80-и тестов занимает больше получаса. Пусть Джо остается неуловимым, тем более разница между самым быстрым ручным тестом и самым быстрым Linq-тестом около 2%.


Выводы


После написания тестов и анализа результатов, мое мнение о LINQ не изменилось — используя его моя производительность в написании кода выше, чем без него; с производительностью «LINQ to Objects» все в порядке. Использование отложенного исполнения LINQ-кода, как средства повышения производительности, не имеет особого смысла.


Если в каком-то проекте существуют проблемы с производительностью из-за сборщика мусора — родовой травмы .net, то вероятно выбор этой технологии был не лучшим решением.


Код моих тестов доступен здесь.

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

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

    0
    Может для CRUD и формочек разницы нет, но в разработке фреймворков и алгоритмов Linq однозначно нет. К примеру, можете заоптимизировать такой код?

    Некоторый код
    	[Config(typeof(BenchmarkConfig))]
    	public class Benchmark
    	{
    		readonly int[] Values = Enumerable.Range(0, 5000).Select(i => i).ToArray();
    		const int OuterCount = 1000;
    
    		[Benchmark]
    		public int LinqBench()
    		{
    			var value = 0;
    			
    			for (var i = 0; i < OuterCount; i++)
    				value |= Values.Where(j => j % 2 == 0).Sum();
    
    			return value;
    		}
    
    		[Benchmark]
    		public int ForBench()
    		{
    			var value = 0;
    
    			for (var i = 0; i < OuterCount; i++)
    			{
    				var sum = 0;
    
    				foreach (var val in Values)
    					if (val % 2 == 0)
    						sum += val;
    
    				value |= sum;
    			}
    
    			return value;
    		}
    	}
    


    Результат бенчмарка
    BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18362.836 (1903/May2019Update/19H1)
    Intel Core i7-5820K CPU 3.30GHz (Broadwell), 1 CPU, 12 logical and 6 physical cores
    .NET Core SDK=3.1.300
    [Host]: .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT
    MediumRun: .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT

    Job=MediumRun BuildConfiguration=Release Toolchain=.NET Core 3.1
    IterationCount=15 LaunchCount=2 WarmupCount=10

    | Method | Mean | Error | StdDev |
    |---------- |----------:|----------:|----------:|
    | LinqBench | 22.458 ms | 0.0325 ms | 0.0476 ms |
    | ForBench | 3.865 ms | 0.0186 ms | 0.0273 ms |


      +1
      но в разработке фреймворков и алгоритмов Linq однозначно нет

      Про "алгоритмы" не знаю (хотя правильно примененный LINQ не обязательно меняет алгоритмическую сложность), а вот во фреймворках — да пожалуйста, сколько угодно. Главное, понимать, зачем.

        0
        Дело не в алгоритмической сложности, она же как раз не меняется, дело в лишних телодвижениях, которые тянет Linq (лишние вызовы методов, аллокации), в примере сверху разница на элементарной операции в ~6 раз. Фреймворки разные бывают, возможно в каких-нибудь вспомогательных функциях и используется, но точно не performance-critical (а в статье тег 'Высокая производительность'). Где-нибудь в ядре asp.net core или roslyn Linq врядли используется хоть в одном методе, который десятки тысяч раз в секунду выполняется. Понимать зачем, конечно, надо.
          0

          Я наблюдаю некоторую разницу между утверждениями "в разработке фреймворков [...] Linq однозначно нет" и "Фреймворки разные бывают [...] но точно не performance-critical"


          Где-нибудь в ядре asp.net core или roslyn Linq врядли используется хоть в одном методе, который десятки тысяч раз в секунду выполняется.

          И много таких методов в среднестатистическом фреймворке? А так-то в asp.net Core больше тысячи упоминаний System.Linq (да, я вижу, что многие из них — в тестах и билдере).

            0
            Согласен, разница в утверждениях есть, я потому мысль свою уточнил. Упоминания System.Linq в roslyn и asp.net core я тоже смотрел, там где Linq не влияет на производительность он используется, что и логично. Но вы же не станете спорить, что Linq добавляет некоторый overhead, и если в ядре какого-нибудь фреймворка метод выполняться будет сотни миллионов раз, и написание + пары строк для простого цикла сэкономит хотя бы 1% производительности, то можно пожертвовать выразительностью?
              0
              Но вы же не станете спорить, что Linq добавляет некоторый overhead

              Не буду. Абстракции вообще обычно добавляют оверхед.


              если в ядре какого-нибудь фреймворка метод выполняться будет сотни миллионов раз, и написание + пары строк для простого цикла сэкономит хотя бы 1% производительности, то можно пожертвовать выразительностью?

              Если. Сколько раз типичный программист сталкивается с подобными методами за свою карьеру?

                0
                Я не знаю про типичных программистов, может они и фреймворки, типа asp.net core, не разрабатывают. В любом случае, нужно просто правильно выбирать инструмент для решения задачи, а не топить за Linq добро/зло и разоблачающие статьи на эту тему писать.
                  0
                  В любом случае, нужно просто правильно выбирать инструмент для решения задачи, а не топить за Linq добро/зло и разоблачающие статьи на эту тему писать.

                  Ну так чтобы правильно выбирать инструмент, нужно понимать, где он добро. А не писать вещи типа "в разработке фреймворков [...] однозначно нет".

                    0
                    Вы придрались к одной фразе, которую я уже пояснил и согласился, что она слишком категорична. Как бы больше нет причины продолжать спор по этому поводу.
        +1
        Но это-же нечестно, оптимизатор просто выкидывает вложенный цикл из второго бенчмарка, давайте хотя-бы так, уже не так однозначно получается:
        Заголовок спойлера
        		[Benchmark]
        		public int LinqBench()
        		{
        			var value = 0;
        
        			for (var i = 1; i < OuterCount; i++)
        			{
        				value |= Values.Where(j => j % i == 0).Sum();
        			}
        
        			return value;
        		}
        
        		[Benchmark]
        		public int ForBench()
        		{
        			var value = 0;
        
        			for (var i = 1; i < OuterCount; i++)
        			{
        				var sum = 0;
        
        				foreach (var val in Values)
        					if (val % i == 0)
        						sum += val;
        
        				value |= sum;
        			}
        
        			return value;
        		}
        



        BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.836 (1909/November2018Update/19H2)
        Intel Core i7-9750H CPU 2.60GHz, 1 CPU, 12 logical and 6 physical cores
        .NET Core SDK=3.1.202
        [Host]: .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT
        DefaultJob: .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT

        | Method | Mean | Error | StdDev |
        |---------- |---------:|---------:|---------:|
        | LinqBench | 17.81 ms | 0.350 ms | 0.535 ms |
        | ForBench | 13.34 ms | 0.261 ms | 0.268 ms |
          +1
          Я, если честно, не смотрел asm код, но на каком основании оптимизатор должен был выкинуть вложенный цикл? Он эвристически в момент компиляции вычислил, что на каждой итерации внешнего цикла результат вложенного будет одинаковым и битовое 'или' также даст одинаковый результат? Он так не имеет права сделать, может я в другом потоке этот массив параллельно изменяю. В вашем примере просто операция вычисления остатка от деления на произвольное число сильнее нагрузило процессор, чем остаток от деления на 2, потому и накладные расходы Linq на этом фоне кажутся меньше. Замените в своём примере 'j % i == 0' на '(j+i) % 2 == 0', если так хотите, чтобы i участвовала. На моём компьютере 26 мс против 4мс. В любом случае, вы уже изменили алгоритм, а не оптимизировали, мне нужен был именно результат 1-го варианта, а не другой алгоритм.
            0
            Да, действительно, был не прав, (j+i) % 2 опять показывает большой отрыв.
            Первый вариант слишком легко оптимизировать, достаточно сделать два последовательных цикла вместо вложенных, но это уже никакого отношения к linq vs обычный цикл не имеет.
            На самом деле в данном случае цикл выигрывает у linq варианта потому, что обращается к элементам массива по индексу, что значительно быстрее, чем итератор. Если тип у Values будет какой-нибудь IReadOnlyCollection, результаты сравняются и linq даже может чуточку выигрывать.
            Первый вариант на моей машине, поменял тип на IReadOnlyCollection:

            | Method | Mean | Error | StdDev |
            |---------- |---------:|---------:|---------:|
            | LinqBench | 23.65 ms | 0.465 ms | 0.886 ms |
            | ForBench | 25.52 ms | 0.474 ms | 0.633 ms |

            Так что если к вам данные приходят в виде IEnumerable, IReadOnlyCollection или еще в чем-то, где нельзя обратиться по индексу, то отказываться от linq нет особого смысла.
              0
              Я не призываю отказываться от Linq, мне он нравится и я им пользуюсь. Но нужно понимать, что он тоже имеет свою цену.
        0
        Оффтоп:
        Посему, я часто пишу
        Первый абзац
          0
          Спасибо, интересная статься!
            0
            Сколько не писал, в 99% случаев оптимизировать приходится процедуры и функции БД, на C# как бы ты оптимально код не написал, как правило ничего не меняет, за исключением редких случаев, если в БД бардак — а чаще именно там основные проблемы.

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

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