...что-то заигрался я в бенчмарки, но тут интересное:
NET8
При добавлении заранее отсортированных элементов у SortedList скорость ожидаемо растёт, а у SortedDictionary - неожиданно падает. Хотя если подумать - слишком часто приходится перебалансировать дерево.
В общем, нюансов у этих Sorted* масса, как я уже писал: если нужна производительность - скорее всего придётся писать своё специализированное.
А, ну и да - SortedDictionary выделяет память в куче при каждом добавлении - это означает, что его не имеет особого смысла пулить/переиспользовать, а вот SortedList - стоит.
Плюс у SortedList можно установить Capacity, и он не будет выделять новые массивы при добалении элементов в рамках установленной capacity.
Ну и ещё одна мелочь - внутри у SortedList не список, а два массива - ключи и значения.
SortedList может выиграть (за счет более компактного представления в памяти) в сценарии, когда
SortedList выигрывает в любом сценарии, когда нам нужна именно отсортированная коллекция - он гораздо лучше при перечислении (плюс предоставляет доступ по индексу). SortedDictionary при каждом вызове GetEnumerator создаёт Stack и в дальнейшем его использует, что может приводить к выделению одного или более массивов в куче - в зависимости от глубины дерева.
Если же нам не нужен доступ перечислением - то нам не нужны и SortedList/SortedDictionary, логично?
Но и при добавлении и поиске в NET6/NET7 SortedList БЫЛ лучше - я поднял некоторые свои бенчмарки и обнаружил, что в NET8 SortedDictionary наконец-то стал быстрее при добавлении и поиске - приятный сюрприз, нужно будет посмотреть, что они изменили.
О чём я ещё забыл и сейчас обнаружил - SortedList тоже выделяет память в куче при каждом вызове GetEnumerator - но выделяет константный объём, 48 байтов. Не помню и не смотрел, что именно он выделяет, но это в любом случае лучше, чем Stack в SortedDictionary.
В качестве обмена опытом: в сценариях, где важна [даже относительно] высокая производительность SortedDictionary не подходит: производительность добавления ожидаемая, но на каждое добавление происходить выделение памяти, скорость поиска ожидаемо невысокая, перечисление медленное, при перечислении выделяет память.
SortedList, к слову, тоже так себе. Не помню уже кто был быстрее, кто медленнее, помоему SortedList побыстрее, но точно размещает меньше индивидуальных инстанцев в куче.
При необходимости рекомендую проанализировать сценарий и написать свой специализированный компонент.
С другой стороны, в клиентском приложении на ЮИ не на горячем пути вполне применим.
Возможно не стоит, а возможно и стоит - написание руками класса с полем и методом, повторяющим то, что сделал бы компилятор для лямбды - это разумно/упрощает/стоит того?
Я склоняюсь к тому, что универсального ответат нет, зато выбор есть.
Про замыкания, ну бокс бог с ним - не будем называть это прямо "боксингом"
Не "не будем", а "нельзя".
Боксинг - хоть в .НЕТ, хоть в абстрактном CS-определении - это не "копировние из стека в кучу" и кроме аллокации тянет за собой и вычислительные расходы.
В случае с захватом этого не происходит.
Более того, и самой локальной переменной на стеке вообще [в большинстве случаев] не окажется, она сразу будет определена в классе, созданном компилятором для лямбды.
но факт, что (возможно, нежелательное) копирование из стека в кучу при замыкании вполне возможно
Не "вполне возможно", а обязательно произойдёт, бай дизайн, так сказать.
When a callvirtmethod instruction has been prefixed by constrainedthisType, the instruction is executed as follows:
If thisType is a reference type (as opposed to a value type) then ptr is dereferenced and passed as the 'this' pointer to the callvirt of method.
If thisType is a value type and thisType implements method then ptr is passed unmodified as the 'this' pointer to a callmethod instruction, for the implementation of method by thisType.
If thisType is a value type and thisType does not implement method then ptr is dereferenced, boxed, and passed as the 'this' pointer to the callvirtmethod instruction.
This last case can occur only when method was defined on Object, ValueType, or Enum and not overridden by thisType. In this case, the boxing causes a copy of the original object to be made. However, because none of the methods of Object, ValueType, and Enum modify the state of the object, this fact cannot be detected.
Но ок, box в IL действительно нет, спасибо за напоминание.
А в чём суть возражений?
...что-то заигрался я в бенчмарки, но тут интересное:
При добавлении заранее отсортированных элементов у SortedList скорость ожидаемо растёт, а у SortedDictionary - неожиданно падает. Хотя если подумать - слишком часто приходится перебалансировать дерево.
В общем, нюансов у этих Sorted* масса, как я уже писал: если нужна производительность - скорее всего придётся писать своё специализированное.
А, ну и да - SortedDictionary выделяет память в куче при каждом добавлении - это означает, что его не имеет особого смысла пулить/переиспользовать, а вот SortedList - стоит.
Плюс у SortedList можно установить Capacity, и он не будет выделять новые массивы при добалении элементов в рамках установленной capacity.
Ну и ещё одна мелочь - внутри у SortedList не список, а два массива - ключи и значения.
SortedList выигрывает в любом сценарии, когда нам нужна именно отсортированная коллекция - он гораздо лучше при перечислении (плюс предоставляет доступ по индексу). SortedDictionary при каждом вызове GetEnumerator создаёт Stack и в дальнейшем его использует, что может приводить к выделению одного или более массивов в куче - в зависимости от глубины дерева.
Если же нам не нужен доступ перечислением - то нам не нужны и SortedList/SortedDictionary, логично?
Но и при добавлении и поиске в NET6/NET7 SortedList БЫЛ лучше - я поднял некоторые свои бенчмарки и обнаружил, что в NET8 SortedDictionary наконец-то стал быстрее при добавлении и поиске - приятный сюрприз, нужно будет посмотреть, что они изменили.
О чём я ещё забыл и сейчас обнаружил - SortedList тоже выделяет память в куче при каждом вызове GetEnumerator - но выделяет константный объём, 48 байтов. Не помню и не смотрел, что именно он выделяет, но это в любом случае лучше, чем Stack в SortedDictionary.
Результат бенчмарка для NET8 и NET7:
Накладными расходами, очевидно.
В качестве обмена опытом: в сценариях, где важна [даже относительно] высокая производительность SortedDictionary не подходит: производительность добавления ожидаемая, но на каждое добавление происходить выделение памяти, скорость поиска ожидаемо невысокая, перечисление медленное, при перечислении выделяет память.
SortedList, к слову, тоже так себе. Не помню уже кто был быстрее, кто медленнее, помоему SortedList побыстрее, но точно размещает меньше индивидуальных инстанцев в куче.
При необходимости рекомендую проанализировать сценарий и написать свой специализированный компонент.
С другой стороны, в клиентском приложении на ЮИ не на горячем пути вполне применим.
Поддерживаю вопрос товарища @dopusteam
У меня есть несколько догадок касательно того, что имелось ввиду, но ни в одной не уверен.
А когда локальная переменная передаётся как ref - она перестаёт работать как локальная?
Для рантайма она больше не локальная переменная, но это скрыто и незаметно (пока не упираемся в особые случаи типа ref [struct]). Ну, чтож.
Возможно не стоит, а возможно и стоит - написание руками класса с полем и методом, повторяющим то, что сделал бы компилятор для лямбды - это разумно/упрощает/стоит того?
Я склоняюсь к тому, что универсального ответат нет, зато выбор есть.
Не "не будем", а "нельзя".
Боксинг - хоть в .НЕТ, хоть в абстрактном CS-определении - это не "копировние из стека в кучу" и кроме аллокации тянет за собой и вычислительные расходы.
В случае с захватом этого не происходит.
Более того, и самой локальной переменной на стеке вообще [в большинстве случаев] не окажется, она сразу будет определена в классе, созданном компилятором для лямбды.
Не "вполне возможно", а обязательно произойдёт, бай дизайн, так сказать.
Ноль вопросов, никаких личностей, просто я (лично) считаю, что учиться никогда не поздно и не зазорно, а иногда ещё и нужно ;)
Вообще, не сказал бы, что прям неявно:
https://learn.microsoft.com/en-us/dotnet/api/system.reflection.emit.opcodes.constrained?view=net-8.0&redirectedfrom=MSDN
Но ок, box в IL действительно нет, спасибо за напоминание.
Тем не менее, что насчёт обсуждаемого случая?
Есть там цитата?
Отлично, первые шаги к изучению учебника сделаны.
А можно теперь конкретную цитату, которая относится к обсуждаемому случаю?
Любопытно было бы увидеть примеры, не поделитесь?
...но это, к примеру, легко доступная элементарная оптимизация:
Объявляем локальную переменну, объявляем лямбду, которая её захватывает.
В цикле n раз изменяем значение переменной и вызываем метод, в который передаём лямбду - итого одна аллокация вместо n
Всё может быть чревато :)
С "проблемой цикла" можно научиться жить, а вот невозможность изменять захваченную переменную - мне бы мешало.
А вот это можно почитать и в учебнике.
Жаль нельзя на большие деньги поспорить, погулял бы на НГ за чужой счёт в кои-то веки.
Повторю: боксинга нет, ref struct захватывать нельзя по другой причине (да, именно из-за отъезда в кучу).
"Уезжать в кучу" != боксинг.
нет там никакого боксинга.
Большое спасибо.
А можете добавить в бенчмарки измерение аллокаций и GC?