狠狠色丁香婷婷综合尤物/久久精品综合一区二区三区/中国有色金属学报/国产日韩欧美在线观看 - 国产一区二区三区四区五区tv

LOGO OA教程 ERP教程 模切知識交流 PMS教程 CRM教程 開發文檔 其他文檔  
 
網站管理員

深度分析C#中Array的存儲結構

freeflydom
2023年11月29日 8:39 本文熱度 701
數組是C#中最基礎的存儲結構之一,很多的存儲結構其底層的實現中都是基于數組實現的,如:List、Queue、Stack、Dictionary、Heap等等,如果大家讀過這些類型的底層實現源碼,其實就可以發現,這些存儲結構都是在其內部維護了一個或多個數組。本文重點來學習一下數組存儲結構的實現邏輯。
  首先,我們來看看數組的定義:靜態數組是由相同類型的元素線性排列的數據結構,在計算機上會分配一段連續的內存,對元素進行順序存儲。從以上的描述中,我們可以發現幾個征:"相同類型、連續內存、順序存儲",這樣的結構特性,可以能做到基于下標,對數組進行 O(1) 時間復雜度的快速隨機訪問。
  那么數組為什么可以做到快速隨機訪問?我們可以先來簡單的說明一下,"存儲數組時,會事先分配一段連續的內存空間,將數組元素依次存入內存。因為數組元素的類型都是一樣的,所以每個元素占用的空間大小也是一樣的,這樣我們就很容易用“數組的開始地址 +index* 元素大小”的計算方式,快速定位到指定索引位置的元素,這也是數組基于下標隨機訪問的復雜度為 O(1) 的原因。"這樣的描述可能是絕大部分同學都有所接觸到的內容,并且也能讓大家大致的了解到其存儲原理,但是C#數組的存儲結構是如何具體實現的呢?
  本文將從一個數組的基礎操作開始,逐步來推導數組的在C#基礎操作、數組在CoreCLR的維護策略,數組在C++的內存分配等階段具體是如何實現的。
  首先,我們先來看一個簡單的數組定義、初始化、賦值、取值的過程。

1         int[] myIntArray = new int[5] { 1, 2, 3, 4, 5 };
2 
3         for (int j = 0; j < 10; j++ )
4         {
5            Console.WriteLine("Element[{0}] = {1}", j, myIntArray[j]);
6         }

  這個過程中具體的實現邏輯什么樣的呢,對于C#數組在內存的存儲方式、數組的Cpoy、動態數組的擴容機制是什么樣的呢?在C#中Array充當數組的基類,用于創建、處理、搜索數組并對數組進行排序,但是只有系統和編譯器才能顯式從 Array 類派生。接下來我們就來了解一下Array底層源碼實現。對于數組的初始化,我們使用以上示例中的int[]進行介紹。在C#中所有的數組類型都集成自抽象類Array,在對int[]初始化的過程中,都會使用array的createInstance()方法,該方法存在多個重載,主要區別為用于創建一維、二維、三維等不同維數的數組結構,以下我們來看一下對于一維數據的創建代碼。


1         public static unsafe Array createInstance(Type elementType, int length)
2         {
3             RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType;
4 
5             return Internalcreate(t, 1, &length, null);
6         }

  上面的代碼中,我們可以發現兩個地方需要關注,第一部分:RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType;該方法獲取數組元素類型的基礎系統類型,并將其轉換為 RuntimeType。第二部分:Internalcreate(t, 1, &length, null)具體創建數組的操作,我們來看一下其實現的源碼。(源碼進行部分刪減)


 1         private static unsafe Array Internalcreate(RuntimeType elementType, int rank, int* pLengths, int* pLowerBounds) 
 2         { 
 3             if (rank == 1) 
 4             { 
 5                 return RuntimeImports.RhNewArray(elementType.MakeArrayType().TypeHandle.ToEETypePtr(), pLengths[0]); 
 6             } 
 7             else 
 8             { 
 9                 int* pImmutableLengths = stackalloc int[rank];
 10                 
 11                 for (int i = 0; i < rank; i++) pImmutableLengths[i] = pLengths[i];
 12 
 13                 return NewMultiDimArray(elementType.MakeArrayType(rank).TypeHandle.ToEETypePtr(), pImmutableLengths, rank);
 14             }
 15         }

  該方法用于在運行時創建數組,其中參數elementType表示數組元素運行時的類型,rank表示數組的維度,pLengths表示指向數組長度的指針,pLowerBounds表示指向數組下限(如果有的話)的指針。根據設定的rank的值,創建一維或多維數組。其中elementType.MakeArrayType().TypeHandle.ToEETypePtr()表示先將當前type 對象表示的類型通過 MakeArrayType 方法創建一個數組類型,然后獲取該數組類型的運行時類型句柄,最后通過 ToEETypePtr 方法將運行時類型句柄轉換為指向類型信息的指針。我們先看一下創建一維數組的邏輯,具體代碼如下:


        [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);

  該方法是具體實現數組創建的邏輯,我們先來看一下參數,其中EETypePtr是CLR中用于表示對象類型信息的指針類型。每個.NET對象在運行時都關聯有一EEType結構,它包含有關對象類型的信息,例如該類型的方法表、字段布局、基類信息等。

  這里簡單的介紹一下代碼上面的兩個自定義屬性:

(1)、[MethodImpl(MethodImplOptions.InternalCall)] 
   指示編譯器生成的方法體會被一個外部實現取代,而該外部實現通常由運行時環境提供。
(
2)、[RuntimeImport(RuntimeLibrary, "RhNewArray")]     這是一個自定義的特性,在項目中定義的用于指示運行時導入的特性。
在C#中,使用屬性標記運行時導入的位置通常是為了提供額外的元數據和信息,以告訴編譯器和運行時環境如何正確地處理外部方法的調用。

  使用屬性標記運行時導入的主要目的有以下幾點:

(1)、元數據信息:運行時導入的位置可能包括一些元數據信息,如函數名稱、庫名稱、調用約定等。     使用屬性可以將這些信息嵌入到C#代碼中,使得代碼更加自解釋,并提供足夠的信息供編譯器和運行時使用。 
(2)、優化和安全性:編譯器和運行時環境可能會使用屬性來進行性能優化或安全性檢查。 例如,通過指定調用約定或其他屬性,可以幫助編譯器生成更有效的代碼。 
(3)、與運行時環境交互:屬性可以提供一種與底層運行時環境進行交互的機制。 例如,通過自定義屬性,可以向運行時環境傳遞一些特殊的標志或信息,以影響方法的行為。
(4)、代碼維護和可讀性:使用屬性可以提高代碼的可維護性和可讀性。 在代碼中使用屬性來標記運行時導入的位置,使得代碼的意圖更加清晰,也有助于團隊協作。

  在CLR的內部,EETypePtr是一個指向EEType結構的指針,其中EEType是運行時中用于描述對象類型的結構。EEType結構的內容由運行時系統生成和管理,而EETypePtr則是對這個結構的指針引用。根據傳入的運行時對象類型進行處理,我們接下來看一下pEEType.ToPointer()的實現。

