這篇文章主要講解了“怎么理解List的擴(kuò)容機(jī)制”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“怎么理解List的擴(kuò)容機(jī)制”吧!
創(chuàng)新互聯(lián)是專業(yè)的昭化網(wǎng)站建設(shè)公司,昭化接單;提供成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行昭化網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!一:背景
1. 講故事
在前一篇大內(nèi)存排查中,我們看到了Dictionary正在做擴(kuò)容操作,當(dāng)時(shí)這個(gè)字典的count=251w,你把字典玩的66飛起,其實(shí)都是底層為你負(fù)重前行,比如其中的擴(kuò)容機(jī)制,當(dāng)你遇到幾百萬(wàn)甚至千萬(wàn)的大集合這個(gè)擴(kuò)容機(jī)制還真的需要挖一下,免的入戲太深,難以自拔。
為了方便講述,我準(zhǔn)備從List說(shuō)起,因?yàn)樗詈?jiǎn)單哈
二:List擴(kuò)容機(jī)制
1. 如何查看
要想看它的擴(kuò)容機(jī)制,可以用ILSpy去看看List的源碼即可,非常簡(jiǎn)單。
從源碼的 int num = (_items.Length == 0) ? 4 : (_items.Length * 2) 可以非常清楚的看到,4個(gè)空間起步,后面都是 *2 的擴(kuò)容,也就說(shuō)當(dāng)你有 2^(n-1) + 1 個(gè)元素,實(shí)際上你需要占用 2^n個(gè)空間。
下面我用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個(gè)元素的時(shí)候,再往其中塞入一個(gè)元素,僅僅是多一個(gè),在底層可是翻倍的空間占用哦,太可氣了,要想往深處看可以用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
可以清楚的看到,一個(gè)int[] 占用 16777240 byte /1024/1024 =16M,一個(gè) int[] 占用 33554456 byte/1024/1024 =32M,可這是翻倍的空間哈。
2. 真的以為是僅僅翻了一倍嗎?
為什么我要這么說(shuō)呢?仔細(xì)看看Capacity的Set實(shí)現(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ì)研讀,這個(gè)流程是先定義好新size的數(shù)組array,然后將老的數(shù)組(_items) copy到 新數(shù)組array中,然后將array的引用給了老的數(shù)組,不難看出真正的Size應(yīng)該是 array(32M) + _items(16M) =48M 才是真正的大小,只要GC沒(méi)有回收老的_items(16M),那就一直保持48M的大小,你說(shuō)呢?
要怎么驗(yàn)證呢? 大家可以用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,按照剛才的理論這個(gè)16777240的int[]應(yīng)該是沒(méi)有引用根的等待被GC回收,所以用!gcroot 把兩個(gè) int[] 都打印出來(lái)。
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 確實(shí)是沒(méi)有引用根,也就驗(yàn)證了其實(shí)真正的是48M,而不是32M,翻了2倍哦。。。有點(diǎn)小恐怖。
二: 如何壓縮
1. 系統(tǒng)提供的壓縮機(jī)制
回過(guò)頭來(lái)看 Capacity 屬性中的擴(kuò)容機(jī)制,你只需要將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();
}
從圖中可以看到,數(shù)組中的 8388608-4194305 =4194303 個(gè)int直接給滅掉了,優(yōu)化了空間。
2. 自定義List
其實(shí)問(wèn)題的根源出在了擴(kuò)容機(jī)制,舉個(gè)例子,如果當(dāng)length大于400w的時(shí)候,默認(rèn)情況下是翻倍成800w,有時(shí)候根據(jù)你的業(yè)務(wù)不需要翻到800w,其實(shí)500w就足夠了,這樣300w的虛占就可以免掉,所以必要的時(shí)候自己實(shí)現(xiàn)一個(gè)list,然后靈活控制它的擴(kuò)容機(jī)制。
感謝各位的閱讀,以上就是“怎么理解List的擴(kuò)容機(jī)制”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)怎么理解List的擴(kuò)容機(jī)制這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián),小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
網(wǎng)站名稱:怎么理解List的擴(kuò)容機(jī)制-創(chuàng)新互聯(lián)
分享地址:http://m.newbst.com/article34/hpgpe.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供標(biāo)簽優(yōu)化、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)站內(nèi)鏈、微信小程序、定制開(kāi)發(fā)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容