ByReferenceTypeComparer #скорость

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

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

Таким образом, если у нас есть Dictionary<Type, ???>, то мы можем ускорить его работу на 20-30%, просто передав ему сравниватель, который будет проверять равенство по ссылке, а hash брать из заголовка типа.

private sealed class ByReferenceComparer<T> : IEqualityComparer<T>
    where T : class
{
    public static readonly IEqualityComparer<T> Instance = new ByReferenceComparer<T>();

    private ByReferenceComparer()
    {
    }

    public bool Equals(T? x, T? y) => ReferenceEquals(x, y);

    public int GetHashCode(T obj) => RuntimeHelpers.GetHashCode(obj);
}

Бенчмарк в комментариях.
Запуск на MacBook.

P.S.: Если кого-то волнует, работает ли подобный подход в сценарии, когда мы создаём тип "налету" (а-ля typeof(List<>).MakeGenericType(typeof(int))), то да, так тоже работает.

P.P.S.: Остаётся открытым вопрос, почему так не делают в .net по-умолчанию. Скорее всего, есть какой-то нюанс, который я упускаю (напр., тут). Возможно, мы вместе найдём на него ответ. Предположительный ответ.

Аллокация объектов на стеке #память

Наверное, многие слышали, что .NET 9 теперь старается не размещать короткоживущие объекты в куче, если они являются boxed value-типами. Теперь результат "боксинга" таких типов располагается на стеке, что позволяет разгрузить GC и увеличить производительность.

Конечно же, есть "но". Дело в том, что runtime должен быть уверен, что результат боксинга не выходит за границы метода. В этом и только в этом случае, результат боксинга value-типа (фактически object) будет располагаться на стеке. Это очень похоже на Rust, где есть встроенная в язык функция наблюдения за временем жизни переменной. Выход из метода "удаляет" все сущности, которые были созданы внутри него, но не используются вне него.

В примере ниже, как и раньше до .NET 9, произойдёт боксинг цифр "3" и "4" при вызове метода Compare. Однако runtime (JIT) "видит", что эти объекты не выходят за пределы метода RunIt. Следовательно, результат боксинга можно разместить на стеке.

static bool Compare(object? x, object? y)
{
    if (x == null || y == null)
    {
        return x == y;
    }

    return x.Equals(y);
}

public static int RunIt()
{
    bool result = Compare(3, 4);
    return result ? 0 : 100;
}

Понимание механики работы этой оптимизации важно, так как, например, позволяет решить проблему следующего кода:

var result = 0;
foreach ((int a, int b) in _values)
{
    result += Compare(a, b) ? 1 : -1;
}
return result;

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

Есть и иное предположение. Оно основано на том, что функция Compare принимает, условно, всё, что угодно. Это, в свою очередь, значит, что JIT справедливо полагает: размер данных в аргументах функции может быть разным на любой итерации for. А это означает, что невозможно вызывать Compare с уравниванием всех возможных типов аргументов по размеру (см. вот этот комментарий).

Кажется, что решение очевидно: нам нужно создать промежуточный метод, который будет определять типы (для понимания размера) и границы создаваемых временных переменных. Некий контекст, который подскажет JIT'у, что боксинг временный и нужен только на одну итерацию for.

bool CloseContext(int a, int b) => Compare(a, b);

Но, увы, это не сработает, так как в дело включается другая оптимизация - method inlining. Для JIT'a этот метод - прекрасный случай для автоматического инлайнинга. Увы, это ломает нашу прекрасную идею с обозначением контекста, в рамках которого будут жить наши boxed value-типы.

Значит, мы должны не только создать отдельный метод, но и прямо указать, что делать ему "инлайн" не нужно. Благо, у нас есть специальный атрибут для подобных указаний - [MethodImpl(MethodImplOptions.NoInlining)]. В этом случае, боксинг происходит, но его результат остаётся на стеке. Результаты хорошо видны на бенчмарке.

Код бенчмарка тут. Если нужно больше подробностей, то я написал этот пост под впечатлениями вот отсюда.

Dictionary.AlternateLookup #память #скорость

Несколько лет назад я устраивался в компанию, которая дала тестовое задание. Его суть - показать максимальную скорость и минимальную аллокацию при обработке большого объема данных. Что-то вроде "посчитать количество слов в документе" (я упрощаю).

