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 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.

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 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.

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 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.

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.

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.

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.

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.