Предыдущий пост тут.
FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 3. Ещё строки.
Сегодня рассмотрим оставшиеся реализации FrozenDictionary с ключом типа string. Напомню, что у LengthBucketsFrozenDictionary есть ограничения: если невозможно распределить ключи по бакетам, будет использоваться одна из 11 реализаций абстрактного класса OrdinalStringFrozenDictionary.
Не стоит пугаться большого количества этих реализаций. Все они основаны на одном и том же принципе – расчёте хэш-кода строки. Отличия заключаются в выборе оптимального алгоритма в зависимости от наличия не-ASCII символов, заданных правил сравнения строк (StringComparison) и наличия в ключах уникальных подстрок. Что это всё значит рассмотрим далее.
💡 Выбор оптимальной реализации OrdinalStringFrozenDictionary начинается с анализа ключей классом KeyAnalyzer. Очевидно, что чем длиннее строка, тем медленнее выполняется расчёт хэш-кода. Поэтому KeyAnalyzer пытается найти подстроки наименьшей длины, позволяющие однозначно идентифицировать ключ. Для лучшего понимания рассмотрим пример с фруктами: apple, grape, fig, lime, lemon и kiwi.
Сперва KeyAnalyzer анализирует подстроки длиной в 1 символ при левостороннем выравнивании ключей (рис. 1). В нашем примере есть повторяющиеся подстроки. Например, 0-й символ lime и lemon, 1-й символ fig и lime и 2-й символ в lime и lemon. То есть невозможно при левостороннем выравнивании однозначно идентифицировать ключ по одному символу. Поэтому поиск подстроки продолжается при правостороннем выравнивании. В этом случае при использовании 2-го или 1-го символа с конца подстроки будут уникальны. То есть, зная выравнивание, индекс начала и длину подстроки можно однозначно идентифицировать строку рассчитав хэш-код её подстроки.
Если уникальных подстрок длиной в 1 символ нет, то поиск продолжится для подстрок в 2 символа, 3 символа, вплоть до максимальной длины подстроки. Это значение рассчитывается как минимальное между minLength (минимальная длина ключа) и MaxSubstringLengthLimit = 8. Такое ограничение сделано специально, чтобы не анализировать слишком длинные подстроки, так как их использование не даёт прироста в производительности.
Если уникальных подстрок нет вообще, то расчёт хэш-кода будет производиться для всей строки.
🔍 Поиск в словарях, основанных на OrdinalStringFrozenDictionary, происходит следующим образом:
1. Проверяется, находится ли длина ключа в пределах допустимого диапазона. Это нужно для быстрого определения ключей, которые явно не подходят по длине.
2. Рассчитывается хэш-код подстроки и осуществляется поиск в хэш-таблице.
3. В случае коллизии, осуществляется линейный поиск.
📊 В качестве ключей для бенчмарка я использовал GUID. При инициализации FrozenDictionary, KeyAnalyzer выбрал класс OrdinalStringFrozenDictionary_LeftJustifiedSubstring.
По результатам бенчмарка, FrozenDictionary размером до 75 тыс. элементов быстрее обычного Dictionary. Однако при дальнейшем увеличении размера словаря скорость поиска снижается (рис. 2).
Высокая скорость FrozenDictionary обусловлена быстрым расчётом хэш-кода ключей (рис. 3). Алгоритм FrozenDictionary на 90% – 75% быстрее обычного Dictionary.
Падение производительности в словарях размером 75 тыс. элементов и более вызвано возрастающим количеством коллизий хэша при увеличении размера словаря (рис. 4).
Как видно из графиков, алгоритм, используемый в FrozenDictionary, позволяет ускорить расчёт хэш-кода строки, улучшая производительность до 70%. Но в то же время, такой подход негативно сказывается на производительности поиска в относительно больших словарях.
Со словарями с ключом типа string мы закончили. В FrozenDictionary осталось ещё 2 реализации, которые используются для всех остальных случаев, но в них нет ничего примечательного. Их рассмотрим в заключительном посте в серии про FrozenDictionary. Также, как и обещал, в заключительном посте рассмотрим класс FrozenHashTable – основу большинства «замороженных» словарей.
FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 3. Ещё строки.
Сегодня рассмотрим оставшиеся реализации FrozenDictionary с ключом типа string. Напомню, что у LengthBucketsFrozenDictionary есть ограничения: если невозможно распределить ключи по бакетам, будет использоваться одна из 11 реализаций абстрактного класса OrdinalStringFrozenDictionary.
Не стоит пугаться большого количества этих реализаций. Все они основаны на одном и том же принципе – расчёте хэш-кода строки. Отличия заключаются в выборе оптимального алгоритма в зависимости от наличия не-ASCII символов, заданных правил сравнения строк (StringComparison) и наличия в ключах уникальных подстрок. Что это всё значит рассмотрим далее.
Сперва KeyAnalyzer анализирует подстроки длиной в 1 символ при левостороннем выравнивании ключей (рис. 1). В нашем примере есть повторяющиеся подстроки. Например, 0-й символ lime и lemon, 1-й символ fig и lime и 2-й символ в lime и lemon. То есть невозможно при левостороннем выравнивании однозначно идентифицировать ключ по одному символу. Поэтому поиск подстроки продолжается при правостороннем выравнивании. В этом случае при использовании 2-го или 1-го символа с конца подстроки будут уникальны. То есть, зная выравнивание, индекс начала и длину подстроки можно однозначно идентифицировать строку рассчитав хэш-код её подстроки.
Если уникальных подстрок длиной в 1 символ нет, то поиск продолжится для подстрок в 2 символа, 3 символа, вплоть до максимальной длины подстроки. Это значение рассчитывается как минимальное между minLength (минимальная длина ключа) и MaxSubstringLengthLimit = 8. Такое ограничение сделано специально, чтобы не анализировать слишком длинные подстроки, так как их использование не даёт прироста в производительности.
Если уникальных подстрок нет вообще, то расчёт хэш-кода будет производиться для всей строки.
1. Проверяется, находится ли длина ключа в пределах допустимого диапазона. Это нужно для быстрого определения ключей, которые явно не подходят по длине.
2. Рассчитывается хэш-код подстроки и осуществляется поиск в хэш-таблице.
3. В случае коллизии, осуществляется линейный поиск.
По результатам бенчмарка, FrozenDictionary размером до 75 тыс. элементов быстрее обычного Dictionary. Однако при дальнейшем увеличении размера словаря скорость поиска снижается (рис. 2).
Высокая скорость FrozenDictionary обусловлена быстрым расчётом хэш-кода ключей (рис. 3). Алгоритм FrozenDictionary на 90% – 75% быстрее обычного Dictionary.
Падение производительности в словарях размером 75 тыс. элементов и более вызвано возрастающим количеством коллизий хэша при увеличении размера словаря (рис. 4).
Как видно из графиков, алгоритм, используемый в FrozenDictionary, позволяет ускорить расчёт хэш-кода строки, улучшая производительность до 70%. Но в то же время, такой подход негативно сказывается на производительности поиска в относительно больших словарях.
Со словарями с ключом типа string мы закончили. В FrozenDictionary осталось ещё 2 реализации, которые используются для всех остальных случаев, но в них нет ничего примечательного. Их рассмотрим в заключительном посте в серии про FrozenDictionary. Также, как и обещал, в заключительном посте рассмотрим класс FrozenHashTable – основу большинства «замороженных» словарей.
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
🆒3
Последние 2 месяца занимался автоматизацией PKI (Public Key Infrastructure). Поработал с Let’s Encrypt, GoDaddy, Active Directory Certificate Servcies (PKI от Microsoft), а также с алгоритмами асимметричного шифрования, хэширования и процессом выписывания сертификатов и т.д.
В процессе изучения темы сохранил множество полезных ресурсов, которые помогли мне разобраться в многообразии криптографических алгоритмов, протоколов и стандартов. Охотно делюсь этим списком с вами.
1. Книга «Practical Cryptography for Developers, Svetlin Nakov».
Бесплатная open-source книга о базовых концептах в криптографии. Написана простым языком, без матана, поскольку автор старался написать книгу, подходящую для практического применения IT-специалистами, а не для академического изучения в университетах. Книга всё ещё в разработке и некоторые главы не дописаны. Тем не менее считаю её очень полезной.
2. Серия роликов о PKI.
Видео о том, что такое PKI, Certificate Authority (CA), Root CA, зачем нужны сертификаты, что такое цепочка сертификатов, для чего она и так далее.
3. Статья на Википедии о Certificate Signing Request (CSR) и PKCS#10.
CSR – это то, с чего начинается процесс выпуска сертификата. Самый распространённый формат CSR – PKCS#10. Поэтому про него тоже обязательно нужно прочитать.
4. Видео про X.509 сертификаты.
Видеоролик с объяснением работы сертификатов X.509. Немного повторяет серию роликов о PKI, но повторение - мать учения.
5. Неймспейс System.Security.Cryptography.
Если вы C# разработчик, то этот неймспейс – ваш бро. Серьёзно, там есть если не всё, так очень многое, что требуется для работы с X.509, асимметричными ключами, алгоритмами шифрования и т.д.
6. Алгоритм подписи на эллиптических кривых (ECDSA).
Отличная статья на Хабре, понятно объясняющая как устроена криптография на эллиптических кривых.
7. Протокол Automated Certificate Management Environment (ACME).
Видео об основах работы протокола ACME. Понимание на базовом уровне этого протокола необходимо для автоматизации получения сертификатов от провайдеров, которые его поддерживают, например, Let’s Encrypt и GoDaddy. При желании углубиться в протокол можно почитать RFC 8555.
8. C# клиент для работы с ACME.
Одна из немногих опенсорсных C# библиотек для работы с ACME, которая более-менее активно поддерживается. В дискуссии можно даже найти мой коммент с благодарностью. :)
Под конец, небольшой оффтоп: набор шпаргалок по теме информационной безопасности.
И проверим, сколько из нас знает, как работает криптография с публичным ключом 👇
Please open Telegram to view this post
VIEW IN TELEGRAM
🆒3
Bob wants to send a secret message to Alice using public key cryptography. Which of the following actions should Bob take?
Anonymous Quiz
10%
Use his own public key to encrypt the message and send it to Alice
8%
Use Alice's private key to encrypt the message and send it to Alice
31%
Use his own private key to encrypt the message and send it to Alice
51%
Use Alice's public key to encrypt the message and send it to Alice
🆒5
Заключительный пост по FrozenDictionary
Вместо короткого заключительного поста про FrozenDictionary, я решил переработать существующий материал и написать полноценную статью. Тем более, я не видел ни в рунете, ни в англоязычном интернете таких подробных разборов.
Я доработал бенчмарки, добавил поясняющие диаграммы, обновил графики. Вроде получилось интересно и познавательно.
Сегодня публикую на своём сайте. Завтра выйдет на Хабре. В ближайшие дни займусь переводом.
Приглашаю к чтению.
Вместо короткого заключительного поста про FrozenDictionary, я решил переработать существующий материал и написать полноценную статью. Тем более, я не видел ни в рунете, ни в англоязычном интернете таких подробных разборов.
Я доработал бенчмарки, добавил поясняющие диаграммы, обновил графики. Вроде получилось интересно и познавательно.
Сегодня публикую на своём сайте. Завтра выйдет на Хабре. В ближайшие дни займусь переводом.
Приглашаю к чтению.
🆒7
Быстрый расчёт остатка от деления
В процессе работы над статьёй про FrozenDictionary заметил немало интересных деталей, о которых хочется рассказать. Начнём с простого, поэтому сегодня о быстром алгоритме расчёта остатка от деления.
Как известно, индекс бакета в словаре рассчитывается как остаток от деления
В общем случае, эта операция включает в себя деление, которое выполняется медленнее, чем другие арифметические операции. Поэтому была придумана следующая формула:
Идея этого подхода в том, что если количество бакетов известно заранее, то можно вычислить значение
В FrozenDictionary и Dictionary используется другой вариант формулы, который, по словам разработчиков Microsoft немного быстрее, что подтверждается результатами бенчмарка (рисунок 1):
Кроме того, JIT-компилятор способен оптимизировать код и заменить деление на несколько операций умножения и битовый сдвиг, если значение
Код бенчмарка и результаты тут.
В процессе работы над статьёй про FrozenDictionary заметил немало интересных деталей, о которых хочется рассказать. Начнём с простого, поэтому сегодня о быстром алгоритме расчёта остатка от деления.
Как известно, индекс бакета в словаре рассчитывается как остаток от деления
hashCode на bucketsCount. В C# и многих других языках программирования для этого используется оператор %:var bucketNum = hashCode % bucketsCount;
В общем случае, эта операция включает в себя деление, которое выполняется медленнее, чем другие арифметические операции. Поэтому была придумана следующая формула:
uint FastModLemier(
uint hashcode,
ulong multiplier,
uint bucketsNum) =>
(uint)((((UInt128)(hashcode
* multiplier))
* bucketsNum) >> 64);
Идея этого подхода в том, что если количество бакетов известно заранее, то можно вычислить значение
multiplier по формуле ulong.MaxValue / bucketsNum + 1. Это позволяет заменить деление на умножение и битовые сдвиги. Если интересны подробности и математическое обоснование формулы, то можете ознакомиться со статьёй Дэниела Лемира, разработчика данного метода. Для общего понимания достаточно прочитать главы 1 и 3.2.В FrozenDictionary и Dictionary используется другой вариант формулы, который, по словам разработчиков Microsoft немного быстрее, что подтверждается результатами бенчмарка (рисунок 1):
uint FastModDotNet(
uint hashcode,
ulong multiplier,
uint bucketsNum) =>
(uint)(((((multiplier
* hashcode) >> 32)
+ 1) * bucketsNum) >> 32);
Кроме того, JIT-компилятор способен оптимизировать код и заменить деление на несколько операций умножения и битовый сдвиг, если значение
bucketsCount известно на этапе компиляции. В результате ASM-код для DefaultModConst будет идентичен коду FastModDotNet (рисунок 2).Код бенчмарка и результаты тут.
👍12
Создание массивов в C#: способы и производительность
Как создать массив в C#? Вопрос кажется простым. Но с каждой новой версией .NET появляются всё новые и новые фичи. На данный момент я знаю аж 7 способов создания массивов:
1. new T[]. Самый очевидный, простой и популярный способ создания объектов и массивов в частности. Этот оператор используется повсеместно и является основным для большинства сценариев.
2. stackalloc T[]. Выделяет память в стеке для массива заданного размера и возвращает указатель. Когда-то давно оператор
Для небольших массивов
3. ArrayPool<T>. ArrayPool выделяет массив из пула, что минимизирует количество аллокаций памяти и уменьшает нагрузку на сборщик мусора. Массивы, возвращаемые из пула, могут быть больше запрошенного размера, например, для массива из 700 элементов будет возвращён массив длиной 1024. Использование пула полезно, для относительно больших временных массивов, которые часто создаются и уничтожаются.
4. GC.AllocateUninitializedArray<T>. Этот метод создаёт массив без инициализации его элементов значениями по умолчанию. Использование этого метода может быть небезопасным, так как массив содержит неинициализированные данные. Обязательно перезаписывайте все значения в созданном массиве.
GC.AllocateUninitializedArray<T> быстрее
5. Array.Initialize. Позволяет создавать массивы, задавая тип во время выполнения. Например, когда тип неизвестен на этапе компиляции. Полезно для сценариев, связанных с динамической типизацией.
Производительность аналогична
6. InlineArrayAttribute. Относительно новая фича, появившаяся в C# 12. Позволяет объявить структуру с атрибутом InlineArray, которая будет вести себя как массив. Память для массива выделяется в стеке со всеми вытекающими ограничениями.
Быстрее
7. collections expressions. Синтаксический сахар, который позволяет записать массив в виде литерала. Например,
создаёт массив в куче, аналогично использованию
создаёт массив в стеке, аналогично
Код бенчмарка и результаты тут.
Как создать массив в C#? Вопрос кажется простым. Но с каждой новой версией .NET появляются всё новые и новые фичи. На данный момент я знаю аж 7 способов создания массивов:
1. new T[]. Самый очевидный, простой и популярный способ создания объектов и массивов в частности. Этот оператор используется повсеместно и является основным для большинства сценариев.
2. stackalloc T[]. Выделяет память в стеке для массива заданного размера и возвращает указатель. Когда-то давно оператор
stackalloc требовал использования небезопасного (unsafe) контекста. С появлением Span<T> его можно применять и без unsafe. Этот способ ограничен размером доступной памяти в стеке и при необдуманном использовании может привести к StackOverflowException.Для небольших массивов
stackalloc T[] быстрее new T[] в среднем на 20% и на 88% для больших массивов. Под небольшими массивами я подразумеваю массивы размером меньше 85 000 байт, т.е. размещаемые в куче малых объектов (SOH), а под большими – в куче больших объектов (LOH).3. ArrayPool<T>. ArrayPool выделяет массив из пула, что минимизирует количество аллокаций памяти и уменьшает нагрузку на сборщик мусора. Массивы, возвращаемые из пула, могут быть больше запрошенного размера, например, для массива из 700 элементов будет возвращён массив длиной 1024. Использование пула полезно, для относительно больших временных массивов, которые часто создаются и уничтожаются.
ArrayPool<T> быстрее new T[] в среднем на 30% для небольших массивов и на 89% для больших массивов. Однако для массивов размером менее 300–400 байт использование пула может быть медленнее.4. GC.AllocateUninitializedArray<T>. Этот метод создаёт массив без инициализации его элементов значениями по умолчанию. Использование этого метода может быть небезопасным, так как массив содержит неинициализированные данные. Обязательно перезаписывайте все значения в созданном массиве.
GC.AllocateUninitializedArray<T> быстрее
new T[] в среднем на 15% для массивов 2048 – 85 000 байт. В остальных случаях производительность с new T[] одинаковая.5. Array.Initialize. Позволяет создавать массивы, задавая тип во время выполнения. Например, когда тип неизвестен на этапе компиляции. Полезно для сценариев, связанных с динамической типизацией.
Производительность аналогична
new T[], либо хуже.6. InlineArrayAttribute. Относительно новая фича, появившаяся в C# 12. Позволяет объявить структуру с атрибутом InlineArray, которая будет вести себя как массив. Память для массива выделяется в стеке со всеми вытекающими ограничениями.
Быстрее
new T[] в среднем на 39% для небольших массивов и на 91% для больших массивов.7. collections expressions. Синтаксический сахар, который позволяет записать массив в виде литерала. Например,
int[] array = [1, 2, 3]
создаёт массив в куче, аналогично использованию
new T[]. А конструкцияSpan<int> array = [1, 2, 3]
создаёт массив в стеке, аналогично
stackalloc.Код бенчмарка и результаты тут.
👍16
alexeyfv
Как в FrozenDictionary подсчитываются коллизии хэша
Второй короткий пост о деталях реализации FrozenDictionary, которые остались за кадром. Сегодня об алгоритме подсчёта количества коллизий хэша.
Как в FrozenDictionary подсчитываются коллизии хэша
Второй короткий пост о деталях реализации FrozenDictionary, которые остались за кадром. Сегодня об алгоритме подсчёта количества коллизий хэша.
Второй короткий пост о деталях реализации FrozenDictionary, которые остались за кадром. Сегодня об алгоритме подсчёта количества коллизий хэша.
👍6
Как ошибки в бенчмарке могут привести к неправильным выводам
Видел я однажды пост в LinkedIn, заголовок которого утверждал, что .NET 9 медленнее, чем .NET 8. Сильное заявление. Проверять я его конечно буду. Ведь я сам большой любитель замеров производительности. Перейдём сразу к тому, что не так с бенчмарком.
❌ Методы не возвращают результат
Современные компиляторы умные. Они могут понять, когда выполняемый код не влияет на результат программы, и просто удаляют его. Такая оптимизация называется dead-code elimination (DCE). В данном случае, метод
✅ Всегда возвращайте результат из методов
Исправленный вариант может выглядеть так. Нам неважно, что будет в переменной sum. Главное, что её использование предотвращает DCE и не оказывает значительного влияния на результаты бенчмарка.
❌ Слепое сравнивание foreach
Как мы знаем,
- foreach с массивом будет преобразован в while c индексатором;
- foreach со списком – в while с List<int>.Enumerator;
- foreach с ICollection<int> – в while с IEnumerator<int>.
✅ Сравнивать производительность foreach нужно с разными типами
Поскольку
❌ Передача метода в виде параметра
При передаче метода в виде параметра создаётся делегат. В нашем примере –
✅ При передаче метода в виде параметра нужно заранее создать экземпляр делегата
Правильнее было бы проинициализировать делегат в методе
Выводы
Теперь посмотрим на результаты исправленного бенчмарка. Bad – изначальный бенчмарк, Better – после исправления.
В бенчмарке Bad, который я запустил на своём ноутбуке, метод
В бенчмарке Better, метод
В целом, результаты во всех трёх версиях .NET кажутся плюс-минус одинаковыми. Поэтому, я бы не стал заявлять о том, что .NET 9 медленнее .NET 8.
Видел я однажды пост в LinkedIn, заголовок которого утверждал, что .NET 9 медленнее, чем .NET 8. Сильное заявление. Проверять я его конечно буду. Ведь я сам большой любитель замеров производительности. Перейдём сразу к тому, что не так с бенчмарком.
❌ Методы не возвращают результат
Современные компиляторы умные. Они могут понять, когда выполняемый код не влияет на результат программы, и просто удаляют его. Такая оптимизация называется dead-code elimination (DCE). В данном случае, метод
DoSomeThing фактически не делает ничего, поэтому компилятор удаляет его в методе For. Но в методе ForEach_Linq такое сделать нельзя, т.к. в нём создаётся делегат. В результате получается сравнение методов с разным поведением (рисунок 2).✅ Всегда возвращайте результат из методов
Исправленный вариант может выглядеть так. Нам неважно, что будет в переменной sum. Главное, что её использование предотвращает DCE и не оказывает значительного влияния на результаты бенчмарка.
❌ Слепое сравнивание foreach
Как мы знаем,
foreach предназначен для итерации по коллекциям, которые возвращают Enumerator. Но даже если коллекция возвращает Enumerator, это не гарантирует, что он будет использоваться. Рассмотрим пример на рисунке 3:- foreach с массивом будет преобразован в while c индексатором;
- foreach со списком – в while с List<int>.Enumerator;
- foreach с ICollection<int> – в while с IEnumerator<int>.
✅ Сравнивать производительность foreach нужно с разными типами
Поскольку
foreach компилируется в различный код в зависимости от коллекции, производительность может значительно отличаться. Поэтому важно сравнивать каждый тип отдельно. Не исключаю, что эта деталь реализации может измениться в будущем.❌ Передача метода в виде параметра
При передаче метода в виде параметра создаётся делегат. В нашем примере –
Action<int> (рисунок 4). Делегат, как известно ссылочный тип, то есть его создание – аллокация памяти, которая влияет на результаты бечмарка.✅ При передаче метода в виде параметра нужно заранее создать экземпляр делегата
Правильнее было бы проинициализировать делегат в методе
GlobalSetup, который выполняется перед бенчмарками.Выводы
Теперь посмотрим на результаты исправленного бенчмарка. Bad – изначальный бенчмарк, Better – после исправления.
В бенчмарке Bad, который я запустил на своём ноутбуке, метод
ForEach_LinqParallel отработал на .NET 9 чуть быстрее, чем на .NET 8. То есть та разница в, о которой говорил автор, была в рамках погрешности.В бенчмарке Better, метод
ForEach_LinqParallel отработал на .NET 9 медленнее чем на .NET 8 на 90 мкс. Такую разницу я бы тоже отнёс к погрешности и не стал акцентировать внимание.В целом, результаты во всех трёх версиях .NET кажутся плюс-минус одинаковыми. Поэтому, я бы не стал заявлять о том, что .NET 9 медленнее .NET 8.
👍9