Почему массивы не могут быть обрезаны?

Ответ 1

Чтобы ответить на ваш вопрос, он связан с дизайном системы управления памятью.

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

Тогда возникает вопрос, почему он не был разработан таким образом. Ответ заключается в том, что система управления памятью сделала компромисс между эффективным использованием памяти и производительностью.

Например, большинство систем управления памятью не управляют памятью до байта. Вместо этого они разбивают память на 8 Кбайт кусков. Есть множество причин, из-за которых большинство из них находятся вокруг производительности.

Некоторые из причин связаны с тем, насколько хорошо процессор перемещает память. Например, скажем, что процессор был намного лучше при копировании 8 КБ данных одновременно, тогда он был при копировании 4 КБ. Тогда есть преимущество в производительности для хранения данных в 8 Кбайтах. Это будет компромисс дизайна на основе архитектуры процессора.

Существуют также алгоритмические компромиссы с производительностью. Например, скажем, изучая поведение большинства приложений, вы обнаружите, что 99% приложений времени выделяют блоки данных размером от 6 КБ до 8 КБ.

Если система памяти позволяла вам выделять и выпускать 4 КБ, она осталась бы с бесплатным блоком 4 КБ, который не сможет использовать 99% распределений. Если вместо того, чтобы выделять 8 КБ, хотя требуется только 4 КБ, он будет намного более многоразовым.

Рассмотрим еще один проект. Скажем, у вас есть список свободных мест памяти, которые могут быть любого размера, и был сделан запрос на выделение 2 Кбайт памяти. Один из подходов состоял бы в том, чтобы просмотреть список свободной памяти и найти ту, которая имеет размер не менее 2 КБ, но вы просматриваете весь список, чтобы найти этот самый маленький блок, или вы найдете первый, который достаточно большой, и используйте что.

Первый подход более эффективен, но медленнее, второй подход менее эффективен, но быстрее.

Это становится еще интереснее в таких языках, как С# и Java, которые имеют "управляемую память". В управляемой системе памяти память даже не освобождается; он просто перестает привыкать, что позже сборщик мусора, в некоторых случаях гораздо позже, обнаруживает и освобождает.

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

https://en.wikipedia.org/wiki/Memory_management

Ответ 2

Неиспользуемая память на самом деле не используется. Это задача любой реализации кучи, чтобы отслеживать дыры в куче. Как минимум, менеджер должен знать размер отверстия и должен отслеживать их местоположение. Это всегда стоит как минимум 8 байт.

В .NET System.Object играет ключевую роль. Все знают, что он делает, что не так очевидно, что он продолжает жить после сбора объекта. Два дополнительных поля в заголовке объекта (syncblock и type handle) затем превращаются в обратный и прямой указатель на предыдущий/следующий свободный блок. Он также имеет минимальный размер, 12 байтов в 32-битном режиме. Гарантирует, что всегда имеется достаточно места для хранения свободного размера блока после сбора объекта.

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

Ответ 3

Я искал ответ на ваш вопрос, так как я нашел для него очень интересный вопрос. Я нашел этот ответ, который имеет интересную первую строку:

Вы не можете освободить часть массива - вы можете только free() указатель, который вы получили от malloc(), и когда вы это сделаете, вы освободите все выделенное вами предложение.

Таким образом, проблема заключается в том, что регистр хранит память. Вы не можете просто освободить часть выделенного вами блока, вам нужно полностью освободить его или вообще не освободить. Это означает, что для освобождения этой памяти вам сначала нужно перенести данные. Я не знаю, делает ли управление памятью .NET что-то особенное в этом отношении, но я думаю, что это правило также относится к CLR.

Ответ 4

Я думаю, это потому, что старый массив не разрушен. Он по-прежнему существует, если на него ссылаются где-то еще, и он все еще может быть доступен. Вот почему новый массив создается в новой ячейке памяти.

Пример:

int[] original = new int[] { 1, 2, 3, 4, 5, 6 };
int[] otherReference = original; // currently points to the same object

Array.Resize(ref original, 3);

Console.WriteLine("---- OTHER REFERENCE-----");

for (int i = 0; i < otherReference.Length; i++)
{
    Console.WriteLine(i);
}

Console.WriteLine("---- ORIGINAL -----");

for (int i = 0; i < original.Length; i++)
{
    Console.WriteLine(i);
}

Печать

---- OTHER REFERENCE-----
0
1
2
3
4
5
---- ORIGINAL -----
0
1
2

Ответ 5

