Java: многомерный массив против одномерного
Например:
-
a) int [x][y][z]
vs
-
b) int[x*y*z]
Первоначально предполагалось, что я поеду с a) для простоты
Я знаю, что Java не хранит массивы линейно в памяти, например, C. Но какие последствия имеет это для моей программы?
Ответы
Ответ 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
Если вы выберете последний маршрут, вам придется выполнить арифметику для каждого доступа к одному массиву. Это будет болезненным и подверженным ошибкам (если вы не обернете его в класс, предоставляющий эту функциональность).
Я не считаю, что существует какая-либо (значительная) оптимизация при выборе вашего плоского массива (особенно учитывая, что арифметика взята для индексации в нее). Как всегда с оптимизацией, вам нужно будет выполнить некоторые измерения и определить, действительно ли это стоит.
