二维数组及其在c++中的性能

Question

我想优化一段区域增长代码，该代码目前在其算法中使用两个2D数组。一个2D数组保存了2D纹理中每个像素的访问状态，一个2D数组保存了每个像素的"should be masking"布尔值。

我运行Intel VTune Amplifier XE来分析该方法的性能。下面是512x512图像最重要的统计数据:

• 在array2D[x][y]中查找需要~10-15ms
• 写入array2D[x][y]需要~1-2ms
创建和初始化每个数组需要8-10ms

此外，我执行的读操作几乎和写操作一样多。以最基本的方式创建2D数组:

bool** array2D = new bool*[desc.Width];
for(unsigned int i = 0; i < desc.Width; ++i)
    array2D[i] = new bool[desc.Height];
for(unsigned int x = 0; x < desc.Width; x++){
    for(unsigned int y = 0; y < desc.Height; y++){
        array2D[x][y] = false;
    }
}

我正在寻找更好的结构来保存这些信息。欢迎提供代码示例，以及一般想法(包括估计)。

Answer 1

您可以通过从2D数组切换到1D数组来尝试以牺牲可读性为代价来优化性能。您可以使用array[x*Height+y]或array[x+y*Width](以行为主或以列为主的顺序)代替array2D[x][y]，这取决于您的访问模式。这样可以避免单独分配。

如果数组很大，还可以尝试将布尔值打包成更大的整型。这将使访问代码稍微慢一些，但是相当小的内存占用可能会用更好的缓存性能来弥补访问速度的减慢。

Answer 2

将2d数组转换为1d数组:

type* array = new type[width * height];
array[x + y * width] = data_at_x_y;