java.lang.ArrayIndexOutOfBoundsException: 40

GitHub | d-moos | 4 months ago
  1. 0

    Failed to update profile and inventory (level 40)

    GitHub | 4 months ago | d-moos
    java.lang.ArrayIndexOutOfBoundsException: 40
  2. 0

    ArrayIndexOutOfBoundsException Help!!

    Oracle Community | 1 decade ago | 807569
    java.lang.ArrayIndexOutOfBoundsException: 40
  3. Speed up your debug routine!

    Automated exception search integrated into your IDE

  4. 0

    FULL PRODUCT VERSION : java version "1.7.0_75" OpenJDK Runtime Environment (IcedTea 2.5.4) (7u75-2.5.4-1~precise1) OpenJDK 64-Bit Server VM (build 24.75-b04, mixed mode) ADDITIONAL OS VERSION INFORMATION : Every OS, since this is portable Java code. A DESCRIPTION OF THE PROBLEM : As previously reported in bug 8011944, the function mergeCollapse in the TimSort class does not preserve the invariant runLen[i] > runLen[i+1]+runLen[i+2]. This leads to an ArrayIndexOutOfBoundsException in TimSort's pushRun method. We refer to 8011944 for more details. The bug was marked as fixed, after an update in which the allocated length of runLen, as declared in the constructor, was increased. However, we found that the fix does not suffice, see the attached test case. In particular, the declared length 40 of runLen which is chosen if the length of the input array is >= 119151, does not suffice. We provide a full analysis of the bug in a paper, which is available at: http://envisage-project.eu/?page_id=1412 REGRESSION. Last worked in version 6u43 ADDITIONAL REGRESSION INFORMATION: Last worked in version 6u31, according to bug report 8011944 STEPS TO FOLLOW TO REPRODUCE THE PROBLEM : Run the attached test case as follows: java TestTimSort 67108864 (<=changed from paper to correct value) or java -Xmx8G TestTimSort 1073741824 EXPECTED VERSUS ACTUAL BEHAVIOR : EXPECTED - No Exception occurs during sorting. ACTUAL - ArrayIndexOutOfBoundsException ERROR MESSAGES/STACK TRACES THAT OCCUR : Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 40 at java.util.TimSort.pushRun(TimSort.java:386) at java.util.TimSort.sort(TimSort.java:213) at java.util.TimSort.sort(TimSort.java:173) at java.util.Arrays.sort(Arrays.java:659) at TestTimSort.main(TestTimSort.java:18) REPRODUCIBILITY : This bug can be reproduced always. ---------- BEGIN SOURCE ---------- import java.util.*; public class TestTimSort { private static final int MIN_MERGE = 32; private static final Comparator<Object> NATURAL_ORDER = new Comparator<Object>() { @SuppressWarnings("unchecked") public int compare(Object first, Object second) { return ((Comparable<Object>)first).compareTo(second); } }; private final int minRun; private final List<Long> runs = new ArrayList<Long>(); public static void main(String[] args) { int length = Integer.parseInt(args[0]); Arrays.sort(JDKWorstCase(length), NATURAL_ORDER); } private TestTimSort(int len) { minRun = minRunLength(len); } private static int minRunLength(int n) { assert n >= 0; int r = 0; // Becomes 1 if any 1 bits are shifted off while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r; } /** * Adds a sequence x_1, ..., x_n of run lengths to <code>runs</code> such that:<br> * 1. X = x_1 + ... + x_n <br> * 2. x_j >= minRun for all j <br> * 3. x_1 + ... + x_{j-2} < x_j < x_1 + ... + x_{j-1} for all j <br> * These conditions guarantee that TimSort merges all x_j's one by one * (resulting in X) using only merges on the second-to-last element. * @param X The sum of the sequence that should be added to runs. */ private void generateJDKWrongElem(long X) { for(long newTotal; X >= 2*minRun+1; X = newTotal) { //Default strategy newTotal = X/2 + 1; //Specialized strategies if(3*minRun+3 <= X && X <= 4*minRun+1) { // add x_1=MIN+1, x_2=MIN, x_3=X-newTotal to runs newTotal = 2*minRun+1; } else if(5*minRun+5 <= X && X <= 6*minRun+5) { // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=X-newTotal to runs newTotal = 3*minRun+3; } else if(8*minRun+9 <= X && X <= 10*minRun+9) { // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=X-newTotal to runs newTotal = 5*minRun+5; } else if(13*minRun+15 <= X && X <= 16*minRun+17) { // add x_1=MIN+1, x_2=MIN, x_3=MIN+2, x_4=2MIN+2, x_5=3MIN+4, x_6=X-newTotal to runs newTotal = 8*minRun+9; } runs.add(0, X-newTotal); } runs.add(0, X); } /** * Fills <code>runs</code> with a sequence of run lengths of the form<br> * Y_n x_{n,1} x_{n,2} ... x_{n,l_n} <br> * Y_{n-1} x_{n-1,1} x_{n-1,2} ... x_{n-1,l_{n-1}} <br> * ... <br> * Y_1 x_{1,1} x_{1,2} ... x_{1,l_1}<br> * The Y_i's are chosen to satisfy the invariant throughout execution, * but the x_{i,j}'s are merged (by <code>TimSort.mergeCollapse</code>) * into an X_i that violates the invariant. * @param X The sum of all run lengths that will be added to <code>runs</code>. */ private void runsJDKWorstCase(int length) { long runningTotal = 0, Y=minRun+4, X=minRun; while(runningTotal+Y+X <= length) { runningTotal += X + Y; generateJDKWrongElem(X); runs.add(0,Y); // X_{i+1} = Y_i + x_{i,1} + 1, since runs.get(1) = x_{i,1} X = Y + runs.get(1) + 1; // Y_{i+1} = X_{i+1} + Y_i + 1 Y += X + 1; } if(runningTotal + X <= length) { runningTotal += X; generateJDKWrongElem(X); } runs.add(length-runningTotal); } private Integer[] createArray(int length) { Integer[] a = new Integer[length]; Arrays.fill(a, 0); int endRun = -1; for(long len : runs) a[endRun+=len] = 1; a[length-1]=0; return a; } public static Integer[] JDKWorstCase(int length) { TestTimSort t = new TestTimSort(length); t.runsJDKWorstCase(length); return t.createArray(length); } } ---------- END SOURCE ---------- CUSTOMER SUBMITTED WORKAROUND : There are two options: 1. In the constructor of the TimSort class, change int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : len < 119151 ? 24 : 40); to int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : len < 119151 ? 24 : 49); 2. Change the mergeCollapse method of TimSort to: private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; if ( n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] || n-1 > 0 && runLen[n-2] <= runLen[n] + runLen[n-1]) { if (runLen[n - 1] < runLen[n + 1]) n--; } else if (n<0 || runLen[n] > runLen[n + 1]) { break; // Invariant is established } mergeAt(n); } }

    JDK Bug System | 2 years ago | Webbug Group
    java.lang.ArrayIndexOutOfBoundsException: 40

    Not finding the right solution?
    Take a tour to get the most out of Samebug.

    Tired of useless tips?

    Automated exception search integrated into your IDE

    Root Cause Analysis

    1. java.lang.ArrayIndexOutOfBoundsException

      40

      at ink.abb.pogo.scraper.gui.SocketServer.sendProfile()
    2. ink.abb.pogo
      SocketServer.sendProfile
      1. ink.abb.pogo.scraper.gui.SocketServer.sendProfile(SocketServer.kt:73)
      1 frame