前言

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

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

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

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

1.SmallVector概述

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

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

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

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

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

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

內(nèi)存的位置不同導(dǎo)致了std::array與std::vector效率的不同。因?yàn)閟td::vector是通過(guò)malloc申請(qǐng)的堆內(nèi)存，而std::array是棧內(nèi)存。

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

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

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

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

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

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

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

SmallVector繼承關(guān)系圖

2.1 SmallVector

其中SmallVector繼承自SmallVectorImpl和SmallVectorStorage。

template

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

2.2 SmallVectorStorage

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

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

2.3 SmallVectorImpl

template <typename T>
class SmallVectorImpl : public SmallVectorTemplateBase

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

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

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

2.4 SmallVectorTemplateBase

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

template

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

template <typename T, bool TriviallyCopyable>
void SmallVectorTemplateBase

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

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

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

template <class Size_T>
void SmallVectorBase

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

2.5 SmallVectorTemplateCommon

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

SmallVectorTemplateCommon是不依賴于是否為POD類(lèi)型的公共部分，冗余的模版參數(shù)T是為了給ArrayRef使用。ArrayRef可以是SmallVector或者std::Vector的引用，后續(xù)會(huì)寫(xiě)文章介紹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)提到過(guò)，當(dāng)元素?cái)?shù)量較少時(shí)是存儲(chǔ)在SmallVectorStorage定義的數(shù)組中。因此BeginX的初始值應(yīng)該是InlineElts的地址。如下所示是SmallVectorTemplateCommon的構(gòu)造函數(shù)

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

調(diào)用該構(gòu)造函數(shù)時(shí)會(huì)首先對(duì)SmallVectorBase的構(gòu)造函數(shù)，此時(shí)會(huì)對(duì)BeginX進(jìn)行初始化，上面的Base就代表SmallVectorBase?？梢钥吹紹eginX是調(diào)用getFirstEl()進(jìn)行初始化的。在來(lái)看看getFirstEl()，該函數(shù)會(huì)通過(guò)this指針的地址加上一個(gè)偏移量來(lái)得到。這個(gè)偏移量是通過(guò)一個(gè)SmallVectorAlignmentAndSize的struct得到。

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

再來(lái)看看SmallVectorAlignmentAndSize這個(gè)結(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維護(hù)的是一個(gè)連續(xù)的線性空間普通的指針都可以作為SmallVector的迭代器滿足所有的必要條件，例如operator*，operator++，operator--等。不需要額外的對(duì)這些操作符進(jìn)行重載。

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

4總結(jié)

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

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