前言

作為一個優秀的開源編譯器框架，llvm的代碼比gcc代碼的可讀性更好。因此無論是學習c++，還是學習編譯原理、設計模式、數據結構，都是一個很好的學習目標。

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

原創不易，您的關注就是我最大的動力。希望看到的朋友能點個關注，后續會把這個llvm數據結構系列持續更新下去。

本文將對llvm中源碼進行分析，主要是了解其中一個類似于std::vector的數據結構。并與之進行對比。

1.SmallVector概述

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

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

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

2.局部緩存設計模式

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

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

內存的位置不同導致了std::array與std::vector效率的不同。因為std::vector是通過malloc申請的堆內存，而std::array是棧內存。

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

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

smallvector的本質就是當元素個數少的時候像std::array一樣將存儲元素的內存放在類里面，當元素個數多的時候像std::vector一樣分配堆內存。這樣就兼具了兩者的優點。這種操作被稱為局部緩存設計模式，在llvm很多地方都有體現。

下一節會對SmallVector進行詳細介紹，主要是關注類之間的抽象。

2.SmallVector的繼承關系

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

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

SmallVector繼承關系圖

2.1 SmallVector

其中SmallVector繼承自SmallVectorImpl和SmallVectorStorage。

template

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

2.2 SmallVectorStorage

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

這個數組會和對象放在同一塊內存，當需要存放的元素較少時就可以放在這個數組中，避免了調用malloc產生巨大的開銷。

2.3 SmallVectorImpl

template <typename T>
class SmallVectorImpl : public SmallVectorTemplateBase

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

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

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

2.4 SmallVectorTemplateBase

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

template

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

template <typename T, bool TriviallyCopyable>
void SmallVectorTemplateBase

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

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

下面是POD類型時grow函數的實現方式。

template <class Size_T>
void SmallVectorBase

與非POD類型的grow函數對比可以發現，這兒移動元素是調用memcpy直接對整體的內存進行拷貝。同時也沒有對每一個元素的內存進行釋放。

2.5 SmallVectorTemplateCommon

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

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

2.6 SmallVectorBase

SmallVectorBase是SmallVector所有的公共部分

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

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

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

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

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

再來看看SmallVectorAlignmentAndSize這個結構體，是由SmallVectorBase和FirstEl組成，正好SmallVector中SmallVectorBase占有內存后就是SmallVectorStorage中InlineElts占有的內存，因此FirstEl的偏移量也是InlineElts的偏移量。

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

3.SmallVector迭代器

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

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

4總結

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

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