"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
