8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824

[David Holmes]

Hi Lev,

On 13/02/2015 2:56 AM, Lev Priima wrote:
> Christos,
>
> Test may fail on shorter arrays(page 8 of paper). For instance, on worst
> case, generated by test, it starts to fail on length 67108864.
> After increasing stack size of runs to merge, Arrays.sort(T[]) works
> also on maximum possible array for HotSpot JVM.

I'd also like to see this documented somewhere in the code. Presently 
there is a reference to listsort.txt but then you have to go and find it 
on the web. :( At a minimum could we please add:

  175          * computation below must be changed if MIN_MERGE is 
decreased.  See
  176          * the MIN_MERGE declaration above for more information.
+             * The maximum value of 49 allows for an array up to length
+             * Integer.MAX_VALUE-4.

> Roger, David,
> I've updated the test (
> http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/test/java/util/Arrays/TimSortStackSize2.java.html
> ) to make it more suitable for regular execution:
>
>    27  * @run main/othervm TimSortStackSize2 67108864

This will still fail on small memory devices:

:~> java TimSortStackSize2 67108864
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

as the default heap ergonomics may not be large enough. I had to add a 
minimum heap of -Xmx385M to get it to run.

Thanks,
David

>    28  * not for regular execution on all platforms:
>    29  * run main/othervm -Xmx8g TimSortStackSize2 1073741824
>    30  * run main/othervm -Xmx32g TimSortStackSize2 2147483644
>
> Could you please push this:
> http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/
> ?
>
> Lev
>
> On 02/12/2015 12:54 PM, christos at zoulas.com wrote:
>> On Feb 12,  9:57pm,david.holmes at oracle.com  (David Holmes) wrote:
>> -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on
>>
>> | Ok - thanks Lev!
>> |
>> | David
>>
>> For posterity can someone document this, and also the value for which
>> Integer.MAX_VALUE-4 fails?
>>
>> christos
>