由 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.