Repository: netty/netty
Issue: Optimize log2 in PoolThreadCache

Optimize log2 in PoolThreadCache

Currently io.netty.buffer.PoolThreadCache uses log2 implementation based on a shift loop.
It is not a most efficient way:
https://gist.github.com/netudima/e1e8206bf58ff0ab6e2d637a4362bfc2
```
NettyLog2Benchmark.bits           avgt   25   2.612 ± 0.009  ns/op
NettyLog2Benchmark.cycle          avgt   25  10.909 ± 0.157  ns/op
NettyLog2Benchmark.leadingZeroes  avgt   25   1.921 ± 0.006  ns/op

# JMH version: 1.21
# VM version: JDK 11.0.5, OpenJDK 64-Bit Server VM, 11.0.5+10-b520.38
# CPU: 2,6 GHz 6-Core Intel Core i7
```

It looks like for the current versions of JDK using Integer.numberOfLeadingZeros (intrinsic) is an optimal approach.

Note: PoolChunk also has log2 but it is already implemented based on Integer.numberOfLeadingZeros.

## Netty version
4.1.48, 4.0.56

### JVM version (e.g. `java -version`)
JDK 11.0.5, OpenJDK 64-Bit Server VM, 11.0.5+10-b520.38

### OS version (e.g. `uname -a`)
Darwin MBP 19.3.0 Darwin Kernel Version 19.3.0: Thu Jan  9 20:58:23 PST 2020; root:xnu-6153.81.5~1/RELEASE_X86_64 x86_64

Issue comments:
Hi! 
I agree that the approach using the instrinsic is to be preferred, but I'm curious about the impact: do we have benchmarks that measure the benefit of replacing it on `PoolThreadCache` and mimic a real case usage?
Originally I noticed the log2 method in a async profiler cpu framegraph for an application, it is reported as 3% of Context.flush method and 0.4% of total.
Prepared a test with Allocator: https://gist.github.com/netudima/7984e90458c40fde00e0b6fec6d192f8

Loop based:
```
Benchmark                              Mode  Cnt    Score   Error  Units
NettyAllocatorBenchmark.getAndRelease  avgt   15  101.912 ± 0.489  ns/op
```

numberOfLeadingZeros based:
```
Benchmark                              Mode  Cnt   Score   Error  Units
NettyAllocatorBenchmark.getAndRelease  avgt   15  99.826 ± 1.293  ns/op
```
numberOfLeadingZeros is a bit faster. 
The difference is not so large because io.netty.buffer.PoolThreadCache#cacheForNormal has 
```
normCapacity >> numShiftsNormalDirect
``` 
logic and due to this shift the input values for the log2 function are usually small (numShiftsNormalDirect by default is 13).
In case of small values the difference between the log2 options is not so large, for example if value = 2:
```
Benchmark                         Mode  Cnt  Score   Error  Units
NettyLog2Benchmark.bits           avgt   15  2.687 ± 0.010  ns/op
NettyLog2Benchmark.cycle          avgt   15  2.705 ± 0.024  ns/op
NettyLog2Benchmark.leadingZeroes  avgt   15  1.995 ± 0.023  ns/op
```
leadingZeroes is still faster and does not depend on a value, at the same time the loop is not much slower due to the small number of iterations.
I suggest to minic some real usage of it by changing https://gist.github.com/netudima/7984e90458c40fde00e0b6fec6d192f8#file-nettyallocatorbenchmark-java-L53 into:
```java

    @Param({"0", "5", "10", "100"})
    public long dutyTokens;

    @Benchmark
    public void getAndRelease(MyState state) {
        ByteBufAllocator alloc = PooledByteBufAllocator.DEFAULT;
        ByteBuf buf = alloc.directBuffer(state.value);
        final long tokens = dutyTokens;
        if (tokens > 0)
            BlackHole::consumeCPU(tokens);
        buf.release();
    }
```
Not super good, would be even better to use a `final static long DUTY_TOKENS` to be set with a sys property, but it's ok anyway. Try this with different values of dutyTokens and let me know if it makes a big difference.

