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

Ivan Gerasimov ivan.gerasimov at oracle.com
Mon Aug 13 19:09:32 UTC 2018

Okay, your last variant is the winner :)

Here's the updated webrev, benchmark and the graphs:

With kind regards, Ivan

On 8/13/18 10:10 AM, Ivan Gerasimov wrote: > Hi Martin! >> Good point about the command line flags, thanks! >> These variants are close to numberOfTrailingZeros07 that I've already > tested, though you did better by saving one arithmetic operation at > the return line! >> I'll rerun the benchmarks. >> With kind regards, >> Ivan >>> On 8/13/18 7:56 AM, Martin Buchholz wrote: >> The number of plausible variants is astonishing! >>>> --- >>>> Your use of -client and -server is outdated, which explains why you >> get the same results for both (-client is ignored). >>>> I'm not sure what's blessed by hotspot team, but for C1 I use >> -XX:+TieredCompilation -XX:TieredStopAtLevel=1 and for C2 I use >> -XX:-TieredCompilation -server >>>> --- >>>> Now I understand the advantage of using ~i & (i - 1): the subsequent >> zero check is a short-circuit for all odd numbers, better than i & >> -i, which explains your results - they depend on being able to >> short-circuit. >>>> So just use a more faithful inlining of nlz without trying to improve >> on it. >>>> static int ntzinlineNlz5(int i) { >> i = ~i & (i - 1); >> _if (i <= 0)_ >> return (i == 0) ? 0 : 32; >> int n = 1; >> if (i >= 1 << 16) { n += 16; i >>>= 16; } >> if (i >= 1 << 8) { n += 8; i >>>= 8; } >> if (i >= 1 << 4) { n += 4; i >>>= 4; } >> if (i >= 1 << 2) { n += 2; i >>>= 2; } >> return n + (i >>> 1); >> } >>>> But it's hard to resist the urge to optimize out a branch: >>>> static int ntzinlineNlz6(int i) { >> i = ~i & (i - 1); >> _if (i <= 0) return i & 32;_ >> int n = 1; >> if (i >= 1 << 16) { n += 16; i >>>= 16; } >> if (i >= 1 << 8) { n += 8; i >>>= 8; } >> if (i >= 1 << 4) { n += 4; i >>>= 4; } >> if (i >= 1 << 2) { n += 2; i >>>= 2; } >> return n + (i >>> 1); >> } >>>

With kind regards, Ivan Gerasimov