Одна из основных проблем в подобной задаче - поиск ключа (слова) в большом словаре Dictionary<string, int> и инкремент значения (количества). В то время мне пришлось взять код обычного Dictionary и модернизировать его так, чтобы он принимал ReadOnlySpan<char> в качестве ключа - так я пытался не аллоцировать строки, которые уже существуют в словаре. Инкремент был выполнен в стиле современного CollectionsMarshal.GetValueRefOrAddDefault. Решение коллегам понравилась и меня взяли на работу.

В современном .NET 9 эта задача решается максимально просто, так как нам предоставили прекрасный метод словаря GetAlternateLookup, возвращающий специальную структуру, которая может принимать в качестве ключа то, что сам программист считает сравнимым с ключом словаря.

var dic = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
var lookup = dic.GetAlternateLookup<ReadOnlySpan<char>>();

foreach (ReadOnlySpan<char> word in wordCollection)
{
    CollectionsMarshal.GetValueRefOrAddDefault(lookup, word, out _)++;
}

В данном примере, сравнение ReadonlySpan<char> с типом string возможно потому, что у StringComparer существует реализация интерфейса IAlternateEqualityComparer<ReadOnlySpan<char>, string>. Если ознакомиться с его кодом, то мы видим, что этот интерфейс требует не только реализовать операции сравнения, но и метод создания string из ReadOnlySpan<char>. Таким образом, lookup имеет возможность не только сравнивать значения ключа, но и, в случае его отсутствия, создавать в словаре запись с этим ключом.

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

Чтение из БД: Dapper, Linq2Db, EF #хранилище

Недавно в соседнем канале я наткнулся на обсуждение скорости работы ORM. Естественно, разговор крутился вокруг Dapper, Linq2Db и EntityFramework (EF, EF Core). Заявлялось, что библиотека Linq2db не только удобна как EF, но и быстра, как Dapper. Это меня удивило, так как в моём мировоззрении скорость Dapper достижима только при отказе от удобства уровня EF и при написании чистого SQL (хотя, возможно, кому-то нравится писать запросы руками).

Я взял классическую задачу - есть блоги, у блогов есть посты. Я развернул базу данных PostgreSQL в Docker, добавил в неё 100 блогов по 200 постов. Код с использованием EF я написал быстро, с Linq2Db пришлось немного сложнее, но помогла документация, а вот Dapper дался сильно не сразу - именно поэтому по нему два бенчмарка.

Замечу, что я замерял только чтение (SELECT). Измерения скорости добавления и удаления я, возможно, произведу позже.

Тем более, что результаты чтения меня удивили, так как Linq2Db работает очень эффективно. При этом код, который необходимо написать для получения блогов и их постов, подозрительно краток и лаконичен. Ещё более меня удивило то, что скорость близка к Dapper (замер с двумя запросами) и немного выше, чем у рекомендованного для данного случая QueryAsync<Blog, Post, Blog> с маппингом и splitOn.

Мой фаворит, по результатам замеров - Linq2Db, который весьма неплохо справляется с чтением данных из БД, при этом код устойчив к изменениям и прост, в отличии от того же Dapper. EF традиционно отстаёт, но проигрывает не сильно. При выполнении SQL-запросов через метод FromSqlRaw EF показывает впечатляющие результаты, не очень сильно отставая от Dapper.

Пока готовил бенчмарки, с ужасом осознал, что "готовить" EF я более-менее могу, а вот с Dapper и Linq2Db у меня сложности. Поэтому, если уважаемые читатели заметят какие-либо проблемы с кодом и его оптимальностью, я буду счастлив. Дело в том, что этим бенчмарком я получил неожиданные для себя результаты. Хотелось бы вернуть мир на место.

Кода много, поэтому он тут. Я думаю, что интересующимся не составит труда самостоятельно поднять PG в Docker'e и наполнить БД данными через миграцию в EF.

P.S.: Бенчи Ef_ToArray и Ef_ToList отдельно рассмотрены тут. То, что их результаты разные в данном измерении - скорее всего погрешность измерителя. Они должны быть плюс-минус одинаковыми.

EF: ToArray vs ToList #отдых

Бился в соседнем канале на тему поста выше. Появилось интересное предположение, что в EF лучше материализовать коллекции через ToList, так как ToArray имеет следующий код:

public static async Task<TSource[]> ToArrayAsync<TSource>(
        this IQueryable<TSource> source,
        CancellationToken cancellationToken = default)
        => (await source.ToListAsync(cancellationToken).ConfigureAwait(false)).ToArray();

То есть в самом начале выполняется ToList, а потом, из уже созданного списка, выполняется ToArray. Программирование подсказывает нам, что будет создано две коллекции, одна из которых - лишняя.

Но на бенчмарке этого не заметно: скорость выполнения и аллокация почти идентичные. Как так получается и где программирование сломалось - загадка.

Бенч (сравнение ToList, ToArray) в комментах. Бенч из предыдущего поста, но на ToList, тут. Как и предполагалось скорость и аллокация одинаковые. Но почему?

Предполагаю, что его размер просто потерялся при 100 блогах и 200 постах. Если сделать один блог и один пост, и написать материализацию через AsAsyncEnumerable, то вроде как его видно (разница 0.3 КБ, но она есть). Другое объяснение, что всё оптимизировали настолько, что просто магия.

Новый params #скорость #память

Как многие знают, начиная с .NET 9 (C# 13) появилась возможность по новому взглянуть на ключевое слово params. Напомню, что это ключевое слово позволяет программисту указывать несколько аргументов метода одного типа через запятую, которые, в самом методе, будут представлены в виде коллекции. Ранее этой коллекцией мог быть только массив. Теперь это может быть ReadOnlySpan, Span, List и даже IEnumerable.

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

Начиная с .NET 9 (C# 13) компилятор делает это сам.

Результаты хорошие - решение с params ReadOnlySpan<T> значительно быстрее, чем params T[] и, к тому же, вообще не аллцирует память в куче. См. скриншот.

Бенчмарк в комментариях.

P.S.: Для особо пытливых, которые хотят понять, а почему есть разница между ReadOnlySpan и Span, я рекомендую посмотреть low-level C# (в Rider, например). В первом случае используется RuntimeHelpers.CreateSpan, а во втором случае создаётся InlineArray размером в количество элементов (про него я писал тут).

Случайная строка из 12 символов #отдых

Недавно я снова упражнялся с роботами (LLM, GPT). Мне сказали, что они стали значительно умнее за последние 6 месяцев. Действительно, беседы на темы, где я не специалист выглядели весьма убедительно. Роботы стали предлагать более умные решения, исправляться и уточнять, если меня что-то не устраивает, признавать ошибки и предлагать альтернативные варианты.

При этом, конечно, в областях, где я специалист, всё по прежнему не очень радужно. Так, простая задача по созданию случайной строки (random string) всё ещё решается в стиле "посмотреть на stackoverflow и предложить самый популярный вариант". Роботы прямо предлагали решения из вот этой вот темы.

const string chars = "чарики";
return new string(Enumerable
    .Repeat(chars, length)
    .Select(s => s[random.Next(s.Length)])
  .ToArray());

Это решение мягко говоря сомнительное и не оптимальное (см. Linq в результатах бенчмарка). Я уже встречался с таким лет 10 назад, когда stackoverflow-junior-программист предлагал подобный код. Впрочем, немного побеседовав с роботом, я таки получил предложение использовать современное решение на основе метода Random.GetItems.

Далее я попробовал узнать, а какое решение по созданию строки является криптостойким в .NET. Ответ был из всё той же темы на stackoverflow, мол, используй RNGCryptoServiceProvider. Я удивился, так как этот класс указан в документации как obsolete аж с .NET 6. Я указал на это роботу, после чего получил вполне вменяемый и современный совет по использованию RandomNumberGenerator.

В принципе, общение меня обрадовало. Теперь робот не бездумно настаивает на своём решении, а пытается предложить варианты и альтернативы, если предложенное им решение в чём-то не нравится пользователю. Это успех. С удовольствием продолжу наблюдать за роботами.

Также, я воспользовался случаем и написал бенчмарк о том, какое решение по созданию строки более оптимально для случаев строки в 12 символов, так это ограничение одного из методов (Path.GetRandomFileName), который тестировался в бенчмарке. В реальности создание тысячи символов из того же Guid потребует бОльшего количества кода и бОльших расходов ресурсов.

P.S.: Иван, спасибо! Я попробовал.
P.P.S: Список тестов в этом посте - то и только то, что предлагали роботы. Речь не про самый оптимальный способ сгенерить строку, выбрать оптимальный из того, что предлагали роботы.
P.P.P.S: Всё дело было в промпте. Если задать грамотный вопрос, то робот возвращает грамотный ответ. То есть меня подвело то, что я мало работал с этим инструментом.

StorageS3 0.6.4 #решение #хранилище

На прошлой неделе выпустил новую версию библиотеки для экономного доступа к S3. Новая версия включает просьбы коллег по пробросу в библиотеку кастомного пула для массивов. Это было необходимо для случаев, когда стандартное поведение ArrayPool не устраивало.

Также, добавлены исправления от других коллег, за что им большое спасибо!

По традиции, обновил бенчмарки. Как оказалось, AWS (4.0.0) значительно улучшил производительность и потребление памяти. Minio тоже не стоит на месте, но всё ещё является не самой лучшей библиотекой для оптимального доступа к S3. Предыдущие замеры можно посмотреть тут.

Новая версия уже в nuget.

Быстрый код #отдых #философия

Основатель компании id Software, гениальный и легендарный программист Джон Кармак признался, что вся современная индустрия компьютеров существует едва ли не благодаря не очень добросовестным программистам.

В своем микроблоге в заблокированной в России американской соцсети Х (ранее Twitter) он написал, что миллиарды людей запросто могли бы работать на старых компьютерах и не тратить деньги на новые, если бы разработчики ставили в приоритет оптимизацию своего программного кода.

Кармак открыто написал в своем микроблоге, что очень многие пользователи могли бы не тратить деньги на регулярное обновление ПК или покупку нового ноутбука.

"Большое количество пользователей по всему миру, чем многие могут себе представить, могли бы пользоваться устаревшим оборудованием, если бы оптимизация ПО на самом деле была приоритетом", – заявил создатель Doom.

P.S.: Это пост из канала banksta.

IList as Span #скорость #память

В соседнем канале снова подняли вопрос по поводу разницы в скорости итерации по List<T> и IList<T>. Напомню, что я уже писал про это, но давно.

Если кратко, то при итерации по IList возникает проблема с боксингом получаемого List<T>.Enumerator, так как он кастится к IEnumerator<T>. Это даёт 40 лишних байт аллокации. Также, вызов методов IEnumerator<T> приводит к поиску конкретной реализации по таблице виртуальных методов (callvirt в IL). Что, как не трудно догадаться, медленно, если существует более чем одна (это важно!) имплементация IEnumerator<T>.

С тех пор, когда я про это писал, прошло много времени. Теперь я использую другой подход для случаев, когда коллеги используют IList, а мне ну уж очень надо выпендриться бежать по нему быстро.

Этот метод есть в BCL, но является internal. Он весьма неплохо оптимизирован и используется, например, для случаев, когда нужно сделать IEnumerable<T>.Sum. Код меня более чем устраивает, так как позволяет избавиться от аллокации (боксинг List<T>.Enumerator) и немного поднять скорость (не использовать callvirt, про который я писал тут). В production-коде я редко встречаю собственные реализации IList, поэтому метод работает очень неплохо.

Вот код:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
internal static bool TryGetSpan<T>(this IEnumerable<T> source, out ReadOnlySpan<T> span)
{
    bool result = true;
    if (source.GetType() == typeof(T[]))
    {
        span = Unsafe.As<T[]>(source);
    }
    else if (source.GetType() == typeof(List<T>))
    {
         span = CollectionsMarshal.AsSpan(Unsafe.As<List<T>>(source));
    }
    else
    {
        span = default;
        result = false;
    }

    return result;
}

В принципе, всё весьма очевидно, кроме использования CollectionsMarshal (о нём писал тут) для случая превращения List<T> в Span<T>. По скорости получается плюс-минус так же, как если бы я сделал CollectionsMarshal.AsSpan, только с небольшой щепоткой unsafe в виде Unsafe.As (для быстрого каста ссылочных типов).

Если нам нужно поддержать другую реализацию IList, нужно просто добавить этот случай (source.GetType() == typeof(MyList)) в этот метод. Обратите внимание, что это extension, что позволяет использовать его весьма удобно.

Бенчмарк тут. Результаты на картинке.

P.S.: Обратите внимание на комментарий в коде BCL (this could be changed to a cast in the future if the JIT starts to recognize it). Я понимаю это так, что чаяния разработчиков, которые хотят, чтобы компилятор выполнял код из этого метода на этапе компиляции... как минимум коллегами имеются ввиду и могут быть реализованы. Но в будущем. Наверное. Хотя, может быть, я выдаю желаемое за действительное.