Tip: beware considering `async-profiler` output for small inlineable methods as the source of truth (see http://psy-lob-saw.blogspot.com/2018/07/how-inlined-code-confusing-profiles.html) prefer reading `perfasm` output instead to be sure of what's going on (skid permitting)!
```
        final long tokens = dutyTokens;
        if (tokens > 0)
            BlackHole::consumerCPU(tokens);
        buf.release();
```

@franz1981 it actually could be simplified to:

`return buf.release();` with replacing the `state.value` to `@param`.
But anyway, micro optimization seems nice.
@doom369 yep, my point was more related to validate the improvement against some more realistic behaviour ie with some cpu activity between each alloc-release.
Looping n times summing bytes read from the buffer would have been ok too, but is more prone to cache misses depending on the arena configuration, size of caches etc etc: consumeCPU tends to be more deterministic if tokens are not too few...
Anyway, feel free to send the PR "regardless" the result of the bench (hopefully positive): it's something that makes sense to change :+1: 
Thank you for the feedback and the tip.
The results of the bench: https://gist.github.com/netudima/787176639eac62ae8e4ab8430f95e883

Loop:
```
Benchmark                              (dutyTokens)  Mode  Cnt    Score   Error  Units
NettyAllocatorBenchmark.getAndRelease             0  avgt   15  104.455 ± 1.604  ns/op
NettyAllocatorBenchmark.getAndRelease             5  avgt   15  107.287 ± 1.437  ns/op
NettyAllocatorBenchmark.getAndRelease            10  avgt   15  113.684 ± 4.852  ns/op
NettyAllocatorBenchmark.getAndRelease           100  avgt   15  258.181 ± 2.718  ns/op
```

LeadingZeroes:
```
Benchmark                              (dutyTokens)  Mode  Cnt    Score   Error  Units
NettyAllocatorBenchmark.getAndRelease             0  avgt   15   97.994 ± 0.797  ns/op
NettyAllocatorBenchmark.getAndRelease             5  avgt   15  102.724 ± 1.672  ns/op
NettyAllocatorBenchmark.getAndRelease            10  avgt   15  106.537 ± 1.813  ns/op
NettyAllocatorBenchmark.getAndRelease           100  avgt   15  255.368 ± 2.089  ns/op
```
I will send a PR soon.
PR: https://github.com/netty/netty/pull/10128

Pull request review comments:

Patch that resolved the issue:
diff --git a/buffer/src/main/java/io/netty/buffer/PoolThreadCache.java b/buffer/src/main/java/io/netty/buffer/PoolThreadCache.java
index c1bf7e6d074..92e46a0f02d 100644
--- a/buffer/src/main/java/io/netty/buffer/PoolThreadCache.java
+++ b/buffer/src/main/java/io/netty/buffer/PoolThreadCache.java
@@ -42,6 +42,7 @@
 final class PoolThreadCache {
 
     private static final InternalLogger logger = InternalLoggerFactory.getInstance(PoolThreadCache.class);
+    private static final int INTEGER_SIZE_MINUS_ONE = Integer.SIZE - 1;
 
     final PoolArena<byte[]> heapArena;
     final PoolArena<ByteBuffer> directArena;
@@ -151,13 +152,9 @@ private static <T> MemoryRegionCache<T>[] createNormalCaches(
         }
     }
 
+    // val > 0
     private static int log2(int val) {
-        int res = 0;
-        while (val > 1) {
-            val >>= 1;
-            res++;
-        }
-        return res;
+        return INTEGER_SIZE_MINUS_ONE - Integer.numberOfLeadingZeros(val);
     }
 
     /**
@@ -323,6 +320,7 @@ private MemoryRegionCache<?> cacheForSmall(PoolArena<?> area, int normCapacity)
 
     private MemoryRegionCache<?> cacheForNormal(PoolArena<?> area, int normCapacity) {
         if (area.isDirect()) {
+            // sizeClass == Normal => normCapacity >= pageSize => the shifted value > 0
             int idx = log2(normCapacity >> numShiftsNormalDirect);
             return cache(normalDirectCaches, idx);
         }


Test patch: