Затраты на размещение объектов Java

Question

Я пишу неизменное дерево DOM на Java, чтобы упростить доступ из нескольких потоков. *

Тем не менее, он должен поддерживать вставки и обновления как можно быстрее. И поскольку он неизменен, если я внесу изменение в узел на N-м уровне дерева, мне нужно выделить как минимум N новых узлов, чтобы вернуть новое дерево.

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

Стоит ли это делать? Любые другие советы по ускорению?

Кроме того, кто-нибудь знает, есть ли уже неизменяемая библиотека DOM? Я искал, но ничего не смог найти.

* Примечание. Для тех из вас, кто не знаком с понятием неизменяемости, это в основном означает, что при любой операции над объектом, который ее изменяет, метод возвращает копию объекта с изменениями на месте. чем измененный объект. Таким образом, если другой поток все еще читает объект, он продолжит счастливо работать со «старой» версией, не подозревая, что были внесены изменения, вместо того, чтобы ужасно падать. Смотри http://www.javapractices.com/topic/TopicAction.do?Id=29

Answer 1

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

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

Answer 2

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

Answer 3

Я не уверен, что вы сможете избежать явной синхронизации определенных методов, чтобы убедиться, что все поточно-ориентировано.

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

Попробуйте мыслить на более высоком уровне. У вас есть IMMUTABLE дерево (это в основном набор узлов, указывающих на его дочерние элементы). Вы хотите вставить в него узел. Тогда нет никакого выхода: вам нужно создать новое ВСЕ дерево.

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

Если вы можете справиться с менее прямой реализацией, вы должны уметь обходиться только созданием частей узлов, используя методы, аналогичные описанным в Чисто функциональные структуры данных , чтобы либо снизить среднюю стоимость создания, или вы можете обойти его, используя полуфункциональные подходы (такие как создание итератора, который оборачивает существующий итератор, но возвращает новый узел вместо старого, вместе с механизмом для восстановления таких патчей в структуре как время идет) API-интерфейс в стиле XPath в этом случае может быть лучше API-интерфейса DOM - возможно, вы немного больше отделите узлы от дерева и будете более разумно обращаться с измененным деревом.

Answer 4

Я думаю, что у @Outlaw есть смысл. Структура дерева DOM находится в самих узлах, имея узел, указывающий на его дочерние элементы. Чтобы изменить структуру дерева, вы должны изменить узел, чтобы его нельзя было объединить, нужно создать новый.

Попробуйте мыслить на более высоком уровне. У вас есть IMMUTABLE дерево (это в основном набор узлов, указывающих на его дочерние элементы). Вы хотите вставить в него узел. Тогда нет никакого выхода: вы должны создать новое ВСЕ дерево.

Да, неизменяемое дерево является поточно-ориентированным, но оно влияет на производительность. Создание объекта может быть быстрым, но не быстрее, чем создание объекта НЕТ. :)

Answer 5

@ Outlaw Programmer

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

Каждый узел не должен быть неизменным внутри пакета, только для внешнего интерфейса. node.addChild() будет неизменной функцией с общедоступной видимостью и вернет Document, тогда как node.addChildInternal() будет обычной изменяемой функцией с видимостью пакета. Но поскольку он является внутренним по отношению к пакету, его можно назвать только потомком addChild(), и вся структура в целом гарантированно безопасна для потоков (при условии, что я синхронизирую доступ к пулу объектов). Вы видите недостаток в этом ...? Если это так, пожалуйста, скажите мне!

Я думаю, что использование неизменяемых узлов, вероятно, не даст вам необходимую вам безопасность потоков. Что произойдет, если 1 поток выполняет итерации по узлам (поиск или что-то еще), а другой поток добавляет / удаляет узлы?

Дерево в целом будет неизменным. Скажем, у меня есть Thread1 и Thread2 и дерево dom1. Thread1 начинает операцию чтения на dom1, в то время как Thread2 запускает операцию записи на dom1. Тем не менее, все изменения, которые вносит Thread2, будут фактически внесены в новый объект, dom2 и dom1 будут неизменными. Это правда, что значения, прочитанные Thread1, будут (на несколько микросекунд) устаревшими, но они не будут аварийно завершать работу при исключении IndexOutOfBounds или NullPointer или чем-то подобном, если бы он читал изменяемый объект, для которого была записана запись. Затем Thread2 может запустить событие, содержащее dom2, в Thread1, чтобы он мог снова выполнить его чтение и при необходимости обновить свои результаты.

Редактировать: уточнено

Answer 6

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

Я думаю, что использование неизменяемых узлов, вероятно, не даст вам необходимую вам безопасность потоков. Что произойдет, если 1 поток выполняет итерации по узлам (поиск или что-то еще), а другой поток добавляет / удаляет узлы? Не будут ли результаты поиска недействительными? Я не уверен, сможете ли вы избежать явной синхронизации определенных методов, чтобы убедиться, что все они поточно-ориентированы.