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

Performance issue in java.base.java.util.PriorityQueue.grow()

XMLWordPrintable

      A DESCRIPTION OF THE PROBLEM :
      In java.base.java.util.PriorityQueue.grow(), to get the new capacity of queue array, there's such code
       "
      int newCapacity = ArraysSupport.newLength(oldCapacity,
                      minCapacity - oldCapacity, /* minimum growth */
                      oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                                                 /* preferred growth */);
      "
      , besides a single line comment "// Double size if small; else grow by 50%".

      I reckon that when "oldCapacity < 64", the newCapacity should be "oldCapacity * 2" thus double size, other than "oldCapacity + 2". I wonder that if this drag down the performance of array's copy, since "oldCapacity + 2" might cause frequently copying of array when oldCapacity is less than 64.

      This issue not only shows up in version 17.0.1, but also JDK14 and JDK8. I don't know if it's intentional or a slip "+" instead of "*". I see that there is a version that "(oldCapacity + 1) * 2" on some blog, but I don't know what version is that.

      I wonder why if it's intentional, please. Sorry to interrupt.
      Best Regards.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      no need to reproduce, it's in the source code.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      int newCapacity = ArraysSupport.newLength(oldCapacity,
                      minCapacity - oldCapacity, /* minimum growth */
                      oldCapacity < 64 ? oldCapacity * 2 : oldCapacity >> 1
                                                 /* preferred growth */);
      ACTUAL -
      int newCapacity = ArraysSupport.newLength(oldCapacity,
                      minCapacity - oldCapacity, /* minimum growth */
                      oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                                                 /* preferred growth */);

            smarks Stuart Marks
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: