Please review fix for 8011944 : Sort fails with ArrayIndexOutOfBoundsException

[roger riggs]

Hi,

I reviewed the algorithm of the test case and it seems to me that it
produces the smallest number of total items to sort for a given stack depth.
I ran it with other stack depths and confirmed that the implementation did
not exceed the new limit.

I was unable to discover a specific explanation or computation for the
current choices to thresholds and corresponding stack depths.

An alternative implementation could use the conservative estimate
and resize the array as needed.  It would avoid overallocation of a
temporary in the normal case.

Thanks, Roger

On 8/23/2013 10:56 AM, Alan Bateman wrote:
> On 22/08/2013 15:25, roger riggs wrote:
>> Please review the fix for:
>>
>>   JDK-8011944[1] : Sort fails with ArrayIndexOutOfBoundsException
>>
>> The pending run stack size is estimated based on the input size.
>> The worst case sequence of inputs exceeds the current allocation and 
>> an exception occurs.
>> Increasing the allocation of the pending run stack addresses the issue.
>> This was present in the original contribution of Timsort and 
>> ComparableTimSort.
>>
>> Webrev[2]:
>>   http://cr.openjdk.java.net/~rriggs/webrev-timsort-8011944/
> Increasing the size of the merge stack looks right. Do you know if 
> there is potential for other cases that could cause problems?
>
> -Alan