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

Question

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

我用在堆上分配内存的数组 class 替换了 VLA（堆栈分配）。性能受到的影响是巨大的，降低了 3.2 倍（参见下面的基准）。 我可以在 C++ 中使用什么快速 VLA 替换？我的目标是在为 C++ 重写代码时尽量减少性能损失。

向我建议的一个想法是编写一个数组 class，它在 class 中包含一个固定大小的存储（即可以堆栈分配）并将其用于小型数组，并自动切换到更大数组的堆分配。我的实现是在 post 的末尾。它工作得很好，但我仍然无法达到原始 C99 代码的性能。为了接近它，我必须将这个固定大小的存储（下面的MSL）增加到我不喜欢的大小。我不想在堆栈上分配太大的数组 即使对于许多不需要它的小数组 因为我担心它会触发堆栈溢出。 C99 VLA 实际上不太容易出现这种情况，因为它永远不会使用超过需要的存储空间。

我发现了 std::dynarray，但我的理解是它没有被标准接受（还没有？）。

我知道 clang 和 gcc 支持 C++ 中的 VLA，但我也需要它才能与 MSVC 一起工作。事实上，更好的可移植性是重写为 C++ 的主要目标之一（另一个目标是将原本是命令行工具的程序变成可重用的库）。

基准

MSL 指的是我切换到堆分配的数组大小。我对一维和二维数组使用不同的值。

原始C99代码：115秒。
MSL = 0（即堆分配）：367 秒（3.2 倍）。
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]; }
};

Answer 1

我认为您已经在问题和评论中列举了大部分选项。

使用std::vector。这是最明显、最简单但也可能是最慢的解决方案。
在提供它们的平台上使用特定于平台的扩展。例如，GCC 支持 variable-length arrays in C++ as an extension. POSIX specifies alloca which is widely supported to allocate memory on the stack. Even Microsoft Windows provides _malloca，正如快速网络搜索告诉我的那样。

为了避免维护噩梦，您确实希望将这些平台依赖项封装到一个抽象接口中，该接口可以自动透明地为当前平台选择合适的机制。为所有平台实施此功能将需要一些工作，但如果如您所报告的那样，这个单一功能导致 3 倍的速度差异，那么这可能是值得的。作为未知平台的后备方案，我会保留 std::vector 作为最后的手段。运行缓慢但正确比表现不稳定或根本不运行更好。
构建您自己的可变大小数组类型，实现“小数组”优化嵌入为对象本身的缓冲区，如您在问题中所示。我只是注意到我宁愿尝试使用 std::array 的 union 和 std::vector 而不是滚动我自己的容器。

一旦你有了一个自定义类型，你就可以做一些有趣的分析，比如维护一个全局散列 table 所有出现的这种类型（按源代码位置），并在一个过程中记录每个分配大小程序的压力测试。然后，您可以在程序退出时转储散列 table 并绘制各个数组的分配大小分布。这可能会帮助您微调为堆栈上的每个数组单独保留的存储量。
使用带有自定义分配器的 std::vector。在程序启动时，分配几兆字节的内存并将其交给一个简单的堆栈分配器。对于堆栈分配器，分配只是比较和添加两个整数，而释放只是一个减法。我怀疑编译器生成的堆栈分配会快得多。然后，您的“数组堆栈”将与您的“程序堆栈”相关联。这种设计还有一个优点，即意外缓冲区超过运行秒——同时仍然调用未定义的行为、丢弃随机数据和所有那些坏东西——不会轻易破坏程序堆栈（return 地址）就像使用原生 VLA 一样。

C++ 中的自定义分配器有点肮脏，但有些人确实报告说他们正在成功使用它们。（我自己没有太多使用它们的经验。）您可能想开始查看 cppreference. Alisdair Meredith who is one of those people that promote the usage of custom allocators gave a double-session talk at CppCon'14 titled “Making Allocators Work” (part 1, part 2)，您可能也会觉得有趣。如果 std::allocator 接口对你来说太难用了，实现你自己的变量（相对于动态）大小的数组 class 用你自己的分配器应该也是可行的。

Answer 2

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

允许客户端以 FILO 方式（类似堆栈）从中请求内存。（这模仿了它在 C VLA 中的工作方式；而且它很有效，因为每个 request/return 只是一个整数 addition/subtraction）。

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

把它包装得漂亮一点，这样你就可以说 stack_array<T> x(1024);，让 stack_array 处理 construction/destruction（注意 ->~T()，其中 T 是 int 是一个合法的 noop，构造也可以类似地是一个 noop)，或者让 stack_array<T> 包装一个 std::vector<T, TLS_stack_allocator>.

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

SBO stack_array<T> 可以通过分配器和与 std 数组联合的 std 向量来实现，或者通过唯一的 ptr 和自定义销毁器，或者无数其他方式来实现。您或许可以改进您的解决方案，将您的 new/malloc/free/delete 替换为对上述 TLS 存储的调用。

我说使用 TLS，因为它消除了同步开销的需要，同时允许多线程使用，并反映了堆栈本身是隐式 TLS 的事实。

Stack-buffer based STL allocator? 是一个 SO Q&A，答案中至少有两个 "stack" 分配器。他们将需要一些调整才能自动从 TLS 获取缓冲区。

请注意，TLS 作为一个大缓冲区在某种意义上是一种实现细节。您可以进行大量分配，当您 space 中的运行进行另一次大规模分配时。您只需要跟踪每个 "stack page" 当前容量和堆栈页面列表，因此当您清空一个页面时，您可以移至较早的页面。这让您在 TLS 初始分配中更加保守，而不必担心运行ning OOM；重要的是你是 FILO 并且很少分配，而不是整个 FILO 缓冲区是一个连续的缓冲区。

Answer 3

关于对 MSVC 的支持：

如果有足够的可用堆栈 space，MSVC 有 _alloca which allocates stack space. It also has _malloca 分配堆栈 space，否则回退到动态分配。

您无法利用 VLA 类型系统，因此您必须更改代码以基于指向此类数组第一个元素的指针工作。

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

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

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

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

c++

arrays

performance

variable-length-array

stack-allocation

基准

代码