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

Faster rounding up to nearest power of two

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Resolved
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 11
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b15

      Backports

        Description

        In java.util.HashMap the table size is calculated to be rounded up to a power of two:

            static final int tableSizeFor(int cap) {
                int n = cap - 1;
                n |= n >>> 1;
                n |= n >>> 2;
                n |= n >>> 4;
                n |= n >>> 8;
                n |= n >>> 16;
                return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
            }


        It could be done faster with use of Integer.numberOfLeadingZeros():

            static final int tableSizeFor(int cap) {
                int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
                return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
            }

        The same trick can be used in TimSort and ComparableTimSort.

          Attachments

            Issue Links

              Activity

                People

                Assignee:
                igerasim Ivan Gerasimov
                Reporter:
                igerasim Ivan Gerasimov
                Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                  Dates

                  Created:
                  Updated:
                  Resolved: