std :: vector-like类优化以容纳少量项目

Question

在程序的一个时间关键部分,有一个类的成员看起来像这样:std :: vector m_vLinks; 在分析期间,我注意到大约99.98%的执行此向量仅包含0或1个项目.然而,在极少数情况下它可能会持有更多.根据探查器,这个向量肯定是一个瓶颈,所以我正在考虑如下优化:

在开始对这个东西进行原型设计以确定它是否有帮助之前,我想知道是否有人在某些第三方库中遇到了具有类似功能的自定义容器？

我已经考虑过boost :: array,但是不希望它强加的大小限制

Answer 1

LLVM有一个名为SmallVector的类.

通常,层次结构不会使代码变慢.编译器看到了这一点.特别是,如果你在层次结构中看到像`is_pod <T>`这样的东西,你知道那是编译时计算. (3认同)
当然,一个问题是:它更快,真的吗？有一个相当重的层次结构,我不知道它是否可以管理`vector`的速度. (2认同)
@MatthieuM. - 对我来说,下面的程序运行大约4.5秒:http://pastebin.com/Vmr47x0b - 当我将它切换为使用`llvm :: SmallVector`时,它会持续大约1.5秒. (2认同)

Answer 2

在代码的非时间关键部分,执行:m_vLinks.reserve(1);.这样,在时间关键部分,通常不会有动态分配.

Answer 3

我的第一次尝试是优化内存分配器.天真的malloc实现效率不高,你可能想尝试tcmalloc或jemalloc.

我的第二次尝试是改变分配器.Howard Hinnant演示了如何使用在堆栈上预先分配了一些内存的有状态分配器.这在C++ 11中仅符合标准,但可能已经受支持.

我的第三次尝试是更改代码并尽可能预先分配内存.不是vector每次都重新构建,而是可以保留它:它的容量不会减少,因此后续使用不会分配内存.

自制程序实现与std::vector<T>类的速度相匹配的可能性很小,因为许多方法已经过调整以获得最佳性能.