Для определения realloc существует две причины: во-первых, совершенно ясно, что нет гарантии, что вызов realloc с меньшим размером вернет тот же указатель. Если ваша программа делает это предположение, ваша программа нарушена. Даже если указатель тот же 99,99% времени. Если в середине множества пустого пространства есть большой блок, он может вызывать фрагментацию кучи, а затем realloc может свободно перемещать его, если это возможно.

Во-вторых, существуют реализации, где это абсолютно необходимо. Например, MacOS X имеет реализацию, где один большой блок памяти используется для выделения блоков malloc размером от 1 до 16 байт, другого большого блока памяти для блоков malloc от 17 до 32 байт, один для блоков malloc от 33 до 48 байтов и т.д. Это делает очень естественным, что любое изменение размера, которое остается в диапазоне от 33 до 48 байт, возвращает один и тот же блок, но изменение на 32 или 49 байтов должно перераспределять блок.

Нет гарантии для выполнения realloc. Но на практике люди не делают размер немного меньше. Основными случаями являются: Распределить память до предполагаемой верхней границы необходимого размера, заполнить ее, а затем изменить размер до фактического гораздо меньшего размера. Или выделите память, а затем измените ее на что-то очень маленькое, когда оно больше не понадобится.

Ответ 6

Только разработчики среды выполнения .NET могут рассказать вам свои фактические аргументы. Но я предполагаю, что безопасность памяти имеет первостепенное значение в .NET, и было бы очень дорого поддерживать как безопасность памяти, так и изменяемую длину массива, не говоря уже о том, насколько сложным будет любой код с массивами.

Рассмотрим простой случай:

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  fun ^= array[i];
}

Чтобы сохранить безопасность памяти, каждый доступ array должен быть проверен границами, гарантируя, что проверка границ не будет нарушена другими потоками (время выполнения .NET имеет гораздо более строгие гарантии, чем, скажем, компилятор C).

Итак, вам нужна потокобезопасная операция, которая считывает данные из массива, одновременно проверяя границы. Там нет такой инструкции для CPU, поэтому ваш единственный вариант - это примитив синхронизации. Ваш код превращается в:

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  lock (array)
  {
    if (i >= array.Length) throw new IndexOutOfBoundsException(...);

    fun ^= array[i];
  }
}

Излишне говорить, что это ужасно дорого. Обеспечение неизменной длины массива дает вам два больших преимущества:

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

В действительности, то, что на самом деле работает, заканчивается тем, что больше похоже на это:

var fun = 0;
var len = array.Length; // Provably safe

for (var i = 0; i < len; i++)
{
  // Provably safe, no bounds checking needed
  fun ^= array[i];
}

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

Теперь рассмотрим все плюсы и минусы добавления массива, уменьшающегося так, как вы хотите:

Плюсы:

• В очень редком случае, когда вы хотите уменьшить размер массива, это означает, что массив не нужно копировать, чтобы изменить его длину. Однако в будущем все же потребуется уплотнение кучи, которое требует большого количества копий.
• Если вы храните ссылки на объекты в массиве, вы можете получить некоторые преимущества от локализации кэш-памяти, если выделение массива и элементов будет выделено. Излишне говорить, что это даже реже, чем Pro # 1.

Минусы:

• Любой доступ к массиву станет ужасно дорогостоящим, даже в жестких циклах. Таким образом, каждый будет использовать код unsafe вместо этого, и там ваша безопасность памяти.
• Каждый отдельный код, относящийся к массивам, должен ожидать, что длина массива может измениться в любое время. Каждому доступу к массиву понадобится try ... catch (IndexOutOfRangeException), и все, итерации по массиву, должны иметь возможность иметь дело с изменяющимся размером - когда-либо задавались вопросом, почему вы не можете добавлять или удалять элементы из List<T>, которые вы повторяете?
• Огромная работа для команды CLR, которая не может использоваться на другой, более важной функции.

Есть некоторые детали реализации, которые делают это еще менее полезным. Самое главное, что куча .NET не имеет ничего общего с шаблонами malloc/free. Если мы исключим LOH, текущая куча MS.NET ведет себя совершенно по-другому:

• Выделения всегда сверху, как в стеке. Это делает затраты почти такими же дешевыми, как распределение стека, в отличие от malloc.
• Из-за шаблона распределения, на фактически "свободную" память, вы должны сжать кучу после выполнения коллекции. Это перемещает объекты так, чтобы заполнялись свободные пространства в куче, что делает верхнюю часть кучи ниже, что позволяет выделять больше объектов в куче или просто освобождать память для использования другими приложениями в системе.
• Чтобы помочь сохранить локальность кеша (в предположении, что объекты, которые обычно используются вместе, также распределены близко друг к другу, что является довольно хорошим предположением), это может включать перемещение каждого отдельного объекта в куче, который выше свободного места вниз. Таким образом, вы могли бы сохранить себе копию массива размером в 100 байтов, но в любом случае вам нужно переместить 100 MiB других объектов.