1         internal unsafe Internal.Runtime.MethodTable* ToPointer()
2         {
3             return (Internal.Runtime.MethodTable*)(void*)_value;
4         }

  ToPointer()方法目的是將其對象或值轉換為指針,MethodTable 是CLR用于管理類和對象的元數據,用于存儲類型相關信息的數據結構,每個對象在內存中都包含一個指向其類型信息的指針,這個指針指向該類型的 MethodTable,用于支持CLR在運行時進行類型檢查、虛方法調用等操作。那我們來具體看一下MethodTable的數據結構。


 1         struct MethodTable 
 2         { 
 3             // 指向類型的虛方法表(VTable) 
 4             IntPtr* VirtualMethodTable; 
 5  
 6             // 字段表 
 7             FieldInfo* Fields; 
 8  
 9             // 接口表
 10             InterfaceInfo* Interfaces;
 11 
 12             // 其他元數據信息...
 13         }

  我們從原始的數組初始化和賦值,一直推導至對象的數組空間維護。截止當前,我們獲取到數組的MethodTable* pEEType數據結構。接下來我們來看一下CLR對數組的內存空間分配邏輯和維護方案。由于CoreCLR中的實現代碼我們沒有辦法全面的了解,我們接下按照預定的邏輯進行一定的推論。(CCoreCLR的實現代碼絕大部分是使用C++實現)


 1 #include <cstdint> 
 2  
 3 extern "C" { 
 4     struct MethodTable { // 方法表等信息...}; 
 5     struct Array { // 數組相關信息...}; 
 6     void* RhNewArray(void* pEEType, int length) { 
 7         // 假設存在一個用于對象分配的函數,該函數分配數組的內存 
 8         void* rawArrayMemory = AllocationFunction(length * sizeof(Array)); 
 9         // 將傳遞的 pEEType 信息保存到數組對象中
 10         Array* newArray = static_cast<Array*>(rawArrayMemory);
 11         //為數組對象設置元數據信息
 12         newArray->MethodTablePointer = pEEType;
 13         return rawArrayMemory;
 14     }
 15 }

  以上代碼是一種假設實現方式, AllocationFunction 的函數用于內存分配,并且數組對象(Array)有一個成員 MethodTablePointer 用于存儲 MethodTable 的指針。接下來我們再來看一下AllocationFunction()方法推測實現邏輯。


1 void* AllocationFunction(size_t size) {
2     // 使用標準庫的 malloc 函數進行內存分配
3     void* memory = malloc(size);
4     //處理內存分配失敗的情況
5     ...
6     return memory;
7 }

  以上的代碼中,使用標準函數庫malloc()進行內存的分配,malloc ()是C標準庫中的一個函數,用于在運行時動態分配內存。malloc ()接受一個 size 參數,表示要分配的內存字節數。它返回一個指向分配內存起始地址的指針,或者在分配失敗時返回 NULL。malloc ()內存分配邏輯通常涉及以下步驟:

(1)、請求內存空間: malloc() 根據傳遞的 size 參數向系統請求一塊足夠大的內存空間。 (2)、內存分配:如果系統成功分配了請求的內存塊,malloc 會在這塊內存中標記已分配的部分,并將其起始地址返回給調用者。 

(3)、返回結果:如果分配成功,malloc 返回一個指向新分配內存的指針。如果分配失?。ɡ?,系統內存不足),則返回 NULL。

(4)、內存對齊:部分系統要求分配的內存是按照特定字節對齊的。因此,malloc 通常會確保返回的內存地址滿足系統的對齊要求。 

(5)、初始化內存:malloc 返回的內存通常不會被初始化,即其中的數據可能是未知的。在使用之前,需要通過其他手段對內存進行初始化。 

(6)、內存管理:一些實現可能會使用內部數據結構來跟蹤已分配和未分配的內存塊,以便在 free 被調用時能夠釋放相應的內存。


  以上簡單的描述了C++在底層實現內存分配的簡單實現方式,對于CoreCLRe中對于數組的內存空間申請相對非常復雜,可能涉及內存池、分配策略、對齊要求等方面的考慮。后續有機會再做詳細的介紹。既然說到CoreCLR的內存實現為C++的內存分配策略,那我們接下來看一下其對應的常用策略管理策略。我們用一個簡單的數組的內存分配。

1 int myArray[5]; 
// 聲明一個包含5個整數的數組
2 
3 +------+------+------+------+------+
4 | int0 | int1 | int2 | int3 | int4 |
5 +------+------+------+------+------+

  myArray 是整個數組的起始地址,然后每個 int 元素按照其大小排列在一起?;谝陨系姆治?,我們可以看到C++對于內存的分配概述大致如下:


(1)、元素的內存布局:數組的元素在內存中是依次排列的,每個元素占用的內存空間由元素的類型決定。     例如,一個 int 數組中的每個整數元素通常占用4個字節(32位系統)或8個字節(64位系統)。 
(2)、數組的起始地址:數組的內存分配通常從數組的第一個元素開始。數組的起始地址是數組第一個元素的地址。
(3)、連續存儲:數組的元素在內存中是連續存儲的,這意味著數組中的每個元素都直接跟在前一個元素的后面。

  上面介紹了內存空間的分配,我們接下來看一下這段代碼的實現邏輯,rawArrayMemory: 這是一個 void* 類型的指針,通常指向分配的內存塊的起始位置。static_cast 運算符,將 rawArrayMemory 從 void* 類型轉換為 Array* 類型。

1  Array* newArray = static_cast<Array*>(rawArrayMemory);

  我們從以上對于數組的創建過程中,分析了C#、CoreCLR、C++等多個實現視角進行了簡單的分析。

  接下來我們回歸到CoreCLR中對于數組的內存空間管理策略,數組內存分配的常用步驟:

、分配對象頭:為數組對象分配對象頭,對象頭包含一些元數據,如類型指針、同步塊索引等信息。
、分配數組元素空間:分配存儲數組元素的內存塊,這是實際存儲數組數據的地方。
、初始化數組元素:根據數組類型的要求,初始化數組元素。這可能涉及到對元素進行默認初始化,例如將整數數組的每個元素初始化為零。
、返回數組引用:返回指向數組對象的引用,使得該數組可以被使用。

  當我們在托管代碼中聲明一個數組時,CoreCLR會在托管堆上動態分配內存,以存儲數組的元素,并在分配的內存塊中存儲有關數組的元數據,這些元數據通常包括數組的長度和元素類型等信息。CoreCLR通常會對分配的內存進行對齊,以提高訪問效率,這可能導致分配的內存塊略大于數組元素的實際大小??赡苡型瑢W會問為什么要進行內存的對齊,這里就簡單的說明一下。

、硬件要求:訪問特定類型的數據時,其地址應該是某個值的倍數。

、提高訪問速度:對齊的內存訪問通常比不對齊的訪問更加高效。處理器通常能夠更快地訪問對齊的內存,因為這符合硬件訪問模式。

、減少內存碎片:內存對齊還有助于減少內存碎片,使得內存的使用更加緊湊。內存碎片可能導致性能下降,因為它可能增加了分配和釋放內存的開銷。

、硬件事務:一些處理器和操作系統支持原子操作,但通常要求數據是按照特定的對齊方式排列的。


  上面介紹了為什么需要進行內存對齊,那么對于CoreCLR的內部實現是如何進行內存對齊的呢?我們簡潔的介紹一下實現大流程:


、使用操作系統的內存分配函數:使用操作系統提供的內存分配函數來分配托管堆上的內存。在Windows上可能是HeapAlloc。
、對齊方式的指定:在調用內存分配函數時,會指定所需的對齊方式。通常是以字節為單位的對齊值。常見的對齊值包括4字節、8字節等。
、內存塊的對齊:內存分配函數返回的內存塊通常是按照指定的對齊方式進行對齊的。CLR確保返回的內存塊的起始地址符合對齊規則。
、對齊規則的維護:維護對齊規則的信息,確保在托管堆上分配和釋放的內存塊都符合相同的對齊方式。
、內存對齊的優化:對內存對齊進行一些優化,以提高訪問效率。例如,它可以在對象的布局中考慮對齊規則,以減少內存碎片。

  具體的數組內存分配策略可能會因CLR的版本和實現而異。不同的垃圾回收算法(如標記-清除、復制、標記-整理等)以及不同的GC代(新生代、老年代)也可能影響內存分配的具體實現。在.NET中,CLR提供了不同的垃圾回收器實現,例如Workstation GC和Server GC。Workstation GC通常適用于單處理器或少量處理器的環境,而Server GC適用于多處理器環境。這些GC實現可能在內存分配和回收方面有一些差異。

  本文借助了一個數組的初始化和賦值為樣例,逐層的分析了數組對象運行時結構的獲取、對象MethodTable結構的分析、CoreCLR底層對數組內存結構的創建推導、C++對于內存的分配策略等視角,最后還綜合的介紹了CoreCLR對于數組內存的創建步驟。

  我們一直以來對于數組的內存分配,都有一個整體的認識,其特點是"相同類型、連續內存、順序存儲",對于其連續內存的特點記憶深刻,但是在內部如何實現進行的連續內存卻沒有整體的了解,C#內部是如何完成不同類型對象數組的運行時創建,在CoreCLR內部如何進行內存的劃分是沒有做過了解和推導,甚至于CoreCLR內部是如何維護一個對象的結構,很多時候都只是了解到運行時對象使用Type類型就可以得到,那么CoreCLR內部如何來維護這個Type呢?其實很多時候沒有特點去了解過其結構。

  以上內容是對C#中Array的存儲結構的簡單介紹,如錯漏的地方,還望指正。



該文章在 2023/11/29 8:39:58 編輯過
關鍵字查詢
相關文章
正在查詢...
點晴ERP是一款針對中小制造業的專業生產管理軟件系統,系統成熟度和易用性得到了國內大量中小企業的青睞。
點晴PMS碼頭管理系統主要針對港口碼頭集裝箱與散貨日常運作、調度、堆場、車隊、財務費用、相關報表等業務管理,結合碼頭的業務特點,圍繞調度、堆場作業而開發的。集技術的先進性、管理的有效性于一體,是物流碼頭及其他港口類企業的高效ERP管理信息系統。
點晴WMS倉儲管理系統提供了貨物產品管理,銷售管理,采購管理,倉儲管理,倉庫管理,保質期管理,貨位管理,庫位管理,生產管理,WMS管理系統,標簽打印,條形碼,二維碼管理,批號管理軟件。
點晴免費OA是一款軟件和通用服務都免費,不限功能、不限時間、不限用戶的免費OA協同辦公管理系統。
Copyright 2010-2025 ClickSun All Rights Reserved