C++替代C99VLA(目标:保持性能)

我正在移植一些C99代码,这些代码大量使用可变长度数组(VLA)到C++.

我用一个在堆上分配内存的数组类替换了VLA(堆栈分配).业绩受到巨大影响,放缓了3.2倍(见下面的基准). 我可以在C++中使用什么快速的VLA替换？我的目标是在重写C++代码时尽量减少性能损失.

向我建议的一个想法是编写一个数组类,其中包含类中的固定大小的存储(即可以是堆栈分配)并将其用于小型数组,并自动切换到更大数组的堆分配.我的实现是在帖子的最后.它工作得相当好,但我仍然无法达到原始C99代码的性能.为了接近它,我必须将这个固定大小的存储空间(MSL下面)增加到我不熟悉的尺寸.即使对于许多不需要它的小型数组,我也不想在堆栈上分配太大的数组,因为我担心它会触发堆栈溢出.C99 VLA实际上不太容易发生这种情况,因为它永远不会使用比所需更多的存储空间.

我遇到了std::dynarray,但我的理解是它没有被标准接受(但是？).

我知道clang和gcc在C++中支持VLA,但我也需要它与MSVC一起工作.事实上,更好的可移植性是重写为C++的主要目标之一(另一个目标是将程序(最初是命令行工具)转换为可重用的库).

---

基准

MSL指的是我在其上切换到堆分配的数组大小.我对1D和2D数组使用不同的值.

原始C99代码:115秒.
MSL = 0(即堆分配):367秒(3.2x).
1D-MSL = 50,2D-MSL = 1000:187秒(1.63x).
1D-MSL = 200,2D-MSL = 4000:143秒(1.24x).
1D-MSL = 1000,2D-MSL = 20000:131(1.14x).

增加MSL进一步提高性能,但最终程序将开始返回错误的结果(我假设由于堆栈溢出).

这些基准测试是在OS X上使用clang 3.7,但是gcc 5显示了非常相似的结果.

---

码

这是我使用的当前"小向量"实现.我需要1D和2D矢量.我切换到大小超过堆分配MSL.

template
class lad_vector {
    const size_t len;
    T sdata[MSL];
    T *data;
public:
    explicit lad_vector(size_t len_) : len(len_) {
        if (len <= MSL)
            data = &sdata[0];
        else
            data = new T[len];
    }

    ~lad_vector() {
        if (len > MSL)
            delete [] data;
    }

    const T &operator [] (size_t i) const { return data[i]; }
    T &operator [] (size_t i) { return data[i]; }

    operator T * () { return data; }
};


template
class lad_matrix {
    const size_t rows, cols;
    T sdata[MSL];
    T *data;

public:
    explicit lad_matrix(size_t rows_, size_t cols_) : rows(rows_), cols(cols_) {
        if (rows*cols <= MSL)
            data = &sdata[0];
        else
            data = new T[rows*cols];
    }

    ~lad_matrix() {
        if (rows*cols > MSL)
            delete [] data;
    }

    T const * operator[] (size_t i) const { return &data[cols*i]; }
    T * operator[] (size_t i) { return &data[cols*i]; }
};

Yakk - Adam .. 38

在线程本地存储中创建一个大缓冲区(MB +).(堆上的实际内存,TLS中的管理).

允许客户端以FILO方式从堆栈请求内存(类似堆栈).(这模仿它在C语言协议中如何工作;并且它是有效的,因为每个请求/返回只是一个整数加法/减法).

从中获取您的VLA存储空间.

包装它漂亮,所以你可以说stack_array x(1024);,并且有stack_array处理施工/破坏(注意->~T()哪里T是int合法的noop,建筑可以类似地是noop),或者stack_array包装a std::vector.

数据不会像C VLA数据那样本地化,因为它将在一个单独的堆栈上有效.你可以使用SBO(小缓冲区优化),这是当地方真正重要的时候.

SBO stack_array可以使用分配器和std向量与std数组联合,或者使用唯一的ptr和自定义驱逐程序,或者无数其他方式来实现.您可以通过调用上述TLS存储来改造您的解决方案,替换新的/ malloc/free/delete.

我说使用TLS,因为它在允许多线程使用时消除了对同步开销的需求,并且反映了堆栈本身是隐式TLS的事实.

基于堆栈缓冲的STL分配器？是一个SO问答,答案中至少有两个"堆栈"分配器.他们需要一些适应性来自动从TLS获取缓冲区.

注意,作为一个大缓冲区的TLS在某种意义上是实现细节.你可以做大量的分配,当你用完空间时再做一次大的分配.您只需要跟踪每个"堆栈页面"当前容量和堆栈页面列表,因此当您清空一个堆栈页面时,您可以移动到较早的堆栈页面.这让你在TLS初始分配中更加保守,而不必担心运行OOM; 重要的是你很少是FILO并且很少分配,而不是整个FILO缓冲区是一个连续的缓冲区.

1> Yakk - Adam ..：

---

在线程本地存储中创建一个大缓冲区(MB +).(堆上的实际内存,TLS中的管理).

允许客户端以FILO方式从堆栈请求内存(类似堆栈).(这模仿它在C语言协议中如何工作;并且它是有效的,因为每个请求/返回只是一个整数加法/减法).

