Накладные расходы на выделение объектов Java

Question

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

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

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

Стоит ли это делать?Есть еще какие-нибудь советы по ускорению процесса?

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

Попытайтесь мыслить на более высоком уровне.У вас есть НЕИЗМЕНЯЕМОЕ дерево (которое в основном представляет собой набор узлов, указывающих на его дочерние элементы).Вы хотите вставить в него узел.Тогда выхода нет.:вы должны создать новое ЦЕЛОЕ дерево.

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

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

Answer 4

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

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

Answer 5

@Программист Вне закона

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

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

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

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

Редактировать:проясненный

Answer 6

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

Попытайтесь мыслить на более высоком уровне.У вас есть НЕИЗМЕНЯЕМОЕ дерево (которое в основном представляет собой набор узлов, указывающих на его дочерние элементы).Вы хотите вставить в него узел.Тогда выхода нет.:вы должны создать новое ЦЕЛОЕ дерево.

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