Ускоряем Dictionary в C# при помощи структур и CollectionsMarshal

Если вы C# разработчик, то наверняка вам знаком класс Dictionary. В качестве значений вы, скорее всего, использовали классы. Но что если я скажу, что в Dictionary можно использовать структуры? Не стоит бояться того, что структуры копируются при передаче в метод или возврате из него. Есть способ этого избежать, и это работает быстро.

Дисклеймер

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

Сценарий использования

Представим, что есть некоторый массив данных data. От нас требуется реализовать следующий функционал:

Преобразовать data в словарь для последующего поиска.
По некоторому ключу найти в словаре объект и изменить его.
Повторить п. 2 столько раз, сколько требуется.

Напишем код, который имитирует такое поведение:

// Инициализация словаря  
var dict = new Dictionary<int, SomeClass>(Length);

// Заполнение словаря  
foreach (var (i, obj) in data) {  
    dict.Add(i, obj);  
}

// Поиск значения и изменение данных  
for (int i = 0; i < Length; i++) {  
    dict[i].DoWork(i);  
}

Код выше работает как задумано. Давайте попробуем его ускорить. Заменим класс SomeClass на структуру SomeStruct и сравним производительность обоих вариантов.

// Инициализация словаря  
var dict = new Dictionary<int, SomeClass>(Length);

// Заполнение словаря  
foreach (var (i, obj) in data) {  
    dict.Add(i, obj);  
}

// Поиск значения и изменение данных  
for (int i = 0; i < Length; i++) {  
    var obj = dict[i];  
    obj.DoWork(i);  
    dict[i] = obj;  
}

Бенчмарк

Замер производительности осуществлялся на массиве данных в 100 000 элементов. Размер классов (без заголовка) и структур менялся от 4 до 128 байт. Для замеров производительности я использовал библиотеку BenchmarkDotNet. Код бенчмарка и результаты можно найти в GitHub.

content Среднее время выполнения бенчмарка в зависимости от размера сущности

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

Инициализация словаря

Бенчмарк показал ожидаемые результаты. Время инициализации и размер словаря со структурами линейно возрастают с увеличением размера структур.

content Среднее время инициализации словаря в зависимости от размера сущности

Связано это с тем, что массив entries в таком случае хранит непосредственно значения, а не ссылки. Соответственно, для хранения такого словаря нужно банально больше памяти.

Справедливости ради нужно отметить, что для классов CLR выделила памяти даже больше, просто это произошло ранее – во время инициализации массива data. Если замерять время, затраченное на инициализацию массива классов и структур, то результаты будут не в пользу классов. Но это выходит за рамки статьи.

Заполнение словаря

И снова ожидаемые результаты. Время копирования структур, происходящее при заполнении словаря, линейно зависит от размера структур. Хотя разница между структурами и классами практически не заметна вплоть до 20 байт.

content Среднее время заполнения словаря в зависимости от размера сущности

Поиск значения и его изменение

И в третий раз результаты не в пользу структур.

content Среднее время поиска значения и его изменения в зависимости от размера сущности

Связано это с тем, что поиск по ключу и копирование структур осуществляется дважды:

SomeStruct s = dict[i]; // 1-й поиск по ключу и копирование структуры  
s.DoWork(i);  
d[i] = s; // 2-й поиск по ключу и копирование структуры

Вот тут нам и поможет класс CollectionsMarshal.

Кто такой этот ваш CollectionsMarshal?

Если кратко, то это класс с четырьмя extension-методами:

AsSpan<T> – возвращает Span<T> для элементов List<T>.
GetValueRefOrAddDefault<TKey, TValue> – по ключу возвращает из словаря ссылку на элемент TValue, создавая default значение если элемента не существует.
GetValueRefOrNullRef<TKey, TValue> – по ключу возвращает из словаря ссылку на элемент TValue или ссылку на null, если элемента не существует.
SetCount<T> – устанавливает значение Count для List<T>.

Нас интересуют только GetValueRefOrAddDefault и GetValueRefOrNullRef. При помощи этих методов можно извлечь значения из словаря по ссылке, что позволит избежать двойного поиска по ключу и двойного копирования структуры. Например, код выше можно переписать следующим образом:

ref SomeStruct s = ref CollectionsMarshal.GetValueRefOrNullRef(dict, i);  
s.DoWork(i);

Ещё немного бенчмарков

Сделаем замеры реализации с GetValueRefOrNullRef и сравним с предыдущими результатами:

content Среднее время поиска значения и его изменения в зависимости от размера сущности

Время выполнения кода с CollectionsMarshal даже быстрее, чем с классами. Чтобы компенсировать потери производительности при инициализации и заполнении словаря, количество операций поиска должно быть многократно больше, чем размер массива.

content Время выполнения бенчмарка. Графики разбиты по количеству операций поиска.

Особенности CollectionsMarshal

Проверка на default и null

Как упоминалось ранее, методы GetValueRefOrAddDefault и GetValueRefOrNullRef возвращают ссылку на default структуру и ссылку на null.

Проверить, дефолтная ли структура, т.е. все поля имеют дефолтное значение, довольно просто – нужно проверить флаг exists:

ref var element = ref CollectionsMarshal.GetValueRefOrAddDefault(  
    dict, key, out bool exist);

if (exist) {  
    // some code here  
} 

Со ссылкой на null ситуация другая. Булевого флага нет, а при сравнении с null будет выброшено исключение NullReferenceException. Лучше воспользоваться методом Unsafe.IsNullRef<T>(ref T source).

ref var element = ref CollectionsMarshal.GetValueRefOrNullRef(dict, key);  
if (Unsafe.IsNullRef<T>(ref element)) {  
    // some code here  
}

Изменение словаря после получения ссылки на структуру

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

ref var element = ref CollectionsMarshal.GetValueRefOrNullRef(dict, key);

Console.WriteLine($"ref element: {element.Item1}"); // 30  
Console.WriteLine($"dict[key]: {dict[key].Item1}"); // 30

element.Item1 = 50; // change #1

Console.WriteLine($"ref element: {element.Item1}"); // 50  
Console.WriteLine($"dict[key]: {dict[key].Item1}"); // 50

dict.Add(100, new (100)); // add a new element  
element.Item1 = 60; // change #2

Console.WriteLine($"ref element: {element.Item1}"); // 60  
Console.WriteLine($"dict[key]: {dict[key].Item1}"); // 50

Выводы

Структуры – недооценённые элементы C#, которые, при определённых условиях, способны ускорить ваше приложение. При использовании структур в качестве значений для Dictionary лучше воспользоваться классом CollectionsMarshal. Методы этого класса GetValueRefOrAddDefault и GetValueRefOrNullRef позволяют получать элементы словаря по ссылке. Это, в свою очередь, может положительно сказаться на производительности кода при относительно большом количестве операций поиска в словаре.