C#多维数组在内存中的排列

Question

如果一个在C#中是多维数组，那么a[0,1]或a[1,0]是否紧随a[0,0]在内存中。这对于知道如何迭代整个多维数组的顺序非常重要。如果操作错误，将会导致不断缺失缓存，而且错误的方式会非常慢。

就是这样。

for (int i = 0; i < count1; ++ i ) {
  for (int j = 0; j < count2; ++ j ) {
    do something with a[i,j]
  }
}

应该有非常不同的性能。

for (int j = 0; j < count2; ++ j ) {
  for (int i = 0; i < count1; ++ i ) {
    do something with a[i,j]
  }
}

而哪个是快的，哪个是慢的取决于我的问题的答案。

- user334911

---

它是[0, 0] [0, 1] [0, 2] [1, 0] [1, 1] [1, 2]。因此，第一段代码片段是最佳的。你可以通过这种方式找到答案（https://dev59.com/Lojca4cB1Zd3GeqPvlww#28815972）。为了快速索引，请使用锯齿形数组。 - Hans Passant

[0,0] [0,1] [0,2] [1,0] [1,1] [1,2] - Rusty

非常好的答案Hans。感谢你指出了这一点。 - user334911

@HansPassant Jagged数组如何更快地进行索引？一个索引进入“外部”数组以获取“内部”数组在内存中的位置，这听起来缓存效率低下（因为您必须抓取两个远离的内存位置而不是一个）？我不是在争论，只是好奇。 - user334911

两个原因。元素地址计算是 arr + N*i + j 而不是 subarr + j。而且抖动不能消除高维度上的索引边界检查。每个元素访问都需要 2 次边界检查，而对于锯齿数组只需要 1 次。 - Hans Passant

Answer 1

内存结构有点像 [0,0] [0,1] [0,2] [1,0 ] [1,1] [1,2]
我的建议是外部循环遍历第一维，内部循环遍历第二维。这样更简单...

- Rusty

---

与“更简单”无关，速度才是关键。在有效利用处理器缓存方面，引用局部性是一个很重要的问题。 - Hans Passant