[hibernate-issues] [Hibernate-JIRA] Assigned: (HHH-6848) The duration of hibernate merge rises quadratically with the amount of entities in a to be merged objectgraph

The duration of hibernate merge rises quadratically with the amount of entities in a to be merged objectgraph ------------------------------------------------------------------------------------------------------------- Key: HHH-6848 URL: http://opensource.atlassian.com/projects/hibernate/browse/HHH-6848 Project: Hibernate Core Issue Type: Improvement Components: core Affects Versions: 3.6.8, 4.0.0.CR6 Environment: Any Hibernate version, any database platform. Reporter: Wim Ockerman Assignee: Gail Badner Labels: hibernate, merge, performance, quadratic Attachments: HibernateMergeMeasurementBeforeAndAfterSolution.png, Sample_JProfiler_hotspot_research_in_a_merge_of_a_big_object_graph.png Tests with merging large objectgraphs showed quadratic rise of duration of the merge related to the object-graph size. From a certain number of objects in the graph this becomes substantial. This limits hibernate scalability for larger object-graph usages. Analysis (based on 3.6.8 code branch): The merge algorithm of hibernate is a recursive objectgraph walking algorithm. During it's execution it builds up algorithm state information e.g. of merged entities to original objects in the input graph. The information is stored in the EventCache object in the *entityToCopyMap* member. ( org.hibernate.event.def.EventCache) At certain places in the merge algorithm the inverse relation as hold in the EventCache object is needed. see e.g. def.AbstractSaveEventListener.performSaveOrReplicate -> calling persister.getPropertyValuesToInsert(.., *getMergeMap()*,..) The getMergeMap() call calls through to the EventCache's invertMap method. In the implementation of invertMap() a new map is created on the spot and all the elements in the entityToCopyMap where put in, now as copy to entity direction. The call invertMap() happens more in a big detached graph wile merging, and also the size of the entityToCopyMap rises with the number of object already merged in the graph. Thus we have a quadratic relation between the total inverMap() execution time and the number of objects in a graph to be merged. JProfiler screenshot sample attached showing a high call count and high duration time on the invertMap method in a merge vs time it took for a flush of the merged object graph. The latter was unexpected, as the flush time is a good higher bound reference for an object graph operation. To solve this problem see proposed solution in pull request #208 of [hibernate-core] Performance Optimization of in memory merge algorithm. With the solution, the merge duration behaves more linear with respect to the size of the to be merged objectgraph. See attached plot of the original hibernate merge behaviour vs entities in a graph (redline) and the proposed solution's timeing.