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

HasFlag #скорость

Недавно, как продвинутый, беседовал с Claude 4.0 Sonnet, который утверждал, что прямая битовая проверка (bitwise) наличия флага в enum быстрее, чем применение my_enum.HasFlag(flag). Я не поверил, так как проверял это пару лет назад, где-то в предоливьешные времена, после выхода .NET 5.

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

[Flags]
public enum Operator: short {
   None = 0x0,

   // Flags
   NonOperator = 0x0001,
   Comparison = 0x0002,
   ...

   // Comparison Operators
   Equals = 0x0700 | Comparison,
   NotEquals = 0x0800 | Comparison,
   ...

   // Specific non-operators
   Whitespace = 0x2000 | NonOperator,
   Quotes = 0x2100 | NonOperator,
   ...
}

Согласно примеру выше, флаги нужны, когда наш код ветвится как от типа оператора, так и от самого оператора. Можно создать два enum'a, а можно запихать всё в один, как сделано в примере. Иногда это очень удобно, а иногда экономно, если мы, например, пишем компактные структурки.

По результатам тестирования чуда не произошло, и HasFlag имеет примерно ту же производительность, что и bitwise (см. скриншот для Windows или для macOS). Для полноты картины, я запихнул в тест то, что часто видел на разных проектах для выполнения подобной задачи - классифицировать значения в enum (проверка через массив, через HashSet и через switch).

Вывод: проверяем флаги через Enum.HasFlag, так как это читабельнее, да и поддерживать проще. Проверка через bitwise тоже хорошо, но только для пацанов, которым HasFlag не завезли.

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

P.S.: Коллега подтверждает, что шарплаб утверждает, что разница на низком уровне всё-таки есть. Может быть она и играет, когда мы наблюдаем небольшую разницу между bitwise и HasFlag. Она вылезает на Windows, при многочисленных перезапусках бенчмарка (её и сейчас видно в RatioSD). Удивительно, но на macOS всё стабильно.

JsonPath в .NET #решение

Представим себе, что есть сервис, который умеет получать данные из Kafka и складывать полученные данные в БД. Без программирования, просто декларативным указанием topic и таблицы в БД. То есть:

1. Сервис работает по запросу (job или unit-of-work).
2. При создании job описывается маппинг данных из Kafka в нужную таблицу.
3. Описывается фильтрация и преобразовывает данных из Kafka так, как пользователю удобно. Ну чтобы не заниматься этим при каждом запросе в БД.

То есть, во-первых, нужен вменяемый API, которым удобно пользоваться. Во-вторых, нужно описание маппинга полей сообщения из Kafka в поля Data-base-object (DBO). Ну и всякая фильтрация (например, отсечение удалённых), выбор определённых полей и некие операции над ними.

Например, нам нужно взять подразделения компании, перенести часть нужных нам полей, а, также, налету, создать поле, в котором лежит полный путь до этого подразделения в дереве (например, "Бизнес-юнит 3/Департамент 2/Подразделение 1"). Представим себе, что в исходном сообщении эти данные есть, но в виде массива родительских подразделений. То есть нужно взять их названия, правильно отсортировать и соединить в строку.

Какой же интерфейс предоставить программистам, чтобы они могли это сделать? Правильно, формализованный JsonPath (RFC). Конечный пользователь тоже не пострадает, так как сможет, с помощью программистов, натыкать такое на UI.

Когда сервис будет вычитывать сообщение из Kafka, исходное сообщение будет преобразовано, размаплено по нужным полям DBO и помещено в базу. Маппинг, при создании job будет выглядеть примерно так.

{
   "id": "$.id",
   "1c_id": "$.1c.id",
   "full_path": "join(sort($.parents, @.lvl), '/')",
   "name": "$.name",
   "manager_id": "$.manager.oauth.id",
   "filters": [
      "$.is_deleted == false", 
      "$.draft == false"
   ]
}

Но чтобы сделать этот маппинг, увы, нужно приложить усилия. Дело в том, что стандартная (с некоторых пор) библиотека для работы с json в .NET это System.Text.Json. А он не умеет выбирать узел по JsonPath. Опустим и то, что мало кто из библиотек умеет работать с функциями высшего порядка (см. full_path в примере), но это, со скрипом, можно сделать самому.

Основная задача - получение нужных узлов исходного сообщения в Kafka по выражению JsonPath. Для решения этой задачи можно найти несколько библиотек: непотопляемый Newtonsoft.Json, модный Hyperbee.Json, хмурый JsonCons.Net и популярный JsonPath.Net).

Так как сервис представляется весьма нагруженным, а поиск и преобразования по JsonPath - частыми, нужно выбрать именно ту библиотеку, которая работает быстро и, при этом, потребляет мало памяти. Результаты на скриншоте. Кажется, что Newtonsoft.Json или Hyperbee.Json - весьма неплохой выбор, по скорости и потреблению памяти.

Естественно, все эти библиотеки отличаются функционалом и возможностями расширения (например, в данном примере нужно добавлять свои функции к JsonPath для мутации данных). Тот же Newtonsoft.Json огромная и уважаемая библиотека. Однако, если нужно только парсить JsonPath, то выбор похож на очевидный.

Бенчмарк вот тут.

P.S.: Банчмарки включают в себя создание JsonDocument, JsonNode и JObject, чтобы приблизиться к реальной ситуации. В реальности сервис получает одну из этих структур данных и работает с ней. Если эти штуки предварительно создавать, то, в принципе, результат не изменится. Единственное, что изменится - пропадёт аллокация.
P.P.S.: Пакет Microsoft.AspNetCore.JsonPatch исключён из тестирования, так как основывается на Newtonsoft.Json.
P.P.P.S.: Ребята из Hyperbee.Json, кажется, выложили на nuget библиотеку, которая скомпилирована в Debug. Исправили.

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

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

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

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

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

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

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

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