为什么不能修剪数组？

Question

在MSDN文档站点上,它说明了以下有关该Array.Resize方法的信息:

如果newSize大于旧数组的Length,则分配一个新数组,并将所有元素从旧数组复制到新数组.

如果newSize小于旧数组的长度,则分配一个新数组,并将元素从旧数组复制到新数组,直到填充新数组为止.旧数组中的其余元素将被忽略.

数组是一系列相邻的存储块.如果我们需要一个更大的阵列,我理解我们不能为它添加内存,因为它旁边的内存可能已经被其他一些数据声明了.所以我们必须要求一个具有所需更大尺寸的新的相邻内存块序列,复制我们的条目并删除我们对旧空间的主张.

但为什么要创建一个更小尺寸的新阵列？为什么数组不仅可以删除它对最后一个内存块的声明？然后它将是O(1)操作而不是O(n),就像现在一样.

它是否与数据在计算机体系结构或物理层面的组织方式有关？

Answer 1

未使用的内存实际上并未使用.任何堆实现的工作都是跟踪堆中的漏洞.管理者至少需要知道洞的大小,并需要跟踪他们的位置.这总是花费至少8个字节.

在.NET中,System.Object起着关键作用.每个人都知道它做了什么,在收集一个物体后它继续存在的不那么明显.对象标题中的两个额外字段(同步块和类型句柄)然后变成指向前一个/下一个空闲块的向后和向前指针.它还具有最小大小,32位模式下12个字节.保证在收集对象后总是有足够的空间来存储空闲块大小.

所以你现在可能已经看到了问题,减小数组的大小并不能保证创建一个足够大的空洞来适应这三个字段.没有什么可以做,但抛出"不能做那个"的例外.还取决于过程的位数.完全太难看了.

Answer 2

要回答你的问题,它与内存管理系统的设计有关.

从理论上讲,如果你正在编写自己的内存系统,你可以完全按照你所说的方式设计它.

那么问题就变成了为什么不是这样设计的.答案是内存管理系统在有效使用内存与性能之间进行了权衡.

例如,大多数内存管理系统不管理内存到字节.相反,他们将内存分成8 KB的块.这有很多原因,其中大部分是围绕性能.

一些原因与处理器移动内存的程度有关.例如,假设处理器一次复制8 KB数据要好得多,那么复制4 KB就好了.然后,以8 KB块的形式存储数据有一个性能优势.这将是基于CPU架构的设计权衡.

还有算法性能权衡.例如,通过研究大多数应用程序的行为,您会发现99%的应用程序分配大小为6 KB到8 KB的数据块.

如果内存系统允许您分配和释放4KB,那么将留下一个具有免费4KB块的内存,99%的分配将无法使用.如果不是过度分配到8 KB,即使只需要4 KB,它也会更加可重用.

考虑另一种设计.假设您有一个可用内存位置列表,可以是任意大小,并且请求分配2KB内存.一种方法是查看您的可用内存列表并找到一个大小至少为2KB的内存,但是您是否查看整个列表以找到最小的块,或者您确实找到了第一个足够大并使用的内存那.

第一种方法效率更高,但速度更慢,第二种方法效率更低但速度更快.

它在C#和Java等具有"托管内存"的语言中变得更加有趣.在托管内存系统中,内存甚至没有被释放; 它只是停止使用,垃圾收集器稍后,在某些情况下很久以后会检测并释放.

有关不同内存管理和分配的更多信息,您可能需要查看Wikipedia上的这篇文章:

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

Answer 3

我正在寻找你的问题的答案,因为我发现它是一个非常有趣的问题.我发现这个答案有一个有趣的第一行:

你无法释放数组的一部分 - 你只能free()得到一个指针,malloc()当你这样做时,你将释放你所要求的所有分配.

所以实际上问题是寄存器保持分配哪个内存.你不能只是释放你已分配的块的一部分,你必须完全释放它,或者你根本不释放它.这意味着为了释放内存,您必须先移动数据.我不知道.NET内存管理在这方面是否做了一些特别的事情,但我认为这条规则也适用于CLR.

Answer 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

Answer 5

