Java: многомерный массив против одномерного

Question

Например:

• а) int [x][y][z]

  против

• b) int[x*y*z]

Первоначально думал, что я пойду с а) для простоты

Я знаю, что Java не хранит массивы линейно в памяти, как Си. Но какое это имеет значение для моей программы?

Answer 1

Обычно лучше всего искать ответы на такие вопросы, чтобы увидеть, как варианты компилируются в байт-код JVM:

multi = new int[50][50];
single = new int[2500];

Это переводится на:

BIPUSH 50
BIPUSH 50
MULTIANEWARRAY int[][] 2
ASTORE 1
SIPUSH 2500
NEWARRAY T_INT
ASTORE 2

Итак, как вы можете видеть, JVM уже знает, что мы говорим о многомерном массиве.

Сохраняя его дальше:

for (int i = 0; i < 50; ++i)
    for (int j = 0; j < 50; ++j)
    {
        multi[i][j] = 20;
        single[i*50+j] = 20;
    }

Это переводится (пропуская циклы) в:

ALOAD 1: multi
ILOAD 3: i
AALOAD
ILOAD 4: j
BIPUSH 20
IASTORE

ALOAD 2: single
ILOAD 3: i
BIPUSH 50
IMUL
ILOAD 4: j
IADD
BIPUSH 20
IASTORE

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

Я не думаю, что производительность будет такой проблемой.

РЕДАКТИРОВАТЬ:

Я сделал несколько простых тестов, чтобы увидеть, что здесь происходит,Я решил попробовать разные примеры: линейное чтение, линейная запись и произвольный доступ.Время выражается в миллисекундах (и рассчитывается с использованием System.nanoTime(). Вот результаты:

Линейная запись

• Размер: 100x100 (10000) Мульти: 5.786591 Один: 6.131748
• Размер: 200x200 (40000) Мульти: 1.216366 Одноместный: 0.782041
• Размер: 500x500 (250000) Мульти: 7.177029 Одноместный: 3.667017
• Размер: 1000x1000 (1000000) Мульти: 30.508131 Одноместный:18.064592
• Размер: 2000x2000 (4000000) Мульти: 185.3548 Одноместный: 155.590313
• Размер: 5000x5000 (25000000) Мульти: 955.5299 Одноместный: 923.264417
• Размер: 10000x10000 (100000000) Мульти: 4084.798753 Одиночный: 4015.448829

Линейное чтение

• Размер: 100x100 (10000) Мульти: 5.241338 Одноместный: 5.135957
• Размер: 200x200 (40000) Мульти: 0.080209 Одноместный: 0.044371
• Размер: 500x500 (250000) Мульти: 0.088742 Одноместный: 0,084476
• Размер: 1000x1000 (1000000) Мульти: 0.232095 Одноместный: 0.167671
• Размер: 2000x2000(4000000) Мульти: 0,481683 Одноместный: 0,33321
• Размер: 5000x5000 (25000000) Multi: 1.222339 Single: 0.828118 Размер: 10000x10000 (100000000) Multi: 2.496302 Single: 1.650691

Случайное чтение

• Размер: 100x100 (10000) Мульти: 22.317393 Одноместный: 8.546134
• Размер: 200x200 (40000) Мульти: 32.287669 Одноместный: 11.022383
• Размер: 500x500 (250000) Мульти: 189.542751 Одноместный: 68.181343
• Размер: 1000x1000 (1000000) Мульти: 1124.78609 Одноместный: 272.235584
• Размер: 2000x2000 (4000000) Мульти: 6814.477101 Одноместный: 1091.998395
• Размер: 5000x5000 (25000000) Мульти: 50051.306239 Одноместный: 7028.422262

Случайное значение немного вводит в заблуждение, поскольку оно генерирует 2 случайных числа для многомерного массива, а одно - для одномерного (и PNRG могут потреблять некоторое количество ресурсов ЦП).

Имейте в виду, что я попытался позволить JIT работать, используя бенчмаркинг только после 20-го запуска того же цикла.Для полноты моей виртуальной машины Java является следующее:

версия Java "1.6.0_17" Java (TM) SE Runtime Environment (сборка 1.6.0_17-b04) Java HotSpot (TM) 64-битная виртуальная машина сервера(сборка 14.3-b01, смешанный режим)

Answer 2

На современных процессорах доступ к не кэшированной памяти в сотни раз медленнее, чем арифметика (см. эту презентацию и чтение Что должен знать каждый программист о памяти ). Опция a) приведет к примерно 3 поискам памяти, тогда как опция b) приведет к примерно 1 поиску памяти. Также алгоритмы предварительной выборки ЦП могут не работать так же хорошо. Таким образом, опция b) может быть быстрее в некоторых ситуациях (это горячая точка, и массив не помещается в кэш процессора). Насколько быстрее? - это будет зависеть от приложения.

