许多堆栈分配与动态分配

Question

在一个多维数组中，第二个维度的大小是已知的（尽管每个第一维度的大小不同），从性能角度来看，对于实际构建这些数组，硬编码是否更快？

int* number[1000];

int secondDim[1];
number[0] = secondDim;

int secondDimTwo[2];
number[1] = secondDim;

或者每次动态分配第二个维度：

等等，这样重复1,000遍（我知道，我知道）

for(int i = 0; i < 1000; i++)
    number[i] = new int[i+1];

我在尝试理解一个概念。

这个概念与IT技术有关。

- user1201584

Answer 1

通常来说，可以假定堆栈分配的速度更快。但请记住，堆栈容量有限，过度使用大型堆栈分配的数组可能会导致堆栈溢出！

无论如何，你的问题是合理的，但是到目前为止我看到的解决方案都非常有限。事实上，你可以轻松创建一个作为三角矩阵的实用程序类型，然后根据具体使用情况将其存储在堆栈或堆上。看一下这个例子：

namespace meta
{
    template <size_t N>
    struct sum
    {
        static const int value = (N + 1) * N / 2;
    };
}

template <size_t Size>
struct MultiArray
{
    // actual buffer
    int numbers[ meta::sum<Size>::value ];

    // run-time indexing
    int* getArray(size_t dimensions)
    {
        // get sum of (dimensions-1)
        size_t index = (dimensions * (dimensions-1)) >> 1;
        return &numbers[index];
    }

    // compile-time indexing
    template <size_t dimensions>
    int* getArray()
    {
        size_t index = meta::sum<dimensions - 1>::value ;
        return &numbers[ index ];
    }

    int* operator[](size_t index)
    {
        return getArray(index);
    }
};

现在就看你想把它存储在哪里了。

MultiArray<1000> storedOnStack;
MultiArray<1000>* storedOnHeap = new MultiArray<1000>();

您需要使用访问器来进入内部数组：

int* runTimeResolvedArray = storedOnStack.getArray(10);
int* compileTimeResolvedArray = storedOnStack.getArray<10>();
int* runTimeResolvedArray2 = storedOnStack[10];
storedOnStack[10][0] = 666;

希望这可以帮到你！编辑：我还必须说，我不喜欢“堆栈分配”这个术语。这是有误导性的。堆栈分配实质上只是增加堆栈指针寄存器。因此，如果你在堆栈上“分配”100字节，则指针将增加100字节。但是，如果您在堆上分配了100字节，则会变得复杂 - 当前分配器必须找到合适的空闲内存空间，更新分配映射等等。如果它是一次性分配-继续在堆上执行，动态分配的开销不会很明显。但是，如果每秒进行多次操作，请选择堆栈分配。此外，堆栈数组可能更容易访问，因为堆栈内容更有可能在缓存中。但是，显然真正巨大的数组将无法适应缓存。因此，答案是：要 进行性能分析 。

- gwiazdorrr

Answer 2

除非你已经进行了分析，并知道动态分配是一个问题：

std::vector<std::vector<int> > number;
for ( size_t i = 0; i < 1000; ++ i ) {
    number.push_back( std::vector<int>( i + 1 );
}

或者（如果您的编译器尚未具备移动语义，可能会稍微快一些）：

std::vector<std::vector<int> > number( 1000 );
for ( size_t i = 0; i != number.size() ; ++ i ) {
    number[i].resize( i + 1 );
}

如果这确实会引起性能问题，或者只是为了更好地封装，您可以编写一个简单的类来表示数据结构：

class TriangularMatrix
{
    std::vector<int> myData;
    size_t mySize;

    size_t rowIndex( size_t i ) const
    {
        return (i * (i + 1)) / 2;
    }
public:
    TriangularMatrix( size_t size )
        : myData( rowIndex( size ) )
        , mySize( size )
    {
    }
    int* operator[]( size_t i )  // Returns row
    {
        assert( i < mySize );
        return &myData[rowIndex( i )];
    }
    int const* operator[]( size_t i ) const  // Returns row
    {
        assert( i < mySize );
        return &myData[rowIndex( i )];
    }
    int& operator( int i, int j )  // indexation
    {
        assert( j <= i );
        return operator[]( i )[ j ];
    }
    int const& operator( int i, int j ) const  // indexation
    {
        assert( j <= i );
        return operator[]( i )[ j ];
    }
};

事实上，我认为这样做会更加简洁易读。

- James Kanze

---

定义一个Row类作为myData的切片会更加清晰，而不是返回原始的int*。这不仅可以使注释变得多余，还可以确保适当的边界检查。 - Matthieu M.

将项附加/访问到向量比在堆栈中分配/访问更快？就论证而言，假设需要速度。 - user1201584

@MatthieuM。同意。但是代码示例已经有点长了。 - James Kanze

@user1201584 访问应该差不多；这在很大程度上取决于编译器优化器。无论如何，索引计算很可能占主导地位。(根据机器的不同，为索引创建缓存可能是值得的。尽管在大多数现代机器上，我认为(i + (i + 1)) / 2比内存访问更快。)而且(单个)向量从一开始就具有正确的大小。通过封装，几乎不可能避免单个动态分配，而没有封装，像这样的事情几乎不可能维护。 - James Kanze

Answer 3

如果您已经知道所需数组的大小，应该使用堆栈上的数组。
请注意，通常情况下，动态分配比堆栈分配更昂贵。
如果性能差异对于您的情况足够显著，则只能通过分析来确定。
此外，避免使用动态分配，因为它们更容易出错，除非您使用基于RAII的某种资源管理。

- Alok Save

---

有没有比我上面所做的硬编码更快的编码方式？ - user1201584

Answer 4

更好的方法是一次性分配整个数组，这样所有数据都是连续的（缓存效果更好）。

int * arr; arr = malloc(sizeof(int)*sum(1,n)); 你必须定义sum函数。

只需分配一个二维数组（第一维），并将指针设置为arr中的正确位置即可。

- James Cotter

---

不，你永远不想使用malloc（也不是new[]）。应用程序代码中唯一适合使用动态分配的时间是单个元素；一旦存在多个元素，就使用std::vector。 - James Kanze

这对于大型数组的分配速度是否像使用堆栈一样快？访问速度也一样快吗？在我的情况下，速度是唯一的优先考虑因素。 - user1201584