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

一:背景

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

从图中可以看到,数组中的 8388608-4194305 =4194303 个int直接给灭掉了,优化了空间。

2. 自定义List

其实问题的根源出在了扩容机制,举个例子,如果当length大于400w的时候,默认情况下是翻倍成800w,有时候根据你的业务不需要翻到800w,其实500w就足够了,这样300w的虚占就可以免掉,所以必要的时候自己实现一个list,然后灵活控制它的扩容机制,妙哉妙哉~~~

五:总结

明白扩容机制对你了解在大数据量下使用List还是非常有帮助的,大家根据自己的场景合理化使用,下一篇我们聊一聊HashSet。

到此这篇关于详解C#中的扩容机制的文章就介绍到这了,更多相关c# 扩容机制内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C#控制台基础 list<>初始化的两种方法

    代码一. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { List<int> list1 = new List<int> { 1, 2,

  • C#中list用法实例

    本文实例讲述了C#中list用法.分享给大家供大家参考,具体如下: protected void Page_Load(object sender, EventArgs e) { List<string> studentNames = new List<string>(); studentNames.Add("John"); studentNames.Add("Mary"); studentNames.Add("Rose")

  • c#对list排序示例

    复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ListSort { class Program { static void Main(string[] args) { List listCustomer = new List(); listCustomer.Add(new Customer { name = "客户1",

  • c# list部分操作实现代码

    C# Linq获取两个List或数组的差集交集 复制代码 代码如下: List<int> list1 = newList<int>();list1.Add(1);list1.Add(2);list1.Add(3);List<int> list2 = newList<int>();list2.Add(3);list2.Add(4);list2.Add(5);//得到的结果是4,5 即减去了相同的元素.List<int> list3 = list2.

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

    一:背景 1. 讲故事 在前一篇大内存排查中,我们看到了Dictionary正在做扩容操作,当时这个字典的count=251w,你把字典玩的66飞起,其实都是底层为你负重前行,比如其中的扩容机制,当你遇到几百万甚至千万的大集合这个扩容机制还真的需要挖一下,免的入戏太深,难以自拔. 二:List扩容机制 1. 如何查看 要想看它的扩容机制,可以用ILSpy去看看List的源码即可,非常简单. 从源码的 int num = (_items.Length == 0) ? 4 : (_items.Len

  • 一文读懂ava中的Volatile关键字使用

    在本文中,我们会介绍java中的一个关键字volatile. volatile的中文意思是易挥发的,不稳定的.那么在java中使用是什么意思呢? 我们知道,在java中,每个线程都会有个自己的内存空间,我们称之为working memory.这个空间会缓存一些变量的信息,从而提升程序的性能.当执行完某个操作之后,thread会将更新后的变量更新到主缓存中,以供其他线程读写. 因为变量存在working memory和main memory两个地方,那么就有可能出现不一致的情况. 那么我们就可以使

  • 一文看懂JAVA设计模式之工厂模式

    工厂顾名思义就是创建产品,根据产品是具体产品还是具体工厂可分为简单工厂模式和工厂方法模式,根据工厂的抽象程度可分为工厂方法模式和抽象工厂模式.该模式用于封装和管理对象的创建,是一种创建型模式.本文从一个具体的例子逐步深入分析,来体会三种工厂模式的应用场景和利弊. 1. 简单工厂模式 该模式对对象创建管理方式最为简单,因为其仅仅简单的对不同类对象的创建进行了一层薄薄的封装.该模式通过向工厂传递类型来指定要创建的对象,其UML类图如下: 下面我们使用手机生产来讲解该模式: Phone类:手机标准规范

  • 一文搞懂Java中的反射机制

    前一段时间一直忙,所以没什么时间写博客,拖了这么久,也该更新更新了.最近看到各种知识付费的推出,感觉是好事,也是坏事,好事是对知识沉淀的认可与推动,坏事是感觉很多人忙于把自己的知识变现,相对的在沉淀上做的实际还不够,我对此暂时还没有什么想法,总觉得,慢慢来,会更快一点,自己掌握好节奏就好. 好了,言归正传. 反射机制是Java中的一个很强大的特性,可以在运行时获取类的信息,比如说类的父类,接口,全部方法名及参数,全部常量和变量,可以说类在反射面前已经衣不遮体了(咳咳,这是正规车).先举一个小栗子

  • 教你一文搞懂Kotlin中的Jvm注解

    JvmOverloads 创建一个kotlin的类 class Student(val name: String, val sex: Int = 1, val age: Int = 18) 可以看出来 这个构造函数的参数是有默认值的,kotlin的特性对吧,我们在使用的时候可以方便的使用,比如: val student = Student("wuyue") val student2 = Student("wuyue", age = 18) 但是这个特性如果你用jav

  • 一文看懂PHP进程管理器php-fpm

    php-fpm是什么 php-fpm是PHP的一个进程管理器.php下面的众多work进程皆有php-fpm进程管理器管理. php-fpm的工作原理 php-fpm全名是PHP FastCGI进程管理器.php-fpm启动后会先读php.ini,然后再读相应的conf配置文件,conf配置可以覆盖php.ini的配置. 启动php-fpm之后,会创建一个master进程,监听9000端口(可配置),master进程又会根据fpm.conf/www.conf去创建若干子进程,子进程用于处理实际的

  • 一文搞懂Python中pandas透视表pivot_table功能详解

    目录 一.概述 1.1 什么是透视表? 1.2 为什么要使用pivot_table? 二.如何使用pivot_table 2.1 读取数据 2.2Index 2.3Values 2.4Aggfunc 2.5Columns 一文看懂pandas的透视表pivot_table 一.概述 1.1 什么是透视表? 透视表是一种可以对数据动态排布并且分类汇总的表格格式.或许大多数人都在Excel使用过数据透视表,也体会到它的强大功能,而在pandas中它被称作pivot_table. 1.2 为什么要使用

  • 一文搞懂Python中pandas透视表pivot_table功能

    目录 一.概述 1.1 什么是透视表? 1.2 为什么要使用pivot_table? 二.如何使用pivot_table 2.1 读取数据 2.2Index 2.3Values 2.4Aggfunc 2.5Columns 一文看懂pandas的透视表pivot_table 一.概述 1.1 什么是透视表? 透视表是一种可以对数据动态排布并且分类汇总的表格格式.或许大多数人都在Excel使用过数据透视表,也体会到它的强大功能,而在pandas中它被称作pivot_table. 1.2 为什么要使用

  • 一文看懂JSONP原理和应用

    目录 什么是JSONP JSONP原理 JSONP具体实现 1.ajax中如果进行跨域请求会如何 2.使用JSONP,将前端代码中的ajax请求去掉 3.将前端代码再进行修改 4.最后jQuery提供了方便使用JSONP的方式 什么是JSONP 首先提一下JSON这个概念,JSON是一种轻量级的数据传输格式,被广泛应用于当前Web应用中.JSON格式数据的编码和解析基本在所有主流语言中都被实现,所以现在大部分前后端分离的架构都以JSON格式进行数据的传输. 那么JSONP是什么呢? 首先抛出浏览

  • 一文搞懂Python中的进程,线程和协程

    目录 1.什么是并发编程 2.进程与多进程 3.线程与多线程 4.协程与多协程 5.总结 1.什么是并发编程 并发编程是实现多任务协同处理,改善系统性能的方式.Python中实现并发编程主要依靠 进程(Process):进程是计算机中的程序关于某数据集合的一次运行实例,是操作系统进行资源分配的最小单位 线程(Thread):线程被包含在进程之中,是操作系统进行程序调度执行的最小单位 协程(Coroutine):协程是用户态执行的轻量级编程模型,由单一线程内部发出控制信号进行调度 直接上一张图看看

随机推荐