从中获取您的VLA存储空间.

包装它漂亮,所以你可以说stack_array x(1024);,并且有stack_array处理施工/破坏(注意->~T()哪里T是int合法的noop,建筑可以类似地是noop),或者stack_array包装a std::vector.

数据不会像C VLA数据那样本地化,因为它将在一个单独的堆栈上有效.你可以使用SBO(小缓冲区优化),这是当地方真正重要的时候.

SBO stack_array可以使用分配器和std向量与std数组联合,或者使用唯一的ptr和自定义驱逐程序,或者无数其他方式来实现.您可以通过调用上述TLS存储来改造您的解决方案,替换新的/ malloc/free/delete.

我说使用TLS,因为它在允许多线程使用时消除了对同步开销的需求,并且反映了堆栈本身是隐式TLS的事实.

基于堆栈缓冲的STL分配器？是一个SO问答,答案中至少有两个"堆栈"分配器.他们需要一些适应性来自动从TLS获取缓冲区.

注意,作为一个大缓冲区的TLS在某种意义上是实现细节.你可以做大量的分配,当你用完空间时再做一次大的分配.您只需要跟踪每个"堆栈页面"当前容量和堆栈页面列表,因此当您清空一个堆栈页面时,您可以移动到较早的堆栈页面.这让你在TLS初始分配中更加保守,而不必担心运行OOM; 重要的是你很少是FILO并且很少分配,而不是整个FILO缓冲区是一个连续的缓冲区.

---

我想知道为什么这是低估的.该用例正在用C99中最初编写的代码替换C99 VLA.这意味着数组总是以它们创建的相反顺序销毁,所以从"手动管理的堆栈"获取存储的想法应该有效...如果存在预期的问题,我想知道.

2> 5gon12eder..：

---

我想你已经在你的问题和评论中列举了大多数选项.

使用std::vector.这是最明显,最轻松,但也可能是最慢的解决方案.

在提供它们的平台上使用特定于平台的扩展.例如,GCC支持C++中的可变长度数组作为扩展.POSIX指定alloca广泛支持哪些在堆栈上分配内存.甚至微软Windows提供的_malloca,作为一个快速的网络搜索告诉我.

为了避免维护噩梦,您真的希望将这些平台依赖关系封装到一个抽象接口中,该接口自动且透明地为当前平台选择适当的机制.为所有平台实现这一点将会有一些工作,但如果这个单一功能在报告时占3倍的速度差异,那么它可能是值得的.作为未知平台的后备,我将std::vector保留作为最后的手段.运行缓慢但正确比运行不稳定或根本不运行更好.

构建您自己的可变大小的数组类型,实现一个"小数组"优化,作为您在问题中显示的对象内部的缓冲区.我只是要注意,我宁愿尝试使用uniona std::array和a std::vector而不是滚动我自己的容器.

一旦有了自定义类型,就可以进行有趣的分析,例如维护所有此类事件(通过源代码位置)的全局哈希表,并在程序的压力测试期间记录每个分配大小.然后,您可以在程序出口处转储哈希表,并将分布绘制为各个阵列的分配大小.这可以帮助你微调存储保留为每个阵列量分别在堆栈中.

使用std::vector自定义分配器.在程序启动时,分配几兆字节的内存并将其分配给一个简单的堆栈分配器.对于堆栈分配器,分配只是比较和添加两个整数,而解除分配只是一个减法.我怀疑编译器生成的堆栈分配可以更快.然后,您的"阵列堆栈"将与您的"程序堆栈"相关联.这种设计还具有以下优点:意外缓冲区溢出 - 同时仍然调用未定义的行为,丢弃随机数据和所有不良内容 - 不会像使用本机VLA那样容易地破坏程序堆栈(返回地址).

C++中的自定义分配器是一个有点脏的业务,但有些人确实报告他们成功使用它们.(我自己使用它们的经验不多.)您可能想要开始查看cppreference.Alisdair Meredith是促进自定义分配器使用的人之一,他在CppCon'14上发表了题为"让分配器工作"(第1 部分,第2部分)的双重会话,你可能会觉得有趣.如果std::allocator接口使用起来太笨拙,那么使用自己的分配器实现自己的变量(而不是动态)大小的数组类也应该是可行的.

---

@Alex这是自C++ 11以来的安全.当然,你必须注意编写你的析构函数,以调用`union`当前活动成员的相应析构函数.

3> M.M..：

---

关于对MSVC的支持:

MSVC具有_alloca分配堆栈空间的功能._malloca如果有足够的可用堆栈空间,它还会分配堆栈空间,否则会回退到动态分配.

您无法利用VLA类型系统,因此您必须根据指向此类数组的第一个元素的指针将代码更改为工作.

您可能最终需要使用具有不同定义的宏,具体取决于平台.例如,调用_alloca或_malloca在MSVC上,以及在g ++或其他编译器上,调用alloca(如果它们支持它),或者生成VLA和指针.

---

考虑调查重写代码的方法,而无需分配未知量的堆栈.一种选择是分配一个固定大小的缓冲区,这是您需要的最大缓冲区.(如果这会导致堆栈溢出,则意味着您的代码无论如何都会被窃听).