Маленький словарь #скорость #память

Часто бывает, что мы получаем данные из внешнего источника или БД, создаём временный словарь, ищем по нему, а потом про него забываем. Часто бывает, что приходящих данных мало, например, 10-15 элементов.

При этом, многие помнят, что поиск по словарю при небольшом количестве элементов не всегда эффективен (поиск по массиву будет быстрее). Также, те коллеги, которые помнят устройство Dictionary, могут вспомнить, что эта структура данных имеет два внутренних массива, выделение которых на горячих направлениях кода может вызвать неплохой memory pressure. Например, создание одного словаря размером в 10 элементов - почти 1кб памяти.

В принципе, решение задачи лежит на поверхности.

Необходимо создать такую структуру данных, которая бы с самого начала хранила данные в массиве, а, в случае большого количества элементов, переходила на честный словарь, чтобы избежать потерь производительности. Также, было бы неплохо переиспользовать массив и сам словарь, так как представляется, что сценарий "заполнили, поискали и бросили/материализовали во что-то другое" весьма распространён.

Я набросал небольшой пример, который проще прочитать, чем пояснять. Из интересного там только Enumerator, который хранит сразу два Enumerator'a для разных случаев (массив и словарь). Не реализовано удаление, на которое у меня просто не хватило времени, и специальные методы для превращения в ToDictionary, ToList, ToArray - их можно написать эффективнее, чем те, которые есть в классе Enumerable. Но, я думаю, что это не проблема для тех, кто понял концепцию.

Сам бенчмарк охватывает сценарий, который описан выше: создаём словарь, ищем ключи, используем словарь для linq операции. В моём примере, возвращение переиспользуемого массива и словаря реализовано через Dispose, который нужно не забывать вызывать, либо просто использовать using.

Как видно из прикреплённой картинки, прирост производительности для количества элементов меньше 20 что-то около 20%. Ну и zero-allocation, конечно. Почему при 50 элементах всё равно существует опережение по скорости - я оставлю на самостоятельное исследование. Не исключена банальная ошибка.

Сезон кода в Нижнем Новгороде

Отвыступал на "Сезоне кода" (организатор Т-Банк). Я давно не ходил на конференции, давно не выступал. Мне очень понравилось. Хорошие темы, интересные спикеры.

Участники конференции задавали много вопросов, затем обсуждение переместилось в кулуары. Это всегда очень здорово и приятно - побеседовать с коллегами, которые давно в теме доклада, которые смотрят на твои проблемы под другим углом, имеют свой опыт, свои решения. Супер.

Ещё из плюсов конференции: трёхразовое питание, много активностей (от решений задач до карьерных консультаций) и афтерпати. Огромные экраны, просторный зал, отличная акустика и звук. Ух! Жаль, что не будет записей докладов - я бы хотел посидеть над некоторыми вдумчиво.

Спасибо организаторам!

Презентация тут.

Unsafe.SkipInit для структур #скорость

Как раз на конференции, в кулуарах, спрашивали про Unsafe.SkipInit. Набросал бенчмарк, который будет в комментариях.

Как я уже говорил, это решение следующей проблемы:
1. Выделяется память.
2. Эта память заполняется дефолтными значениями (чтобы программист не получил в значениях полей структуры явную тарабарщину от предыдущих пользователей памяти). Условно 0000000000.
3. Память, в виде структуры, отдаётся пользователю (программисту). В классическом варианте, программист получит в числовом поле 0 (deafult), а в ссылочном - null.

Вот Unsafe.SkipInit говорит, мол, господин рантайм, я и сам заполню все значения. Ну или, в смысле доклада, я и сам знаю какая область памяти мне нужна как инициализированная. То есть п.2 не выполняется. Что заметно улучшает скорость. Документация тут, там есть интересные примеры.

Кстати, обратите внимание на разницу в .NET 8 и .NET 9.
Коллеги работают!

P.S.: Про массивы читать тут.

Function pointer #скорость

Представим, что у нас есть подсистема вычисления. Один класс отвечает за выбор операции над значениями, а другой производит магию вычисления с использованием выбранной операции. В каждом из классов какая-то сложная логика, поэтому объединить их нельзя или сложно.

Пример: операции над формулами в Excel - до того как мы прочитаем формулу, мы не знаем, какая операция будет произведена над ячейками.

Условно, это выглядит вот так:

MathOperation operation = SelectOperation(Context);

Func<int, int, int> executor = operation switch {
   MathOperation.Add => MathOperations.Add,
   MathOperation.Subtract => MathOperations.Subtract,
   MathOperation.Multiply => MathOperations.Multiply,
   MathOperation.Divide => MathOperations.Divide,
   _ => Error.NotSupported(operation, Context)
};

Calculator.Execute(executor, xValue, yValue);

