массив структур или структура массивов?

Question

Хммм. У меня есть таблица, которая представляет собой массив структур, которые мне нужно хранить в Java. Наивный подход «не беспокойся о памяти» гласит: «1001 *»

public class Record {
  final private int field1;
  final private int field2;
  final private long field3;
  /* constructor & accessors here */
}

List<Record> records = new ArrayList<Record>();

Если я в конечном итоге использую большое количество (> 10 ⁶ ) записей, к которым иногда обращаются к отдельным записям по одному, как бы я выяснил, как предшествующий подход (ArrayList) сравнил бы с оптимизированным подходом к затратам на хранение:

public class OptimizedRecordStore {
  final private int[] field1;
  final private int[] field2;
  final private long[] field3;

  Record getRecord(int i) { return new Record(field1[i],field2[i],field3[i]); }
  /* constructor and other accessors & methods */
}

редактирование:

• предположим, что # записей - это то, что меняется редко или никогда
• Я, вероятно, не собираюсь использовать подход OptimizedRecordStore, но я хочу понять проблему стоимости хранилища, чтобы я мог с уверенностью принять это решение.
• очевидно, если я добавлю / изменим количество записей в подходе OptimizedRecordStore выше, мне придется либо заменить весь объект новым, либо удалить ключевое слово "final".
• kd304 поднимает хороший вопрос, который был у меня в голове. В других ситуациях, подобных этому, мне нужен доступ к столбцам записей, например, если field1 и field2 - это "time" и "position", и для меня важно получить эти значения в виде массива для использования с MATLAB, поэтому я могу эффективно их графически / анализировать.

Answer 1

Ответы, которые дают общее «оптимизировать, когда вам нужно», бесполезны в этом случае, потому что, ИМХО, программисты всегда должны знать о производительности при разных вариантах дизайна, когда этот выбор приводит к снижению производительности на порядок, особенно писатели API.

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

Answer 2

Если у вас есть миллионы записей, второй подход имеет несколько преимуществ:

• Использование памяти : первый подход использует больше памяти, потому что a) каждый объект Java в куче имеет заголовок (содержащий идентификатор класса, состояние блокировки и т. Д.); b) объекты выровнены в памяти; c) каждая ссылка на объект стоит 4 байта (на 64-битных JVM с сжатыми OOP или 32-битными JVM) или 8 байтов (64-битные JVM без сжатых OOP). См. Е. г. CompressedOops для более подробной информации. Таким образом, первый подход требует примерно в два раза больше памяти (точнее: согласно моему тесту, объект с 16 байтами полезной нагрузки + ссылка на него занимает 28 байтов на 32-битной Java 7, 36 байтов на 64-битной Java 7 с сжатые ООП и 40 байтов в 64-битной Java 7 без сжатых ООП).
• Сборка мусора : хотя второй подход, кажется, создает много объектов (по одному на каждый вызов getRecord), это может быть не так, как могут применять современные серверные JVM (например, Oracle 7 Java) избежать анализа и выделения стека, чтобы в некоторых случаях избежать выделения кучи временных объектов; В любом случае, недолговечные объекты GCing дешевы. С другой стороны, сборщику мусора, вероятно, будет проще, если нет миллионов долгоживущих объектов (как в первом подходе), достижимость которых для проверки (или, по крайней мере, такие объекты может сделать ваше приложение более тщательным). настройка размеров генерации ГК). Таким образом, второй подход может быть лучше для производительности GC. Однако, чтобы понять, насколько это реально в реальной ситуации, нужно сделать себе эталон.
• Скорость сериализации : скорость (де) сериализации большого массива примитивов на диске ограничена только скоростью жесткого диска; Сериализация многих небольших объектов неизбежно медленнее (особенно если вы используете сериализацию по умолчанию в Java).

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

Answer 3

Вторая версия намного, намного хуже . Вместо изменения размера одного массива вы изменяете размеры трех массивов при вставке или удалении. Более того, вторая версия приведет к созданию гораздо большего количества временных объектов, и это будет сделано при доступе. Это может привести к большому количеству мусора (с точки зрения GC). Не хорошо.

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

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

Если вы действительно обеспокоены производительностью вставки / удаления, возможно, подходит другая структура данных, например, SortedSet, Map или SortedMap.

Answer 4

Мне было любопытно, поэтому я на самом деле провел тест. Если вы не воссоздаете объект как вы [1], то SoA превосходит AoS на 5-100% в зависимости от рабочей нагрузки [2]. Смотрите мой код здесь:

https://gist.github.com/twolfe18/8168262c5420c7a62d39

[1] Я не добавил этого, потому что, если вы достаточно обеспокоены скоростью, чтобы рассмотреть этот рефакторинг, было бы глупо сделать это.

