C99 VLA的C ++替代（目标：保持性能）

 

我将一些C99代码移植到C ++中，这些代码大量使用了可变长度数组（VLA）。

我用一个在堆上分配内存的数组类来替换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显示了非常相似的结果。

码

这是我使用的当前“smallvector”实现。 我需要一维和二维矢量。 我切换到大小MSL以上的堆分配。 

template<typename T, size_t MSL=50>
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<typename T, size_t MSL=1000>
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]; }
};

在线程本地存储中创建一个大缓冲区（MB +）。 （堆上的实际内存，TLS中的管理）。

允许客户端以FILO的方式请求内存（类似堆栈）。 （这模仿它如何在C的VLA中工作;它是有效的，因为每个请求/返回只是一个整数加/减）。

从中获取您的VLA存储。

把它包裹得很漂亮，所以你可以说stack_array<T> x(1024); ，并具有stack_array处理建设/破坏（注意->~T()其中T是int是一个合法的空操作，并且结构可以类似地一个空操作），或使stack_array<T>紧裹std::vector<T, TLS_stack_allocator> 。

数据将不会像C VLA数据那样本地化，因为它将在单独的堆栈上有效。 您可以使用SBO（小缓存优化），这是当地真正重要的时候。

一个SBO stack_array<T>可以用一个分配器和一个与std数组联合的std向量来实现，或者使用一个唯一的ptr和自定义驱逐器或者其他无数种方法来实现。 您可能可以改装您的解决方案，将您的新/ malloc / free / delete替换为对上述TLS存储的调用。

我说TLS与TLS一起，因为它可以消除同步开销的需求，同时允许多线程使用，并反映堆栈本身隐式TLS的事实。

基于堆栈缓冲区的STL分配器？ 是一个SO问答，在答案中至少有两个“堆栈”分配器。 他们需要一些自适应才能从TLS自动获取缓冲区。

请注意，作为一个大缓冲区的TLS在某种意义上是一个实现细节。 您可以执行大量分配，并且当空间用完时再执行一次大的分配。 你只需要跟踪每个“堆栈页”的当前容量和一个堆栈页的列表，所以当你清空一个，你可以移动到一个更早的。 这可以让你在TLS初始分配时保持一点保守，而不用担心运行OOM; 重要的部分是你是FILO并且很少分配，而不是整个FILO缓冲区是一个连续的缓冲区。

我想你已经在你的问题和评论中列举了大部分选项。

  • 使用std::vector 。 这是最明显，最无忧无虑但也可能是最慢的解决方案。

  • 在提供它们的平台上使用平台特定的扩展。 例如，GCC支持C ++中的可变长度数组作为扩展。 POSIX指定了在堆栈上分配内存时广泛支持的alloca 。 就像微软Windows提供的_malloca ，快速的网络搜索告诉我。

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

  • 构建您自己的可变大小的数组类型，在您的问题中显示的对象内部实现嵌入为缓冲区的“小数组”优化。 我只会注意到，我宁愿尝试使用std::array和std::vector的union ，而不是滚动我自己的容器。

    一旦你有一个自定义类型，你可以做一些有趣的分析，例如维护一个全局散列表（包含源代码位置），并在程序的压力测试中记录每个分配大小。 然后，您可以在程序退出时转储散列表并绘制各个阵列分配大小的分布。 这可以帮助您微调堆栈上单独存储每个阵列的存储量。

  • 使用带有自定义分配器的std::vector 。 在程序启动时，分配几兆字节的内存并将其提供给一个简单的堆栈分配器。 对于堆栈分配器，分配只是比较和添加两个整数，并且释放只是一个减法。 我怀疑编译器生成的堆栈分配会更快。 然后你的“数组堆栈”将脉动与你的“程序堆栈”相关联。 这种设计还具有这样的优点，即意外缓冲区溢出 - 同时仍然调用未定义的行为，垃圾随机数据和所有不良内容 - 不会轻易破坏程序堆栈（返回地址），就像使用本地VLA一样。

    C ++中的自定义分配器是一个有点肮脏的业务，但有些人确实报告他们正在成功使用它们。 （我自己没有太多的使用经验。）您可能想开始查看cppreference。 Alisdair Meredith是促进自定义分配器使用的人之一，他在CppCon'14上发表了题为“Making Allocators Work”（第1部分，第2部分）的双重会话，您可能会感兴趣。 如果std::allocator接口对你来说太麻烦了，那么用你自己的分配器实现你自己的变量（而不是动态地）大小的数组类也应该是可行的。

    • 关于对MSVC的支持：

    MSVC有_alloca分配堆栈空间。 如果有足够的可用堆栈空间，它也有_malloca分配堆栈空间，否则回退到动态分配。

    你不能利用VLA类型系统，所以你必须改变你的代码的工作方式，以指向这样一个数组的第一个元素的指针。

    您可能最终需要使用具有不同定义的宏，具体取决于平台。 例如调用_alloca或_malloca上MSVC，和对于g ++或其他编译器，无论是呼叫alloca （如果支持的话），或使一个VLA和一个指针。

    考虑调查重写代码的方式，而不需要分配未知数量的堆栈。 一种选择是分配一个固定大小的缓冲区，这是您需要的最大值。 （如果这会导致堆栈溢出，这意味着你的代码无论如何都被窃听）。

    链接地址: http://www.djcxy.com/p/18577.html

    上一篇: C++ replacement for C99 VLAs (goal: preserve performance)

    下一篇: length std::array like