[hibernate-issues] [Hibernate-JIRA] Created: (HHH-2957) ActionQueue Insertion sort performance degrades exponentially

ActionQueue Insertion sort performance degrades exponentially ------------------------------------------------------------- Key: HHH-2957 URL: http://opensource.atlassian.com/projects/hibernate/browse/HHH-2957 Project: Hibernate3 Issue Type: Improvement Components: core Affects Versions: 3.2.5 Reporter: Jay Erb Attachments: ActionQueue.java, NewInsertActionSorter.java The algorithm for sorting entity insertions performs poorly for when flushing large numbers of entity insertions. There are a few reasons for this: 1. The sort used linear searches over lists which required nested looping. 2. ArrayLists were used to hold the insertion events. ArrayLists give good performance for looping but they have a couple of significant drawbacks: a. Whenever a new item is added to the list, the list is rebuilt with the new size, which causes another loop over all the entries in the list. b. Since it is an array, a contiguous block of memory must be found to hold the array. As the array get large, it gets harder and harder to find a contiguous block large enough. This causes the garbage collector to be run more often, which obviously reduces performance again. I changed the algorithm so that the product of the sort is exactly the same. The difference is that I used hashes for searches and LinkedLists for storing the insertions. The performance is linear. Attached are my changes. -- This message is automatically generated by JIRA. - If you think it was sent incorrectly contact one of the administrators: http://opensource.atlassian.com/projects/hibernate/secure/Administrators.... - For more information on JIRA, see: http://www.atlassian.com/software/jira