Это работает быстро, но, благодаря "современному" C# (function pointer'ы появились аж 5 лет назад), подобные сценарии можно ускорить на 10-15%. Для этого нужно уйти в лёгкий unsafe, и заменить Func<int, int, int> на delegate*<int, int, int>. Мотивацию появления этого улучшения можно подсмотреть тут.

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

Для библиотечного кода такой unsafe весьма оправдан (так как даёт хороший буст производительности). В случае обычного энтерпрайз-кода я бы такое не использовал никогда.

Бенчмарк тут, чтобы каждый мог убедиться, что мы действительно получаем профит.

P.S.: Коллега напоминает, что ещё function pointer удобен для работы с библиотекам на других технологиях.

Надо тренироваться #отдых

Приехали фото с конференции. Я что-то толстоват. Поэтому понял, что надо усилить тренировки. Я хожу на спорт уже полгода и мне очень нравится: чистит мозги, рабочий перформанс лучше.

Это перекликается с песней моего детства о пиратах из "Остров сокровищ", где говорилось, что в здоровом теле - здоровее дух. Ну и вообще, Джим молодец, потому что утром делает зарядку.

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

Если кто из Нижнего Новгорода, сходите к Денису - он крутой тренер. Не жестит, осторожно и грамотно подходит к тренировкам, мотивирует. Особенно круто, что он всегда рядом, а не уходит в самом начале, сказав программу на сегодня. Следит, бьёт направляет, подсказывает. А ещё с ним очень весело. Самое главное для меня, ему не пофиг, он действительно делает меня лучше.

P.S.: Не реклама. Денис действительно классный.
P.P.S.: Некий Сергей напоминает, что надо сходить ко врачу перед тренировками. Я целиком его поддерживаю!

Dictionary.TryGetValue #скорость

Уж сколько лет прошло и, вроде, все это знают. Но, тем не менее, периодически на собеседование приходит человек, который пишет не оптимальный код извлечения значения из словаря. Я увидел, что я про это не писал, поэтому напомню ещё раз это элементарное правило.

Коллеги, если у нас есть сценарий: проверить существование ключа в Dictionary и извлечь соответствующее ему значение, то не надо делать ContainsKey, а потом извлекать значение. В словаре есть прекрасный метод TryGetValue, который проверяет наличие ключа и, если он есть, тут же, не отходя от кассы, извлекает значение. Это быстрее примерно на 20-30%.

А почему использование TryGetValue быстрее? Ведь поиск в Dictionary это O(1), типа очень быстро. Но надо вспомнить, что O(1) это алгоритмическая сложность, не абсолютные цифры. Это про то и только про то, что скорость поиска не зависит от количества элементов. Алгоритмическая сложность не про прыжки по памяти и не про исполнение кода на процессоре.

Когда же мы пишем код, мы именно про процессор и про память. Заставлять компьютер проделывать действия по поиску ключа дважды - терять скорость. Это понимают даже современные IDE, которые, когда видят паттерн ContainsKey + dic[key], предлагают перейти на TryGetValue, так как это оптимальнее.

Бенчмарк в комментариях. Результаты на Linux любезно представил коллега.

P.S.: По просьбам коллег добавил сравнений с другими методами, которые похожи на TryGetValue (то есть выполняются в одно действие).

Latency numbers every programmer should know

Я всё время теряю эти циферки, особенно когда они нужны в процессе ожесточённой беседы про производительность. Забываю ключевые слова для поиска, нахожу не те картинки.

А ведь эти циферки очень полезны для всех, кто так или иначе интересуется производительностью. Эти цифры и картинка иллюстрируют, что, например, поход в БД значительно более приоритетная цель для оптимизаций, чем, например, замена List на Dictionary. Или что сеть может съесть все перформансные улучшения, связанные с переходом на struct и Span.

Не забывайте про эти цифры, когда исследуете проблемы с производительностью. Смотрите на то, что реально тратит время (или память).

Взял отсюда, а ссылаются ещё вот сюда.

P.S.: Сами цифры вызывают вопросы, но в том, что их отношение друг к другу примерно такое - сомнений нет.
P.P.S: Коллега ещё напоминает о стоимости операций.

L1 cache reference ...................... 0.5 ns
Branch mispredict ......................... 5 ns
L2 cache reference ........................ 7 ns
Mutex lock/unlock ........................ 25 ns
Main memory reference ................... 100 ns             
Syscall on Intel 5150 ................... 105 ns
Compress 1K bytes with Zippy .......... 3,000 ns 
Context switch on Intel 5150 .......... 4,300 ns 
Send 2K bytes over 1 Gbps network .... 20,000 ns  
SSD random read ..................... 150,000 ns  
Read 1 MB sequentially from memory .. 250,000 ns  
Round trip within same datacenter ... 500,000 ns  
Read 1 MB sequentially from SSD* .. 1,000,000 ns
Disk seek ........................ 10,000,000 ns
Read 1 MB sequentially from disk . 20,000,000 ns  
Send packet CA->Netherlands->CA . 150,000,000 ns

