Большая стоимость размещения нового массива в .net

Question

Какова большая O-временная сложность выделения массива в .Net?

Я предполагаю, что если массив достаточно мал, чтобы поместиться в эфемерный сегмент, он должен быть O (1), ночто при увеличении n становится все труднее найти достаточно памяти, чтобы она могла измениться.

Кроме того, куча больших объектов может быть фрагментирована, поэтому, если n достаточно велико, чтобы массив поместился в LOH, это, вероятно,не будет O (1).

Answer 1

Новый массив будет размещен в двух разных кучах, как большинство, вероятно, знают, в зависимости от его размера (и порог размера составляет 85000 байт):

• Куча малых объектов - здесь происходит распределениев так называемом контексте выделения , который является предварительно обнуленной областью памяти, расположенной внутри эфемерного сегмента.Здесь может произойти два сценария:
  • достаточно места для нового массива в текущем контексте выделения - в таком случае мы можем рассматривать это как операцию O (1), просто возвращая адрес для массива (и изменяя указатель)для следующих объектов)
  • там недостаточно места - будет пытаться увеличить контекст выделения с помощью кванта выделения (обычно около 8 кБ), если это возможно (как, например, вконец эфемерного сегмента).Здесь мы оцениваем стоимость обнуления этих 8 КБ, поэтому она значительно больше.Хуже того, контекст выделения может оказаться невозможным для расширения, поскольку он может находиться между уже выделенными объектами.В таком случае будет создан новый контекст размещения - где-то внутри эфемерного сегмента с помощью свободного списка, чтобы использовать фрагментацию.В этом случае стоимость еще больше - обход свободного списка, чтобы найти правильное место и затем обнуление его.Тем не менее, стоимость не зависит напрямую от размера массива и является «постоянной», поэтому мы можем рассматривать ее как O (1), как и ранее.
• куча больших объектов - потому что выделения здесьпо умолчанию гораздо реже, он использует контексты выделения «ad-hoc» - каждый раз, когда здесь происходит распределение, GC ищет подходящее место с помощью свободного списка и обнуляет его.Опять же, здесь происходит как обход свободного списка, так и обнуление памяти, но, поскольку объекты здесь большие, в основном преобладает обнуление стоимости.Здесь мы можем говорить о стоимости O (n).

В случае выделения LOH следует знать о дополнительных скрытых «затратах» - такие распределения не происходят во время некоторых частей Фоновых GC (посколькуоба работают по свободному списку).Таким образом, если случится так, что у вас много длинных фоновых GC, выделение LOH будет приостановлено в ожидании завершения GC.Это, очевидно, приведет к нежелательным задержкам для ваших тем.

Answer 2

Объекты в эфемерном сегменте (SOH; куча небольших объектов) размещаются после последнего известного объекта в этом сегменте.Это должно быть просто указатель на это.

«Пустое» пространство между ними не будет рассматриваться, поскольку пустого пространства нет.Даже если у объекта больше нет ссылки, он все равно будет там, пока не будет собран мусор.Затем SOH будет сжат, поэтому опять нет свободных мест.

Если SOH недостаточно велик, то нужно выбрать другой или создать новый сегмент.Это займет больше времени, но все еще равно O (1).

LOH немного сложнее, так как обычно он не уплотняется.Существуют веб-сайты, которые заявляют, что у LOH есть «свободный список».Но я не уверен, действительно ли это реализация стиля списка.Я думаю, что он имеет лучшее управление и работает как словарь, поэтому он не должен быть хуже, чем O (log (n)).

Что нужно сделать?

• возможно получить новую память из ядра.Если это так, память уже была обнулена и memset () не требуется.
• , если эта новая память недоступна в ОЗУ, сначала замените что-либо на диск.Эта часть может стать очень дорогой, но непредсказуемой.
• Если память уже доступна в .NET, возможно, ее нужно инициализировать нулем.Но реализация memset () оптимизирована (например, с использованием rep stos)
• Инициализировать массив значениями откуда-то (например, из файла).Скорее всего, это будет цикл .NET, за исключением замены одной из дорогих частей.

Обычно я бы не стал беспокоиться о выделении памяти, если бы вы не использовали профилировщик (например,dotMemory), который рассказал вам о проблемах пропускной способности памяти.Доверьтесь Дональду Кнуту: «преждевременная оптимизация - корень всего зла».