realloc的定义有两个原因:首先,它绝对清楚地表明不能保证调用较小大小的realloc会返回相同的指针.如果你的程序做出了这个假设,你的程序就会被破坏.即使指针在99.99%的时间内都是相同的.如果在大量空白空间的中间有一个大块,导致堆碎片,那么realloc可以自由地移动它,如果可能的话.

其次,有些实现绝对有必要这样做.例如,MacOS X有一个实现,其中一个大内存块用于分配1到16个字节的malloc块,另一个大内存块用于17到32个字节的malloc块,一个用于33到48个字节的malloc块等.这很自然地说,保持在范围内的任何大小更改(例如33到48个字节)都返回相同的块,但是更改为32或49个字节必须重新分配块.

无法保证realloc的性能.但实际上,人们并没有把尺寸缩小一点.主要情况是:将内存分配到所需大小的估计上限,填充它,然后调整大小到实际小得多的所需大小.或者分配内存,然后在不再需要时将其调整为非常小的内容.

Answer 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/ freepatterns 无关.如果我们排除LOH,当前的MS.NET堆的行为方式完全不同:

• 分配总是从顶部开始,就像在堆栈中一样.这使得分配几乎与堆栈分配一样便宜,不像malloc.
• 由于分配模式,实际上"释放"内存,您必须在执行收集后压缩堆.这将移动对象,以便填充堆中的空闲空间,这使堆的"顶部"更低,这允许您在堆中分配更多对象,或者只释放内存以供系统上的其他应用程序使用.
• 为了帮助维护缓存局部性(假设通常一起使用的对象也彼此靠近分配,这是一个非常好的假设),这可能涉及将堆中的每个单个对象移动到释放空间之上.所以你可能已经为自己保存了一个100字节数组的副本,但是无论如何你必须移动100 MiB的其他对象.

另外,正如Hans在他的回答中解释得非常好,仅仅是因为数组较小并不一定意味着在相同数量的内存中有足够的空间用于较小的数组,因为对象标题(记住.NET是如何设计的)内存安全？知道正确的对象类型是运行时必须的.但他没有指出的是,即使你有足够的内存,你仍然需要移动阵列.考虑一个简单的数组:

ObjectHeader,1,2,3,4,5

现在,我们删除最后两项:

OldObjectHeader;NewObjectHeader,1,2,3

哎呀.我们需要旧的对象头来保留自由空间列表,否则我们无法正确压缩堆.现在,可以将旧对象标题移动到数组之外以避免复制,但这又是另一个复杂问题.对于noöne将使用的东西来说,这实际上是一个非常昂贵的功能.

这一切都还在管理世界中.但.NET旨在允许您在必要时下载到不安全的代码 - 例如,在与非托管代码进行互操作时.现在,当您想要将数据传递给本机应用程序时,您有两个选项 - 要么固定托管句柄,要么阻止它被收集和移动,要么复制数据.如果您正在进行短暂的同步呼叫,则固定非常便宜(虽然更危险 - 本机代码没有任何安全保障).例如,在紧密循环中操纵数据也是如此,例如在图像处理中 - 复制数据显然不是一种选择.如果您允许Array.Resize更改现有数组,则会完全中断 - 因此Array.Resize需要检查是否存在与您尝试调整大小的数组关联的句柄,如果发生这种情况则抛出异常.

更多的复杂化,更难以推理(你将有很多乐趣跟踪只会偶尔发生一次的错误,当它发生这样的事情,Array.Resize试图调整一个恰好刚刚发生的数组时,会被固定在记忆).

正如其他人所解释的那样,本机代码并没有好多少.虽然你不需要保持相同的安全保证(我不会把它当作一个好处,但是很好),但是仍然存在与分配和管理内存相关的复杂问题.被称为realloc10项目阵列5项？好吧,它要么被复制,要么仍然是10项数组的大小,因为没有办法以任何合理的方式回收剩余的内存.

因此,快速总结一下:你要求的是一个非常昂贵的功能,在一个非常罕见的情况下效果非常有限(如果有的话),并且存在一个简单的解决方法(制作你自己的数组类) .我没有看到通过标杆"当然,让我们实现这个功能!" :)