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

Ответ 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

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

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

EDIT:

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

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

• Размер: 100x100 (10000) Multi: 5.786591 Single: 6.131748
• Размер: 200x200 (40000) Multi: 1.216366 Single: 0.782041
• Размер: 500x500 (250000) Multi: 7.177029 Single: 3.667017
• Размер: 1000x1000 (1000000) Multi: 30.508131 Single: 18.064592
• Размер: 2000x2000 (4000000) Multi: 185.3548 Single: 155.590313
• Размер: 5000x5000 (25000000) Multi: 955.5299 Single: 923.264417
• Размер: 10000x10000 (100000000) Multi: 4084.798753 Single: 4015.448829

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

• Размер: 100x100 (10000) Multi: 5.241338 Single: 5.135957
• Размер: 200x200 (40000) Multi: 0.080209 Single: 0.044371
• Размер: 500x500 (250000) Multi: 0.088742 Single: 0.084476
• Размер: 1000x1000 (1000000) Multi: 0.232095 Однолокальный: 0,167671
• Размер: 2000x2000 (4000000) Multi: 0.481683 Одиночный: 0,33321
• Размер: 5000x5000 (25000000) Multi: 1.222339 Однолокальный: 0,828118 Размер: 10000x10000 (100000000) Multi: 2.496302 Single: 1.650691

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

• Размер: 100x100 (10000) Multi: 22.317393 Single: 8.546134
• Размер: 200x200 (40000) Multi: 32.287669 Single: 11.022383
• Размер: 500x500 (250000) Multi: 189.542751 Single: 68.181343
• Размер: 1000x1000 (1000000) Multi: 1124.78609 Single: 272.235584
• Размер: 2000x2000 (4000000) Multi: 6814.477101 Single: 1091.998395
• Размер: 5000x5000 (25000000) Multi: 50051.306239 Single: 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-разрядная серверная VM (сборка 14.3-b01, смешанный режим)

Ответ 2

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

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

Я сделал сравнительный тест для сравнения 3-мерных массивов int (столбец "Multi" ) с эквивалентными 1-мерными массивами 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)

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

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

Ответ 3

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

Ответ 4

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

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