8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824

[David Holmes]

Ok - thanks Lev!

David

On 12/02/2015 7:58 PM, Lev Priima wrote:
> "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
>>>>>
>>>>
>>>
>