[hibernate-issues] [Hibernate-JIRA] Commented: (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:comment-tabpanel#action_28907 ] 

Steve Ebersole commented on HHH-2957:
-------------------------------------

IANAL, but my understanding is that you explicitly assert your copyright ownership and then explicitly transfer ownership under the terms of the LGPL.

It has more to do with validating origination.

Of course this is such a small piece of the overall codebase that generally we don't fret about it.  However, we are currently discussing changes whereby all contributions would need to come from folks holding contribution agreements.

> 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