萬字長文|深入 C++ 內存管理

內存排布示例

內存碎片

程序的內存往往不是緊湊連續(xù)排布的，而是存在著許多碎片。我們根據碎片產生的原因把碎片分為內部碎片和外部碎片兩種類型：

(1) 內部碎片：系統(tǒng)分配的內存大于實際所需的內存（由于對齊機制）；

(2) 外部碎片：不斷分配回收不同大小的內存，由于內存分布散亂，較大內存無法分配；

內部碎片和外部碎片

為了提高內存的利用率，我們有必要減少內存碎片，具體的方案將在后文重點介紹。

繼承類布局

繼承

如果一個類繼承自另一個類，那么它自身的數據位于父類之后。

含虛函數的類

如果當前類包含虛函數，則會在類的最前端占用4個字節(jié)，用于存儲虛表指針（vpointer)，它指向一個虛函數表（vtable)。

vtable中包含當前類的所有虛函數指針。

字節(jié)序（endianness)

大于一個字節(jié)的值被稱為多字節(jié)量，多字節(jié)量存在高位有效字節(jié)和低位有效字節(jié) (關于高位和低位，我們以十進制的數字來舉例，對于數字482來說，4是高位，2是低位），微處理器有兩種不同的順序處理高位和低位字節(jié)的順序：

● 小端（little_endian)：低位有效字節(jié)存儲于較低的內存位置

● 大端（big_endian)：高位有效字節(jié)存儲于較低的內存位置

我們使用的PC開發(fā)機默認是小端存儲。

大小端排布

一般情況下，多字節(jié)量的排列順序對編碼沒有影響。但如果要考慮跨平臺的一些操作，就有必要考慮到大小端的問題。如下圖，ue4引擎使用了PLATFORM_LITTLE_ENDIAN這一宏，在不同平臺下對數據做特殊處理（內存排布交換，確保存儲時的結果一致）。

ue4針對大小端對數據做特殊處理（ByteSwap.h)

操作系統(tǒng)

對一些基礎概念有所了解后，我們可以來關注操作系統(tǒng)底層的一些設計。在掌握了這些特性后，我們才能更好地針對性地編寫高性能代碼。

SIMD

SIMD，即Single Instruction Multiple Data，用一個指令并行地對多個數據進行運算，是CPU基本指令集的擴展。

例一

處理器的寄存器通常是32位或者64位的，而圖像的一個像素點可能只有8bit，如果一次只能處理一個數據比較浪費空間；此時可以將64位寄存器拆成8個8位寄存器，就可以并行完成8個操作，提升效率。

例二

SSE指令采用128位寄存器，我們通常將4個32位浮點值打包到128位寄存器中，單個指令可完成4對浮點數的計算，這對于矩陣/向量操作非常友好（除此之外，還有Neon/FPU等寄存器）

SIMD并行計算

高速緩存

一般來說CPU以超高速運行，而內存速度慢于CPU，硬盤速度慢于內存。

當我們把數據加載內存后，要對數據進行一定操作時，會將數據從內存載入CPU寄存器?？紤]到CPU讀/寫主內存速度較慢，處理器使用了高速的緩存（Cache)，作為內存到CPU中間的媒介。

L1緩存和L2緩存

引入L1和L2緩存后，CPU和內存之間的將無法進行直接的數據交互，而是需要經過兩級緩存（目前也已出現(xiàn)L3緩存）。

① CPU請求數據：如果數據已經在緩存中，則直接從緩存載入寄存器；如果數據不在緩存中（緩存命中失?。?，則需要從內存讀取，并將內存載入緩存中。

② CPU寫入數據：有兩種方案，(1) 寫入到緩存時同步寫入內存（write through cache) (2) 僅寫入到緩存中，有必要時再寫入內存(write-back)

為了提高程序性能，則需要盡可能避免緩存命中失敗。一般而言，遵循盡可能地集中連續(xù)訪問內存，減少”跳變“訪問的原則（locality of reference)。這里其實隱含了兩個意思，一個是內存空間上要盡可能連續(xù)，另外一個是訪問時序上要盡可能連續(xù)。像節(jié)點式的數據結構的遍歷就會差于內存連續(xù)性的容器。

虛擬內存

虛擬內存，也就是把不連續(xù)的物理內存塊映射到虛擬地址空間（virtual address space)。使內存頁對于應用程序來說看起來是連續(xù)的。一般而言，出于程序安全性和物理內存可能不足的考慮，我們的程序都會運行在虛擬內存上。