Лично я бы сначала использовал параметр а), потому что это приведет к упрощению кода. Если профилировщик показывает, что доступ к массиву является узким местом, я бы преобразовал его в опцию b), чтобы была пара вспомогательных методов для чтения и записи значений массива (таким образом, грязный код будет ограничен этими двумя методы).

Я сделал тест для сравнения трехмерных массивов int (столбец "Multi") с эквивалентными одномерными массивами int (столбец "Single"). Код здесь и тесты здесь . Я запустил его на 64-битном jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 @ 3.0 ГГц, 4 ГБ DDR2, используя параметры JVM -server -Xmx3G -verbose:gc -XX:+PrintCompilation (я удалил выходные данные отладки из следующих результатов). Результаты были:

Out of 20 repeats, the minimum time in milliseconds is reported.

Array dimensions: 100x100x100 (1000000)
            Multi   Single
Seq Write   1       1
Seq Read    1       1
Random Read 99      90    (of which generating random numbers 59 ms)

Array dimensions: 200x200x200 (8000000)
            Multi   Single
Seq Write   14      13
Seq Read    11      8
Random Read 1482    1239    (of which generating random numbers 474 ms)

Array dimensions: 300x300x300 (27000000)
            Multi   Single
Seq Write   53      46
Seq Read    34      24
Random Read 5915    4418    (of which generating random numbers 1557 ms)

Array dimensions: 400x400x400 (64000000)
            Multi   Single
Seq Write   123     111
Seq Read    71      55
Random Read 16326   11144    (of which generating random numbers 3693 ms)

Показывает, что одномерный массив быстрее. Хотя различия настолько малы, что для 99% приложений они не будут заметны.

Я также провел некоторые измерения, чтобы оценить издержки генерации случайных чисел в тесте Random Read, заменив preventOptimizingAway += array.get(x, y, z); на preventOptimizingAway += x * y * z; и добавил измерения вручную в таблицу результатов выше. Генерация случайных чисел занимает 1/3 или меньше от общего времени теста Random Read, поэтому доступ к памяти доминирует в тесте, как и ожидалось. Было бы интересно повторить этот тест с массивами 4 и более измерений. Вероятно, это увеличит разницу в скорости, потому что верхние уровни многомерного массива поместятся в кэш процессора, и только другие уровни потребуют поиск памяти.

Answer 3

Используйте первый вариант (3-мерный), потому что его легче понять и меньше шансов сделать какую-то логическую ошибку (особенно если вы используете его для моделирования 3-мерного пространства)

Answer 4

Если вы выберете последний маршрут, вам придется выполнять арифметику для каждого доступа к массиву. Это будет болезненным и подверженным ошибкам (если вы не заключите его в класс, обеспечивающий эту функциональность).

Я не верю, что есть какая-либо (существенная) оптимизация при выборе вашего плоского массива (особенно с учетом арифметики, взятой для индексации в нем). Как всегда в случае с оптимизацией, вам необходимо выполнить некоторые измерения и определить, действительно ли это того стоит.