将 3 维数组展平为一维数组有什么好处？

Question

我有一个用 Java 表示的 3-D 数组

int[][][] arr = new int[X][Y][z]

如果我尝试使用 1-D as 来实现 3-D 数组

int[] oneDArray = new int[X*Y*Z] 

一维中元素 arr[i][j][k] 的索引将计算为

indx = X*Y*k + i*Y + j;

虽然在内存位置中任何N维数组都会按顺序存储。
对于一维，如果我使用三个索引 (i,j,k) 来访问元素，这会降低 X,Y,Z 较大值的性能吗？

Answer 1

a[x][y][z]

涉及3次内存访问，但计算量很少。

a[x * X * Y + y * Y + z]

涉及一次内存访问，但需要更多计算。

通常，内存访问比乘法更昂贵，如果正在访问的内存不在 CPU 缓存中，则更是如此。

例如，如果您重复访问

int[][][]

中的随机位置，第一个维度可能会在 CPU 缓存中，但其他两个不会，因为按访问的元素从主内存总共 2 次加载。相比之下，使用

int[]

仅涉及主内存的一次加载，因此速度将提高两倍。

另一方面，如果您按顺序访问

int[][][]

，则缓存未命中的情况会非常少，并且

int[]

只会稍微快一些。

总而言之，切换到一维数组会使代码更难读写，除非数组很大并且访问频率很高，否则性能差异将很小而不重要。

为了验证理论，您可以使用以下基准：

public class Benchmark {

    public static void benchmark(String label, Code code) {
        print(25, label);
        
        try {
            for (int iterations = 1; ; iterations *= 2) { // detect reasonable iteration count and warm up the code under test
                System.gc(); // clean up previous runs, so we don't benchmark their cleanup
                long previouslyUsedMemory = usedMemory();
                long start = System.nanoTime();
                code.execute(iterations);
                long duration = System.nanoTime() - start;
                long memoryUsed = usedMemory() - previouslyUsedMemory;
                
                if (iterations > 1E8 || duration > 1E9) { 
                    print(25, new BigDecimal(duration * 1000 / iterations).movePointLeft(3) + " ns / iteration");
                    print(30, new BigDecimal(memoryUsed * 1000 / iterations).movePointLeft(3) + " bytes / iteration\n");
                    return;
                }
            }
        } catch (Throwable e) {
            throw new RuntimeException(e);
        }
    }
    
    private static void print(int desiredLength, String message) {
        System.out.print(" ".repeat(Math.max(1, desiredLength - message.length())) + message);
    }
    
    private static long usedMemory() {
        var r = Runtime.getRuntime();
        return r.totalMemory() - r.freeMemory();
    }

    @FunctionalInterface
    interface Code {
        /**
         * Executes the code under test.
         * 
         * @param iterations
         *            number of iterations to perform
         * @return any value that requires the entire code to be executed (to
         *         prevent dead code elimination by the just in time compiler)
         * @throws Throwable
         *             if the test could not complete successfully
         */
        Object execute(int iterations);
    }

    public static void main(String[] args) {
        benchmark(" int[][][] traversal, sequential", (iterations) -> {
            int n = (int) Math.pow(iterations, 1.0/3);
            int[][][] a = new int[n][n][n];
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    for (int z = 0; z < n; z++) {
                        a[x][y][z] = x + y + z;
                    }
                }
            }
            return a;
        });
        benchmark("flat int[] traversal, sequential", (iterations) -> {
            int n = (int) Math.pow(iterations, 1.0/3);
            int[] a = new int[n * n * n];
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    for (int z = 0; z < n; z++) {
                        a[(x * n + y) * n + z] = x + y + z;
                    }
                }
            }
            return a;
        });
        benchmark(" int[][][] traversal, unordered " , (iterations) -> {
            int n = (int) Math.pow(iterations, 1.0/3);
            int[][][] a = new int[n][n][n];
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    for (int z = 0; z < n; z++) {
                        a[z][y][x] = x + y + z;
                    }
                }
            }
            return a;
        });
        benchmark("flat int[] traversal, unordered ", (iterations) -> {
            int n = (int) Math.pow(iterations, 1.0/3);
            int[] a = new int[n * n * n];
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    for (int z = 0; z < n; z++) {
                        a[(z * n + y) * n + x] = x + y + z;
                    }
                }
            }
            return a;
        });
    }
}

在我的电脑上，打印：

  int[][][] traversal, sequential     1.406 ns / iteration      4.204 bytes / iteration
 flat int[] traversal, sequential     0.926 ns / iteration      3.984 bytes / iteration
  int[][][] traversal, unordered     11.716 ns / iteration      4.188 bytes / iteration
 flat int[] traversal, unordered      5.487 ns / iteration      3.984 bytes / iteration

如您所见，只有每秒进行数百万次数组访问（如果访问是连续的，则进行数千万次数组访问）时，性能差异才重要。因此，出于性能原因而应将

int[][][]

替换为

int[]

的情况确实很少见。