List的扩容机制,你真的明白吗?
source link: http://www.cnblogs.com/huangxincheng/p/12954569.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一:背景
1. 讲故事
在前一篇大内存排查中,我们看到了Dictionary正在做扩容操作,当时这个字典的count=251w,你把字典玩的66飞起,其实都是底层为你负重前行,比如其中的扩容机制,当你遇到几百万甚至千万的大集合这个扩容机制还真的需要挖一下,免的入戏太深,难以自拔。
为了方便讲述,我准备从List说起,因为它最简单哈:grin::grin::grin:
二: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(); }
从图中可以看到,数组中的 8388608-4194305 =4194303
个int直接给灭掉了,优化了空间。
2. 自定义List
其实问题的根源出在了扩容机制,举个例子,如果当length大于400w的时候,默认情况下是翻倍成800w,有时候根据你的业务不需要翻到800w,其实500w就足够了,这样300w的虚占就可以免掉,所以必要的时候自己实现一个list,然后灵活控制它的扩容机制,妙哉妙哉~~~
五:总结
明白扩容机制对你了解在大数据量下使用List还是非常有帮助的,大家根据自己的场景合理化使用,下一篇我们聊一聊HashSet。
如您有更多问题与我互动,扫描下方进来吧~
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK