高效的访问矩arrays

高效的访问问题：我需要按列访问大型矩阵（超过2000×2000），我的算法需要1行传递和1列传递。 行传递对于内存效率（缓存未命中）是好的，但是如何减少列传递中的缓存未命中？ 我需要效率。

我唯一拥有的是：声明n局部变量（基于内存获取大小），

int a1, a2, a3, a4; for ( int j = 0 ; j < DIM_Y ; j+=4 ) for ( int i = 0 ; i < DIM_X ; i++ ) a1 = matrix[i][j]; ... ; a4 = matrix[i][j+4]; // make the column processing on the 4 variables.

它是C或C ++，以及数组或int或char。

任何提议和评论都受到欢迎。

谢谢。

Answer 1

两种基本技术适用：

1）循环阻塞

代替

  for (j=0;j<2000;j++) for (i=0;i<2000;i++) process_element(i,j); 

使用

 for (j=0;j<2000;j+=8) for (i=0;i<2000;i+=8) process_block_of_8x8(i,j); 

2）2行步长的非功率（例如8192字节+64） - 必要时填充

在这种情况下，row [i] .. row [i + 7]不会争用同一个缓存行

数据应该在手动计算填充的连续内存区域中。

Answer 2

存储2D矩阵的有效方法是使用如下的C样式数组：

 | a11 a12 a13 | | a21 a22 a23 | -> memory: [a11,a12,a13,a21,a22,a23,a31,a32,a33] | a31 a32 a33 | Element(i,j) = memory[N_COL*i+j] 

其中i是从0开始的行号索引， j是列号索引也从0开始，而N_COL是列数。

希望编译器/ jit将所有值顺序放在内存中以便快速访问。 通常你试图欺骗编译器的次数越多（比如手动循环展开），你就会越多地伤害自己的性能。 编写干净的代码，让编译器完成它的工作。