[LLVM数据结构]SmallVector

LLVM SmallVector

简介

SmallVector 是一个动态可变长数组，为数组比较小的情况进行了优化。它在类中（实际是在末尾）包含 N 个元素（in-place，在位元素），当元素数量少于这个 N 的时候，数据保存在类中，从而避免了堆的内存分配。这样在数组较小的时候很快很节省，变大了也能够支持。

代码定义

头文件位于llvm/ADT/SmallVector.h

文件中定义有：

• 类 SmallVectorBase -- 不含模板部分的公共基类，提供给各个 SmallVectorXXX<> 做基类
• 模板类 SmallVectorTemplateCommon，派生自 SmallVectorBase
• 模板类 SmallVectorTemplateBase，派生自 SmallVectorTemplateCommon<T>
  • SmallVectorTemplateBase<T, true> 特化版本，针对 POD 数据优化。
• 模板类 SmallVectorImpl，派生自 SmallVectorTemplateBase<T, is_pod>
  • swap() 模板方法，赋值操作符重载。
• 模板类 SmallVector，派生自 SmallVectorImpl<T>
  • SmallVector<T, 0> 特化版本

概述

模板类 SmallVector<T> 从 SmallVectorImpl 派生：

template <typename T, unsigned N>  // 注1
class SmallVector : public SmallVectorImpl<T> {
   U InlineElts[NUM];  // 注2 
   this()  // 多个构造，用计算出来的可容纳 T 元素的数量 NumTsAvailable 调用基类构造。
}

• 注1：N 表示要 in-place 容纳 N 个 T 元素。
• 注2：根据 N 计算出需要多少个 U 的空间能够存放下 N 个 T 元素，空间需求为 N*sizeof(T)。计算结果为 NUM。原代码中有几个 enum 用于做此计算：
  • NumInlineEltsElts -- InlineElts[] 数组大小，以使得有足够的空间容纳 N 个 T 元素。
  • NumTsAvailable -- 表示实际申请的空间可以存放的 T 类型元素的数量。
• 基本功能都在基类中实现了，因此此类比较简单。参见 SmallVectorImpl

实现机理

SmallVector 使用在类里面的空间(in-place空间)保存 N个 T 元素。当 push 更多元素的时候，grow() 函数将从堆中申请空间容纳更多元素。这种实现优化了当大部分情况元素数量都少于等于 N 的时候，不用从堆中分配内存，从而得到空间上的优化。

特化版本

• SmallVector 提供针对 N == 0 的特化版本，保证在不完整的 T 类型(incomplete)时也能实例化（此时不需要访问 T 的成员变量）。

设计目的

• 为了优化内存的分配，针对元素数一般小于 N 的时候，能够不用昂贵的内存分配、释放操作。
• 针对 POD 也有构造、移动、析构等优化。也即为了得到最佳程序性能而设计。