8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824

[Lev Priima]

"49" is also mentioned in the paper as possible solution. I've run test 
from webrev with array length 2147483644 (Integer.MAX_VALUE-4) and 
TimSort passed.

Lev

On 02/11/2015 10:57 PM, David Holmes wrote:
> 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
>>>>
>>>
>>