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

[Martin Buchholz]

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