Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Hi Seth, No. But, General direction of openjdk is mostly care about do not introduce regression in next release. All performance improvements are introduced with a very conservative way with checking that we do not slow down any previous behavior/benchmarks. I'm almost sure that simple increasing stack size do not introduce performance regression, but changing mergeCollapse() may do. Please provide performance comparision of different fixes if you have it. Lev On 02/24/2015 11:51 PM, Cantrell, Seth wrote: Hi Lev, I have a quick question about your patch; did you have any time to do a performance comparison on this vs. the change proposed with the bug report? Thanks, Seth Cantrell Software Engineer Siemens Industry Sector Industry Automation Division Siemens Industry Sector Siemens Product Lifecycle Management Software Inc. 2000 Eastman Dr. Milford, OH 45150 Tel. +1 (513) 576-3799 seth.cantr...@siemens.com www.siemens.com/plm
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
On Feb 12, 4:56pm, lev.pri...@oracle.com (Lev Priima) wrote: -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on | Christos, | | Test may fail on shorter arrays(page 8 of paper). For instance, on worst | case, generated by test, it starts to fail on length 67108864. | After increasing stack size of runs to merge, Arrays.sort(T[]) works | also on maximum possible array for HotSpot JVM. | | | Roger, David, | I've updated the test ( | http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/test/java/util/Arrays/TimSortStackSize2.java.html | ) to make it more suitable for regular execution: | |27 * @run main/othervm TimSortStackSize2 67108864 |28 * not for regular execution on all platforms: |29 * run main/othervm -Xmx8g TimSortStackSize2 1073741824 |30 * run main/othervm -Xmx32g TimSortStackSize2 2147483644 | | Could you please push this: | http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/ | ? | Thanks for the explanation Lev! christos
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
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
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Hi Lev, On 13/02/2015 2:56 AM, Lev Priima wrote: Christos, Test may fail on shorter arrays(page 8 of paper). For instance, on worst case, generated by test, it starts to fail on length 67108864. After increasing stack size of runs to merge, Arrays.sort(T[]) works also on maximum possible array for HotSpot JVM. I'd also like to see this documented somewhere in the code. Presently there is a reference to listsort.txt but then you have to go and find it on the web. :( At a minimum could we please add: 175 * computation below must be changed if MIN_MERGE is decreased. See 176 * the MIN_MERGE declaration above for more information. + * The maximum value of 49 allows for an array up to length + * Integer.MAX_VALUE-4. Roger, David, I've updated the test ( http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/test/java/util/Arrays/TimSortStackSize2.java.html ) to make it more suitable for regular execution: 27 * @run main/othervm TimSortStackSize2 67108864 This will still fail on small memory devices: :~ java TimSortStackSize2 67108864 Exception in thread main java.lang.OutOfMemoryError: Java heap space as the default heap ergonomics may not be large enough. I had to add a minimum heap of -Xmx385M to get it to run. Thanks, David 28 * not for regular execution on all platforms: 29 * run main/othervm -Xmx8g TimSortStackSize2 1073741824 30 * run main/othervm -Xmx32g TimSortStackSize2 2147483644 Could you please push this: http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/ ? Lev On 02/12/2015 12:54 PM, chris...@zoulas.com wrote: On Feb 12, 9:57pm,david.hol...@oracle.com (David Holmes) wrote: -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on | Ok - thanks Lev! | | David For posterity can someone document this, and also the value for which Integer.MAX_VALUE-4 fails? christos
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Christos, Test may fail on shorter arrays(page 8 of paper). For instance, on worst case, generated by test, it starts to fail on length 67108864. After increasing stack size of runs to merge, Arrays.sort(T[]) works also on maximum possible array for HotSpot JVM. Roger, David, I've updated the test ( http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/test/java/util/Arrays/TimSortStackSize2.java.html ) to make it more suitable for regular execution: 27 * @run main/othervm TimSortStackSize2 67108864 28 * not for regular execution on all platforms: 29 * run main/othervm -Xmx8g TimSortStackSize2 1073741824 30 * run main/othervm -Xmx32g TimSortStackSize2 2147483644 Could you please push this: http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/ ? Lev On 02/12/2015 12:54 PM, chris...@zoulas.com wrote: On Feb 12, 9:57pm, david.hol...@oracle.com (David Holmes) wrote: -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on | Ok - thanks Lev! | | David For posterity can someone document this, and also the value for which Integer.MAX_VALUE-4 fails? christos
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
On Feb 12, 9:57pm, david.hol...@oracle.com (David Holmes) wrote: -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on | Ok - thanks Lev! | | David For posterity can someone document this, and also the value for which Integer.MAX_VALUE-4 fails? christos
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Hi Lev, ok, looks fine, I'll sponsor it and push it. Roger On 2/12/2015 11:56 AM, Lev Priima wrote: Christos, Test may fail on shorter arrays(page 8 of paper). For instance, on worst case, generated by test, it starts to fail on length 67108864. After increasing stack size of runs to merge, Arrays.sort(T[]) works also on maximum possible array for HotSpot JVM. Roger, David, I've updated the test ( http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/test/java/util/Arrays/TimSortStackSize2.java.html ) to make it more suitable for regular execution: 27 * @run main/othervm TimSortStackSize2 67108864 28 * not for regular execution on all platforms: 29 * run main/othervm -Xmx8g TimSortStackSize2 1073741824 30 * run main/othervm -Xmx32g TimSortStackSize2 2147483644 Could you please push this: http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/ ? Lev On 02/12/2015 12:54 PM, chris...@zoulas.com wrote: On Feb 12, 9:57pm,david.hol...@oracle.com (David Holmes) wrote: -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on | Ok - thanks Lev! | | David For posterity can someone document this, and also the value for which Integer.MAX_VALUE-4 fails? christos
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Thanks! Lev On 02/12/2015 02:53 PM, Roger Riggs wrote: Hi Lev, ok, looks fine, I'll sponsor it and push it. Roger On 2/12/2015 11:56 AM, Lev Priima wrote: Christos, Test may fail on shorter arrays(page 8 of paper). For instance, on worst case, generated by test, it starts to fail on length 67108864. After increasing stack size of runs to merge, Arrays.sort(T[]) works also on maximum possible array for HotSpot JVM. Roger, David, I've updated the test ( http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/test/java/util/Arrays/TimSortStackSize2.java.html ) to make it more suitable for regular execution: 27 * @run main/othervm TimSortStackSize2 67108864 28 * not for regular execution on all platforms: 29 * run main/othervm -Xmx8g TimSortStackSize2 1073741824 30 * run main/othervm -Xmx32g TimSortStackSize2 2147483644 Could you please push this: http://cr.openjdk.java.net/~lpriima/8072909/webrev.01/ ? Lev On 02/12/2015 12:54 PM, chris...@zoulas.com wrote: On Feb 12, 9:57pm,david.hol...@oracle.com (David Holmes) wrote: -- Subject: Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on | Ok - thanks Lev! | | David For posterity can someone document this, and also the value for which Integer.MAX_VALUE-4 fails? christos
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
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
8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
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 -- Lev
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
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
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
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
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
Am 11.02.2015 um 23:57 schrieb David Holmes: So where did the new magic number 49 come from? And how do we know this is now big enough? Thanks, David +1 Ulf
Re: 8072909: TimSort fails with ArrayIndexOutOfBoundsException on arrays longer than 1073741824
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
