Как мне иметь дело с очень большим массивом в Java?

Question

У меня есть алгоритм, который в настоящее время выделяет очень большой массив значений типа double, который он часто обновляет и ищет. Размер массива составляет N ^ 2/2, где N - количество строк, в которых работает алгоритм. Я также должен сохранить копию всего объекта для целей, связанных с приложением, окружающим алгоритм.

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

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

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

Мой вопрос: как лучше с этим справиться? Должен ли я использовать nio FileChannel и MappedByteBuffer, или есть лучший подход. Если я использую подход nio, какой удар по производительности мне следует ожидать по сравнению с массивом в памяти того же размера?

Спасибо

Answer 1

Если вы начинаете исчерпывать доступную память, то вы, вероятно, также скоро начнете исчерпывать доступные индексы массива, размер массива ограничен до Integer.MAX_VALUE, и при использовании double в качестве элементов массива «только» 32 ГБ.

Получение машины с 32 ГБ памяти стоит дорого, но, вероятно, не так дорого, как ваше время на изменение алгоритма и все связанные с ним тесты.

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

Другой вариант, который у вас есть, если предположить, что массив несколько заполнен, - это использовать одну из различных структур данных разреженного массива, хотя они, как правило, выгодны, только если ваш массив заполнен менее чем на 20%. *

Редактировать : Поскольку кажется, что вы уже исследовали альтернативы, тогда MappedByteBuffer вполне может быть подходящим вариантом. Очевидно, что это повлияет на производительность, однако, если вы выполняете в основном последовательные операции чтения и записи из массива, это не должно быть слишком плохо. Если вы делаете случайное чтение и запись, то это будет очень медленно и очень быстро. Или очень медленно очень медленно ... в зависимости от того, как вы смотрите на эти вещи; -)

Answer 2

Если вы работаете на ПК, размер страниц для сопоставленных файлов может составлять 4 килобайта.

Таким образом, вопрос действительно начинается с того, что если я начну выгружать данные на диск, «насколько случайен мой произвольный доступ к ОЗУ, которое сейчас в файле»?

И (... могу ли я и если да ...), как я могу упорядочить двойные числа, чтобы максимизировать случаи, когда к двоичным объектам на странице 4K обращаются вместе, а не к нескольким за раз на каждой странице перед следующим диском 4K выборки?

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

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

Answer 3

У меня был в целом хороший опыт работы с Java MappedByteBuffers, и я призываю вас взглянуть на него глубже. Это очень хорошо может позволить вам не иметь дело с изменениями -Xmx снова. Имейте в виду, что если вам требуется более 2-4 ГБ адресуемого пространства, то требуется 64-разрядный процессор, ОС и JVM.

Чтобы выйти за рамки проблемы Integer.MAX_VALUE индексов, вы могли бы написать алгоритм разбиения на страницы, как я сделал здесь в связанном ответе на Двоичный поиск в отсортированном (отображенном в памяти?) Файле в Java .

Answer 4

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

Я бы соблазнился сделать это:

1. Поместите все ваши массивы за объектный интерфейс (если они этого еще не сделали), что освобождает вас от необходимости легко менять реализацию.
2. Используйте массив SoftReferences, где каждый SoftReference указывает на массив значений типа double для этой строки. Используйте ReferenceQueue, чтобы сохранить массивы на диск, когда GC выгрузит их. Когда get () возвращает ноль, получить с диска.

Вы можете обнаружить, что таким образом у вас больше контроля над производительностью - -Xmx можно настроить по желанию.

Answer 5

Если проблема заключается в том, что у вас не хватает памяти, простое решение состоит в том, чтобы обновить ваше оборудование за счет увеличения объема памяти, увеличить размер кучи Java и / или переключиться на 64-битную виртуальную машину Java.

С другой стороны, если вы используете ограничение Java по размеру массивов, вы можете пойти по маршруту ByteBuffer или переключиться на использование массива массивов. Позже Sun предлагает обходной путь.

При использовании массива массивов вы можете (теоретически) справиться со значениями N, близкими к 2**31. На практике ваш лимит будет определяться объемом вашей физической памяти и объемом, который можно использовать с помощью вашей комбинации ОС / JVM.

Answer 6

Вы можете попытаться сохранить массив в виде строк в таблице базы данных и использовать хранимые процедуры для обновления и поиска в нем.

Другая идея:

Используйте B-Tree в качестве массива и сохраните несколько листов на диске. Убедитесь, что узлы B-дерева соответствуют размеру страницы или размеру нескольких страниц.

Answer 7

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

Итак, что на самом деле делает ваша программа алгоритмически?