Folly 的 small_vector 容器

作者: , 共 2606 字 , 共阅读 0

由 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

Q. E. D.

类似文章:
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_setfolly::sorted_vector_map,是std::mapstd::set在小数据集上的优化版。代码见: https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h
编程 » C++, folly
folly::fbstring是一个完全兼容std::string的类,可以做到无缝替换,而且性能更高。其代码参见https://github.com/facebook/folly/blob/master/folly/FBString.h
编程 » C++, folly
高效程序总是尽量避免频繁触碰在堆上分配和释放内存,所以无论是std::string还是folly:fbstring都做了SSO( small string optimization )。而folly::FixedString是一个很有意思的实现,它可以把任意长度的字符串都放在堆上。代码可见https://github.com/facebook/folly/blob/master/folly/FixedString.h
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样,folly::dynamic只支持保存以下几种类型:
编程 » C++, 智能指针
理论上而言,当 C++提供了std::unique_ptr, C++的程序就不应该出现普通指针了。所有普通指针都可以用std::unique_ptr代替,避免手动删除对象。
由 Facebook 开发和维护的 C++库 Folly 提供了锁folly::MicroLock,代码文件地址:https://github.com/facebook/folly/blob/master/folly/MicroLock.h
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。
编程 » C++, 智能指针
前面已经提到std::shared_ptr有三个缺陷:
std::thread是 C++ 11 新引入的标准线程库。在同样是 C++ 11 新引入的 lambda 函数的辅助下,std::thread用起来特别方便:
由 Facebook 开发和维护的 C++库 Folly 提供了自旋锁的实现folly::MicroSpinLock,代码文件地址:https://github.com/facebook/folly/blob/master/folly/synchronization/MicroSpinLock.h