8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824

[David Holmes]

On 12/02/2015 5:14 AM, Lev Priima wrote:
> 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

So where did the new magic number 49 come from? And how do we know this 
is now "big enough"?

Thanks,
David

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