Как‑то раз была поставлена задача ускорить работу с Dictionary<int,?>, где ключом всегда выступал int, а значением — структура. Имеющаяся скорость не устраивала. Более того, очень бы хотелось иметь возможность получать ссылку (ref) на значение в Dictionary, чтобы можно было изменять содержимое извне. В настоящий момент полнофункциональный словарь из dotnet такого поведения не поддерживает.
В статье, как и в предыдущей, речь пойдёт о наносекундах и экономии байтиков. Уверен, что 99% программистов этого не нужно, а подобные эксперименты без изучения environment'a будут даже опасны. Однако, если ваш профиль high‑load или геймдев, данная информация может быть востребована.
Как проектируем?
Так как всё, что делает этот словарь связано со структурами, было решено сделать и его структурой. Это чуть‑чуть уменьшит время, которое мы будем тратить на вызов методов — runtime'у не надо будет выяснять по таблице виртуальных методов, кому принадлежит этот метод. Это, в свою очередь, облегчит inline методов — одну из самых эффективных методик оптимизации скорости. Ну, если мы говорим о наносекундах, конечно.
Далее, мы не будем изобретать велосипед и воспользуемся всеми наработками dotnet‑community для того, чтобы реализовать словарь. Так как ключ это всегда int, мы можем смело выбрасывать всё, что касается сравнения ключей и получения hash‑кода. Для того, чтобы размер внутренней коллекции совпадал с вычисленными эмпирическим путём значениями, будем использовать и вот этот класс. Получился — Glossary.
Добавление элементов в словарь
Метод добавления очень похож на метод из настоящего Dictionary. С одним исключением: мы можем, например, добавить ключ и сразу получить ссылку на значение во внутренней коллекции словаря. Классическое добавление тоже, конечно, присутствует.
Если запустить benchmark и измерить скорость добавления элементов, то мы увидим интересную картину:
Method |
Runtime |
Mean |
Ratio |
Gen0 |
Gen1 |
Allocated |
Alloc Ratio |
|---|---|---|---|---|---|---|---|
DictionaryAdd |
.NET 6.0 |
10.95 us |
1.00 |
8.6823 |
1.4343 |
71.16 KB |
1.00 |
GlossaryAdd |
.NET 6.0 |
11.84 us |
1.08 |
6.9580 |
0.2289 |
56.96 KB |
0.80 |
DictionaryAdd |
.NET Core 3.1 |
12.67 us |
1.00 |
8.6823 |
0.8545 |
71.15 KB |
1.00 |
GlossaryAdd |
.NET Core 3.1 |
11.40 us |
0.90 |
6.9580 |
0.2289 |
56.96 KB |
0.80 |
DictionaryAdd |
.NET Framework 4.8 |
12.13 us |
1.00 |
11.5814 |
1.6479 |
71.31 KB |
1.00 |
GlossaryAdd |
.NET Framework 4.8 |
11.10 us |
0.91 |
9.2621 |
0.2594 |
57.09 KB |
0.80 |
Во‑первых, весьма очевидно, что Dictionary в.NET 6 стал заметно шустрее. Это очень радует, команда dotnet — молодец.
Также, специальная имплементация закономерно выигрывает на старых framework'ах. Относительно высокая скорость добавления обусловлена тем, что мы избавились от лишних вызовов EqualityComparer'a, плюс мы используем способ работы с внутренним массивом из Dictionary<int,int>.Enumerator. Видимо ранее разработчики основной библиотеки, к сожалению, не могли произвести все нужные оптимизации. Теперь — всё красиво.
Ну и причины, по которой мы сэкономили немного памяти просты — во внутренней структуре Entry отсутствует поле hashcode, потому что оно не нужно при ключе из int.
Перечисление элементов словаря
Простой benchmark покажет нам, что использовать в Enumerator внутреннюю структуру словаря (Entry) без использования промежуточного KeyValuePair достаточно эффективно. Плюс, немного производительности добавляет ref struct.
Method |
Runtime |
Mean |
Ratio |
|---|---|---|---|
DictionaryEnumeration |
.NET 6.0 |
2.307 us |
1.00 |
GlossaryEnumeration |
.NET 6.0 |
1.012 us |
0.44 |
DictionaryEnumeration |
.NET Core 3.1 |
6.777 us |
1.00 |
GlossaryEnumeration |
.NET Core 3.1 |
2.032 us |
0.30 |
DictionaryEnumeration |
.NET Framework 4.8 |
6.737 us |
1.00 |
GlossaryEnumeration |
.NET Framework 4.8 |
2.037 us |
0.30 |
Если нас смущает, что enumerator отдаёт внутреннюю структуру, то не расстраивайтесь. Во‑первых, эту коллекцию нужно использовать только в особых случаях — её увидят лишь те, кому нужна подобная оптимизация, то есть люди знающие и понимающие. А во‑вторых, мы же говорим про performance, который часто вот такой, не самый красивый. В принципе, можно спрятать поле Next за internal — тогда всё будет хорошо.
Также, мы снова видим улучшение производительности обычного Dictionary, который каждый из нас использует каждый день. Круто! Кстати, не надо забывать, что наша коллекция — всего лишь частный случай, в то время как Dictionary<int, int> является коллекцией общего назначения, которую затачивают под все возможные сценарии.
Чтение и запись по ключу
Завершает тестирование, конечно же, benchmark с получением данных из коллекции, их обработка и запись обработанных данных обратно в словарь.
Начнём с простого чтения.
Method |
Runtime |
Mean |
Ratio |
|---|---|---|---|
DictionaryGetValue |
.NET 6.0 |
4.089 us |
1.00 |
DictionaryTryGetValue |
.NET 6.0 |
4.101 us |
1.00 |
GlossaryGetValue |
.NET 6.0 |
1.740 us |
0.43 |
GlossaryTryGetValue |
.NET 6.0 |
1.757 us |
0.43 |
DictionaryGetValue |
.NET Core 3.1 |
4.771 us |
1.00 |
DictionaryTryGetValue |
.NET Core 3.1 |
5.013 us |
1.05 |
GlossaryGetValue |
.NET Core 3.1 |
2.391 us |
0.50 |
GlossaryTryGetValue |
.NET Core 3.1 |
2.615 us |
0.55 |
DictionaryGetValue |
.NET Framework 4.8 |
6.701 us |
1.00 |
DictionaryTryGetValue |
.NET Framework 4.8 |
6.997 us |
1.04 |
GlossaryGetValue |
.NET Framework 4.8 |
2.478 us |
0.37 |
GlossaryTryGetValue |
.NET Framework 4.8 |
2.629 us |
0.39 |
Результаты, в принципе, ожидаемые, поскольку алгоритм в Glossary не нуждается в сравнении с использованием EqualityComparer, а значит убираются лишние вызовы и код становится более предсказуемым для процессора.
Из интересного: для того, чтобы иметь возможность отдавать ref в методе GetValue, приходится использовать дополнительное статическое поле, которое содержит значение по‑умолчанию. Оно никогда не вернётся, так как чуть выше находится Exception (сам он кидается в методе статического класса Errors). Мотивы, которые побудили меня сделать так описаны в предыдущей статье про inline и throw.
Следующий тест — читаем и записываем новый результат в словарь. Это то самое, ради чего всё затевалось.
Method |
Runtime |
Mean |
Ratio |
|---|---|---|---|
Dictionary |
.NET 6.0 |
7.774 us |
1.00 |
DictionaryMarshal |
.NET 6.0 |
3.763 us |
0.49 |
Glossary |
.NET 6.0 |
2.007 us |
0.26 |
Dictionary |
.NET Core 3.1 |
9.818 us |
1.00 |
Glossary |
.NET Core 3.1 |
7.478 us |
0.76 |
Dictionary |
.NET Framework 4.8 |
12.944 us |
1.00 |
Glossary |
.NET Framework 4.8 |
7.391 us |
0.57 |
В нашем случае неоспоримым преимуществом является то, что мы можем получить ссылку на значение внутренней коллекции, а значит изменить её прямо по ссылке, без необходимости снова инициировать поиск ключа и ячейки, в которой лежит значение. В связи с этим, разница в скорости весьма велика.
Короче говоря, никаких неожиданностей: запись по ссылке во много раз быстрее, чем повторный поиск ячейки со значением по ключу.
Кстати, как правильно заметили в комментариях, в.NET 6 появился способ сходить в словарь и получить значение по ссылке — CollectionsMarshal.GetValueRefOrNullRef. Очень удобный метод, значительно ускоряющий сценарий чтения и записи значения по ссылке. Использовать его крайне рекомендую.
Выводы
Иногда стоит писать свои коллекции. Даже такие сложные, как Dictionary. Тем более, что основной алгоритм поиска значения по ключу давно известен и даже лежит на github.
Иногда не стоит писать свои коллекции. Да-да, именно так. Не смотря на то, что результаты достаточно впечатляющие, они не гарантируют на 100%, что покрыты абсолютно все случаи добавления/удаления данных из коллекции. А что, если множественное добавление и удаление понизит производительность? А как быть с многопоточностью? Если вам хочется отвечать на все эти вопросы - вперёд. Это интересно.
P.S.: Начал писать в телегу про производительность. Заглядывайте, если интересно.
Комментарии (32)
netpilgrim
00.00.0000 00:00+2
Более того, очень бы хотелось иметь возможность получать ссылку (ref) на значение в Dictionary, чтобы можно было изменять содержимое извне.
Начиная с .NET 6 есть CollectionsMarshal.GetValueRefOrNullRef
teoadal Автор
00.00.0000 00:00+1| Method | Runtime | Mean | Ratio | |------------------ |------------------- |----------:|------:| | Dictionary | .NET 6.0 | 7.774 us | 1.00 | | DictionaryMarshal | .NET 6.0 | 3.763 us | 0.49 | | Glossary | .NET 6.0 | 2.007 us | 0.26 |Спасибо! Добавил в статью и обновил бенчмарк.
dyadyaSerezha
00.00.0000 00:00+2runtime'у не надо будет выяснять по таблице виртуальных методов, кому принадлежит этот метод. Это, в свою очередь, облегчит inline методов — одну из самых эффективных методик оптимизации скорости.
Может, я забыл чего в .NET, но если метод невиртуальный, то и выяснять ничего не придётся.
teoadal Автор
00.00.0000 00:00Возможно, я выразился не очень точно. Я говорил об IL-коде, где вызов статического метода это
call, вызов не статического метода - всегдаcallvirt(даже если метод не помечен ключевым словомvirtual).
Вызов методов структур похож на статические методы, там тожеcall, который несколько быстрее, чемcallvirt.
Прочитать можно вот тут и тут.
Про call и callvirt можно тоже прочитать.dyadyaSerezha
00.00.0000 00:00вызов не статического метода - всегда callvirt.
Неверно. Нет такого "всегда" - в приведённых ссылках.
teoadal Автор
00.00.0000 00:00Соглашусь, слово "всегда" слишком сильное. В 80% случаев, кроме некоторых - вот тут относительно недавно обсуждалось.
Я хотел напомнить всё это лишь для того, чтобы объяснить почему я сказал относительно структур "runtime'у не надо будет выяснять по таблице виртуальных методов, кому принадлежит этот метод". Детально вдаваться в объяснения и пояснения, по которым люди пишут длинные посты и даже статьи я не намеревался.
qw1
00.00.0000 00:00+2В 80% случаев, кроме некоторых — вот тут относительно недавно обсуждалось
Так себе аргумент. Там перечислены случаи, когда нужна диспетчеризация. Например, если ваш класс наследовался бы от IDictionary, а клиентский код получил бы интерфейсную ссылку, а не обычную — то да, был бы callvirt. Но вы же не наследуетесь, значит, такой возможности в принципе не будет.
Посмотрим, что мы экономим на struct-словаре. Ровно одну аллокацию, сам класс словаря будет на стеке, а не в куче. Но учитывая, что внутри словаря есть ссылочные типы (массивы _buckets и _entries), нельзя сказать, что такой словарь gc-friendly. Одной аллокацией больше, одной меньше — погоды не делает.
Но что мы теряем. Очень большая вероятность забыть, что это value-тип, и передать его по значению, а значит, на каждой такой передаче будет копирование содержимого, не говоря уже о том, что если такой словарик отдать в функцию, которая его наполняет, она наполнит копию, а не исходный словарь.
Как мне кажется, больше граблей, чем пользы.
teoadal Автор
00.00.0000 00:00Мы, вроде, с вами читаем одни и те же вещи, но понимаем их по разному. Я ещё раз напомню, что моё утверждение состоит в следующем: использовать структуры для увеличения производительности это хороший способ избежать callvirt.
Вот я взял и создал класс Glossary, скопировал в него код структуры, запечатал. Создал такой же класс, но не запечатывал его. Смотрим измерений производительности. Как и предсказывалось: структура быстрее, за счёт того, что есть call, а не callvirt.| Method | Runtime | Mean | Ratio | |----------------------------- |------------------- |---------:|------:| | DictionaryTryGetValue | .NET 6.0 | 4.085 us | 1.00 | | GlossaryTryGetValue | .NET 6.0 | 1.741 us | 0.43 | | GlossaryNonSealedTryGetValue | .NET 6.0 | 2.551 us | 0.63 | | GlossarySealedTryGetValue | .NET 6.0 | 2.499 us | 0.61 | | | | | | | DictionaryTryGetValue | .NET 7.0 | 3.768 us | 1.00 | | GlossaryTryGetValue | .NET 7.0 | 1.510 us | 0.40 | | GlossaryNonSealedTryGetValue | .NET 7.0 | 2.638 us | 0.70 | | GlossarySealedTryGetValue | .NET 7.0 | 2.617 us | 0.70 | | | | | | | DictionaryTryGetValue | .NET Core 3.1 | 4.965 us | 1.00 | | GlossaryTryGetValue | .NET Core 3.1 | 2.534 us | 0.51 | | GlossaryNonSealedTryGetValue | .NET Core 3.1 | 2.526 us | 0.51 | | GlossarySealedTryGetValue | .NET Core 3.1 | 2.528 us | 0.51 | | | | | | | DictionaryTryGetValue | .NET Framework 4.8 | 6.965 us | 1.00 | | GlossaryTryGetValue | .NET Framework 4.8 | 2.575 us | 0.37 | | GlossaryNonSealedTryGetValue | .NET Framework 4.8 | 2.546 us | 0.37 | | GlossarySealedTryGetValue | .NET Framework 4.8 | 2.528 us | 0.37 |
teoadal Автор
00.00.0000 00:00
CallVirt в классе без sealed 
CallVirt в запечатанном классе 
Call в структуре qw1
00.00.0000 00:00-1Я не понимаю, почему в этом случае компилятор делает callvirt.
Может кто-то объяснить?
Ещё пример
mayorovp
00.00.0000 00:00Потому что вызов call не сделает проверку нулевого аргумента на null, что в свою очередь противоречит спецификации языка.
Но это не означает что там обязательно будет косвенный вызов.
qw1
00.00.0000 00:00-1Действительно, поигравшись с SharpLab, я убедился, что несмотря на callvirt в IL-коде, вызов может быть прямым для небольших методов (хотя чаще всего косвенный, но по константной ссылке, видимо чтобы jit легко мог заменить метод при более глубокой оптимизации).
Но даже с прямым вызовом, компилятор добавляет перед ним одну лишнюю инструкцию, например,
cmp [ecx], ecxесли ссылка на экземпляр лежит в
ecx, чтобы упасть на null-ссылке.
teoadal Автор
00.00.0000 00:00Как мне кажется, больше граблей, чем пользы
Я начну комментировать с конца вашего сообщения, так как я полностью согласен с этим утверждением. Вообще, заниматься производительностью это грабли, боль и унижение. Тем не менее, есть 1% случаев, когда это действительно нужно.
Посмотрим, что мы экономим на struct-словаре. Ровно одну аллокацию
Нет, мы экономим на каждом вызове методов словаря. И это только в контексте нашего обсуждения по call/callvirt. См. бенчмарки.
Одной аллокацией больше, одной меньше — погоды не делает.
Мне кажется, что вы рассуждаете с позиции, что для 99% разработчиков одна аллокация погоды не сделает. И это правда. Но есть случаи, когда просто необходима высокая производительность и насколько можно низкая аллокация. Даже за счёт экономии на спичках.
Очень большая вероятность забыть
Раньше я в самом начале своих статей писал более длинное и более развернутое предупреждение о том, что подобные эксперименты - только для специалистов и только для узкого круга случаев применения. В этот раз я ограничился фразой: 99% программистов этого не нужно, а подобные эксперименты без изучения environment'a будут даже опасны.
Я ещё раз скажу, что заниматься производительностью это грабли, боль и унижение. Прежде чем использовать подобные штуки в проде надо подумать миллион раз, потом миллион раз перепроверить, да ещё и тесты с бенчмарками написать. В этом случае вероятность ошибиться есть, но она крайне низка.
NoofSaeidh
00.00.0000 00:00Было бы интересно еще сравнить с новым FrozenDictionary (который правда пока только в превью .NET 8). Но там только GetValue / TryGetValue, без модификации словаря.
teoadal Автор
00.00.0000 00:00Если они сделают как обещали (оптимизация по чтению), то я уверен, что будет быстрее. Но мы, конечно, перепроверим после выхода net8.
Politura
Dictionary не стоит использовать для многопоточности (можно, но надо оборачивать в lock, или еще что-нибудь чтоб гарантировать, что разные потоки одновременно не будут с ним работать), для многопоточности есть ConcurrentDictionary, который как минимум раньше работал быстрее, чем Dictionary с локами.
teoadal Автор
Да, верное замечание.
В принципе,
ConcurrentDictionaryда, быстрее для случаев многопоточности, но есть способ сомнительный и не безопасный способ ускориться с Dictionary: вроде как ставить lock только при записи. Если найду пример и результаты бенчмарков - скину.mayorovp
А зачем нужны небезопасные способы?
teoadal Автор
Для повышения производительности или уменьшения аллокации там, где это нужно. Например, в библиотечном коде или коде таких проектов как RavenDB.
qw1
То есть если один раз на миллион чтений будет возникать IndexOutOfRangeException, потому что параллельно пишущий поток успел обновить _buckets, но не успел обновить _entries, этим можно пренебречь в RavenDB ради небольшого ускорения?
teoadal Автор
Я так сказал?
Мне кажется, что видел что-то вроде вот этого из RavenDB: своя имплементация lock-free dictionary.
qw1
Ну да, вот:
teoadal Автор
Коллега, странный спор, так как я не понимаю, к чему вы ведёте и какую мысль отстаиваете.
Отвечу по существу:
1. Я написал "вроде как". Я помню, что там был какой-то трюк, но вспомнил только lock-free.
2. Я разве писал про то, что код не будет работать в каких-то случаях? Я написал только про то, что мне помнится, что он был сомнительный и небезопасный. Есть разница между словом "небезопасный" и "неработающий".
3. Мне кажется, что у вас в голове сформировалось какая-то реализация, и вы предположили, что я имею ввиду именно эту реализацию. Почему? Я же чётко написал, что я её даже не помню.
mayorovp
Конкретно в случае потокобезопасности слова "небезопасный" и "неработающий" являются синонимами.
teoadal Автор
Мне кажется, что вы неправы. Моё мнение основывается на следующих шагах:
1. Берём любимый поисковик, вбиваем: "C# thread-safe mutex".
2. Убеждаемся, что mutex множество раз употребляется в контексте потокобезопасности.
3. Идём на github в код mutex'a. Вот сюда, например.
4. В открывшемся файле находим ключевое слово
unsafe.Вывод, который я делаю: слово "небезопасный" употребляется в случае потокобезопасности и не означает "неработающий".
mayorovp
"Способ с использованием небезопасного кода" и "небезопасный способ" — это не одно и то же.
teoadal Автор
Коллега, спор походит на лингвистический, с попытками толкования, основываясь на собственном мнении и без приведения аргументов.
Вы к чему ведёте-то в рамках темы?
mayorovp
К тому, что вот эта идея:
не работает независимо от лингвистических изысков. Можно хоть обложиться бенчмарками, но для кода, который приводит к случайным ошибкам, производительность не имеет значения.
teoadal Автор
Давайте говорить предметно.
1. О каком коде мы говорим? Давайте вы изложите его в виде того самого кода, который у вас в голове. Решение должно быть быстрее ConcurrentDictionary и потреблять меньше памяти, подтвердите это бенчмарками.
2. Потом мы его обсудим.
3. Потом мы его сравним с тем способом, который я не помню.
4. Убедимся, что это не тот способ.
5. Согласимся, что ваш способ ошибочен и так поступать не нужно.
И никто, заметьте, с этой умной мыслью не спорит. Наоборот, в самом конце статьи я про это и пишу - надо быть крайне осторожным. Код, который показывает хорошие бенчмарки, но не работает под нужным профилем нагрузки... ну он как бы не решает задачу, не рабочий.
mayorovp
О том, который вы предложили и описали.
Но вы спорите. Более того, вы явно предложили способ (ставить lock только при записи), который не даёт потокобезопасности, после чего вы написали что собираетесь делать для него бенчмарк.
NoofSaeidh
Если случаи многопоточного чтения редки, то обычного lock хватит. Если нет, можно использовать ReaderWriterLockSlim, но он может и для чтения замедлить производительность по сравнению с обычным локом, так что надо использовать осторожно. В большинстве случаев ConcurrectDictionary хватит.
teoadal Автор
Да, для 99% случаев я в обычном коде использую ConcurrentDictionary. Это сильно проще, чем городить высокопроизводительный код, который трудно поддерживать.
ReadWriteLockSlim я тоже использую. С ним, правда, есть нюанс. Если будет очень много читателей, то записывающий код будет ждать очень очень долго, прежде чем ему будет позволено записать что-то.
Там же не очередь, насколько я помню. Где-то в видео от коллег из JetBrains было, что они столкнулись с подобным, и им пришлось написать свой ReadWriteLockSlim, но с очередью.