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

TreeMap: optimization of method computeRedLevel()

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Fixed
    • Icon: P3 P3
    • 9
    • 8
    • core-libs

      A DESCRIPTION OF THE REQUEST :
      This is how this method is implemented in the current jdk. The method is used to discover the level at which red nodes should start when build a Map from a sorted array.

      private static int computeRedLevel(int sz) {
              int level = 0;
              for (int m = sz - 1; m >= 0; m = m / 2 - 1)
                  level++;
              return level;
          }

      The method is computing the integer log of (sz + 1) base 2. It's running time is O(log(sz)).

      The implementation below has fixed cost. It is straight line code with NO jumps. It should be faster for all numbers except for really small sizes.



      JUSTIFICATION :
      There are much faster ways to do this. Here is an alternative implementation that should be a direct replacement (the utility functions are from hacker's delight, second edition).

      private static int computeRedDepth(final int size) {
          return ilog(size + 1);
      }

       // Hacker's delight 2nd edition
        private static final int u = 42; // This quantity is not used.
        private static final int[] nlzTab = new int[]
          {32, 31, u, 16, u, 30, 3, u, 15, u, u, u, 29, 10, 2, u,
           u, u, 12, 14, 21, u, 19, u, u, 28, u, 25, u, 9, 1, u,
           17, u, 4, u, u, u, 11, u, 13, 22, 20, u, 26, u, u, 18,
           5, u, u, 23, u, 27, u, 6, u, 24, 7, u, 8, u, 0, u};

        public static int nlz(final int y) {
          int x = y;
          x |= x >>> 1; // Propagate leftmost
          x |= x >>> 2; // 1-bit to the right.
          x |= x >>> 4;
          x |= x >>> 8;
          x |= x >>> 16;
          x *= 0x06EB14F9; // Multiplier is 7*255**3.

          return nlzTab[x >>> 26];
        }

       public static int ilog(final int y) {
          return 31 - nlz(y);
        }


      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The two functions behave identically.


      CUSTOMER SUBMITTED WORKAROUND :
      This is not a bug. Just a suggestion for a small speed up.

            martin Martin Buchholz
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: