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

Optimize Integer/Long.highestOneBit()

    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:
      b07

      Description

      Currently it is implemented as
          public static int highestOneBit(int i) {
              // HD, Figure 3-1
              i |= (i >> 1);
              i |= (i >> 2);
              i |= (i >> 4);
              i |= (i >> 8);
              i |= (i >> 16);
              return i - (i >>> 1);
          }

      Alternative implementation may be
          public static int highestOneBit(int i) {
              return i == 0 ? 0 : MIN_VALUE >>> numberOfLeadingZeros(i);
          }

      Even though it contains a branch, a benchmark shows the performance improvement (+27% to the throughput):

      Benchmark (arg) Mode Cnt Score Error Units
      MyBenchmark.int_testMethod_new 0 thrpt 35 323430664.593 ± 7492044.171 ops/s
      MyBenchmark.int_testMethod_new 42 thrpt 35 298526237.078 ± 5978291.689 ops/s
      MyBenchmark.int_testMethod_new -42 thrpt 35 302903562.073 ± 7984723.721 ops/s
      MyBenchmark.int_testMethod_org 0 thrpt 35 236245042.891 ± 3635990.596 ops/s
      MyBenchmark.int_testMethod_org 42 thrpt 35 237903410.753 ± 3437684.390 ops/s
      MyBenchmark.int_testMethod_org -42 thrpt 35 238472580.618 ± 2654886.010 ops/s
      MyBenchmark.long_testMethod_new 0 thrpt 35 282646114.501 ± 48028366.305 ops/s
      MyBenchmark.long_testMethod_new 42 thrpt 35 282382228.405 ± 5781529.307 ops/s
      MyBenchmark.long_testMethod_new -42 thrpt 35 276724858.286 ± 6529561.227 ops/s
      MyBenchmark.long_testMethod_org 0 thrpt 35 198500211.972 ± 15096862.367 ops/s
      MyBenchmark.long_testMethod_org 42 thrpt 35 215854630.194 ± 3112930.563 ops/s
      MyBenchmark.long_testMethod_org -42 thrpt 35 217992805.521 ± 2622877.082 ops/s

      This may be due to the numberOfLeadingZeros() being intrinsified.

        Attachments

          Issue Links

            Activity

              People

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

                Dates

                • Created:
                  Updated:
                  Resolved: