Как я должен иметь дело с очень большим массивом в Java?
У меня есть алгоритм, который в настоящее время выделяет очень большой массив, удваивается, который он обновляет и часто ищет. Размер массива является N^2/2, где N является количеством строк, на которые воздействует алгоритм. Я также должен сохранить копию всей вещи в целях связанной с приложением, окружающим алгоритм.
Конечно, это накладывает ограничение на количество строк, которые может обработать мой алгоритм, поскольку у меня есть ограничение "кучи" для утверждения с. До этой точки я имею далеко с выяснением у людей, использующих алгоритм для обновления-Xmx, устанавливающего для выделения большего количества места, и это хорошо работало. Однако у меня теперь есть подлинная проблема, где мне нужен этот массив, чтобы быть больше, чем я могу вписаться в память.
У меня уже есть планы изменить мой алгоритм, чтобы смягчить необходимость этого большого массива и иметь некоторые многообещающие результаты в том домене. Однако это - фундаментальное изменение к процессу и потребует намного большего количества работы, прежде чем это доберется до высоко полируемого условия моего текущего кода, который работает в производстве очень успешно и был в течение нескольких лет.
Так, в то время как я - совершенствование мой новый алгоритм, я хотел расширить жизнь существующей, и это означает заниматься ограничением "кучи", связанным с выделением моего огромного массива, удваивается.
Мой вопрос - то, что лучший способ иметь дело с ним? Если я использую nio FileChannel и MappedByteBuffer, или есть ли лучший подход. Если я действительно использую подход nio, какой удар производительности я должен ожидать получать по сравнению с массивом в оперативной памяти того же размера?
Спасибо
7 ответов
Если вы работаете на ПК, размеры страниц для сопоставленных файлов, вероятно, будет 4 килобайта.
Итак, вопрос действительно начинается с того, если я начну перекачивать данные на диск, «насколько случайным будет мой произвольный доступ к RAM-that-is-now-a-file» ?
И (... могу ли я, и если да ...) как я могу заказать дубли, чтобы максимизировать случаи, когда двойники на странице 4K доступны вместе, а не по нескольку одновременно на каждой странице перед следующим 4K выборка с диска?
Если вы используете стандартный ввод-вывод, вы, вероятно, все еще хотите читать и писать фрагментами, но эти фрагменты могут быть меньше. Секторы будут иметь размер не менее 512 байт, дисковые кластеры - больше, но какой размер чтения лучше всего, учитывая, что для каждого ввода-вывода есть накладные расходы ядра и обратно?
Извините, но боюсь, что ваши следующие шаги зависят от в значительной степени на алгоритм и данные, которые вы используете.
I've had generally good experiences with Java's MappedByteBuffers, and encourage you to have a deeper look at it. It very well may allow you to not deal with the -Xmx changes again. Be aware that if you need more than 2-4GB of addressable space then a 64-bit CPU, OS and JVM are required.
To get beyond the Integer.MAX_VALUE indices issue you could write a paging algorithm, as I have done here in a related answer to Binary search in a sorted (memory-mapped ?) file in Java.
Если проблема в том, что вам не хватает памяти, простое решение - обновить ваше оборудование, добавив больше памяти, увеличить размер кучи Java и / или переключиться на 64-битную JVM.
С другой стороны, если вы работаете с ограничением Java на размер массивов, вы можете пойти по маршруту ByteBuffer или переключиться на использование массива массивов. Последний вариант - это обходной путь, предложенный Sun.
Используя подход с использованием массивов, вы можете (теоретически) справиться со значениями N , близкими к 2 ** 31 . На практике ваш лимит будет определяться объемом имеющейся у вас физической памяти и объемом, который можно адресовать с помощью вашей комбинации ОС / JVM.
Вы переходите в область написания программного обеспечения, которое наилучшим образом использует кэш (например, кэш памяти в процессоре). Это сложно сделать правильно, и «правильный» способ сделать это зависит от того, как разработан ваш алгоритм.
Итак, что в действительности делает ваша программа алгоритмически?
Вы можете попробовать сохранить массив в виде строк в таблице базы данных и использовать сохраненные процедуры для обновления и поиска в нем.
Другая идея:
Используйте B-дерево в качестве вашего массив и оставьте несколько листьев на диске. Убедитесь, что узлы B-Tree имеют размер страницы или несколько страниц.
Это не Segoe. Я потратил последние три дня, пытаясь реконструировать Windows Explorer в Windows 7. Работая с WPF и Vista, Segoe UI был моим первым выбором для семейства шрифтов, но я могу подтвердить, что он не совсем соответствует тому, что Проводник Windows использует.
заключается в использовании одной из различных структур данных разреженного массива, хотя они, как правило, полезны только в том случае, если ваш массив заполнен менее чем на 20%.Изменить : Поскольку кажется, что вы уже исследовали альтернативы, то MappedByteBuffer вполне может быть подходящим вариантом. Очевидно, это повлияет на производительность, однако, если вы в основном выполняете последовательное чтение и запись из массива, это не должно быть так уж плохо. Если вы выполняете произвольное чтение и запись, то это будет очень медленно, очень быстро. Или очень медленно, очень медленно ... в зависимости от того, как вы смотрите на эти вещи; -)
Очевидно, это повлияет на производительность, однако, если вы в основном выполняете последовательное чтение и запись из массива, это не должно быть так уж плохо. Если вы выполняете произвольное чтение и запись, то это будет очень медленно, очень быстро. Или очень медленно, очень медленно ... в зависимости от того, как вы смотрите на эти вещи; -) Очевидно, что это повлияет на производительность, однако, если вы в основном выполняете последовательное чтение и запись из массива, это не должно быть так уж плохо. Если вы выполняете произвольное чтение и запись, то это будет очень медленно, очень быстро. Или очень медленно, очень медленно ... в зависимости от того, как вы смотрите на эти вещи; -)Имейте в виду, что некоторые операционные системы лучше поддерживают отображение памяти, чем другие.
У меня возникнет соблазн сделать это:
- Поместите весь ваш массив получает / помещает за объектный интерфейс (если они еще не были), таким образом освобождая вас, чтобы легко изменить реализацию.
- Используйте массив SoftReferences, где каждый SoftReference указывает на массив двойников для этой строки. Используйте ReferenceQueue для сохранения массивов на диск, когда GC их выталкивает. Когда get () возвращает значение null, выполняется извлечение с диска.
Вы можете обнаружить, что таким образом у вас больше контроля над производительностью - параметр -Xmx может быть изменен по желанию.