8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824

[Lev Priima]

Just briefly looked at it, w/o evaluating formal proof. But original 
Python implementation(written on C) works on stack size even more 
simple, AFAIU it:

/* The maximum number of entries in a MergeState's pending-runs stack.
  * This is enough to sort arrays of size up to about
  *     32 * phi ** MAX_MERGE_PENDING
  * where phi ~= 1.618.  85 is ridiculouslylarge enough, good for an array
  * with 2**64 elements.
  */
#define MAX_MERGE_PENDING 85

Lev

On 02/11/2015 08:32 PM, Roger Riggs wrote:
> Hi Lev,
>
> The fix looks fine.
>
> Did you consider the improvements suggested in the paper to 
> reestablish the invariant?
>
> Roger
>
> On 2/11/2015 11:29 AM, Lev Priima wrote:
>> Hi,
>>
>> Stack length increased previously by JDK-8011944 was insufficient for 
>> some cases.
>> Please review and push:
>> webrev: http://cr.openjdk.java.net/~lpriima/8072909/webrev.00/
>> issue: https://bugs.openjdk.java.net/browse/JDK-8072909
>>
>