C/C++优化数据结构,数组数组或只是数组

使用一个使用16字节4v4单字节矩阵的程序:

unsigned char matrix[4][4];

和一些256字节16v16一个字节矩阵:

unsigned char bigMatrix[16][16];

通常由于数据操作,我被迫在程序中按列循环进行缓存未命中.

如果我使用数组,性能会提高,即

unsigned char matrix[16];
unsigned char matrix[256];

并通过使用一些变量来检索元素来访问元素,即

matrix[variableA*variableB + i];

每次我想访问一个元素时,需要重新计算variableA*variableB + i.

我只想要速度优化和内存没问题.这有什么帮助,比如给出一些性能上的打击或损失,还是差异太小甚至不关心？

没什么区别.在任何一种情况下,数据都以完全相同的方式布局,并且也以相同的方式访问.如果不能生成完全相同的装配,我会感到惊讶.

但是,对于256字节的表,在任何情况下都不可能获得缓存未命中.CPU的L1缓存通常在32到128KB之间,所以我怀疑你在任何情况下都会遇到很多缓存未命中.

贾尔夫大多是对的.L1高速缓存被分成块,块的大小取决于处理器,但大小为32字节.所以,如果你一次一个字节地跳过内存,你每32个字节(或者不管块大小是什么)都会得到一个缓存未命中.现在,英特尔芯片非常聪明,可以检测顺序读取和预取数据,减少高速缓存未命中的影响.

4x4矩阵很可能驻留在单个L1块(或缓存行)中,因此按行或按列访问它几乎没有区别.当然,您不希望将矩阵分割为两个缓存行,因此良好对齐的内存非常重要.

但是,16x16矩阵不适合缓存行.因此,如果您正在跳过数组处理列,那么您将获得大量缓存未命中.正如jalf所说,索引的计算没有什么区别,因为CPU和内存之间的比率很高(即你可以为每个缓存未命中做很多CPU工作).

现在,如果您主要以列为导向处理矩阵,那么您最好的选择是转置所有矩阵(使用列交换行),因此您的内存访问将更加顺序,并且缓存未命中的数量将减少, CPU将能够更好地预取数据.所以,而不是像这样组织矩阵:

  0   1   2 .... 15
 16  17  18 .... 31
....
240 241 242 .... 255

其中数字是从矩阵开始的内存偏移量,因此组织:

 0 16 32 ... 240
 1 17 33 ... 241
 ...
15 31 47 ... 255