一文看懂C#中List的扩容机制_c#

一：背景

1. 讲故事

在前一篇大内存排查中，我们看到了dictionary正在做扩容操作，当时这个字典的count=251w，你把字典玩的66飞起，其实都是底层为你负重前行，比如其中的扩容机制，当你遇到几百万甚至千万的大集合这个扩容机制还真的需要挖一下，免的入戏太深，难以自拔。

二：list扩容机制

1. 如何查看

要想看它的扩容机制，可以用ilspy去看看list的源码即可，非常简单。

从源码的 int num = (_items.length == 0) ? 4 : (_items.length * 2) 可以非常清楚的看到，4个空间起步，后面都是 *2 的扩容，也就说当你有 2^(n-1) + 1 个元素，实际上你需要占用 2^n个空间。

下面我用c#代码演示一下：

 static void main(string[] args)
 {
  var list1 = enumerable.range(0, (int)math.pow(2, 22)).tolist();

  var list2 = new list<int>(list1);
  list2.add(1);

  console.writeline($"list1.capacity={list1.capacity}");
  console.writeline($"list2.capacity={list2.capacity}");

  console.readline();
 }

 ------ output -------

list1.capacity=4194304
list2.capacity=8388608

从代码中可以看到，当list中已有 4194304个元素的时候，再往其中塞入一个元素，仅仅是多一个，在底层可是翻倍的空间占用哦，太可气了，要想往深处看可以用windbg看一下各自数组占用大小。

0:000> !dumpobj /d 000001ec037d2e20
name: system.collections.generic.list`1[[system.int32, mscorlib]]
fields:
  mt field offset   type vt attr  value name
00007ffde2ac8538 400189e 8 system.int32[] 0 instance 000001ec147b9c10 _items
00007ffde2ac85a0 400189f 18  system.int32 1 instance  4194304 _size
00007ffde2ac85a0 40018a0 1c  system.int32 1 instance  4194304 _version
00007ffde2ac5dd8 40018a1 10 system.object 0 instance 0000000000000000 _syncroot
00007ffde2ac8538 40018a2 0 system.int32[] 0 shared  static _emptyarray
     >> domain:value dynamic statics nyi 000001ec01bc0920:notinit <<

0:000> !do 000001ec147b9c10
name: system.int32[]
methodtable: 00007ffde2ac8538
eeclass: 00007ffde2c35918
size: 16777240(0x1000018) bytes
array: rank 1, number of elements 4194304, type int32 (print array)
fields:
none


0:000> !do 000001ec037d2e78
name: system.collections.generic.list`1[[system.int32, mscorlib]]
methodtable: 00007ffde2ada068
eeclass: 00007ffde2c3b008
size: 40(0x28) bytes
file: c:\windows\microsoft.net\assembly\gac_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
fields:
  mt field offset   type vt attr  value name
00007ffde2ac8538 400189e 8 system.int32[] 0 instance 000001ec167b9c80 _items
00007ffde2ac85a0 400189f 18  system.int32 1 instance  4194305 _size
00007ffde2ac85a0 40018a0 1c  system.int32 1 instance  1 _version
00007ffde2ac5dd8 40018a1 10 system.object 0 instance 0000000000000000 _syncroot
00007ffde2ac8538 40018a2 0 system.int32[] 0 shared  static _emptyarray
     >> domain:value dynamic statics nyi 000001ec01bc0920:notinit <<
0:000> !do 000001ec167b9c80
name: system.int32[]
methodtable: 00007ffde2ac8538
eeclass: 00007ffde2c35918
size: 33554456(0x2000018) bytes
array: rank 1, number of elements 8388608, type int32 (print array)
fields:
none

可以清楚的看到,一个int[] 占用 16777240 byte /1024/1024 =16m，一个 int[] 占用 33554456 byte/1024/1024 =32m,可这是翻倍的空间哈。

2. 真的以为是仅仅翻了一倍吗？

为什么我要这么说呢？仔细看看capacity的set实现，如下代码：

public int capacity
{
	get{ return _items.length; }
	set
	{
		if (value > 0)
		{
			t[] array = new t[value];
			if (_size > 0)
			{
				array.copy(_items, 0, array, 0, _size);
			}
			_items = array;
		}
	}
}

大家仔细研读，这个流程是先定义好新size的数组array，然后将老的数组(_items) copy到新数组array中，然后将array的引用给了老的数组,不难看出真正的size应该是 array(32m) + _items（16m） =48m 才是真正的大小，只要gc没有回收老的_items(16m)那就一直保持48m的大小，你说呢？

要怎么验证呢? 大家可以用windbg去看看托管堆中 int[] 不就可以啦。

var list1 = enumerable.range(0, (int)math.pow(2, 22)).tolist();
list1.add(1);

0:000> !dumpheap -mt 00007ffde2ac8538 -min 102400
  address  mt size
0000024c103e9ba0 00007ffde2ac8538 4194328 
0000024c107e9bd8 00007ffde2ac8538 8388632 
0000024c10fe9c10 00007ffde2ac8538 16777240 
0000024c11fe9c48 00007ffde2ac8538 33554456 

statistics:
  mt count totalsize class name
00007ffde2ac8538 4 62914656 system.int32[]
total 4 objects

从信息中看(16777240 + 33554456)byte = 48m，按照刚才的理论这个16777240的int[]应该是没有引用根的等待被gc回收，所以用!gcroot 把两个 int[] 都打印出来。

0:000> !gcroot 0000024c10fe9c10
found 0 unique roots (run '!gcroot -all' to see all roots).

0:000> !gcroot 0000024c11fe9c48
thread 63dc:
 0000007b4abfee60 00007ffd85950938 consoleapp6.program.main(system.string[]) [c:\dream\csharp\consoleapp1\consoleapp6\program.cs @ 28]
 rbp-38: 0000007b4abfee88
  -> 0000024c00002da0 system.collections.generic.list`1[[system.int32, mscorlib]]
  -> 0000024c11fe9c48 system.int32[]

found 1 unique roots (run '!gcroot -all' to see all roots).

可以看到：0000024c10fe9c10 确实是没有引用根，也就验证了其实真正的是48m，而不是32m，翻了2倍哦。。。有点小恐怖。

二：如何压缩

1. 系统提供的压缩机制

回过头来看 capacity 属性中的扩容机制，你只需要将capacity设置与count平齐，_items数组多余的虚占空间就给清掉了。

static void main(string[] args)
 {
  var list1 = enumerable.range(0, (int)math.pow(2, 22)).tolist();
  list1.add(1);
  list1.capacity = list1.count;

  console.readline();
 }