yet another dev

Быстрый расчёт остатка от деления

В процессе работы над статьёй про 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).

Код бенчмарка и результаты тут.

Статья по FrozenDictionary опубликована на Хабре. Поддержите плюсом.

Заключительный пост по FrozenDictionary

Вместо короткого заключительного поста про FrozenDictionary, я решил переработать существующий материал и написать полноценную статью. Тем более, я не видел ни в рунете, ни в англоязычном интернете таких подробных разборов.

Я доработал бенчмарки, добавил поясняющие диаграммы, обновил графики. Вроде получилось интересно и познавательно.

Сегодня публикую на своём сайте. Завтра выйдет на Хабре. В ближайшие дни займусь переводом.

Приглашаю к чтению.

🛡 Криптография для разработчиков

Последние 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, которая более-менее активно поддерживается. В дискуссии можно даже найти мой коммент с благодарностью. :)

Под конец, небольшой оффтоп: набор шпаргалок по теме информационной безопасности.

И проверим, сколько из нас знает, как работает криптография с публичным ключом 👇

Предыдущий пост тут.

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 – основу большинства «замороженных» словарей.

👩‍💻 150 дней LeetCode

Уже больше 150 дней в этом году решаю задачи на LeetCode. На данный момент решено 200 задач, из которых 60% – задачи уровня Medium, 35% – Easy, 5% – Hard.

Сейчас я сосредоточен на улучшении своих слабых сторон, таких как dynamic programming, backtracking, bit manipulation, greedy. Поэтому редко принимаю участие в daily challenge. Вместо этого, решаю задачи из готовых списков, разбитых по темам.

Предыдущий пост тут.

FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 2. Строки.

Продолжаем изучать, что у FrozenDictionary под капотом. Сегодня начнём говорить о словарях с ключом типа string. Для таких словарей предусмотрены аж 12 реализаций FrozenDictionary. Естественно, рассмотрим только принципиальные отличия.

LengthBucketsFrozenDictionary

При создании «замороженных» словарей с ключом типа string, FrozenDictionary в первую очередь попытается создать класс LengthBucketsFrozenDictionary, поэтому начнём именно с него. LengthBucketsFrozenDictionary оптимизирован для ситуаций, когда ключи имеют разную длину. Достигается это распределением ключей по бакетам (корзинам). Алгоритм напоминает блочную сортировку. Для каждой уникальной длины ключа создаётся бакет вместимостью MaxPerLength = 5 элементов.

💡 Чтобы стало понятнее, разберём пример словаря с 6 элементами (рис. 1). В словаре есть ключи длиной 3, 4 и 5 символов. Следовательно, их можно распределить в 3 бакета:

- бакет для ключей длиной 3: fig;
- бакет для ключей длиной 4: lime и kiwi;
- бакет для ключей длиной 5: apple, grape и lemon.

Поскольку известна минимальная (3) и максимальная (5) длина ключей, нет смысла создавать 3 отдельных бакета. Можно всё хранить в одном массиве _lengthBuckets. В таком случае индекс рассчитывается так: (key.Length - minLength) * MaxPerLength.

🔍 Поиск осуществляется в 3 шага (рис. 2):

1. Определяется бакет в массиве _lengthBuckets.
2. Линейным поиском в бакете определяется индекс искомого ключа в _keys.
3. Возвращается значение.

🚫 У LengthBucketsFrozenDictionary есть 2 ограничения:

1. Количество ключей с одинаковой длиной не должно превышать MaxPerLength (принцип Дирихле).
2. Количество пустых бакетов должно быть < 20%. Иначе реализация становится неэффективна с точки зрения использования памяти.

Если одно из этих условий не выполняется, то будет выбрана другая реализация FrozenDictionary. О ней я расскажу в следующей части.

📊 Результаты бенчмарка показывают, что чтение из LengthBucketsFrozenDictionary может быть до 99% быстрее обычного Dictionary. Но если в словаре количество ключей с одинаковой длиной достигает 5, то производительность небольших словарей (до 100 элементов) может быть хуже (рис. 3).

💲Медианный net доход семьи до 35 лет в США около 287к рублей

Это не байт, а выдержка из статьи про средний доход американских домохозяйств основанный на данных свежего опроса ФРС США (см. рис. 1).

Net worth – это все доходы минус все расходы. К доходам относят зарплату, доход от вкладов и сдачи в аренду имущества и т.д. К расходам – арендную плату, ипотечные платежи, платежи по другим кредитам и другие обязательства.

🇺🇸 Стоимость жилья в США

Интересно также отметить стоимость жилья (см. рис. 2 и 3). Люди, которые приобрели жильё в ипотеку или арендовали квартиру после 2022 года, платят на 25% – 65% больше по сравнению с теми, кто успел сделать это раньше. Ничего не напоминает? :)

🇪🇺🇷🇸 Европа и Сербия в тренде

В Европе, и в частности в Сербии, где я сейчас живу, те же самые проблемы – жильё значительно подорожало с тех пор, как сюда релокейтнули десятки тысяч россиян, украинцев и белорусов. Про жильё в Сербии думаю нужно сделать отдельный пост.

🇷🇺 Россия в тренде

В этом плане, Россия тоже движется в рамках мирового тренда. Спасибо льготной ипотеке, из-за которого жильё стало настолько доступным, что с 2020 года подорожало минимум в 2 раза.

🎆 Exceptional customer service

Последние несколько недель занимаюсь автоматизацией PKI на работе. Сделал функционал для Let's Encrypt. Дошёл черёд до GoDaddy. Начал исследовать тему. Обнаружил, что несколько месяцев назад GoDaddy ограничила использование DNS API для пользователей, у которых нет подписки или меньше 10 доменов.

Теперь люди, покупая SSL сертификат минимум за $100 / год, должны ещё доплатить за подписку, чтобы автоматизировать обновление сертификата.

Самое паршивое — это изменение было сделано без каких-либо предупреждений. У людей просто начали отваливаться сервисы из-за отсутствия TLS/SSL. А причины проблемы пользователи узнали только после обращения в техподдержку.

Действительно, exceptional.