Почему этот код требует так много памяти

Question

В настоящее время я пытаюсь решить проблему на одном из конкурсов онлайн-программирования.Ограничение для программы составляет 64 мегабайта в этом конкурсе.

Я написал программу на 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

Теперь,класс имеет только основную процедуру и несколько циклов внутри нее, без каких-либо дополнительных объявленных массивов (просто некоторая переменная для циклического повторения циклов).Однако затем я попытался запустить этот код на своем локальном компьютере с ключом -Xmx64m, у меня возникла ошибка OutOfMemoryError.Его удалось выполнить только с ключом -Xmx128m.

Я также пытался подключиться к онлайн-серверу, он выдал ту же ошибку, а также дал дополнительную информацию о том, что моя программа использовала около 148460 кб.

Но почему так много?Насколько я могу рассчитать из приведенного выше фрагмента, он должен использовать только около 40 мегабайт.Что-то не так с этим расчетом в комментариях?

Answer 1

Эти двое являются самыми большими убийцами:

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издержки байтов для самого массива (длина + общая нагрузка на объект), что означает, что каждый int[][] объект имеет размер 51 * 4 + 16 = 220 байт, а затем каждый объект int[] имеет размер 24 байта.Но у вас есть 29000 * 51 из этих 24-байтовых объектов - что само по себе составляет 35 МБ ... Тогда есть 29000 int[][] объектов, что составляет еще 6 МБ ... (Тогда есть сам массив верхнего уровня, ноэто всего лишь около 120 КБ.)

По сути, вы должны помнить, что 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];

Теперь для каждой из этих переменных существует один массив массивов верхнего уровня, 2 массива-массивов и 102 массива long или int.Это соответствует много меньше накладных расходов.

Ваши другие вычисления тоже неверны, но я думаю, что эти два массива массивов являются худшими.

Answer 2

Проблема в том, что многомерные массивы в Java не являются реальными многомерными массивами;если бы они были, то Java поддерживал бы нотацию [x, y].Но это не так.Потому что многомерные массивы в Java реализованы как массивы массивов.Таким образом, new boolean[1024][1024] - это на самом деле 1024 объекта массива, каждый из которых содержит 1024 логических значения.(1 КБ каждый.)

Я не помню, какое измерение является основным, а какое второстепенным, но, судя по тому, что вашей программе не хватает памяти, первое измерение, вероятно, является основным.Итак, new long[29000][51][2] - это 29000 * 51 = 1479000 объектов массива, каждый из которых содержит 2 длинных значения.Итак, с таким количеством объектов и учитывая накладные расходы на объект, забудьте об этом!

Answer 3

Одно незначительное предложение: я бы попробовал сделать все ваши заявления "окончательными". Большие массивы вызывают проблемы с выделением памяти, потому что нужно не только найти пространство, но и найти непрерывное пространство. Java может перемещать вещи, чтобы освободить место, но если это займет слишком много времени, это вызовет исключение нехватки памяти, даже если пространство теоретически доступно. Похоже, вы уклоняетесь от этой проблемы, забирая всю свою память и сохраняя ее до завершения программы. Использование «final» позволит JVM знать, что вы серьезно относитесь к этому, и, возможно, позволит распределить пространство таким образом, который поможет вам.

Это может не помочь JVM. Я обнаружил, что Java за последние несколько лет становится очень умной, и вам может не понадобиться рассказывать ей, что является окончательным, а что нет. Однако, людям делать нужно сказать. Использование «final» удержит вас и любого, кто еще изменит код, от случайного перераспределения пространства, скажем, с помощью выражения, подобного positions = new int[500010];, где-то в другом месте вашего кода и сокрушит JVM / сборщик мусора.

Answer 4

Как правильно отмечено выше, long[29000][51][2] занимает более 24 мегабайт.Вы можете попытаться уменьшить объем памяти, переместив наибольшее измерение в конец массива, например:

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

Этого может быть достаточно, чтобы ваша программа пропустила в конкурсе программ.