java - 为什么这段代码需要这么多内存

Question

我目前正在尝试解决在线编程竞赛中的一个问题。本次比赛的程序大小限制为64MB。

我用 Java 编写了一个程序，该程序在类声明中有一部分字段，其工作方式如下:

private int[] sizes = new int[1024]; // 4096 bytes
private boolean[][] compat = new boolean[1024][1024]; // 128 kb
private boolean[][] compat2 = new boolean[1024][1024]; // 128 kb

private long[][][] dp = new long[29000][51][2]; // About 3*8 = 24 megabytes
private int [][] masks  = new int[29000][2]; // About 240 kb
private int avail = 0; 
private int avail2 = 0;
private int[] positions = new int[500000]; // About 2 megabytes
private int[][] ranges = new int[29000][2]; // About 240 kb
private int[][] maskToPos = new int[1024][1024]; // About 4 megabytes
private int[][][] init = new int[29000][51][2]; // About 3*4 = 12 megabytes

现在，该类只有一个主过程和其中的一些循环，没有声明任何其他数组(只是一些用于迭代循环的变量)。但是，然后我尝试使用 key -Xmx64m 在本地计算机上运行此代码，但出现了 OutOfMemoryError。它只能使用 -Xmx128m key 执行。

我还尝试在在线服务器上启动，它给出了相同的错误，并且还提供了我的程序使用了大约 148460 kb 的附加信息。

但是为什么这么多呢？据我从上面的片段计算，它只需要使用大约 40 MB。评论里这个计算有问题吗？

Answer 1

这两个是最大的 killer :

private long[][][] dp = new long[29000][51][2]; // About 3*8 = 24 megabytes
private int[][][] init = new int[29000][51][2]; // About 3*4 = 12 megabytes

例如，看看第二个...这不是 12 兆字节。您有 29000 个 int[][] 对象，每个都包含对 51 个 int[] 对象的引用，每个对象包含 2整数。

假设 32 位引用大小和数组本身的 16 字节开销(长度 + 公共(public)对象开销)，这意味着 int[][] 对象的大小分别为 51 * 4 + 16 = 220 字节，然后 int[] 对象的大小均为 24 字节。但是你有 29000 * 51 个 24 字节对象 - 其本身就是 35MB...然后是 29000 个 int[][] 对象，又是 6MB...(然后是顶层数组本身，但只有大约 120K。)

基本上，您需要记住，Java 没有多维数组:它有数组的数组，每个数组都是一个对象，具有单独的开销。我建议您可能想要使用:

private int[] init = new int[29000 * 51 * 2];

相反，您自己计算出适当的偏移量。 (dp 也是如此，这更糟糕，因为它是 long 值而不是 int 值，使得每个 29000 * 51 数组至少占用 32 个字节而不是 24 个字节。)

即使只是颠倒处理尺寸的顺序也会有所帮助:

private long[][][] dp = new long[2][51][29000];
private int[][][] init = new int[2][51][29000];

现在，对于每个变量，都有 1 个顶级数组的数组的数组、2 个数组的数组和 102 个 long 或 int< 数组。这相当于减少了很多开销。

你的其他计算也不正确，但我认为这两个数组的数组的数组是最糟糕的。