C#中Array的存儲結(jié)構(gòu)簡單介紹
數(shù)組是C#中最基礎(chǔ)的存儲結(jié)構(gòu)之一,很多的存儲結(jié)構(gòu)其底層的實現(xiàn)中都是基于數(shù)組實現(xiàn)的,如:List、Queue、Stack、Dictionary、Heap等等,如果大家讀過這些類型的底層實現(xiàn)源碼,其實就可以發(fā)現(xiàn),這些存儲結(jié)構(gòu)都是在其內(nèi)部維護了一個或多個數(shù)組。本文重點來學習一下數(shù)組存儲結(jié)構(gòu)的實現(xiàn)邏輯。
首先,我們來看看數(shù)組的定義:靜態(tài)數(shù)組是由相同類型的元素線性排列的數(shù)據(jù)結(jié)構(gòu),在計算機上會分配一段連續(xù)的內(nèi)存,對元素進行順序存儲。從以上的描述中,我們可以發(fā)現(xiàn)幾個征:"相同類型、連續(xù)內(nèi)存、順序存儲",這樣的結(jié)構(gòu)特性,可以能做到基于下標,對數(shù)組進行 O(1) 時間復(fù)雜度的快速隨機訪問。
那么數(shù)組為什么可以做到快速隨機訪問?我們可以先來簡單的說明一下,"存儲數(shù)組時,會事先分配一段連續(xù)的內(nèi)存空間,將數(shù)組元素依次存入內(nèi)存。因為數(shù)組元素的類型都是一樣的,所以每個元素占用的空間大小也是一樣的,這樣我們就很容易用“數(shù)組的開始地址 +index* 元素大小”的計算方式,快速定位到指定索引位置的元素,這也是數(shù)組基于下標隨機訪問的復(fù)雜度為 O(1) 的原因。"這樣的描述可能是絕大部分同學都有所接觸到的內(nèi)容,并且也能讓大家大致的了解到其存儲原理,但是C#數(shù)組的存儲結(jié)構(gòu)是如何具體實現(xiàn)的呢?
本文將從一個數(shù)組的基礎(chǔ)操作開始,逐步來推導數(shù)組的在C#基礎(chǔ)操作、數(shù)組在CoreCLR的維護策略,數(shù)組在C++的內(nèi)存分配等階段具體是如何實現(xiàn)的。
首先,我們先來看一個簡單的數(shù)組定義、初始化、賦值、取值的過程。
int[] myIntArray = new int[5] { 1, 2, 3, 4, 5 }; for (int j = 0; j < 10; j++ ) { Console.WriteLine("Element[{0}] = {1}", j, myIntArray[j]); }
這個過程中具體的實現(xiàn)邏輯什么樣的呢,對于C#數(shù)組在內(nèi)存的存儲方式、數(shù)組的Cpoy、動態(tài)數(shù)組的擴容機制是什么樣的呢?在C#中Array充當數(shù)組的基類,用于創(chuàng)建、處理、搜索數(shù)組并對數(shù)組進行排序,但是只有系統(tǒng)和編譯器才能顯式從Array類派生。接下來我們就來了解一下Array底層源碼實現(xiàn)。對于數(shù)組的初始化,我們使用以上示例中的int[]進行介紹。在C#中所有的數(shù)組類型都集成自抽象類Array,在對int[]初始化的過程中,都會使用array的CreateInstance()方法,該方法存在多個重載,主要區(qū)別為用于創(chuàng)建一維、二維、三維等不同維數(shù)的數(shù)組結(jié)構(gòu),以下我們來看一下對于一維數(shù)據(jù)的創(chuàng)建代碼。
public static unsafe Array CreateInstance(Type elementType, int length) { RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType; return InternalCreate(t, 1, &length, null); }
上面的代碼中,我們可以發(fā)現(xiàn)兩個地方需要關(guān)注,第一部分:RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType;該方法獲取數(shù)組元素類型的基礎(chǔ)系統(tǒng)類型,并將其轉(zhuǎn)換為 RuntimeType。第二部分:InternalCreate(t, 1, &length, null)具體創(chuàng)建數(shù)組的操作,我們來看一下其實現(xiàn)的源碼。(源碼進行部分刪減)
private static unsafe Array InternalCreate(RuntimeType elementType, int rank, int* pLengths, int* pLowerBounds) { if (rank == 1) { return RuntimeImports.RhNewArray(elementType.MakeArrayType().TypeHandle.ToEETypePtr(), pLengths[0]); } else { int* pImmutableLengths = stackalloc int[rank]; for (int i = 0; i < rank; i++) pImmutableLengths[i] = pLengths[i]; return NewMultiDimArray(elementType.MakeArrayType(rank).TypeHandle.ToEETypePtr(), pImmutableLengths, rank); } }
該方法用于在運行時創(chuàng)建數(shù)組,其中參數(shù)elementType表示數(shù)組元素運行時的類型,rank表示數(shù)組的維度,pLengths表示指向數(shù)組長度的指針,pLowerBounds表示指向數(shù)組下限(如果有的話)的指針。根據(jù)設(shè)定的rank的值,創(chuàng)建一維或多維數(shù)組。其中elementType.MakeArrayType().TypeHandle.ToEETypePtr()表示先將當前type 對象表示的類型通過 MakeArrayType 方法創(chuàng)建一個數(shù)組類型,然后獲取該數(shù)組類型的運行時類型句柄,最后通過 ToEETypePtr 方法將運行時類型句柄轉(zhuǎn)換為指向類型信息的指針。我們先看一下創(chuàng)建一維數(shù)組的邏輯,具體代碼如下:
[MethodImpl(MethodImplOptions.InternalCall)] [RuntimeImport(RuntimeLibrary, "RhNewArray")] private static extern unsafe Array RhNewArray(MethodTable* pEEType, int length); internal static unsafe Array RhNewArray(EETypePtr pEEType, int length) => RhNewArray(pEEType.ToPointer(), length);
該方法是具體實現(xiàn)數(shù)組創(chuàng)建的邏輯,我們先來看一下參數(shù),其中EETypePtr是CLR中用于表示對象類型信息的指針類型。每個.NET對象在運行時都關(guān)聯(lián)有一EEType結(jié)構(gòu),它包含有關(guān)對象類型的信息,例如該類型的方法表、字段布局、基類信息等。
這里簡單的介紹一下代碼上面的兩個自定義屬性:
(1)、[MethodImpl(MethodImplOptions.InternalCall)]
指示編譯器生成的方法體會被一個外部實現(xiàn)取代,而該外部實現(xiàn)通常由運行時環(huán)境提供。
(2)、[RuntimeImport(RuntimeLibrary, "RhNewArray")]
這是一個自定義的特性,在項目中定義的用于指示運行時導入的特性。
在C#中,使用屬性標記運行時導入的位置通常是為了提供額外的元數(shù)據(jù)和信息,以告訴編譯器和運行時環(huán)境如何正確地處理外部方法的調(diào)用。
使用屬性標記運行時導入的主要目的有以下幾點:
(1)、元數(shù)據(jù)信息:運行時導入的位置可能包括一些元數(shù)據(jù)信息,如函數(shù)名稱、庫名稱、調(diào)用約定等。 使用屬性可以將這些信息嵌入到C#代碼中,使得代碼更加自解釋,并提供足夠的信息供編譯器和運行時使用。
(2)、優(yōu)化和安全性:編譯器和運行時環(huán)境可能會使用屬性來進行性能優(yōu)化或安全性檢查。 例如,通過指定調(diào)用約定或其他屬性,可以幫助編譯器生成更有效的代碼。
(3)、與運行時環(huán)境交互:屬性可以提供一種與底層運行時環(huán)境進行交互的機制。 例如,通過自定義屬性,可以向運行時環(huán)境傳遞一些特殊的標志或信息,以影響方法的行為。
(4)、代碼維護和可讀性:使用屬性可以提高代碼的可維護性和可讀性。 在代碼中使用屬性來標記運行時導入的位置,使得代碼的意圖更加清晰,也有助于團隊協(xié)作。
在CLR的內(nèi)部,EETypePtr是一個指向EEType結(jié)構(gòu)的指針,其中EEType是運行時中用于描述對象類型的結(jié)構(gòu)。EEType結(jié)構(gòu)的內(nèi)容由運行時系統(tǒng)生成和管理,而EETypePtr則是對這個結(jié)構(gòu)的指針引用。根據(jù)傳入的運行時對象類型進行處理,我們接下來看一下pEEType.ToPointer()的實現(xiàn)。
internal unsafe Internal.Runtime.MethodTable* ToPointer() { return (Internal.Runtime.MethodTable*)(void*)_value; }
ToPointer()方法目的是將其對象或值轉(zhuǎn)換為指針,MethodTable 是CLR用于管理類和對象的元數(shù)據(jù),用于存儲類型相關(guān)信息的數(shù)據(jù)結(jié)構(gòu),每個對象在內(nèi)存中都包含一個指向其類型信息的指針,這個指針指向該類型的 MethodTable,用于支持CLR在運行時進行類型檢查、虛方法調(diào)用等操作。那我們來具體看一下MethodTable的數(shù)據(jù)結(jié)構(gòu)。
struct MethodTable { // 指向類型的虛方法表(VTable) IntPtr* VirtualMethodTable; // 字段表 FieldInfo* Fields; // 接口表 InterfaceInfo* Interfaces; // 其他元數(shù)據(jù)信息... }
我們從原始的數(shù)組初始化和賦值,一直推導至對象的數(shù)組空間維護。截止當前,我們獲取到數(shù)組的MethodTable* pEEType數(shù)據(jù)結(jié)構(gòu)。接下來我們來看一下CLR對數(shù)組的內(nèi)存空間分配邏輯和維護方案。由于CoreCLR中的實現(xiàn)代碼我們沒有辦法全面的了解,我們接下按照預(yù)定的邏輯進行一定的推論。(CCoreCLR的實現(xiàn)代碼絕大部分是使用C++實現(xiàn))
#include <cstdint> extern "C" { struct MethodTable { // 方法表等信息...}; struct Array { // 數(shù)組相關(guān)信息...}; void* RhNewArray(void* pEEType, int length) { // 假設(shè)存在一個用于對象分配的函數(shù),該函數(shù)分配數(shù)組的內(nèi)存 void* rawArrayMemory = AllocationFunction(length * sizeof(Array)); // 將傳遞的 pEEType 信息保存到數(shù)組對象中 Array* newArray = static_cast<Array*>(rawArrayMemory); //為數(shù)組對象設(shè)置元數(shù)據(jù)信息 newArray->MethodTablePointer = pEEType; return rawArrayMemory; } }
以上代碼是一種假設(shè)實現(xiàn)方式, AllocationFunction 的函數(shù)用于內(nèi)存分配,并且數(shù)組對象(Array)有一個成員 MethodTablePointer 用于存儲 MethodTable 的指針。接下來我們再來看一下AllocationFunction()方法推測實現(xiàn)邏輯。
void* AllocationFunction(size_t size) { // 使用標準庫的 malloc 函數(shù)進行內(nèi)存分配 void* memory = malloc(size); //處理內(nèi)存分配失敗的情況 ... return memory; }
以上的代碼中,使用標準函數(shù)庫malloc()進行內(nèi)存的分配,malloc ()是C標準庫中的一個函數(shù),用于在運行時動態(tài)分配內(nèi)存。malloc ()接受一個 size 參數(shù),表示要分配的內(nèi)存字節(jié)數(shù)。它返回一個指向分配內(nèi)存起始地址的指針,或者在分配失敗時返回 NULL。malloc ()內(nèi)存分配邏輯通常涉及以下步驟:
(1)、請求內(nèi)存空間: malloc() 根據(jù)傳遞的 size 參數(shù)向系統(tǒng)請求一塊足夠大的內(nèi)存空間。 (2)、內(nèi)存分配:如果系統(tǒng)成功分配了請求的內(nèi)存塊,malloc 會在這塊內(nèi)存中標記已分配的部分,并將其起始地址返回給調(diào)用者。
(3)、返回結(jié)果:如果分配成功,malloc 返回一個指向新分配內(nèi)存的指針。如果分配失?。ɡ?,系統(tǒng)內(nèi)存不足),則返回 NULL。
(4)、內(nèi)存對齊:部分系統(tǒng)要求分配的內(nèi)存是按照特定字節(jié)對齊的。因此,malloc 通常會確保返回的內(nèi)存地址滿足系統(tǒng)的對齊要求。
(5)、初始化內(nèi)存:malloc 返回的內(nèi)存通常不會被初始化,即其中的數(shù)據(jù)可能是未知的。在使用之前,需要通過其他手段對內(nèi)存進行初始化。
(6)、內(nèi)存管理:一些實現(xiàn)可能會使用內(nèi)部數(shù)據(jù)結(jié)構(gòu)來跟蹤已分配和未分配的內(nèi)存塊,以便在 free 被調(diào)用時能夠釋放相應(yīng)的內(nèi)存。
以上簡單的描述了C++在底層實現(xiàn)內(nèi)存分配的簡單實現(xiàn)方式,對于CoreCLRe中對于數(shù)組的內(nèi)存空間申請相對非常復(fù)雜,可能涉及內(nèi)存池、分配策略、對齊要求等方面的考慮。后續(xù)有機會再做詳細的介紹。既然說到CoreCLR的內(nèi)存實現(xiàn)為C++的內(nèi)存分配策略,那我們接下來看一下其對應(yīng)的常用策略管理策略。我們用一個簡單的數(shù)組的內(nèi)存分配。
int myArray[5]; // 聲明一個包含5個整數(shù)的數(shù)組 +------+------+------+------+------+ | int0 | int1 | int2 | int3 | int4 | +------+------+------+------+------+
myArray 是整個數(shù)組的起始地址,然后每個 int 元素按照其大小排列在一起?;谝陨系姆治觯覀兛梢钥吹紺++對于內(nèi)存的分配概述大致如下:
(1)、元素的內(nèi)存布局:數(shù)組的元素在內(nèi)存中是依次排列的,每個元素占用的內(nèi)存空間由元素的類型決定。 例如,一個 int 數(shù)組中的每個整數(shù)元素通常占用4個字節(jié)(32位系統(tǒng))或8個字節(jié)(64位系統(tǒng))。
(2)、數(shù)組的起始地址:數(shù)組的內(nèi)存分配通常從數(shù)組的第一個元素開始。數(shù)組的起始地址是數(shù)組第一個元素的地址。
(3)、連續(xù)存儲:數(shù)組的元素在內(nèi)存中是連續(xù)存儲的,這意味著數(shù)組中的每個元素都直接跟在前一個元素的后面。
上面介紹了內(nèi)存空間的分配,我們接下來看一下這段代碼的實現(xiàn)邏輯,rawArrayMemory: 這是一個 void* 類型的指針,通常指向分配的內(nèi)存塊的起始位置。static_cast 運算符,將 rawArrayMemory 從 void* 類型轉(zhuǎn)換為 Array* 類型。
Array* newArray = static_cast<Array*>(rawArrayMemory);
我們從以上對于數(shù)組的創(chuàng)建過程中,分析了C#、CoreCLR、C++等多個實現(xiàn)視角進行了簡單的分析。
接下來我們回歸到CoreCLR中對于數(shù)組的內(nèi)存空間管理策略,數(shù)組內(nèi)存分配的常用步驟:
1、分配對象頭:為數(shù)組對象分配對象頭,對象頭包含一些元數(shù)據(jù),如類型指針、同步塊索引等信息。
2、分配數(shù)組元素空間:分配存儲數(shù)組元素的內(nèi)存塊,這是實際存儲數(shù)組數(shù)據(jù)的地方。
3、初始化數(shù)組元素:根據(jù)數(shù)組類型的要求,初始化數(shù)組元素。這可能涉及到對元素進行默認初始化,例如將整數(shù)數(shù)組的每個元素初始化為零。
4、返回數(shù)組引用:返回指向數(shù)組對象的引用,使得該數(shù)組可以被使用。
當我們在托管代碼中聲明一個數(shù)組時,CoreCLR會在托管堆上動態(tài)分配內(nèi)存,以存儲數(shù)組的元素,并在分配的內(nèi)存塊中存儲有關(guān)數(shù)組的元數(shù)據(jù),這些元數(shù)據(jù)通常包括數(shù)組的長度和元素類型等信息。CoreCLR通常會對分配的內(nèi)存進行對齊,以提高訪問效率,這可能導致分配的內(nèi)存塊略大于數(shù)組元素的實際大小??赡苡型瑢W會問為什么要進行內(nèi)存的對齊,這里就簡單的說明一下。
1、硬件要求:訪問特定類型的數(shù)據(jù)時,其地址應(yīng)該是某個值的倍數(shù)。
2、提高訪問速度:對齊的內(nèi)存訪問通常比不對齊的訪問更加高效。處理器通常能夠更快地訪問對齊的內(nèi)存,因為這符合硬件訪問模式。
3、減少內(nèi)存碎片:內(nèi)存對齊還有助于減少內(nèi)存碎片,使得內(nèi)存的使用更加緊湊。內(nèi)存碎片可能導致性能下降,因為它可能增加了分配和釋放內(nèi)存的開銷。
4、硬件事務(wù):一些處理器和操作系統(tǒng)支持原子操作,但通常要求數(shù)據(jù)是按照特定的對齊方式排列的。
上面介紹了為什么需要進行內(nèi)存對齊,那么對于CoreCLR的內(nèi)部實現(xiàn)是如何進行內(nèi)存對齊的呢?我們簡潔的介紹一下實現(xiàn)大流程:
1、使用操作系統(tǒng)的內(nèi)存分配函數(shù):使用操作系統(tǒng)提供的內(nèi)存分配函數(shù)來分配托管堆上的內(nèi)存。在Windows上可能是HeapAlloc。
2、對齊方式的指定:在調(diào)用內(nèi)存分配函數(shù)時,會指定所需的對齊方式。通常是以字節(jié)為單位的對齊值。常見的對齊值包括4字節(jié)、8字節(jié)等。
3、內(nèi)存塊的對齊:內(nèi)存分配函數(shù)返回的內(nèi)存塊通常是按照指定的對齊方式進行對齊的。CLR確保返回的內(nèi)存塊的起始地址符合對齊規(guī)則。
4、對齊規(guī)則的維護:維護對齊規(guī)則的信息,確保在托管堆上分配和釋放的內(nèi)存塊都符合相同的對齊方式。
5、內(nèi)存對齊的優(yōu)化:對內(nèi)存對齊進行一些優(yōu)化,以提高訪問效率。例如,它可以在對象的布局中考慮對齊規(guī)則,以減少內(nèi)存碎片。
具體的數(shù)組內(nèi)存分配策略可能會因CLR的版本和實現(xiàn)而異。不同的垃圾回收算法(如標記-清除、復(fù)制、標記-整理等)以及不同的GC代(新生代、老年代)也可能影響內(nèi)存分配的具體實現(xiàn)。在.NET中,CLR提供了不同的垃圾回收器實現(xiàn),例如Workstation GC和Server GC。Workstation GC通常適用于單處理器或少量處理器的環(huán)境,而Server GC適用于多處理器環(huán)境。這些GC實現(xiàn)可能在內(nèi)存分配和回收方面有一些差異。
本文借助了一個數(shù)組的初始化和賦值為樣例,逐層的分析了數(shù)組對象運行時結(jié)構(gòu)的獲取、對象MethodTable結(jié)構(gòu)的分析、CoreCLR底層對數(shù)組內(nèi)存結(jié)構(gòu)的創(chuàng)建推導、C++對于內(nèi)存的分配策略等視角,最后還綜合的介紹了CoreCLR對于數(shù)組內(nèi)存的創(chuàng)建步驟。
我們一直以來對于數(shù)組的內(nèi)存分配,都有一個整體的認識,其特點是"相同類型、連續(xù)內(nèi)存、順序存儲",對于其連續(xù)內(nèi)存的特點記憶深刻,但是在內(nèi)部如何實現(xiàn)進行的連續(xù)內(nèi)存卻沒有整體的了解,C#內(nèi)部是如何完成不同類型對象數(shù)組的運行時創(chuàng)建,在CoreCLR內(nèi)部如何進行內(nèi)存的劃分是沒有做過了解和推導,甚至于CoreCLR內(nèi)部是如何維護一個對象的結(jié)構(gòu),很多時候都只是了解到運行時對象使用Type類型就可以得到,那么CoreCLR內(nèi)部如何來維護這個Type呢?其實很多時候沒有特點去了解過其結(jié)構(gòu)。
以上內(nèi)容是對C#中Array的存儲結(jié)構(gòu)的簡單介紹,如錯漏的地方,還望指正。
到此這篇關(guān)于深度分析C#中Array的存儲結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)C# Array存儲結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C#使用動態(tài)規(guī)劃解決0-1背包問題實例分析
這篇文章主要介紹了C#使用動態(tài)規(guī)劃解決0-1背包問題,實例分析了C#動態(tài)規(guī)劃算法的實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-04-04