Альтернативы ArrayList<Double> для примитивных типов в Java для численных вычислений
Мой вопрос: как лучше всего избежать упомянутых накладных расходов? Я не понимаю, почему мой вопрос закрыли по причине: «Этому вопросу нужно быть более целенаправленным».
В настоящее время я работаю над численными вычислениями в определенной области исследований и унаследовал пакет Java, давно реализованный моей командой. Моя задача сейчас — оптимизировать его работу. В пакете широко используется ArrayList<Double>. Насколько мне известно, Java, по крайней мере до версии 9, которую я использую, не поддерживает ArrayList примитивных типов из-за стирания типов в дженериках Java.
С этим есть несколько проблем:
Накладные расходы на хранение: Double — это класс-оболочка для double. Поскольку Double является объектом, он включает заголовок объекта, который занимает 8 байт. Таким образом, каждый объект Double занимает 16 байт памяти.
Несмежная память:
ArrayListвнутренне использует массив для храненияDoubleобъектов, т. е.Double[] data. Этот массив содержит ссылки на экземплярыDouble. Эти экземпляры не хранятся в куче подряд. Например, еслиDouble[] data = {1.0, 2.0}, ссылки в данных являются смежными, а фактические объектыDouble, на которые указывают эти ссылки, — нет. Это приводит к плохой локальности и частым промахам в кэше из-за необходимости разыменования этих указателей.Распаковка и автоупаковка. При выполнении сравнений и вычислений с помощью Double возникают дополнительные накладные расходы из-за распаковки и автоупаковки.
Мои вопросы:
Каковы наилучшие методы, позволяющие избежать упомянутых накладных расходов? Я приветствую любые ответы на вопросы ниже.
Есть ли в последних версиях Java какие-либо новые функции, позволяющие использовать ArrayList с примитивными типами?
Существуют ли какие-либо экспериментальные функции, платформы или библиотеки, поддерживающие это?
Если нет, то возможно ли создать личный
DoubleArrayList, заменив весь объект в исходном кодеArrayListна примитивный двойной? Каковы потенциальные подводные камни такого подхода?
ПС:
У нас очень плотный график, и у нас нет времени переписывать весь пакет на C++, где доступен
vector<double>.В нашем случае контейнер будет менять размер во время вычислений, и мы не знаем размер заранее. Поэтому мы должны использовать массив изменяемого размера (например,
ArrayList) вместоdouble[].
Вы можете рассмотреть возможность использования сторонней библиотеки коллекций; например старая библиотека GNU Trove. Но учтите, что эта библиотека и ей подобные обязательно несовместимы с java.util.List. (Поищите в Google «высокопроизводительные коллекции Java» и самостоятельно изучите альтернативы.)
Совет: избегайте терминов «лучшая практика» и «лучший способ» в Stack Overflow. К сожалению, такие термины часто получают единогласное большинство голосов, даже не прочитав Вопрос.
Ответы 2
Используйте double[].
«Свободное» изменение размера ArrayList — это просто удобство: когда требуется больше места, внутренний резервный массив заменяется массивом в два раза большего размера, а элементы копируются с использованием старого школьного цикла.
Это тривиальная реализация для самостоятельного написания кода.
Создайте класс с полем double[] и скопируйте то, что вам нужно, из ArrayList, но добавьте метод получения для массива и используйте его для своих вычислений.
Если вам это сходит с рук, используйте вместо этого float[], поскольку операции с float будут примерно в два раза быстрее, чем с double.
Спасибо. Это эквивалентно написанию класса-оболочки для double[], который функционирует аналогично ArrayList для двойных значений.
Является ли производительность с плавающей запятой против двойной производительности в значительной степени из-за объема памяти (и, следовательно, кеширования и т. д.)? Я бы подумал, что на современном оборудовании они оба будут обрабатываться одним и тем же оборудованием под капотом (и, в частности, что они оба будут расширены до точности ЦП/ФПУ, которая выше, чем у любого из них).
@yshavit память и процессор; на 32-битном процессоре вычисления занимают вдвое больше циклов. На 64-битных машинах разницы нет. Аналогично и с памятью. Хотя вы, вероятно, правы: большинство машин сейчас имеют 64-битную архитектуру.
@Bohemian Ах, ладно, это имеет смысл — спасибо! Я предполагал 64-битную версию (особенно учитывая, что команда OP явно имеет в виду производительность, поэтому я предполагаю, что они используют современные процессоры, причем, вероятно, среднего и высокого класса), и не знал, есть ли даже в в этом мире есть разница между числами с плавающей запятой и двойными числами.
Проект Валгалла
Есть ли в последних версиях Java какие-либо новые функции, позволяющие использовать ArrayList с примитивными типами?
Ведется работа, которая может размыть две системы типов в Java: примитивы и объекты. Смотрите Проект Валгалла.
Есть ли экспериментальные функции
В рамках Project Valhalla еще не реализовано никаких функций, отвечающих вашим потребностям. Несмотря на активную разработку, вы не скоро получите пользу от этой работы.
Коллекции затмений
библиотеки, которые это поддерживают?
Библиотека Eclipse Collections предлагает коллекции примитивов. Сюда входят интерфейсы:
… с этими реализациями:
Пример:
MutableDoubleList doubleList = DoubleLists.mutable.of( 1.0, 2.0, 3.0 );
Вы должны увидеть резкое сокращение использования памяти. Например, посмотрите на эту диаграмму памяти, сохраненную с помощью IntArrayList на основе примитивов в Eclipse Foundation, а не с ArrayList<Integer>, включенным в Java.
Дополнительную информацию смотрите в руководстве.
возможно ли создать личный DoubleArrayList
Да, можно, как обсуждалось в Ответ Bohemian.
Но я бы сначала изучил классы Eclipse Collections, прежде чем писать свои собственные.
Eclipse Collections имеет открытый исходный код. Таким образом, вы можете проверить детали реализации самостоятельно.
нет времени переписывать весь пакет на C++, где доступен вектор.
Я ожидал, что обработка кода Java для использования преимуществ классов Eclipse Collections будет намного проще, быстрее и менее подвержена ошибкам, чем полное переписывание на другом языке.
Java-версии
версия 9, которую я использую,
Знайте, что срок службы Java 9 истек.
Я настоятельно рекомендую перейти на LTS версию Java: 8, 11, 17, 21 и, возможно, 25.
См. Историю версий Java в Википедии.
Вы можете рассмотреть возможность использования сторонней библиотеки коллекций; например старая библиотека GNU Trove. Но учтите, что эта и подобные ей библиотеки обязательно несовместимы с
java.util.List.