Сравнение производительности массива массивов против многомерных массивов

Question

Когда я использовал C++ в колледже, мне было предложено использовать многомерные массивы (здесь MDA), когда это возможно, поскольку оно обладает лучшей локальностью памяти, поскольку оно выделено в одном большом фрагменте. С другой стороны, массив массивов (AoA) распределяется в несколько меньших фрагментов, возможно, разбросанных по всему месту в физической памяти везде, где найдутся вакансии.

Таким образом, я догадываюсь, что первый вопрос: это миф или это совет, заслуживающий внимания?

Предполагая, что это последнее, тогда следующий вопрос будет состоять в том, что делать на языке Java, который не имеет истинного MDA. Конечно, не так уж сложно подражать MDA с 1DA. По сути, то, что является синтаксическим сахаром для языков с MDA, может быть реализовано как поддержка библиотеки для языков без MDA.

Это стоит усилий? Это слишком низкий уровень проблемы оптимизации для языка, такого как Java? Должны ли мы просто отказаться от массивов и использовать List s даже для примитивов?

---

Другой вопрос: в Java, делает выделение AoA сразу (new int[M][N]), возможно, дают различное распределение памяти, чем делать это иерархически (new int[M][]; for (... new int[N])?

Answer 1

Java и C# выделяют память очень различным образом, что делает C++. На самом деле, в .NET наверняка все массивы AoA будут близки друг к другу, если они распределяются один за другим, потому что в памяти есть только один непрерывный кусок без какой-либо фрагментации.

Но это все еще верно для C++ и по-прежнему имеет смысл, если вы хотите максимальной скорости. Хотя вы не должны следовать этому совету каждый раз, когда вам нужен многомерный массив, сначала нужно написать поддерживающий код, а затем профилировать его, если он медленный, преждевременная оптимизация является корнем для всех зла в этом мире.

Answer 2

Я бы не стал тратить усилия на использование массива 1D в виде многомерного массива в Java, потому что синтаксиса не требуется. Конечно, можно было бы определить функции (методы), чтобы скрыть работу для вас, но вы просто получите вызов функции вместо того, чтобы следовать указателю при использовании массива массивов. Даже если компилятор/интерпретатор ускорит это для вас, я все равно не думаю, что это стоит усилий. Кроме того, вы можете столкнуться с осложнениями при попытке использовать код, который ожидает 2D (или N-Dim) массивы, которые ожидают как массивы массивов. Я уверен, что самый общий код там будет написан для массивов, подобных этому на Java. Также можно недорого переназначить строки (или столбцы, если вы решите так думать).

Если вы знаете, что этот многомерный массив является узким местом, вы можете игнорировать сказанное и видеть, помогает ли ручная оптимизация.

Answer 3

Стоит ли усилий? Это слишком низкий уровень проблемы оптимизации для языка, такого как Java?

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

Должны ли мы просто отказаться от массивов и использовать списки даже для примитивов?

Я бы не зашел так далеко. Предполагая, что вы имеете дело с массивами заданного размера:

• массивов объектов будут немного быстрее, чем эквивалентные списки объектов, и
• массивов примитивов значительно быстрее быть и занимают значительно меньше места, чем эквивалент списки примитивной обертки.

С другой стороны, если вашему приложению необходимо «вырастить» массивы, использование списка упростит ваш код.

Answer 4

Из личного опыта Java многомерные массивы намного медленнее, чем одномерные массивы, если вы загружаете большой объем данных или получаете доступ к элементам в данных, находящихся в разных положениях. Я написал программу, которая взяла изображение с экрана в формате BMP, а затем искала скриншот для меньшего изображения. Загрузка снимка экрана (около 3 мб) в многомерный массив (трехмерный, [xPos] [yPos] [цвет] (с цветом = 0, красным значением и т. Д.)) Занял 14 секунд. Чтобы загрузить его в одномерный массив, потребовалось 1 секунду. Усиление для поиска меньшего изображения на большом изображении было аналогичным. Потребовалось около 28 секунд, чтобы найти меньшее изображение на большом изображении, когда оба изображения были сохранены в виде многомерных массивов. Потребовалось около секунды, чтобы найти меньшее изображение на большом изображении, когда оба изображения были сохранены в виде одномерных массивов. Тем не менее, я сначала написал свою программу, используя размерные массивы для удобства чтения.