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

[Steve Ebersole (JIRA)]

     [ http://opensource.atlassian.com/projects/hibernate/browse/HHH-2957?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Steve Ebersole resolved HHH-2957.
---------------------------------

    Resolution: Fixed

I ended up applying this as an inner class, as that made the most sense.

trunk/3.2

> ActionQueue Insertion sort performance degrades exponentially (Jay Erb)
> -----------------------------------------------------------------------
>
>                 Key: HHH-2957
>                 URL: http://opensource.atlassian.com/projects/hibernate/browse/HHH-2957
>             Project: Hibernate3
>          Issue Type: Patch
>          Components: core
>    Affects Versions: 3.2.5
>            Reporter: Jay Erb
>            Assignee: Steve Ebersole
>             Fix For: 3.2.6, 3.3
>
>         Attachments: ActionQueue.java, NewInsertActionSorter.java, NewInsertActionSorter.java
>
>   Original Estimate: 0 minutes
>  Remaining Estimate: 0 minutes
>
> 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.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira