Folly 的 small

由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector，代码文件地址：https://github.com/facebook/folly/blob/master/folly/small_vector.h。

folly::small_vector的基本特性是，当数据较少时，它类似于静态数组，数据位于栈上，获得最佳的性能（主要是提高缓存命中率）。同时又能确保数据量超出指定容量时不会出错，此时退化为std::vector，能容纳任意长度的数据。有点类似于std::string的实现。

需留意的是，一旦退化到堆上，将不会再回到栈上。

它基本兼容std::vector的 API 以及大多数std容器算法：

folly::small_vector<int, 2> vec;
vec.push_back(0); // Stored in-place on stack.
vec.push_back(1); // Still on the stack.
vec.push_back(2); // Switches to heap buffer.
vec.pop_back();   // pop back but still on heap buffer.

folly主打性能，在small_vector里也用了不少黑魔法，否则代码不会如此晦涩难懂。主要的黑魔法有几个：

其一是支持五个模板变量，并且后面三个可以任意排序。我们看下面的官方例子：

// With space for 32 in situ unique pointers, and only using a
// 4-byte size_type.
small_vector<std::unique_ptr<int>, 32, uint32_t> v;

// A inline vector of up to 256 ints which will not use the heap.
small_vector<int, 256, NoHeap> v;

// Same as the above, but making the size_type smaller too.
small_vector<int, 256, NoHeap, uint16_t> v;

这个是依赖boost::mpl库实现的。对，folly就是依赖了boost，所以说folly直接替代boost的说法是不对的。

其二是small_vector库最大程度优化了内存布局。可以想一下，如果我们自己写这个库，估计是这样子的：

template <typename T, size_t SIZE>
struct small_vector {
  size_t size;   // 当前已有数据长度。
  T stack[SIZE];

  size_t heap_capacity;  // 堆上已分配空间长度。
  T* heap;
};

但实际实现类似于下面这个：

template <typename T, size_t SIZE, typename SIZE_TYPE>
struct small_vector {
  SIZE_TYPE size;   // 当前已有数据长度。
  union {
    T stack[SIZE];
    struct {
      SIZE_TYPE capacity;
      void* ptr;
    } heap;
  } data;
};

那small_vector如何知道目前到底用的是 stack 还是 heap 呢？答案是用size变量的最高位来存储。这也使得容器的最高长度不能超过std::numeric_limits<SIZE_TYPE>::max()的一半。

folly甚至考虑了sizeof(T[SIZE])过小的时候，此时实际实现为：

template <typename T, size_t SIZE, typename SIZE_TYPE>
struct small_vector {
  SIZE_TYPE size;
  union {
    T stack[SIZE];
    struct {
      void* ptr;
    } heap;
  } data;
};

那此时堆长度capacity放到哪里了呢？答案是放在分配的堆内存ptr的开始位置处，数据实际存放地址会往后移。基本设计逻辑是尽量少占用栈上空间，堆上无所谓。

现在内存并不紧张，因此用时间来换空间，并大大增加编程复杂性的做法，值得商酌。我自己肯定不会冒险这么写。

其三是实现中大量使用了makeGuard，这个是为了异常安全。即在makeGuard的保护范围内，一旦发生异常，markGuard被析构，其定义的函数将被调用，以清理异常情况。如果没有发生异常，dismiss()函数将被调用，取消清理行为。如下例：

small_vector(small_vector const& o) {
  auto n = o.size();
  makeSize(n);
  {
    auto rollback = makeGuard([&] {
      if (this->isExtern()) {
        u.freeHeap();
      }
    });
    std::uninitialized_copy(o.begin(), o.end(), begin());
    rollback.dismiss();
  }
  this->setSize(n);
}

工业代码的好处是考虑比较全面。自己写的代码似乎都不会考虑这些情况。因此，对大多数工作，应尽量使用成熟框架和代码。

boost库也提供了boost::container::small_vector，功能类似，但 API 更兼容std container，比如支持std::allocator。

作者暂无likerid, 赞赏暂由本网站代持，当作者有likerid后会全部转账给作者（我们会尽力而为）。


Support author:
Author's Filecoin address:
Or you can use Likecoin to support author: