[hibernate-issues] [Hibernate-JIRA] Commented: (HHH-2957) ActionQueue Insertion sort performance degrades exponentially (Jay Erb)
Steve Ebersole (JIRA)
noreply at atlassian.com
Tue Nov 20 15:49:56 EST 2007
[ http://opensource.atlassian.com/projects/hibernate/browse/HHH-2957?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_28904 ]
Steve Ebersole commented on HHH-2957:
-------------------------------------
The second one is acceptable.
You can, if desired, also still hold copyright. If you are interested in that aspect, let me know and I can help you with the wording. The specifics depend on whether you or you employer control copyright.
> 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
More information about the hibernate-issues
mailing list