[2] Это также не учитывает перераспределение, но опять же, это часто то, что вы можете амортизировать или знать статически. Это разумное предположение для эталона с чистой скоростью.

Answer 5

Как вы собираетесь получить доступ к данным? Если доступ к полям всегда связан, то используйте первый вариант, если вы собираетесь обрабатывать поля самостоятельно, тогда второй вариант лучше.

См. Эту статью в википедии: Parallel Array

Хорошим примером того, когда удобнее иметь отдельные массивы, могут быть симуляции, когда числовые данные упакованы вместе в одном массиве, и другие атрибуты, такие как имя, цвет и т. Д., Которые доступны только для представления данных другой массив.

Answer 6

(не прямой ответ, но тот, который, я думаю, должен быть дан)

Из вашего комментария,

"cletus - я очень уважаю ваши мысли и мнения, но вы дали мне точку зрения программирования и разработки программного обеспечения высокого уровня, а это не то, что я ищу. Я не могу научиться игнорировать оптимизацию, пока не получу интуитивный смысл для стоимости различных стилей реализации и / или возможность оценить эти затраты. - Джейсон С. 14 июля 2009 г. в 14:27 "

Вы всегда должны игнорировать оптимизацию, пока она не станет проблемой. Наиболее важно, чтобы система была пригодна для использования разработчиком (чтобы они могли сделать ее доступной для пользователя). Очень редко вы должны заниматься оптимизацией, ведь за ~ 20 лет профессионального кодирования я заботился об оптимизации всего два раза:

1. Написание программы, основной целью которой было быть быстрее, чем другой продукт
2. Написание приложения для смартфона с целью уменьшения объема данных, передаваемых между клиентом и сервером

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

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

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

Лично я предпочел бы получить правильный ответ медленно, чем неправильный ответ быстро. Как только я знаю, как получить правильный ответ, я могу выяснить, где система работает медленно, и заменить ее на более быстрые реализации.

Answer 7

Я бы выбрал первый метод (массив структур) , если вы не заходите в магазин относительно редко и сталкиваетесь с серьезными проблемами с памятью.

Первая версия в основном хранит объекты в их «естественной» форме (+1 КСТАТИ за использование неизменяемых записей). Это использует немного больше памяти из-за накладных расходов на объект (вероятно, около 8-16 байт в зависимости от вашей JVM), но очень хорошо для доступа и возврата объектов в удобной и понятной для человека форме за один простой шаг.

Вторая версия использует меньше памяти в целом, но выделение нового объекта при каждом "get" - довольно уродливое решение, которое не будет работать хорошо, если доступ будет частым.

Некоторые другие возможности для рассмотрения:

Интересным «крайним» вариантом было бы взять вторую версию, но написать свои алгоритмы / методы доступа для непосредственного взаимодействия с базовыми массивами. Это явно приведет к сложным взаимозависимостям и некоторому уродливому коду, но, вероятно, даст вам абсолютную лучшую производительность, если вам действительно это нужно. Этот подход довольно часто используется для интенсивных графических приложений, таких как манипулирование большим массивом трехмерных координат.

«Гибридный» вариант - хранить базовые данные в структуре массивов, как во второй версии, но кэшировать объекты, к которым осуществляется доступ, в HashMap, чтобы вы генерировали объект только при первом обращении к определенному индексу. Может иметь смысл, если только малая часть объектов будет доступна, но все данные нужны «на всякий случай».

Answer 8

Всякий раз, когда я пытался выполнить сокращение чисел в Java, мне всегда приходилось возвращаться к кодированию в стиле C (т. Е. Близко к вашему варианту 2). Это минимизировало количество объектов, плавающих вокруг в вашей системе, поскольку вместо 1 000 000 объектов у вас есть только 3. Я смог провести небольшой FFT-анализ звуковых данных в реальном времени с использованием стиля C, и это было слишком медленно используя объекты.

Answer 9

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

Кроме того, единственная память, которую вы выигрываете во втором подходе, (возможно) связана с выравниванием элементов. (и необходимость выделять отдельный объект). В противном случае они имеют одинаковое использование памяти, асимптотически. Первый вариант намного лучше из-за населенного пункта, ИМО

Answer 10

Поскольку вы делаете поля int [] окончательными, вы застряли только с одной инициализацией массива, и это все. Таким образом, если вы хотите 10 ^ 6 field1, Java должен был бы выделить столько памяти для каждого из этих int [], потому что вы не можете переназначить размер этих массивов. С ArrayList, если вы заранее не знаете количество записей и потенциально будете удалять записи, вы сэкономите много места заранее, а затем и позже, когда будете удалять записи.