为什么 List 使用的内存几乎是数组的 3 倍？

Question

我正在尝试向列表中添加大量数据，但它似乎比数组使用更多的 RAM。我想知道为什么会这样，是否有更好的解决方案。

这个带有数组的解决方案需要大约 78 MB 的 RAM。有意义，因为 4 字节 * 20000000 ~= 76 MB:

float[] arrayValues = new float[20000000];

for (int i = 0; i < 20000000; i++)
     arrayValues[i] = i;

但是这个带有列表的解决方案需要 206 MB (!!):

List<float> listValues = new();

for (int i = 0; i < 20000000; i++)
     listValues.Add(i);

怎么可能？它基本上在做同样的事情——保存 20000000 个浮点值。额外的 128 MB 是从哪里来的？有没有更好的方法不会产生这么多开销？

Answer 1

当您 Add 将新项目放入 List<T> 时，它必须进行 内存重新分配 才能为这些新项目提供足够的 space。让我们看看这个过程：

  List<float> listValues = new();

  int capacity = listValues.Capacity;

  for (int i = 0; i < 20000000; i++) {
    listValues.Add(i);

    if (capacity != listValues.Capacity) {
      capacity = listValues.Capacity;

      Console.WriteLine(capacity);
    }
  }

结果：

4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432 // <- Finally, list allocates memory for 33554432 items

如您所见，现在 33554432 项已分配，4 + 8 + 16 + ... + 16777216 是垃圾。在最坏的情况下，我们有 33554432 分配项目和 33554432 垃圾项目；总共 33554432 + 33554432 = 67108864 ~ 3 * 20000000，你可以看到这个 3 因素。

你能做什么？

指定Capacity以避免重新分配（典型解决方案）：

  // We can avoid all this mess with reallocations
  // by specifing required capacity: 20000000 items in our case 
  List<float> listValues = new(20000000);

  for (int i = 0; i < 20000000; i++) {
    listValues.Add(i);
  }

测量前收集所有垃圾：

  // Business as usual
  List<float> listValues = new();

  for (int i = 0; i < 20000000; i++) {
    listValues.Add(i);
  }

  // Collect garbage to measure real List efficency:
  // List allocates 33554432 items vs. 20000000 in case of array 
  // About ~70% overhead 
  GC.Collect(2);

为什么 List 使用的内存几乎是数组的 3 倍？

Why does a List use almost 3x the memory of an array?

c#

memory

list