3D 数组删除 C++ 性能低下

Question

int newHeight = _height/2;
    int newWidth = _width/2;

    double*** imageData = new double**[newHeight];
    for (int i = 0; i < newHeight; i++)
    {
        imageData[i] = new double*[newWidth];
        for (int j = 0; j < newWidth; j++)
        {
            imageData[i][j] = new double[4];
        }
    }

我动态分配了这个3D矩阵。在这里释放内存的最快和最安全的方法是什么？

这是我完成的，但这需要几秒钟我的矩阵很大 (1500,2000,4)

  for (int i = 0; i != _height/2; i++)
        {
            for (int j = 0; j != _width/2; j++)
            {
                delete[] imageData[i][j];
            }
            delete[] imageData[i];
        }
        delete[] imageData;

更新
根据建议，我选择了这个解决方案：

std::vector<std::vector<std::array<double,4>>>

性能非常适合我的情况

Answer 1

将整个图像数据分配为一个块，以便您可以将其作为一个块释放，即。 double* imageData = new double[width*height*4]; delete [] imageData; 并使用偏移量对其进行索引。现在你正在进行 3 百万 单独的 分配，这正在破坏你的堆。

Answer 2

我同意 qartar 的回答，直到他说 "index into it using offsets"。那没有必要。您也可以拥有单一分配和多个下标访问 (imageData[i][j][k])。我之前展示过这种方法，将它应用于 3-D 情况并不难：

配置代码如下：

double*** imageData;
imageData = new double**[width];
imageData[0] = new double*[width * height];
imageData[0][0] = new double[width * height * 4];
for (int i = 0; i < width; i++) {
    if (i > 0) {
        imageData[i] = imageData[i-1] + height;
        imageData[i][0] = imageData[i-1][0] + height * 4;
    }
    for (int j = 1; j < height; j++) {
        imageData[i][j] = imageData[i][j-1] + 4;
    }
}

解除分配变得更简单：

delete[] imageData[0][0];
delete[] imageData[0];
delete[] imageData;

当然，您可以而且应该使用 std::vector 自动进行释放：

std::vector<double**> imageData(width);
std::vector<double*> imageDataRows(width * height);
std::vector<double> imageDataCells(width * height * 4);
for (int i = 0; i < width; i++) {
    imageData[i] = &imageDataRows[i * height];
    for (int j = 0; j < height; j++) {
        imageData[i][j] = &imageDataCells[(i * height + j) * 4];
    }
}

并且释放是完全自动的。

有关更多说明，请参阅。

或者最后一个下标使用std::array<double,4>，通过这种方式使用二维动态分配

Answer 3

答案的第一个想法略有不同：

double ***imagedata = new double**[height];
double **p = new double*[height * width];
double *q = new double[height * width * length];
for (int i = 0; i < height; ++i, p += width) {
    imagedata[i] = p;
    for (int j = 0; j < width; ++j, q += length) {
        imagedata[i][j] = q;
    }
}
// ...
delete[] imagedata[0][0];
delete[] imagedata[0];
delete[] imagedata;

可以通过一次分配完成所有事情，但这会带来一些您可能不想支付的复杂性。

现在，事实上每个 table 查找都涉及从内存中背靠背读取指针，这个解决方案几乎总是不如分配平面数组和做索引将三重索引转换为一个平面索引的计算（您应该编写一个包装器 class 来为您进行这些索引计算）。

使用指向数组指针数组的指针数组的主要原因是当你的数组参差不齐时——也就是说，imagedata[a][b] 和 imagedata[c][d] 有不同的长度——或者可能是为了交换行，例如 swap(imagedata[a][b], imagedata[c][d])。在这种情况下，vector 如您所用，最好使用它，直到证明不是这样。

Answer 4

您的算法中影响性能的主要部分是您进行的分配的粒度和绝对数量。您总共生产 3001501 细分为：

1 分配 1500 double**
1500个分配，每个获得2000个double*
3000000个分配每个获得double[4]

这可以大大减少。您当然可以按照其他人的建议去做，只需分配 1 个大型双精度数组，将索引计算留给访问函数。当然，如果您这样做，您需要确保随身携带尺码。然而，结果将轻松提供最快的分配时间和访问性能。使用 std::vector<double> arr(d1*d2*4); 并根据需要进行偏移数学运算将非常有用。

另一种方式

如果您坚持使用指针数组方法，则可以通过在单次分配中获得两个次级维度来消除 3000000 次分配。您的最次级维度是固定的 (4)，因此您可以这样做：（但稍后您会看到更多以 C++ 为中心的机制）：

double (**allocPtrsN(size_t d1, size_t d2))[4]
{
    typedef double (*Row)[4];
    Row *res = new Row[d1];

    for (size_t i=0; i<d1; ++i)
        res[i] = new T[d2][4];

    return res;
}

