前言

作為一個優(yōu)秀的開源編譯器框架，llvm的代碼比gcc代碼的可讀性更好。因此無論是學(xué)習(xí)c++，還是學(xué)習(xí)編譯原理、設(shè)計模式、數(shù)據(jù)結(jié)構(gòu)，都是一個很好的學(xué)習(xí)目標(biāo)。

這篇文章是受侯捷老師《STL源碼剖析》的啟發(fā)，希望對llvm中的數(shù)據(jù)結(jié)構(gòu)進行一些解讀，因為llvm中有許多類似于STL中的數(shù)據(jù)。例如 map-like containner、set-like container、sequential container、string container、bit container等容器。

原創(chuàng)不易，您的關(guān)注就是我最大的動力。希望看到的朋友能點個關(guān)注，后續(xù)會把這個llvm數(shù)據(jù)結(jié)構(gòu)系列持續(xù)更新下去。

本文將對llvm中源碼進行分析，主要是了解其中一個類似于std::vector的數(shù)據(jù)結(jié)構(gòu)。并與之進行對比。

1.SmallVector概述

SmallVector是llvm中自定義的一種通用數(shù)據(jù)結(jié)構(gòu)，在llvm的各層次間都可以使用。SmallVector與std::Vector非常類似 ，支持迭代、push_back、pop_back，以及隨機存取元素。

但是SmallVector對于元素較少的情況時性能是優(yōu)于std::vector的。這是因為SmallVector使用了一種比較通用的局部緩存設(shè)計模式，減少了malloc/free的巨大開銷。接下來會以SmallVecotor為載體，一步步揭開局部緩存設(shè)計模式的神秘面紗。同時我們還可以從中學(xué)到一些設(shè)計類的技巧。

這篇文章需要一點c++基礎(chǔ)，需要c++資料的同學(xué)可以在我的公眾號[程序芯世界]回復(fù)c++即可獲取Modern C++的學(xué)習(xí)資料。里面有一本講c++ 設(shè)計模式的書個人感覺不錯，并且提到了本文中的局部緩存設(shè)計模式，有興趣的可以看看（因為覺得不錯，當(dāng)初還花了我30塊買的這本電子書）。

2.局部緩存設(shè)計模式

在詳細(xì)了解SmallVector之前先來回顧一下std::vector和std::array，對比之后更容易了解SmallVector的優(yōu)勢。

std::vector會調(diào)用malloc函數(shù)申請一塊內(nèi)存用于放置元素 std::array是對內(nèi)置數(shù)組的一個封裝，因此其存放元素的數(shù)組會與std::array放置在同一個位置。如果std::array是在棧上聲明的，那么其存放元素的數(shù)組也位于棧上。

內(nèi)存的位置不同導(dǎo)致了std::array與std::vector效率的不同。因為std::vector是通過malloc申請的堆內(nèi)存，而std::array是棧內(nèi)存。

堆內(nèi)存的申請需要調(diào)用系統(tǒng)函數(shù)分配內(nèi)存，這個開銷是巨大的。相比之下，棧內(nèi)存幾乎是零開銷，因為只需要調(diào)整棧指針。當(dāng)然std::array也并不總是在棧上的，取決于你分配它的方式。但是任然會比std::vector少分配一次堆內(nèi)存。

stackoverflow上有一個很好的關(guān)于兩者的對比。std::vector versus std::array in C++

smallvector的本質(zhì)就是當(dāng)元素個數(shù)少的時候像std::array一樣將存儲元素的內(nèi)存放在類里面，當(dāng)元素個數(shù)多的時候像std::vector一樣分配堆內(nèi)存。這樣就兼具了兩者的優(yōu)點。這種操作被稱為局部緩存設(shè)計模式，在llvm很多地方都有體現(xiàn)。

下一節(jié)會對SmallVector進行詳細(xì)介紹，主要是關(guān)注類之間的抽象。

2.SmallVector的繼承關(guān)系

為了減少代碼冗余和提高代碼的可復(fù)用性，llvm對SmallVecotr這個類進行了多個層次的抽象。本節(jié)主要介紹與SmallVecotr有繼承關(guān)系的六個類。

由于這幾個類之間本身的關(guān)系并不復(fù)雜，因此沒有使用UML圖，而是簡單的畫出了繼承關(guān)系。

SmallVector繼承關(guān)系圖

2.1 SmallVector

其中SmallVector繼承自SmallVectorImpl和SmallVectorStorage。

复制template

首先來看SmallVector，它繼承了SmallVectorImpl和SmallVectorStorage。SmallVector本身只有一系列構(gòu)造函數(shù)（拷貝構(gòu)造、賦值構(gòu)造等），沒有成員變量，具體的一些成員函數(shù)放在SmallVectorImpl中，存儲元素的數(shù)組放在SmallVectorStorage中。需要注意的是SmallVectorStorage類中直接聲明了一個數(shù)組。

2.2 SmallVectorStorage

复制template <typename T, unsigned N>
struct SmallVectorStorage {
  alignas(T) char InlineElts[N * sizeof(T)];
};

這個數(shù)組會和對象放在同一塊內(nèi)存，當(dāng)需要存放的元素較少時就可以放在這個數(shù)組中，避免了調(diào)用malloc產(chǎn)生巨大的開銷。

2.3 SmallVectorImpl

复制template <typename T>
class SmallVectorImpl : public SmallVectorTemplateBase

