詳解C#中List的擴容機制

發(fā)布時間：2020-07-20 16:21:58 來源：億速云閱讀：206 作者：小豬欄目：編程語言

小編這次要給大家分享的是詳解C#中List的擴容機制，文章內(nèi)容豐富，感興趣的小伙伴可以來了解一下，希望大家閱讀完這篇文章之后能夠有所收獲。

一：背景

1. 講故事

在前一篇大內(nèi)存排查中，我們看到了Dictionary正在做擴容操作，當(dāng)時這個字典的count=251w，你把字典玩的66飛起，其實都是底層為你負(fù)重前行，比如其中的擴容機制，當(dāng)你遇到幾百萬甚至千萬的大集合這個擴容機制還真的需要挖一下，免的入戲太深，難以自拔。

詳解C#中List的擴容機制

二：List擴容機制

1. 如何查看

要想看它的擴容機制，可以用ILSpy去看看List的源碼即可，非常簡單。

詳解C#中List的擴容機制

從源碼的 int num = (_items.Length == 0) ? 4 : (_items.Length * 2) 可以非常清楚的看到，4個空間起步，后面都是 *2 的擴容，也就說當(dāng)你有 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

從代碼中可以看到，當(dāng)List中已有 4194304個元素的時候，再往其中塞入一個元素，僅僅是多一個，在底層可是翻倍的空間占用哦，太可氣了，要想往深處看可以用windbg看一下各自數(shù)組占用大小。

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. 真的以為是僅僅翻了一倍嗎？

為什么我要這么說呢？仔細(xì)看看Capacity的Set實現(xiàn)，如下代碼：

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;
		}
	}
}

大家仔細(xì)研讀，這個流程是先定義好新size的數(shù)組array，然后將老的數(shù)組(_items) copy到新數(shù)組array中，然后將array的引用給了老的數(shù)組,不難看出真正的Size應(yīng)該是 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[]應(yīng)該是沒有引用根的等待被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. 系統(tǒng)提供的壓縮機制

回過頭來看 Capacity 屬性中的擴容機制，你只需要將Capacity設(shè)置與Count平齊，_items數(shù)組多余的虛占空間就給清掉了。

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();
 }

詳解C#中List的擴容機制

從圖中可以看到，數(shù)組中的 8388608-4194305 =4194303 個int直接給滅掉了，優(yōu)化了空間。

2. 自定義List

其實問題的根源出在了擴容機制，舉個例子，如果當(dāng)length大于400w的時候，默認(rèn)情況下是翻倍成800w，有時候根據(jù)你的業(yè)務(wù)不需要翻到800w，其實500w就足夠了，這樣300w的虛占就可以免掉，所以必要的時候自己實現(xiàn)一個list，然后靈活控制它的擴容機制，妙哉妙哉~~~

五：總結(jié)

明白擴容機制對你了解在大數(shù)據(jù)量下使用List還是非常有幫助的，大家根據(jù)自己的場景合理化使用，下一篇我們聊一聊HashSet。

看完這篇關(guān)于詳解C#中List的擴容機制的文章，如果覺得文章內(nèi)容寫得不錯的話，可以把它分享出去給更多人看到。

向AI問一下細(xì)節(jié)

詳解C#中List的擴容機制

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