內(nèi)存排布示例

內(nèi)存碎片

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

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

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

內(nèi)部碎片和外部碎片

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

繼承類布局

繼承

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

含虛函數(shù)的類

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

vtable中包含當(dāng)前類的所有虛函數(shù)指針。

字節(jié)序（endianness)

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

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

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

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

大小端排布

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

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

操作系統(tǒng)

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

SIMD

SIMD，即Single Instruction Multiple Data，用一個指令并行地對多個數(shù)據(jù)進(jìn)行運(yùn)算，是CPU基本指令集的擴(kuò)展。

例一

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

例二

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

SIMD并行計(jì)算

高速緩存

一般來說CPU以超高速運(yùn)行，而內(nèi)存速度慢于CPU，硬盤速度慢于內(nèi)存。

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

L1緩存和L2緩存

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

① CPU請求數(shù)據(jù)：如果數(shù)據(jù)已經(jīng)在緩存中，則直接從緩存載入寄存器；如果數(shù)據(jù)不在緩存中（緩存命中失?。?，則需要從內(nèi)存讀取，并將內(nèi)存載入緩存中。

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

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

虛擬內(nèi)存

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

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

缺頁

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

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

分頁

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

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

置換算法

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

常見的置換有如下幾種：

● 最近未使用置換（NRU）

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

● 先入先出置換（FIFO)

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

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

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

C++語法

位域（Bit Fields）

表示結(jié)構(gòu)體位域的定義，指定變量所占位數(shù)。它通常位于成員變量后，用 聲明符：常量表達(dá)式 表示。（參考資料）

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

以下是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)]; // 內(nèi)存分配 for (size_t i = 0; i < size; i++) { new (buf + i * sizeof(A)) A(i); // 對象構(gòu)造 }
 A* arr = (A*)buf; for (size_t i = 0; i < size; i++) { arr[i].print(); arr[i].~A(); // 對象析構(gòu) } // 棧上預(yù)分配的內(nèi)存自動釋放 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; // 構(gòu)造allocator對象 auto const p = alloc.allocate(n); // 分配n個未初始化的string 

auto q = p;
alloc.construct(q++, "hello"); // 在分配的內(nèi)存處創(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指定的未構(gòu)造的原始內(nèi)存中； uninitialized_copy(b, n, b2) // 從迭代器b指向的元素開始，拷貝n個元素到b2開始的內(nèi)存中； uninitialized_fill(b, e, t) // 從迭代器b和e指定的原始內(nèi)存范圍中創(chuàng)建對象，對象的值均為t的拷貝； uninitialized_fill_n(b, n, t) // 從迭代器b指向的內(nèi)存地址開始創(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;