8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Lev Priima
lev.priima at oracle.com
Wed Feb 11 19:14:52 UTC 2015
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
>>
>
More information about the core-libs-dev
mailing list