Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8164793

new ArrayDeque(2**N) allocates backing array of size 2**(N+1)

    XMLWordPrintable

    Details

      Description

      FULL PRODUCT VERSION :
      java version "1.6.0_45"
      Java(TM) SE Runtime Environment (build 1.6.0_45-b06)
      Java HotSpot(TM) Client VM (build 20.45-b01, mixed mode, sharing)

      ADDITIONAL OS VERSION INFORMATION :
      All OS

      A DESCRIPTION OF THE PROBLEM :
      The problem is on the method allocateElements.
      When the paramenter is a number power of 2 (8, 16, 32, etc.) the calculated capacity is the double (16, 32, 64, etc.).
      The problem is on the strategy to add the bits at the rigth, because the bits are allays added even the passed argument have a valid size (number power 2).
      One way to resolve, is:
      1 - on the if convert "<=" on "<", this will solve the problem for minimum capacity (8);
      2 - initially inside the if, assign the passed argument -1 to the initialCapacity variable: "initialCapacity = numElements - 1;" ; (this will make the algoritm start on the previous number that wil be anulated by "initialCapacity++;" at the end;

      problematic method with my annotations:

          private void allocateElements(int numElements) {
              int initialCapacity = MIN_INITIAL_CAPACITY;
              // Find the best power of two to hold elements.
              // Tests "<=" because arrays aren't kept full.
              if (numElements >= initialCapacity) { // change to: if (numElements = initialCapacity) {
                  initialCapacity = numElements; // change to: initialCapacity = numElements - 1;
                  initialCapacity |= (initialCapacity >>> 1);
                  initialCapacity |= (initialCapacity >>> 2);
                  initialCapacity |= (initialCapacity >>> 4);
                  initialCapacity |= (initialCapacity >>> 8);
                  initialCapacity |= (initialCapacity >>> 16);
                  initialCapacity++;

                  if (initialCapacity < 0) // Too many elements, must back off
                      initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
              }
              elements = (E[]) new Object[initialCapacity];
          }


      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      unit test code:

          @Test
          public void testArrayDequeAllocateElements() throws Exception {
              Object[] elementsArr = getelementsArrFromArrayDeque(new ArrayDeque<String>(8));
              assertEquals(8, getelementsArrFromArrayDeque(new ArrayDeque<String>(8)).length);// faill
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(9)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(10)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(11)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(12)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(13)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(14)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(15)).length);
              assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(16)).length);// faill
              assertEquals(32, getelementsArrFromArrayDeque(new ArrayDeque<String>(17)).length);
          }

          private Object[] getelementsArrFromArrayDeque(ArrayDeque<String> ad) throws NoSuchFieldException, IllegalAccessException {
              Object[] elementsArr = new Object[0];
              Field elementsField = ArrayDeque.class.getDeclaredField("elements");
              elementsField.setAccessible(true);
              elementsArr = (Object[]) elementsField.get(ad);
              return elementsArr;
          }


      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The capacity should be the passed argument (if power of 2) ou the next power of 2 value
      ACTUAL -
      when power of 2 value passed (8, 16, 32, etc.) the capacity is the the double (16, 32, 64, etc.)

      REPRODUCIBILITY :
      This bug can be reproduced always.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                martin Martin Buchholz
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                7 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: