Производительность Java - ArrayLists и Arrays для быстрого чтения

Question

У меня есть программа, в которой мне нужно сделать от 100 000 до 1 000 000 операций чтения с произвольным доступом к объекту, подобному списку, как можно быстрее (как в миллисекундах) для программы, подобной клеточным автоматам. Я думаю, что алгоритм обновления, который я использую, уже оптимизирован (эффективно отслеживает активные ячейки и т. Д.). Списки должны изменить размер, но эта производительность не так важна. Поэтому мне интересно, достаточно ли производительности от использования Arrays вместо ArrayLists, чтобы иметь значение, когда приходится иметь дело с таким количеством операций чтения за такой короткий промежуток времени. В настоящее время я использую ArrayLists.

Редактировать: я забыл упомянуть: я просто храню целые числа, поэтому еще одним фактором является использование класса-оболочки Integer (в случае ArrayLists) по сравнению с int (в случаемассивов). Кто-нибудь знает, если использование ArrayList на самом деле потребует 3 поиска указателя (один для ArrayList, один для базового массива и один для Integer-> int), где для массива потребуется только 1 (адрес массива + смещение для конкретногоINT)? Хотел бы HotSpot оптимизировать дополнительные просмотры? Насколько значительны эти дополнительные поиски?

Edit2: Кроме того, я забыл упомянуть, что мне нужно также выполнять записи с произвольным доступом (записи, а не вставки).

Answer 1

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

@ viking reportsЗначительное (в десять раз!) ускорение использования Trove в его приложении - см. комментарии. Обратной стороной является то, что типы коллекций Trove несовместимы по типу со стандартными API коллекции Java. Таким образом, Trove (или подобные библиотеки) не будет ответом во всех случаях.

Answer 2

Попробуйте оба, но измерьте.

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

Кроме того, попробуйте Java 6 update 14 и используйте -XX: + DoEscapeAnalysis

Answer 3

Использование массива ArrayList вместо массива приведет к дополнительным расходам, но, скорее всего, оно будет небольшим. Фактически, полезный бит данных в ArrayList может храниться в регистрах, хотя вы, вероятно, будете использовать больше (например, размер List).

В своем редактировании вы упоминаете, что используете оболочкуобъекты. Это действительно имеет огромное значение. Если вы обычно используете одно и то же значение несколько раз, тогда может быть полезна разумная политика кэширования (Integer.valueOf дает те же результаты для -128 до 128). Для примитивов примитивные массивы обычно выигрывают комфортно.

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

Answer 4

Я бы пошел с советом Кевина.

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

Answer 5

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

Кстати, дублируйте: Массив или Список в Java. Что быстрее?

Answer 6

Если вы создаете список один раз и выполняете тысячи чтений из него, накладные расходы из ArrayList вполне могут быть достаточно незначительными, чтобы их игнорировать. Если вы создаете тысячи списков, используйте стандартный массив. Создание объекта в цикле быстро становится квадратичным, просто из-за всех затрат на создание экземпляров переменных-членов, вызов конструкторов в цепочке наследования и т. Д.

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

Answer 7

Java использует двойное косвенное обращение для своих объектов, чтобы их можно было перемещать в памяти и сохранять свои ссылки действительными, это означает, что каждый поиск ссылок эквивалентен двум поискам указателей. Эти дополнительные поиски нельзя полностью оптимизировать.

Возможно, еще хуже то, что производительность вашего кэша будет ужасной. Доступ к значениям в кэше будет во много раз быстрее, чем доступ к значениям в основной памяти. (возможно, 10x) Если у вас есть int [], вы знаете, что значения будут последовательными в памяти и, следовательно, легко загружаются в кэш. Тем не менее, для Integer [] отдельные объекты Integer могут случайно появляться в вашей памяти и с гораздо большей вероятностью будут пропускать кэш. Кроме того, Integer использует 24 байта, что означает, что они с меньшей вероятностью поместятся в ваши кэши, чем значения в 4 байта.

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

Answer 8

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

, например:

  SomeObj[] directArray = myArrayList.lockArray();
  try{
    // myArrayList.add(), delete() would throw an illegal state exception
    for (int i = 0; i < 50000; i++){
      directArray[i] += 1;
    }
  } finally {
    myArrayList.unlockArray();
  }

Этот подход продолжает инкапсулировать поведение массива / etc ... поведенияArrayList.

Answer 9

Возможны следующие варианты:
1. Чтобы использовать массив
2. Чтобы использовать ArrayList, который внутренне использует массив

Очевидно, что ArrayList вносит некоторые накладные расходы (см. Исходный код ArrayList). Для 99% случаев использования эти накладные расходы могут быть легко проигнорированы. Однако если вы реализуете чувствительные ко времени алгоритмы и выполняете десятки миллионов операций чтения из списка по индексу, тогда использование пустых массивов вместо списков должно принести заметную экономию времени. ИСПОЛЬЗОВАТЬ ОБЩИЙ СМЫСЛ.

Пожалуйста, посмотрите здесь: http://robaustin.wikidot.com/how-does-the-performance-of-arraylist-compare-to-array Я бы лично настроил тест, чтобы избежать оптимизации компилятора, например, я бы изменил "j =" на "j + =" с последующимиспользование «j» после цикла.

Answer 10

Примитивы намного (намного) быстрее. Всегда. Даже с JIT escape-анализом и т. Д. Пропустите упаковку в java.lang.Integer. Кроме того, пропустите проверку границ массива, которую делает большинство реализаций ArrayList для get (int). Большинство JIT могут распознавать простые шаблоны циклов и удалять циклы, но для этого нет особой причины, если вы беспокоитесь о производительности.

Вам не нужно кодировать примитивный доступ самостоятельно - яДержу пари, что вы можете перейти к использованию IntArrayList из библиотеки COLT - см. http://acs.lbl.gov/~hoschek/colt/ - «Colt предоставляет набор библиотек с открытым исходным кодом для высокопроизводительных научных и технических вычислений в Java») - за несколько минут рефакторинга.