并简单地调用为：

double (**arr3D)[4] = allocPtrsN(d1,d2);

其中 d1 和 d2 是您的两个高级维度。这会产生 d1 + 1 个分配，第一个是 d1 指针，其余是 d1 个分配，每个 double[d2][4].

使用 C++ 标准容器

前面的代码显然很繁琐，而且坦率地说容易出现相当大的错误。 C++ 提供了一个简洁的解决方案，使用固定数组的向量向量，这样做：

std::vector<std::vector<std::array<double,4>>> arr(1500, std::vector<std::array<double,4>>(2000));

最终这将执行几乎与前面显示的相当迟钝的代码相同的分配技术，但在执行时为您提供标准库的所有可爱的好处。您可以获得 std::vector 和 std::array 模板的所有方便成员，以及作为额外奖励的 RAII 功能。

但是，这是一个显着差异。前面显示的原始指针方法将不值初始化每个分配的实体；数组法向量的向量将。如果您认为这没有什么不同...

#include <iostream>
#include <vector>
#include <array>
#include <chrono>

using Quad = std::array<double, 4>;
using Table = std::vector<Quad>;
using Cube = std::vector<Table>;

Cube allocCube(size_t d1, size_t d2)
{
    return Cube(d1, Table(d2));
}

double ***allocPtrs(size_t d1, size_t d2)
{
    double*** ptrs = new double**[d1];
    for (size_t i = 0; i < d1; i++)
    {
        ptrs[i] = new double*[d2];
        for (size_t j = 0; j < d2; j++)
        {
            ptrs[i][j] = new double[4];
        }
    }
    return ptrs;
}

void freePtrs(double***& ptrs, size_t d1, size_t d2)
{
    for (size_t i=0; i<d1; ++i)
    {
        for (size_t j=0; j<d2; ++j)
            delete [] ptrs[i][j];
        delete [] ptrs[i];
    }
    delete [] ptrs;
    ptrs = nullptr;
}

double (**allocPtrsN(size_t d1, size_t d2))[4]
{
    typedef double (*Row)[4];
    Row *res = new Row[d1];

    for (size_t i=0; i<d1; ++i)
        res[i] = new double[d2][4];

    return res;
}

void freePtrsN(double (**p)[4], size_t d1, size_t d2)
{
    for (size_t i=0; i<d1; ++i)
        delete [] p[i];
    delete [] p;
}

std::vector<std::vector<std::array<double,4>>> arr(1500, std::vector<std::array<double,4>>(2000));

template<class C>
void print_duration(const std::chrono::time_point<C>& beg,
                    const std::chrono::time_point<C>& end)
{
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - beg).count() << "ms\n";
}

int main()
{
    using namespace std::chrono;
    time_point<system_clock> tp;
    volatile double vd;

    static constexpr size_t d1 = 1500, d2 = 2000;

    tp = system_clock::now();
    for (int i=0; i<10; ++i)
    {
        double ***cube = allocPtrs(d1,d2);
        cube[d1/2][d2/21][1] = 1.0;
        vd = cube[d1/2][d2/2][3];
        freePtrs(cube, 1500, 2000);
    }
    print_duration(tp, system_clock::now());

    tp = system_clock::now();
    for (int i=0; i<10; ++i)
    {
        Cube cube = allocCube(1500,2000);
        cube[d1/2][d2/21][1] = 1.0;
        vd = cube[d1/2][d2/2][3];
    }
    print_duration(tp, system_clock::now());

    tp = system_clock::now();
    for (int i=0; i<10; ++i)
    {
        auto cube = allocPtrsN(d1,d2);
        cube[d1/2][d2/21][1] = 1.0;
        vd = cube[d1/2][d2/21][1];
        freePtrsN(cube, d1, d2);
    }
    print_duration(tp, system_clock::now());
}

输出

5328ms
418ms
95ms

因此，如果您打算为每个元素加载除零之外的任何内容，请牢记这一点。

结论

如果性能很关键，我会使用 24MB（无论如何在我的实现中）单一分配，可能在 std::vector<double> arr(d1*d2*4); 中，并根据需要使用一种形式的二级索引或另一种形式进行偏移计算。其他答案对此提出了有趣的想法，尤其是 Ben 的，它从根本上减少了分配计数两个 three 块（数据和两个辅助指针数组）。抱歉，我没有时间坐板凳，但我怀疑性能会很出色。但是，如果您真的想要保留现有技术，请考虑在 C++ 容器中进行，如上所示。如果花费在初始化世界上的额外周期不是太重的代价，那么它将更容易管理（与原始指针相比，显然要处理的代码更少）。

祝你好运。

3D 数组删除 C++ 性能低下

slow performance for 3D array delete C++

c++

memory-management