Comments 32
А как быть с многопоточностью?
Dictionary не стоит использовать для многопоточности (можно, но надо оборачивать в lock, или еще что-нибудь чтоб гарантировать, что разные потоки одновременно не будут с ним работать), для многопоточности есть ConcurrentDictionary, который как минимум раньше работал быстрее, чем Dictionary с локами.
Да, верное замечание.
В принципе, ConcurrentDictionaryда, быстрее для случаев многопоточности, но есть способ сомнительный и не безопасный способ ускориться с Dictionary: вроде как ставить lock только при записи. Если найду пример и результаты бенчмарков - скину.
А зачем нужны небезопасные способы?
Для повышения производительности или уменьшения аллокации там, где это нужно. Например, в библиотечном коде или коде таких проектов как RavenDB.
То есть если один раз на миллион чтений будет возникать IndexOutOfRangeException, потому что параллельно пишущий поток успел обновить _buckets, но не успел обновить _entries, этим можно пренебречь в RavenDB ради небольшого ускорения?
Я так сказал?
Мне кажется, что видел что-то вроде вот этого из RavenDB: своя имплементация lock-free dictionary.
Я так сказал?
Ну да, вот:
способ сомнительный и не безопасный способ ускориться с Dictionary: вроде как ставить lock только при записи
Коллега, странный спор, так как я не понимаю, к чему вы ведёте и какую мысль отстаиваете.
Отвечу по существу:
1. Я написал "вроде как". Я помню, что там был какой-то трюк, но вспомнил только lock-free.
2. Я разве писал про то, что код не будет работать в каких-то случаях? Я написал только про то, что мне помнится, что он был сомнительный и небезопасный. Есть разница между словом "небезопасный" и "неработающий".
3. Мне кажется, что у вас в голове сформировалось какая-то реализация, и вы предположили, что я имею ввиду именно эту реализацию. Почему? Я же чётко написал, что я её даже не помню.
Конкретно в случае потокобезопасности слова "небезопасный" и "неработающий" являются синонимами.
Мне кажется, что вы неправы. Моё мнение основывается на следующих шагах:
1. Берём любимый поисковик, вбиваем: "C# thread-safe mutex".
2. Убеждаемся, что mutex множество раз употребляется в контексте потокобезопасности.
3. Идём на github в код mutex'a. Вот сюда, например.
4. В открывшемся файле находим ключевое слово unsafe.
Вывод, который я делаю: слово "небезопасный" употребляется в случае потокобезопасности и не означает "неработающий".
"Способ с использованием небезопасного кода" и "небезопасный способ" — это не одно и то же.
Коллега, спор походит на лингвистический, с попытками толкования, основываясь на собственном мнении и без приведения аргументов.
Вы к чему ведёте-то в рамках темы?
К тому, что вот эта идея:
есть способ сомнительный и не безопасный способ ускориться с Dictionary: вроде как ставить lock только при записи
не работает независимо от лингвистических изысков. Можно хоть обложиться бенчмарками, но для кода, который приводит к случайным ошибкам, производительность не имеет значения.
Давайте говорить предметно.
для кода...
1. О каком коде мы говорим? Давайте вы изложите его в виде того самого кода, который у вас в голове. Решение должно быть быстрее ConcurrentDictionary и потреблять меньше памяти, подтвердите это бенчмарками.
2. Потом мы его обсудим.
3. Потом мы его сравним с тем способом, который я не помню.
4. Убедимся, что это не тот способ.
5. Согласимся, что ваш способ ошибочен и так поступать не нужно.
...который приводит к случайным ошибкам, производительность не имеет значения
И никто, заметьте, с этой умной мыслью не спорит. Наоборот, в самом конце статьи я про это и пишу - надо быть крайне осторожным. Код, который показывает хорошие бенчмарки, но не работает под нужным профилем нагрузки... ну он как бы не решает задачу, не рабочий.
О каком коде мы говорим?
О том, который вы предложили и описали.
И никто, заметьте, с этой умной мыслью не спорит.
Но вы спорите. Более того, вы явно предложили способ (ставить lock только при записи), который не даёт потокобезопасности, после чего вы написали что собираетесь делать для него бенчмарк.
Если случаи многопоточного чтения редки, то обычного lock хватит. Если нет, можно использовать ReaderWriterLockSlim, но он может и для чтения замедлить производительность по сравнению с обычным локом, так что надо использовать осторожно. В большинстве случаев ConcurrectDictionary хватит.
Да, для 99% случаев я в обычном коде использую ConcurrentDictionary. Это сильно проще, чем городить высокопроизводительный код, который трудно поддерживать.
ReadWriteLockSlim я тоже использую. С ним, правда, есть нюанс. Если будет очень много читателей, то записывающий код будет ждать очень очень долго, прежде чем ему будет позволено записать что-то.
Там же не очередь, насколько я помню. Где-то в видео от коллег из JetBrains было, что они столкнулись с подобным, и им пришлось написать свой ReadWriteLockSlim, но с очередью.
Более того, очень бы хотелось иметь возможность получать ссылку (ref) на значение в Dictionary, чтобы можно было изменять содержимое извне.
Начиная с .NET 6 есть CollectionsMarshal.GetValueRefOrNullRef
runtime'у не надо будет выяснять по таблице виртуальных методов, кому принадлежит этот метод. Это, в свою очередь, облегчит inline методов — одну из самых эффективных методик оптимизации скорости.
Может, я забыл чего в .NET, но если метод невиртуальный, то и выяснять ничего не придётся.
Возможно, я выразился не очень точно. Я говорил об IL-коде, где вызов статического метода это call, вызов не статического метода - всегда callvirt(даже если метод не помечен ключевым словом virtual).
Вызов методов структур похож на статические методы, там тоже call, который несколько быстрее, чем callvirt.
Прочитать можно вот тут и тут.
Про call и callvirt можно тоже прочитать.
вызов не статического метода - всегда callvirt.
Неверно. Нет такого "всегда" - в приведённых ссылках.
Соглашусь, слово "всегда" слишком сильное. В 80% случаев, кроме некоторых - вот тут относительно недавно обсуждалось.
Я хотел напомнить всё это лишь для того, чтобы объяснить почему я сказал относительно структур "runtime'у не надо будет выяснять по таблице виртуальных методов, кому принадлежит этот метод". Детально вдаваться в объяснения и пояснения, по которым люди пишут длинные посты и даже статьи я не намеревался.
В 80% случаев, кроме некоторых — вот тут относительно недавно обсуждалось
Так себе аргумент. Там перечислены случаи, когда нужна диспетчеризация. Например, если ваш класс наследовался бы от IDictionary, а клиентский код получил бы интерфейсную ссылку, а не обычную — то да, был бы callvirt. Но вы же не наследуетесь, значит, такой возможности в принципе не будет.
Посмотрим, что мы экономим на struct-словаре. Ровно одну аллокацию, сам класс словаря будет на стеке, а не в куче. Но учитывая, что внутри словаря есть ссылочные типы (массивы _buckets и _entries), нельзя сказать, что такой словарь gc-friendly. Одной аллокацией больше, одной меньше — погоды не делает.
Но что мы теряем. Очень большая вероятность забыть, что это value-тип, и передать его по значению, а значит, на каждой такой передаче будет копирование содержимого, не говоря уже о том, что если такой словарик отдать в функцию, которая его наполняет, она наполнит копию, а не исходный словарь.
Как мне кажется, больше граблей, чем пользы.
Мы, вроде, с вами читаем одни и те же вещи, но понимаем их по разному. Я ещё раз напомню, что моё утверждение состоит в следующем: использовать структуры для увеличения производительности это хороший способ избежать 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 |
Я не понимаю, почему в этом случае компилятор делает callvirt.
Может кто-то объяснить?
Ещё пример
Потому что вызов call не сделает проверку нулевого аргумента на null, что в свою очередь противоречит спецификации языка.
Но это не означает что там обязательно будет косвенный вызов.
Действительно, поигравшись с SharpLab, я убедился, что несмотря на callvirt в IL-коде, вызов может быть прямым для небольших методов (хотя чаще всего косвенный, но по константной ссылке, видимо чтобы jit легко мог заменить метод при более глубокой оптимизации).
Но даже с прямым вызовом, компилятор добавляет перед ним одну лишнюю инструкцию, например,
cmp [ecx], ecxесли ссылка на экземпляр лежит в ecx, чтобы упасть на null-ссылке.
Как мне кажется, больше граблей, чем пользы
Я начну комментировать с конца вашего сообщения, так как я полностью согласен с этим утверждением. Вообще, заниматься производительностью это грабли, боль и унижение. Тем не менее, есть 1% случаев, когда это действительно нужно.
Посмотрим, что мы экономим на struct-словаре. Ровно одну аллокацию
Нет, мы экономим на каждом вызове методов словаря. И это только в контексте нашего обсуждения по call/callvirt. См. бенчмарки.
Одной аллокацией больше, одной меньше — погоды не делает.
Мне кажется, что вы рассуждаете с позиции, что для 99% разработчиков одна аллокация погоды не сделает. И это правда. Но есть случаи, когда просто необходима высокая производительность и насколько можно низкая аллокация. Даже за счёт экономии на спичках.
Очень большая вероятность забыть
Раньше я в самом начале своих статей писал более длинное и более развернутое предупреждение о том, что подобные эксперименты - только для специалистов и только для узкого круга случаев применения. В этот раз я ограничился фразой: 99% программистов этого не нужно, а подобные эксперименты без изучения environment'a будут даже опасны.
Я ещё раз скажу, что заниматься производительностью это грабли, боль и унижение. Прежде чем использовать подобные штуки в проде надо подумать миллион раз, потом миллион раз перепроверить, да ещё и тесты с бенчмарками написать. В этом случае вероятность ошибиться есть, но она крайне низка.
Было бы интересно еще сравнить с новым FrozenDictionary (который правда пока только в превью .NET 8). Но там только GetValue / TryGetValue, без модификации словаря.
Dictionary<int, T>: очень специальный