RFR 8209171 : Simplify Java implementation of Integer/Long.numberOfTrailingZeros() (original) (raw)

Martin Buchholz martinrb at google.com
Sun Aug 12 00:54:50 UTC 2018

Hi Ivan,

Oh the allure of bit-twiddling!

I'm skeptical that ntz should ever delegate to nlz, and not only because of the overhead of a wrapper, but because small numbers are more common, and we can take that into account when implementing ntz. At least add "1" to the set of numbers to benchmark. Here's my own entry in this race:

static int ntz(int i) {
    if (i == 0) return 32;
    int n = 0;
    if ((i << 16)  == 0) { n += 16; i >>>= 16; }
    if ((i & 0xFF) == 0) { n +=  8; i >>>=  8; }
    if ((i & 0xF)  == 0) { n +=  4; i >>>=  4; }
    if ((i & 0x3)  == 0) { n +=  2; i >>>=  2; }
    return n + (~i & 1);
}

Whatever happens, we ought to check in the microbenchmarks somewhere. It looks like the new jmh-jdk-microbenchmarks is the place. I also suspect that tests for these methods could be improved (but there are existing hotspot tests).

nlz seems harder than ntz in the sense that for nlz "small ints" and random bits may have different optimal implementations.

On Fri, Aug 10, 2018 at 7:03 PM, Ivan Gerasimov <ivan.gerasimov at oracle.com> wrote:

Thanks Martin!

On 8/9/18 5:42 PM, Martin Buchholz wrote:

On Thu, Aug 9, 2018 at 5:27 PM, Ivan Gerasimov <ivan.gerasimov at oracle.com> wrote: I did not use the intrinsified variants of numberOfLeadingZeros in the benchmark. Oops! Should have looked more closely! Did you know about http://www.hackersdelight.org/hdcodetxt/ntz.c.txt Ah, right, ntz1() is even better because it has less branches. How could I miss that? Here's the updated webrev and benchmarks: http://cr.openjdk.java.net/~igerasim/8209171/01/webrev/ http://cr.openjdk.java.net/~igerasim/8209171/01/bench/int/MyBenchmark.java http://cr.openjdk.java.net/~igerasim/8209171/01/bench/ long/MyBenchmark.java -- With kind regards, Ivan Gerasimov

More information about the core-libs-dev mailing list