🎆 Exceptional customer service

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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).

👩‍💻 150 дней LeetCode

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

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

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

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