Dictionary.AlternateLookup #память #скорость

Несколько лет назад я устраивался в компанию, которая дала тестовое задание. Его суть - показать максимальную скорость и минимальную аллокацию при обработке большого объема данных. Что-то вроде "посчитать количество слов в документе" (я упрощаю).

Одна из основных проблем в подобной задаче - поиск ключа (слова) в большом словаре Dictionary<string, int> и инкремент значения (количества). В то время мне пришлось взять код обычного Dictionary и модернизировать его так, чтобы он принимал ReadOnlySpan<char> в качестве ключа - так я пытался не аллоцировать строки, которые уже существуют в словаре. Инкремент был выполнен в стиле современного CollectionsMarshal.GetValueRefOrAddDefault. Решение коллегам понравилась и меня взяли на работу.

В современном .NET 9 эта задача решается максимально просто, так как нам предоставили прекрасный метод словаря GetAlternateLookup, возвращающий специальную структуру, которая может принимать в качестве ключа то, что сам программист считает сравнимым с ключом словаря.

var dic = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
var lookup = dic.GetAlternateLookup<ReadOnlySpan<char>>();

foreach (ReadOnlySpan<char> word in wordCollection)
{
    CollectionsMarshal.GetValueRefOrAddDefault(lookup, word, out _)++;
}

В данном примере, сравнение ReadonlySpan<char> с типом string возможно потому, что у StringComparer существует реализация интерфейса IAlternateEqualityComparer<ReadOnlySpan<char>, string>. Если ознакомиться с его кодом, то мы видим, что этот интерфейс требует не только реализовать операции сравнения, но и метод создания string из ReadOnlySpan<char>. Таким образом, lookup имеет возможность не только сравнивать значения ключа, но и, в случае его отсутствия, создавать в словаре запись с этим ключом.

Бенчмарк в комментариях. Он содержит сравнение наивного подхода с реализацией через AlternateLookup. В наивном подходе мы создаём строки для поиска наличия ключа, а в случае с AlternateLookup строки создаются только тогда, когда запись в словаре отсутствует. Более сложные сравнения с созданием специального словаря я опущу, хотя в этом случае, как мне кажется, всё-таки возможно выжать ещё немного скорости.