這意味著，每個程序都有自己的地址空間，我們使用的內存存在一個虛擬地址和一個物理地址，兩者之間需要進行地址翻譯。

缺頁

在虛擬內存中，每個程序的地址空間被劃分為多個塊，每個內存塊被稱作頁，每個頁的包含了連續(xù)的地址，并且被映射到物理內存。并非所有頁都在物理內存中，當我們訪問了不在物理內存中的頁時，這一現(xiàn)象稱為缺頁，操作系統(tǒng)會從磁盤將對應內容裝載到物理內存；當內存不足，部分頁也會寫回磁盤。

在這里，我們將CPU，高速緩存和主存視為一個整體，統(tǒng)稱為DRAM。由于DRAM與磁盤之間的讀寫也比較耗時，為了提高程序性能，我們依然需要確保自己的程序具有良好的“局部性”——在任意時刻都在一個較小的活動頁面上工作。

分頁

當使用虛擬內存時，會通過MMU將虛擬地址映射到物理內存，虛擬內存的內存塊稱為頁，而物理內存中的內存塊稱為頁框，兩者大小一致，DRAM和磁盤之間以頁為單位進行交換。

簡單來說，如果想要從虛擬內存翻譯到物理地址，首先會從一個TLB（Translation Lookaside Buffer)的設備中查找，如果找不到，在虛擬地址中也記錄了虛擬頁號和偏移量，可以先通過虛擬頁號找到頁框號，再通過偏移量在對應頁框進行偏移，得到物理地址。為了加速這個翻譯過程，有時候還會使用多級頁表，倒排頁表等結構。

置換算法

到目前為止，我們已經接觸了不少和“置換”有關的內容：例如寄存器和高速緩存之間，DRAM和磁盤之間，以及TLB的緩存等。這個問題的本質是，我們在有限的空間內存儲了一些快速查詢的結構，但是我們無法存儲所有的數據，所以當查詢未命中時，就需要花更大的代價，而所謂置換，也就是我們的快速查詢結構是在不斷更新的，會隨著我們的操作，使得一部分數據被裝在到快速查詢結構中，又有另一部分數據被卸載，相當于完成了數據的置換。

常見的置換有如下幾種：

● 最近未使用置換（NRU）

出現(xiàn)未命中現(xiàn)象時，置換最近一個周期未使用的數據。

● 先入先出置換（FIFO)

出現(xiàn)未命中現(xiàn)象時，置換最早進入的數據。

● 最近最少使用置換（LRU)

出現(xiàn)未命中現(xiàn)象時，置換未使用時間最長的數據。

C++語法

位域（Bit Fields）

表示結構體位域的定義，指定變量所占位數。它通常位于成員變量后，用 聲明符：常量表達式 表示。（參考資料）

聲明符是可選的，匿名字段可用于填充。

以下是ue4中Float16的定義：

struct { #if PLATFORM_LITTLE_ENDIAN uint16 Mantissa : 10;
    uint16 Exponent : 5;
    uint16 Sign : 1; #else uint16 Sign : 1;
    uint16 Exponent : 5;
    uint16 Mantissa : 10; #endif } Components;

::(optional) new (placement_params)(optional) ( type ) initializer(optional)

p_var = new type(initializer); // p_var = new type{initializer}; 

p_var = new type[size]; // 分配 delete[] p_var; // 釋放 

auto p = new double[2][2]; auto p = new double[2][2]{ {1.0,2.0},{3.0,4.0} };

new (nothrow) Type (optional-initializer-expression-list)

auto p = new auto('c');

class A { private: int data; public:
 A(int indata) 
  : data(indata) { } void print() { cout << data << endl;
 }
}; int main() { const int size = 10; char buf[size * sizeof(A)]; // 內存分配 for (size_t i = 0; i < size; i++) { new (buf + i * sizeof(A)) A(i); // 對象構造 }
 A* arr = (A*)buf; for (size_t i = 0; i < size; i++) { arr[i].print(); arr[i].~A(); // 對象析構 } // 棧上預分配的內存自動釋放 return 0;
}

auto p = new(std::align_val_t{ 32 }) A;

// Default placement versions of operator new. inline void* operator new(std::size_t, void* __p) throw() { return __p; } inline void* operator new[](std::size_t, void* __p) throw() { return __p; } // Default placement versions of operator delete. inline void operator delete (void*, void*) throw() { } inline void operator delete[](void*, void*) throw() { }

void* operator new(std::size_t, const std::nothrow_t&) throw(); void* operator new[](std::size_t, const std::nothrow_t&) throw(); void operator delete(void*, const std::nothrow_t&) throw(); void operator delete[](void*, const std::nothrow_t&) throw();

#pragma pack(n) 

struct alignas(8) S { // ... }; struct alignas(1) U {
    S s;
};

struct alignas(2) S { int n;
};

struct alignas(3) S { };

// every object of type sse_t will be aligned to 16-byte boundary struct alignas(16) sse_t { float sse_data[4];
}; // the array "cacheline" will be aligned to 128-byte boundary alignas(128) char cacheline[128];

struct Foo { int i; float f; char c;
}; struct Empty { }; struct alignas(64) Empty64 { }; int main() { std::cout << "Alignment of" "\n" "- char          :" << alignof(char)    << "\n" // 1 "- pointer       :" << alignof(int*)    << "\n" // 8 "- class Foo     :" << alignof(Foo)     << "\n" // 4 "- empty class   :" << alignof(Empty)   << "\n" // 1 "- alignas(64) Empty:" << alignof(Empty64) << "\n"; // 64 }

template < class T, class Alloc = allocator> class vector; // generic template 

allocator<string> alloc; // 構造allocator對象 auto const p = alloc.allocate(n); // 分配n個未初始化的string 

auto q = p;
alloc.construct(q++, "hello"); // 在分配的內存處創(chuàng)建對象 alloc.construct(q++, 10, 'c');

while(q != p)
    alloc.destroy(--q);

alloc.deallocate(p, n);

uninitialized_copy(b, e, b2) // 從迭代器b, e 中的元素拷貝到b2指定的未構造的原始內存中； uninitialized_copy(b, n, b2) // 從迭代器b指向的元素開始，拷貝n個元素到b2開始的內存中； uninitialized_fill(b, e, t) // 從迭代器b和e指定的原始內存范圍中創(chuàng)建對象，對象的值均為t的拷貝； uninitialized_fill_n(b, n, t) // 從迭代器b指向的內存地址開始創(chuàng)建n個對象； 

shared_ptr<int> p = make_shared<int>(42);

auto p = make_shared<int>(42); auto r = make_shared<int>(42);
r = q; // 遞增q指向的對象，遞減r指向的對象 

shared_ptr<int> p1 = new int(1024); // err shared_ptr<int> p2(new int(1024)); // ok 

p.reset(new int(1024));

unique_ptr<string> p = make_unique<string>("test");

unique_ptr<string> p1(new string("test")); unique_ptr<string> p2(p1); // err unique_ptr<string> p3;
p3 = p2; // err 

unique_ptr<string> p2(p1.release()); unique_ptr<string> p3(new string("test"));
p2.reset(p3.release());

p2.release(); // err auto p = p2.release(); // ok, but remember to delete(p) 

unique_ptr<int> clone(int p) { return unique_ptr<int>(new int(p));
}

auto p = make_shared<int>(42); weak_ptr<int> wp(p); if(shared_ptr<int> np = wp.lock())
{ // ... }

template <typename T> FORCEINLINE constexpr T Align(T Val, uint64 Alignment) { static_assert(TIsIntegral::Value || TIsPointer::Value, "Align expects an integer or pointer type"); return (T)(((uint64)Val + Alignment - 1) & ~(Alignment - 1));
}

/** The global memory allocator's interface. */ class CORE_API FMalloc : public FUseSystemMallocForNew, public FExec
{ public: virtual void* Malloc( SIZE_T Count, uint32 Alignment=DEFAULT_ALIGNMENT ) = 0; virtual void* TryMalloc( SIZE_T Count, uint32 Alignment=DEFAULT_ALIGNMENT ); virtual void* Realloc( void* Original, SIZE_T Count, uint32 Alignment=DEFAULT_ALIGNMENT ) = 0; virtual void* TryRealloc(void* Original, SIZE_T Count, uint32 Alignment=DEFAULT_ALIGNMENT); virtual void Free( void* Original ) = 0; // ... };

 /** Which allocator is being used */ enum EMemoryAllocatorToUse
 {
  Ansi, // Default C allocator Stomp, // Allocator to check for memory stomping TBB, // Thread Building Blocks malloc Jemalloc, // Linux/FreeBSD malloc Binned, // Older binned malloc Binned2, // Newer binned malloc Binned3, // Newer VM-based binned malloc, 64 bit only Platform, // Custom platform specific allocator Mimalloc, // mimalloc };

struct CORE_API FMemory { /** @name Memory functions (wrapper for FPlatformMemory) */ static FORCEINLINE void* Memmove( void* Dest, const void* Src, SIZE_T Count ) { return FPlatformMemory::Memmove( Dest, Src, Count );
 } static FORCEINLINE int32 Memcmp( const void* Buf1, const void* Buf2, SIZE_T Count ) { return FPlatformMemory::Memcmp( Buf1, Buf2, Count );
 } // ... static void* Malloc(SIZE_T Count, uint32 Alignment = DEFAULT_ALIGNMENT); static void* Realloc(void* Original, SIZE_T Count, uint32 Alignment = DEFAULT_ALIGNMENT); static void Free(void* Original); static SIZE_T GetAllocSize(void* Original); // ... };

template<typename InElementType, typename InAllocator> class TArray { // ... };

template <int IndexSize> class TSizedHeapAllocator { ... }; // Default Allocator using FHeapAllocator = TSizedHeapAllocator<32>;

templateclass TAlignedHeapAllocator
{ // ... };

template typename SecondaryAllocator = FDefaultAllocator>
class TInlineAllocator
{ //... };

template class TNonRelocatableInlineAllocator { // ... };

template class TFixedAllocator { // ... };

template<typename InElementAllocator = FDefaultAllocator,typename InBitArrayAllocator = FDefaultBitArrayAllocator>
class TSparseArrayAllocator
{ public: typedef InElementAllocator ElementAllocator; typedef InBitArrayAllocator BitArrayAllocator;
};

template< typename InSparseArrayAllocator               = TSparseArrayAllocator<>, typename InHashAllocator                      = TInlineAllocator<1,FDefaultAllocator>,
 uint32   AverageNumberOfElementsPerHashBucket = DEFAULT_NUMBER_OF_ELEMENTS_PER_HASH_BUCKET,
 uint32   BaseNumberOfHashBuckets              = DEFAULT_BASE_NUMBER_OF_HASH_BUCKETS,
 uint32   MinNumberOfHashedElements            = DEFAULT_MIN_NUMBER_OF_HASHED_ELEMENTS
 >
class TSetAllocator
{ public: static FORCEINLINE uint32 GetNumberOfHashBuckets(uint32 NumHashedElements) { //... } typedef InSparseArrayAllocator SparseArrayAllocator; typedef InHashAllocator        HashAllocator;
};

template< class ObjectType, ESPMode Mode > class TSharedPtr { // ... private:
 ObjectType* Object;
 SharedPointerInternals::FSharedReferencer< Mode > SharedReferenceCount;
};

template< class ObjectType, ESPMode Mode > class TSharedRef { // ... private:
 ObjectType* Object;
 SharedPointerInternals::FSharedReferencer< Mode > SharedReferenceCount;
};

template<typename ReferencedType> class TRefCountPtr { // ... private:
 ReferencedType* Reference;
};

class FRefCountBase { public: // ... private: mutable int32 NumRefs = 0;
};

template< class ObjectType, ESPMode Mode > class TWeakPtr { };

template<class T, class TWeakObjectPtrBase> struct TWeakObjectPtr : private TWeakObjectPtrBase
{ // ... }; struct FWeakObjectPtr { // ... private:
 int32  ObjectIndex;
 int32  ObjectSerialNumber;
};

typedef __m128 VectorRegister; FORCEINLINE VectorRegister VectorLoad( const void* Ptr ) { return _mm_loadu_ps((float*)(Ptr));
} FORCEINLINE VectorRegister VectorAdd( const VectorRegister& Vec1, const VectorRegister& Vec2 ) { return _mm_add_ps(Vec1, Vec2);
} FORCEINLINE VectorRegister VectorSubtract( const VectorRegister& Vec1, const VectorRegister& Vec2 ) { return _mm_sub_ps(Vec1, Vec2);
} FORCEINLINE VectorRegister VectorMultiply( const VectorRegister& Vec1, const VectorRegister& Vec2 ) { return _mm_mul_ps(Vec1, Vec2);
}

 /** Addition operator. */ friend FORCEINLINE TSHVector operator+(const TSHVector& A,const TSHVector& B)
 {
  TSHVector Result; for(int32 BasisIndex = 0;BasisIndex < NumSIMDVectors;BasisIndex++) { VectorRegister AddResult = VectorAdd( VectorLoadAligned(&A.V[BasisIndex * NumComponentsPerSIMDVector]), VectorLoadAligned(&B.V[BasisIndex * NumComponentsPerSIMDVector]) ); VectorStoreAligned(AddResult, &Result.V[BasisIndex * NumComponentsPerSIMDVector]); } return Result;