Оптимизация словаря в C#: один поиск вместо двух

Почему ваш счётчик частот в C# работает медленнее, чем мог бы

Недавно я профилировал парсер логов. Ничего особенного — он просто считает, как часто встречается каждый код ошибки за день. Горячий цикл — это инкремент счётчика в словаре: увидел код, увеличил его счётчик. Самая скучная часть кода. Но в профилировщике она занимала больше времени, чем ожидалось. Я копнул глубже, и причина оказалась почти забавной.

Вот цикл, как его пишут почти все:

if (counts.TryGetValue(code, out int c))
    counts[code] = c + 1;
else
    counts[code] = 1;

Читается ровно так, как вы задумали. Но этот код хеширует ключ дважды. TryGetValue вычисляет хеш, проходит по бакету, находит запись. Затем counts[code] = ... выбрасывает всё это и повторяет операцию для записи. Тот же ключ, тот же хеш, тот же проход по бакету — дважды на каждый токен. При отсутствии ключа та же история: один поиск для неудачи, другой для вставки.

Один поиск вместо двух: CollectionsMarshal.GetValueRefOrAddDefault

Существует метод, который пропускает второе путешествие. CollectionsMarshal.GetValueRefOrAddDefault находит или создаёт слот один раз и возвращает ref, указывающий прямо на него:

ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, code, out _);
slot++;

Один хеш, один проход по бакету, и вы изменяете хранилище на месте. Если ключ отсутствовал, он добавляется как default(int), то есть 0, так что первый slot++ делает его 1. out bool сообщает, существовал ли ключ ранее. Мне это здесь не нужно, поэтому я его отбрасываю.

Измерение: насколько это быстрее?

Мне нужна была реальная цифра, поэтому я создал небольшой счётчик на 5 миллионов токенов из словаря в 20 000 слов, со смещением, чтобы несколько слов доминировали, а редкие составляли длинный хвост. Примерно так выглядит реальный текст. Обе версии работают на одних и тех же данных. Я сначала проверяю, что гистограммы идентичны, затем замеряю время каждой как медиану 11 запусков. Выделения памяти беру из GC.GetAllocatedBytesForCurrentThread. Workstation GC, небольшой Linux-контейнер. Это не лаборатория, и я не гонюсь за микросекундами — мне важно соотношение.

• tokens: 5,000,000, distinct vocab: 20,000
• identical results: True (distinct keys: 20,000)

Результаты:

TryGetValue + indexer (два поиска)      медиана   160.0 мс   ~   1,914 КБ/запуск
GetValueRefOrAddDefault (один поиск)   медиана    95.0 мс   ~   1,914 КБ/запуск

Примерно в 1.7 раза быстрее на цикле, и это сохранялось в каждом запуске. Версия с двумя поисками колебалась между 157 и 170 мс. Версия с ref держалась около 95 мс.

Теперь часть, которая мне действительно нравится, потому что она честная. Посмотрите на колонку выделений памяти. Они идентичны. Обе версии строят один и тот же словарь, те же 20 000 строковых ключей, те же внутренние массивы. GetValueRefOrAddDefault не экономит ни одного байта. Это не трюк с памятью. Всё, что он убирает, — это CPU: избыточное хеширование и пробирование при каждом из 5 миллионов инкрементов. Если ваша нагрузка ограничена выделением памяти, это ничего не изменит. Если вы считаете или агрегируете в плотном цикле — это большая часть стоимости.

Почему разрыв такой большой

Выигрыш масштабируется с тем, как часто вы попадаете на уже существующий ключ. В корпусе, близком к распределению Ципфа, большинство токенов повторяются, поэтому большинство итераций идут по пути «найдено», а именно на этом пути наивная версия платит за два полных поиска. Если вместо этого подать 5 миллионов уникальных ключей, разрыв сократится, потому что путь добавления в любом случае выполняет реальную работу. Выигрыш пропорционален вашему соотношению обновлений к вставкам, а счётчики живут на самом «обновленческом» конце этого спектра. Вот почему этот пример так хорош, а нагрузка с преимущественными вставками не дала бы такого эффекта.

Осторожно: ссылка может стать недействительной

Здесь есть острый край, о котором стоит сказать прямо. Возвращаемый ref указывает непосредственно на внутреннее хранилище словаря и остаётся действительным только до следующего структурного изменения. Если вы добавите или удалите ключ, пока держите эту ссылку, она может стать висячей. После перестройки внутреннего массива вы можете записать в неправильный слот. Поэтому правило простое: получите ссылку, измените её, отпустите. Не сохраняйте её, не держите через другую вставку в тот же словарь. Для цикла инкремента на месте это естественный способ написания, именно поэтому счётчики подходят идеально, а словарь, который вы переписываете в середине итерации — нет.

Когда использовать, а когда нет

Ещё одно предостережение, прежде чем вы рассыплете это повсюду. Пространство имён — CollectionsMarshal. Это слово говорит вам, что это низкоуровневая дверь. Для словаря, к которому вы обращаетесь несколько сотен раз, TryGetValue понятнее, и никто никогда не заметит разницы. Моё честное мнение: версия с ref оправдывает себя только тогда, когда цикл счётчика действительно горячий, что для меня означает парсинг и агрегацию. Во всех остальных случаях читаемость побеждает, и я оставляю скучную версию как есть.

Практический вывод

Если вы пишете код подсчёта частот, агрегации или любые операции со словарём в плотном цикле, измерьте свой код. Если профилировщик показывает, что доступ к словарю — узкое место, замените паттерн TryGetValue + индексатор на CollectionsMarshal.GetValueRefOrAddDefault. Вы получите ускорение до 1.7 раза без изменения памяти. Но помните: используйте ссылку локально, не храните её, и применяйте этот приём только в действительно горячих путях. Попробуйте прямо сейчас на своих данных — и вы увидите разницу.

Полный рабочий пример: https://github.com/ssukhpinder/dev-to-code-samples/tree/main/022-dictionary-ref-upsert

Какой самый горячий цикл со словарём в вашем коде? Считали ли вы когда-нибудь, сколько поисков он выполняет? Мне было бы интересно, подтвердится ли соотношение на реальных данных.