ActionQueue Insertion sort performance degrades exponentially (Jay Erb)

Description

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.

Environment

None

Activity

Show:
Jay Erb
November 20, 2007, 11:37 PM

What benefit would anyone (me, my company, or hibernate users) get from holding a copyright on something covered by an LGPL license. I know that LGPL allows for copyrighting, but it seems any rights would be relinquished by LGPL.

Steve Ebersole
November 20, 2007, 11:50 PM

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.

Jay Erb
November 21, 2007, 2:29 AM

OK. I don't see the need to make any more changes. The un-copyrighted version is fine with me if it's fine with hibernate.
This will at least give me something to talk about with my lawyer brother-in-law over thanksgiving

Steve Ebersole
February 3, 2008, 7:58 AM

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

trunk/3.2

Steve Ebersole
March 21, 2011, 7:04 PM

Bulk closing stale resolved issues

Assignee

Steve Ebersole

Reporter

Jay Erb

Fix versions

Labels

None

backPortable

None

Suitable for new contributors

None

Requires Release Note

None

Pull Request

None

backportDecision

None

Components

Affects versions

Priority

Major
Configure