上面提到SmallVector中之定義了一些構(gòu)造函數(shù)，而其他的一些具體的操作函數(shù)則定義在SmallVectorImpl。這樣做的原因是什么呢？看明白下面這個小例子就理解為啥這樣設(shè)計了。

复制// DISCOURAGED: Clients cannot pass e.g. SmallVector
hardcodedSmallSize(SmallVector

從上述的例子可以看出，hardcodedSmallSize函數(shù)接受的參數(shù)是SmallVector，如果傳入的參數(shù)是SmallVector肯定是類型不匹配。此時SmallVectorImpl就起作用了，因為SmallVectorImpl是SmallVector的父類，可以向上隱式轉(zhuǎn)換，同時也不用傳遞參數(shù)N。這就是設(shè)計SmallVectorImpl的妙處。

2.4 SmallVectorTemplateBase

下面兩個都是SmallVectorTemplateBase類，不同的是第二個模板參數(shù)不同。針對元素是否為POD類型進行了偏特化。

复制template

以grow函數(shù)為例，來看是否為POD類型時不同的處理方式。下面為類型為非POD類型時grow函數(shù)的實現(xiàn)方式

复制template <typename T, bool TriviallyCopyable>
void SmallVectorTemplateBase

可以看到，非POD類型時，會調(diào)用moveElementsForGrow函數(shù)對每一個元素進行移動。同時會調(diào)用takeAllocationForGrow，如果是在堆上分配的內(nèi)存takeAllocationForGrow會調(diào)用free釋放之前分配的內(nèi)存。

复制template <typename T>
class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon

下面是POD類型時grow函數(shù)的實現(xiàn)方式。

复制template <class Size_T>
void SmallVectorBase

與非POD類型的grow函數(shù)對比可以發(fā)現(xiàn)，這兒移動元素是調(diào)用memcpy直接對整體的內(nèi)存進行拷貝。同時也沒有對每一個元素的內(nèi)存進行釋放。

2.5 SmallVectorTemplateCommon

复制template <typename T, typename = void>
class SmallVectorTemplateCommon
    : public SmallVectorBase

SmallVectorTemplateCommon是不依賴于是否為POD類型的公共部分，冗余的模版參數(shù)T是為了給ArrayRef使用。ArrayRef可以是SmallVector或者std::Vector的引用，后續(xù)會寫文章介紹ArrayRef。

2.6 SmallVectorBase

SmallVectorBase是SmallVector所有的公共部分

复制template <class Size_T> class SmallVectorBase {
protected:
  void *BeginX;
  Size_T Size = 0, Capacity;
  ...
}

其中BeginX表示目前使用空間的頭部，Size表示已經(jīng)使用的空間大小，Capacity表示目前空間的容量。需要注意的是BeginX的初始化。前面已經(jīng)提到過，當(dāng)元素數(shù)量較少時是存儲在SmallVectorStorage定義的數(shù)組中。因此BeginX的初始值應(yīng)該是InlineElts的地址。如下所示是SmallVectorTemplateCommon的構(gòu)造函數(shù)

复制SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}

調(diào)用該構(gòu)造函數(shù)時會首先對SmallVectorBase的構(gòu)造函數(shù)，此時會對BeginX進行初始化，上面的Base就代表SmallVectorBase。可以看到BeginX是調(diào)用getFirstEl()進行初始化的。在來看看getFirstEl()，該函數(shù)會通過this指針的地址加上一個偏移量來得到。這個偏移量是通過一個SmallVectorAlignmentAndSize的struct得到。

复制void *getFirstEl() const {
    return const_cast<void *>(reinterpret_cast<const void *>(
        reinterpret_cast<const char *>(this) +
        offsetof(SmallVectorAlignmentAndSize

再來看看SmallVectorAlignmentAndSize這個結(jié)構(gòu)體，是由SmallVectorBase和FirstEl組成，正好SmallVector中SmallVectorBase占有內(nèi)存后就是SmallVectorStorage中InlineElts占有的內(nèi)存，因此FirstEl的偏移量也是InlineElts的偏移量。

复制template <class T, typename = void> struct SmallVectorAlignmentAndSize {
  alignas(SmallVectorBase

3.SmallVector迭代器

同std::Vector一樣，SmallVector維護的是一個連續(xù)的線性空間普通的指針都可以作為SmallVector的迭代器滿足所有的必要條件，例如operator*，operator++，operator--等。不需要額外的對這些操作符進行重載。

需要注意的是SmallVector同Vector一樣，當(dāng)發(fā)生擴容時其迭代器會失效。

4總結(jié)

• SmallVector只定義了一系列構(gòu)造函數(shù)，具體實現(xiàn)在SmallVectorImpl
• SmallVectorStorage定義了存儲元素的數(shù)組
• SmallVectorTemplateBase對是否為POD類型進行了偏特化
• SmallVectorTemplateCommon是不依賴于是否為POD類型的公共部分
• 元素的首地址通過getFirstEl()計算一個偏移量得到
• SmallVector是std::array與std::vector的結(jié)合體，因此具備兩者共同的優(yōu)點。
• SmallVector迭代器在發(fā)生擴容時會失效。

文章到這兒已經(jīng)結(jié)束啦，如果想要更深入的了解可以結(jié)合這篇文章深入了解一下源碼，這樣收獲會更大，沒有涉及到的地方歡迎留言討論。