UnsafeAccessor #скорость

Иногда возникает странное желание изменять приватные поля в классах, код которых нам не доступен. Например, внутренний массив коллекции или настройку, которая почему-то и, по нашей логике, возмутительно не выставлена наружу.

В этом, не самом здоровом желании, нам, конечно, поможет reflection. Код будет тривиальный, что-то вроде typeof(Entry).GetField(...) . Этот код найдёт поле в типе и вернёт нам его объектное представление.

Особо упорные ребята могут делать подобную операцию каждый вызов метода, но это крайне не оптимально на горячих участках кода. Более умные коллеги выполнят поиск поля один раз, положат его в статическую переменную и будут получать значение через fieldInfo.GetValue(_entry), а задавать через fieldInfo.SetValue(_entry, value).

Те, кто читал про ExpressionTree, вполне резонно будут получать и задавать значение через заранее сформированные делегаты: для получения будет что-то вроде Expression.Lambda<Func<Entry, int>>(fieldExpression, getterParameters).Compile(), а для записи - Expression.Lambda<Action<Entry, int>>(Expression.Assign(fieldExpression, valueParameter), setterParameters).Compile(). Этот подход значительно быстрее (раз эдак в 20) и, на моей практике, довольно часто используется.

Однако, современный .NET 8+ может предложить ещё более быстрое решение - UnsafeAccessorAttribute. Код его использования лаконичнее и проще:

private static class Accessor {
   [UnsafeAccessor(UnsafeAccessorKind.Field, Name = FieldName)]
   public static extern ref int GetFieldValue(Entry entry);
}

Как мы можем заметить, доступ осуществляется через метод с ключевым словом extern, которое чаще всего ассоциируется с использованием кода внешних библиотек на других языках программирования. В данном же случае, при аннотации extern-метода с помощью UnsafeAccessor, поиск будет происходить в сборках нашего приложения.

Сигнатура проста. UnsafeAccessorKind указывает, какой тип члена класса мы ищем (поле, метод, конструктор). Имя говорит... про имя члена класса. Ну а первый аргумент метода - в каком типе мы ищем.

Использование этого подхода примерно в 2 раза быстрее, чем с помощью ExpressionTree. В том числе за счёт того, что мы можем получить ref на поле, что, в свою очередь, означает, что мы можем менять его по ссылке и с минимальными накладными расходами. Если у вас современный .NET и существует жгучее желание по новому взглянуть на чудеса а-ля Reflection, я бы хорошенько присмотрелся к UnsafeAccessor'у. Его скорость работы сильно впечатляет. Хотя, конечно, он имеет известные ограничения.

Прочитать больше и подробнее можно у Эндрю Лока.

P.S.: Код и результаты бенчмарка в комментариях. В этом посте много кода, а ТГ, при вставлении картинки, делает сообщение узким.

FastEnum #скорость

Иногда нам нужно не просто быстро, а очень быстро. В этот момент в дело вступают самые необычные оптимизации. Например, оптимизация работы с enum. Типичный сценарий - получить строку из enum'a или, наоборот, enum из строки.

Многие знают, что получение строкового представления enum'a лучше делать через Enum.GetName(MyEnum.Value), а вариант MyEnum.Value.ToString() аллоцирует новую строку и несколько медленнее.

В случае сложной логики получения строкового представления enum'a, чаще всего используется кэш (который, кстати, есть в Enum.GetName). Для этой цели можно написать свой класс, который содержит два словаря. В случае получения строки из enum'a мы идём по одному словарю, а в случае получения enum'a из строки - по другому. Код примерно такой:

private static readonly FrozenDictionary<string, T> StringToValues;
private static readonly FrozenDictionary<T, string> ValuesToString;

static EnumUtils() {
   var enums = Enum.GetValues<T>();
   StringToValues = enums.ToFrozenDictionary(...);
   ValuesToString = enums.ToFrozenDictionary();
}

public static string ToString(T value) {
   return ValuesToString.TryGetValue(value, out var stringValue)
      ? stringValue
      : Throw<string>($"Value '{value}' is not defined");
}

Конечно, никакого ноу-хау тут нет, и для таких оптимизаций уже существует несколько готовых библиотек. Одна из них - FastEnum. Она показывает значительный прирост скорости не только по сравнению с обычными способами работы с enum в .NET (почти в два раза), но и по сравнению с другими подобными библиотеками: от Эндрю Лока и Enums.NET. FastEnum и библиотека от Эндрю Лока используют source generators.

Мне не очень нравится тащить в код лишние зависимости, поэтому, чаще всего, я использую самописный кэш для ускорения работы с enum. Тем более, в нём можно сделать дополнительную логику, специфичную для конкретного проекта. И, в любом случае, я рекомендую присмотреться к этим библиотекам. Они маленькие и понятные, а подходы, которые там используются, могут пригодиться в повседневной работе.

Картинка бенчмарка тут.
Сам бенчмарк тут.