Кроме того, как Ханс объяснил очень хорошо в своем ответе, просто потому, что массив меньше, не обязательно означает, что в нем имеется достаточно места для меньшего массива в том же объеме памяти из-за заголовков объектов (помните, как .NET предназначен для обеспечения безопасности памяти. Знание правильного типа объекта является обязательным для среды выполнения). Но он не указывает на то, что даже если у вас достаточно памяти, вам все равно нужно переместить массив. Рассмотрим простой массив:

ObjectHeader,1,2,3,4,5

Теперь мы удаляем последние два элемента:

OldObjectHeader;NewObjectHeader,1,2,3

К сожалению. Нам нужен старый заголовок объекта, чтобы сохранить список свободного пространства, иначе мы не смогли бы правильно скомпилировать кучу. Теперь можно сделать так, что старый заголовок объекта будет перемещен за пределы массива, чтобы избежать копирования, но это еще одно осложнение. Это оказалось довольно дорогостоящей функцией для чего-то, что когда-либо будет использовать noöne.

И все это в управляемом мире. Но .NET предназначен для того, чтобы вы могли при необходимости упасть до небезопасного кода - например, при взаимодействии с неуправляемым кодом. Теперь, когда вы хотите передать данные в собственное приложение, у вас есть два варианта: вы нажимаете управляемый дескриптор, чтобы он не собирался и не перемещался, или вы копируете данные. Если вы выполняете короткий синхронный вызов, пиннинг очень дешевый (хотя и более опасный - у нативного кода нет никаких гарантий безопасности). То же самое касается, например, манипулирование данными в жестком цикле, например, при обработке изображений. Копирование данных явно не является вариантом. Если вы позволили Array.Resize изменить существующий массив, это сломается полностью, поэтому Array.Resize нужно будет проверить, существует ли дескриптор, связанный с массивом, который вы пытаетесь изменить, и вызывать исключение, если это произойдет.

Больше осложнений, гораздо труднее рассуждать (у вас будет масса удовольствия с отслеживанием ошибки, которая возникает только раз в то время, когда происходит так, что Array.Resize пытается изменить размер массива, который так и происходит в настоящее время привязаны к памяти).

Как объяснили другие, родной код не намного лучше. Хотя вам не нужно поддерживать одни и те же гарантии безопасности (что я бы не принимал в качестве выгоды, но хорошо), все еще есть сложности, связанные с тем, как вы распределяете и управляете памятью. Вызывается realloc, чтобы создать 5-элементный массив из 10 элементов? Ну, это либо будет скопировано, либо оно по-прежнему будет размером с массивом из 10 элементов, потому что нет никакого способа вернуть левую память любым разумным способом.

Итак, чтобы сделать краткое резюме: вы просите очень дорогостоящую функцию, которая была бы очень ограничена (если таковая имеется) в чрезвычайно редком сценарии и для которой существует простейшее обходное решение (создание собственного класс массива). Я не вижу, чтобы пропустить планку "Конечно, пусть это реализовано!":)

Ответ 7

В любой системе управления кучей может существовать множество сложных структур данных, работающих под капотом. Например, они могут хранить блоки в соответствии с их нынешним размером. Это добавило бы много осложнений, если бы блоки были разрешены "разделяться, расти и сокращаться". (И это действительно не сделает вещи "быстрее".)

Следовательно, реализация делает всегда безопасную вещь: он выделяет новый блок и перемещает значения по мере необходимости. Известно, что "эта стратегия всегда будет работать надежно, в любой системе". И это действительно не замедлит работу вообще.

Ответ 8

Под капотом массивы хранятся в блоке непрерывной памяти, но на многих языках все еще являются примитивными.

Чтобы ответить на ваш вопрос, пространство, выделенное для массива, рассматривается как один отдельный блок и хранится в stack в случае локальных переменных или bss/data segments, когда оно является глобальным. AFAIK, когда вы обращаетесь к массиву типа array[3], на низком уровне ОС выведет указатель на первый элемент и перепрыгнет/пропустит, пока он не достигнет (трижды в случае вышеприведенного примера) требуемого блока. Таким образом, может быть архитектурное решение, что размер массива не может быть изменен после его объявления.

Аналогичным образом ОС не может знать, является ли он действительным индексом массива, прежде чем он обратится к требуемому индексу. Когда он пытается получить доступ к запрошенному индексу, достигнув блока памяти после процесса jumping и узнает, что достигнутый блок памяти не является частью массива, он выкинет Exception