.NET性能優(yōu)化之為集合類型設(shè)置初始大小的方法
前言
計劃開一個新的系列,來講一講在工作中經(jīng)常用到的性能優(yōu)化手段、思路和如何發(fā)現(xiàn)性能瓶頸,后續(xù)有時間的話應(yīng)該會整理一系列的博文出來。
今天要談的一個性能優(yōu)化的Tips是一個老生常談的點,但是也是很多人沒有注意的一個點。在使用集合類型是,你應(yīng)該設(shè)置一個預(yù)估的初始大小,那么為什么需要這樣做?我們一起來從源碼的角度說一說。
集合類型
我們先來聊一聊.NET BCL庫中提供的集合類型,對于這個大家肯定都不陌生,比如List
、HashSet
、Dictionary
、Queue
、Stack
等等,這些都是大家每天都用到,非常熟悉的類型了,那么大家在使用的時候有沒有注意過它們有一個特殊構(gòu)造函數(shù)呢?像下面代碼塊中的那樣。
public Stack (int capacity) public List (int capacity) public Queue (int capacity) public HashSet (int capacity) public Dictionary (int capacity)
哎?為什么這些構(gòu)造函數(shù)都有一個叫capacity
的參數(shù)呢?我們來看看這個參數(shù)的注釋。初始化類的新實例,該實例為空并且具有指定的初始容量或默認(rèn)初始容量。
這就很奇怪了不是嗎?在我們印象里面只有數(shù)組之類的才需要指定固定的長度,為什么這些可以無限添加元素的集合類型也要設(shè)置初始容量呢?這其實和這些集合類型的實現(xiàn)方式有關(guān),廢話不多說,我們直接看源碼。
List源碼
首先來看比較簡單的List的源碼(源碼地址在文中都做了超鏈接,可以直接點擊過去,在文末也會附上鏈接地址)。下面是List的私有變量。
// 用于存在實際的數(shù)據(jù),添加進List的元素都由存儲在_items數(shù)組中 internal T[] _items; // 當(dāng)前已經(jīng)存儲了多少元素 internal int _size; // 當(dāng)前的版本號,List每發(fā)生一次元素的變更,版本號都會+1 private int _version;
從上面的源碼中,我們可以看到雖然List是動態(tài)集合,可以無限的往里面添加元素,但是它底層存儲數(shù)據(jù)的還是使用的數(shù)組,那么既然使用的數(shù)組那它是怎么實現(xiàn)能無限的往里面添加元素的?我們來看看Add
方法。
[MethodImpl(MethodImplOptions.AggressiveInlining)] public void Add(T item) { // 版本號+1 _version++; T[] array = _items; int size = _size; // 如果當(dāng)前已經(jīng)使用的空間 小于數(shù)組大小那么直接存儲 size+1 if ((uint)size < (uint)array.Length) { _size = size + 1; array[size] = item; } else { // 注意??! 如果已經(jīng)使用的空間等于數(shù)組大小,那么走AddWithResize方法 AddWithResize(item); } }
從上面的源碼可以看到,如果內(nèi)部_item
數(shù)組有足夠的空間,那么元素直接往里面加就好了,但是如果內(nèi)部已存放的元素_size
等于_item
數(shù)組大小時,會調(diào)用AddWithResize
方法,我們來看看里面做了啥。
// AddWithResize方法 [MethodImpl(MethodImplOptions.NoInlining)] private void AddWithResize(T item) { Debug.Assert(_size == _items.Length); int size = _size; // 調(diào)用Grow方法,并且把size+1,至少需要size+1的空間才能完成Add操作 Grow(size + 1); _size = size + 1; _items[size] = item; } // Grow方法 private void Grow(int capacity) { Debug.Assert(_items.Length < capacity); // 如果內(nèi)部數(shù)組長度等于0,那么賦值為DefaultCapacity(大小為4),否則就賦值兩倍當(dāng)前長度 int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length; // 這里做了一個判斷,如果newcapacity大于Array.MaxLength(大小是2^31元素) // 也就是說一個List最大能存儲2^32元素 if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength; // 如果newpapacity小于預(yù)算需要的容量,也就是說元素數(shù)量大于Array.MaxLength // 后面Capacity會拋出異常 if (newcapacity < capacity) newcapacity = capacity; // 為Capacity屬性設(shè)置值 Capacity = newcapacity; } // Capacity屬性 public int Capacity { // 獲取容量,直接返回_items的容量 get => _items.Length; set { // 如果value值還小于當(dāng)前元素個數(shù) // 直接拋異常 if (value < _size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); } // 如果value值和當(dāng)前數(shù)組長度不匹配 // 那么走擴容邏輯 if (value != _items.Length) { // value大于0新建一個新的數(shù)組 // 將原來的數(shù)組元素拷貝過去 if (value > 0) { T[] newItems = new T[value]; if (_size > 0) { Array.Copy(_items, newItems, _size); } _items = newItems; } // value小于0 那么直接把_items賦值為空數(shù)組 // 原本的數(shù)組可以被gc回收了 else { _items = s_emptyArray; } } }
通過上面的代碼我們可以得到兩個有意思的結(jié)論。
- 一個List元素最大能存放2^31個元素.
- 不設(shè)置Capacity的話,默認(rèn)初始大小為4,后面會以2倍的空間擴容。
List
底層是通過數(shù)組來存放元素的,如果空間不夠會按照2倍大小來擴容,但是它并不能無限制的存放數(shù)據(jù)。
在元素低于4個的情況下,不設(shè)置Capacity不會有任何影響;如果大于4個,那么就會走擴容流程,不僅需要申請新的數(shù)組,而且還要發(fā)生內(nèi)存復(fù)制和需要GC回收原來的數(shù)組。
大家必須知道分配內(nèi)存、內(nèi)存復(fù)制和GC回收內(nèi)存的代價是巨大的,下面有個示意圖,舉了一個從4擴容到8的例子。
上面列舉了我們從源碼中看到的情況,那么不設(shè)置初始化的容量,對性能影響到底有多大呢?所以構(gòu)建了一個Benchmark,來看看在不同量級下的影響,下面的Benchmark主要是探究兩個問題。
- 設(shè)置初始值容量和不設(shè)置有多大的差別
- 要多少設(shè)置多少比較好,還是可以隨意設(shè)置一些值
public class ListCapacityBench { // 宇宙的真理 42 private static readonly Random OriginRandom = new(42); // 整一個數(shù)列模擬常見的集合大小 最大12萬 private static readonly int[] Arrays = { 3, 5, 8, 13, 21, 34, 55, 89, 100, 120, 144, 180, 200, 233, 250, 377, 500, 550, 610, 987, 1000, 1500, 1597, 2000, 2584, 4181, 5000, 6765, 10946, 17711, 28657, 46368, 75025, 121393 }; // 生成一些隨機數(shù) private static readonly int[] OriginArrays = Enumerable.Range(0, Arrays.Max()).Select(c => OriginRandom.Next()).ToArray(); // 不設(shè)置容量 [Benchmark(Baseline = true)] public int WithoutCapacity() { return InnerTest(null); } // 剛好設(shè)置需要的容量 [Benchmark] public int SetArrayLengthCapacity() { return InnerTest(null, true); } // 設(shè)置為8 [Benchmark] public int Set8Capacity() { return InnerTest(8); } // 設(shè)置為16 [Benchmark] public int Set16Capacity() { return InnerTest(16); } // 設(shè)置為32 [Benchmark] public int Set32Capacity() { return InnerTest(32); } // 設(shè)置為64 [Benchmark] public int Set64Capacity() { return InnerTest(64); } // 實際的測試方法 // 不使用JIT優(yōu)化,模擬集合的實際使用場景 [MethodImpl(MethodImplOptions.NoOptimization)] private static int InnerTest(int? capacity, bool setLength = false) { var list = new List<int>(); foreach (var length in Arrays) { List<int> innerList; if (capacity == null) { innerList = setLength ? new List<int>(length) : new List<int>(); } else { innerList = new List<int>(capacity.Value); } // 真正的測試方法 簡單的填充數(shù)據(jù) foreach (var item in OriginArrays.AsSpan()[..length]) { innerList.Add(item); } list.Add(innerList.Count); } return list.Count; }
從上面的Benchmark結(jié)果可以看出來,設(shè)置剛好需要的初始容量最快(比不設(shè)置快40%)、GC次數(shù)最少(50%+)、分配的內(nèi)存也最少(節(jié)約60%),另外不建議不設(shè)置初始大小,它是最慢的。
要是實在不能預(yù)估大小,那么可以無腦設(shè)置一個8表現(xiàn)稍微好一點點。如果能預(yù)估大小,因為它是2倍擴容,可以在2的N次方中找一個接近的。
8 16 32 64 128 512 1024 2048 4096 8192 ......
Queue、Stack源碼
接下來看看Queue和Stack,看看它的擴容邏輯是怎么樣的。
private void Grow(int capacity) { Debug.Assert(_array.Length < capacity); const int GrowFactor = 2; const int MinimumGrow = 4; int newcapacity = GrowFactor * _array.Length; if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength; newcapacity = Math.Max(newcapacity, _array.Length + MinimumGrow); if (newcapacity < capacity) newcapacity = capacity; SetCapacity(newcapacity); }
基本一樣,也是2倍擴容,所以按照我們上面的規(guī)則就好了。
HashSet、Dictionary源碼
HashSet和Dictionary的邏輯實現(xiàn)類似,只是一個Key就是Value,另外一個是Key對應(yīng)Value。不過它們的擴容方式有所不同,具體可以看我之前的博客,來看看擴容的源碼,這里以HashSet
為例。
private void Resize() => Resize(HashHelpers.ExpandPrime(_count), forceNewHashCodes: false); private void Resize(int newSize, bool forceNewHashCodes) { // Value types never rehash Debug.Assert(!forceNewHashCodes || !typeof(T).IsValueType); Debug.Assert(_entries != null, "_entries should be non-null"); Debug.Assert(newSize >= _entries.Length); var entries = new Entry[newSize]; int count = _count; Array.Copy(_entries, entries, count); if (!typeof(T).IsValueType && forceNewHashCodes) { Debug.Assert(_comparer is NonRandomizedStringEqualityComparer); _comparer = (IEqualityComparer<T>)((NonRandomizedStringEqualityComparer)_comparer).GetRandomizedEqualityComparer(); for (int i = 0; i < count; i++) { ref Entry entry = ref entries[i]; if (entry.Next >= -1) { entry.HashCode = entry.Value != null ? _comparer!.GetHashCode(entry.Value) : 0; } } if (ReferenceEquals(_comparer, EqualityComparer<T>.Default)) { _comparer = null; } } // Assign member variables after both arrays allocated to guard against corruption from OOM if second fails _buckets = new int[newSize]; #if TARGET_64BIT _fastModMultiplier = HashHelpers.GetFastModMultiplier((uint)newSize); #endif for (int i = 0; i < count; i++) { ref Entry entry = ref entries[i]; if (entry.Next >= -1) { ref int bucket = ref GetBucketRef(entry.HashCode); entry.Next = bucket - 1; // Value in _buckets is 1-based bucket = i + 1; } } _entries = entries; }
從上面的源碼中可以看到Resize的步驟如下所示。
- 通過
HashHelpers.ExpandPrime
獲取新的Size - 創(chuàng)建新的數(shù)組,使用數(shù)組拷貝將原數(shù)組元素拷貝過去
- 對所有元素進行重新Hash,重建引用
從這里大家就可以看出來,如果不指定初始大小的話,HashSet
和Dictionary
這樣的數(shù)據(jù)結(jié)構(gòu)擴容的成本更高,因為還需要ReHash這樣的操作。
那么HashHelpers.ExpandPrime
是一個什么樣的方法呢?究竟每次會擴容多少空間呢?我們來看HashHelpers源碼。
public const uint HashCollisionThreshold = 100; // 這是比Array.MaxLength小最大的素數(shù) public const int MaxPrimeArrayLength = 0x7FFFFFC3; public const int HashPrime = 101; public static int ExpandPrime(int oldSize) { // 新的size等于舊size的兩倍 int nwSize = 2 * oldSize; // 和List一樣,如果大于了指定最大值,那么直接返回最大值 if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize) { Debug.Assert(MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength"); return MaxPrimeArrayLength; } // 獲取大于newSize的第一素數(shù) return GetPrime(newSize); } public static int GetPrime(int min) { if (min < 0) throw new ArgumentException(SR.Arg_HTCapacityOverflow); // 獲取大于min的第一個素數(shù) foreach (int prime in s_primes) { if (prime >= min) return prime; } // 如果素數(shù)列表里面沒有 那么計算 for (int i = (min | 1); i < int.MaxValue; i += 2) { if (IsPrime(i) && ((i - 1) % HashPrime != 0)) return i; } return min; } // 用于擴容的素數(shù)列表 private static readonly int[] s_primes = { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369 }; // 當(dāng)容量大于7199369時,需要計算素數(shù) public static bool IsPrime(int candidate) { if ((candidate & 1) != 0) { int limit = (int)Math.Sqrt(candidate); for (int divisor = 3; divisor <= limit; divisor += 2) { if ((candidate % divisor) == 0) return false; } return true; } return candidate == 2; }
從上面的代碼我們就可以得出HashSet
和Dictionary
每次擴容后的大小就是大于二倍Size的第一個素數(shù),和List直接擴容2倍還是有差別的。
至于為什么要使用素數(shù)來作為擴容的大小,簡單來說是使用素數(shù)能讓數(shù)據(jù)在Hash以后更均勻的分布在各個桶中(素數(shù)沒有其它約數(shù)),這不在本文的討論范圍,具體可以戳鏈接1、鏈接2、鏈接3了解更多。
總結(jié)
從性能的角度來說,強烈建議大家在使用集合類型時指定初始容量,總結(jié)了下面的幾個點。
從性能的角度來說,強烈建議大家在使用集合類型時指定初始容量,總結(jié)了下面的幾個點。
- 如果你知道集合將要存放的元素個數(shù),那么就直接設(shè)置那個大小,那樣性能最高.
- 比如那種分頁接口,頁大小只可能是50、100
- 或者做Map操作,前后的元素數(shù)量是一致的,那就可以直接設(shè)置
- 如果你不知道,那么可以預(yù)估一下個數(shù),在2的次方中找一個合適的就可以了.
可以盡量的預(yù)估多一點點,能避免Resize操作就避免
附錄
淺析 C# Dictionary:https://www.cnblogs.com/InCerry/p/10325290.html
到此這篇關(guān)于.NET性能優(yōu)化之為集合類型設(shè)置初始大小的方法的文章就介紹到這了,更多相關(guān).NET性能優(yōu)化集合類型設(shè)置初始大小內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
AspNetPager分頁控件源代碼(Version 4.2)
AspNetPager分頁控件源代碼(Version 4.2)...2007-04-04asp.net HttpWebRequest自動識別網(wǎng)頁編碼
HttpWebRequest獲取網(wǎng)頁源代碼時自動識別網(wǎng)頁編碼,通過讀取頁面中的charset和讀取http頭中的編碼信息獲取頁面的編碼,基本可以正確獲取網(wǎng)頁編碼2008-09-09輕量級ORM框架Dapper應(yīng)用之實現(xiàn)In操作
這篇文章介紹了使用Dapper實現(xiàn)In操作的方法,文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-03-03asp.net創(chuàng)建位圖生成驗證圖片類(驗證碼類)
本文提供一個asp.net生成驗證圖片的類,功能是顯示簡單的字符串,大家參考使用吧2014-01-01ASP.NET Core MVC通過IViewLocationExpander擴展視圖搜索路徑的實現(xiàn)
這篇文章主要介紹了ASP.NET Core MVC通過IViewLocationExpander擴展視圖搜索路徑的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04.NET CORE中比較兩個文件內(nèi)容是否相同的最快方法
這篇文章主要給大家介紹了關(guān)于.NET CORE中比較兩個文件內(nèi)容是否相同的最快方法,文中通過示例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用.NET CORE具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06