1

我不擅长 java 约定和最佳实践。

我需要二维缓冲区来进行一些涉及动态编程的大计算，并且怀疑我是否应该使用一维数组并将两个坐标映射到单个坐标，或者使用数组数组并通过索引进行链接访问。

在 CI 中更喜欢第一种方式，但 Java 不是 C，可能有额外的细节很重要。

4

1 回答 1

6

如果您需要最高速度，请务必使用单个数组（一维）并根据需要映射您的索引。正如我在您问题下方评论中链接到的线程中看到的那样，人们似乎无视二维数组对 CPU 缓存行的不良影响，只强调内存查找的数量。

需要考虑一个因素：如果您的内部数组足够大（例如 1K 或更大），那么速度优势就会开始消失。如果内部数组很小（如 10-50），那么差异应该很明显。

编辑

正如正确的要求，这是我的jmh基准：

@OutputTimeUnit(TimeUnit.SECONDS)
public class ArrayAccess
{
  static final int gapRowsize = 128, rowsize = 32, colsize = 10_000;
  static final int[][] twod = new int[colsize][],
      gap1 = new int[colsize][];
  static final int[] oned = new int[colsize*rowsize];
  static final Random r = new Random();
  static {
    for (int i = 0; i < colsize; i++) {
      twod[i] = new int[rowsize];
      gap1[i] = new int[gapRowsize];
    }
    for (int i = 0; i < rowsize*colsize; i++) oned[i] = r.nextInt();
    for (int i = 0; i < colsize; i++)
      for (int j = 0; j < rowsize; j++)
        twod[i][j] = r.nextInt();
  }

  @GenerateMicroBenchmark
  public int oned() {
    int sum = 0;
    for (int i = 0; i < rowsize*colsize; i++)
      sum += oned[i];
    return sum;
  }

  @GenerateMicroBenchmark
  public int onedIndexed() {
    int sum = 0;
    for (int i = 0; i < colsize; i++)
      for (int j = 0; j < rowsize; j++)
        sum += oned[ind(i,j)];
    return sum;
  }

  static int ind(int row, int col) { return rowsize*row+col; }

  @GenerateMicroBenchmark
  public int twod() {
    int sum = 0;
    for (int i = 0; i < colsize; i++)
      for (int j = 0; j < rowsize; j++)
        sum += twod[i][j];
    return sum;
  }

}

注意间隙数组分配：这模拟了碎片堆的最坏情况。

我在 = 32 时看到超过 5 倍的优势，rowsize在 1024 时优势仍然非常明显（25%）。我还发现优势高度取决于间隙大小，显示的 128 是rowsize= 32 的最坏情况（两者都是更高和更低的值会削弱优势），而 512 是rowsize= 1024 的最坏情况。

rowsize = 32, gapRowsize = 128

Benchmark    Mean        Units
oned         8857.400    ops/sec
twod         1697.694    ops/sec


rowsize = 1024, gapRowsize = 512

Benchmark   Mean     Units
oned        147.192  ops/sec
twod        118.275  ops/sec
于 2013-11-08T18:22:02.997 回答