netty/netty — pull request #2582 by normanmaurer (2014-06-20 06:38:10+00:00)
Title: Optimize PoolChunk to not use DFS

I received this from @pavanka who did some optimizations for the algorithm used in PoolChunk to allow faster allocations of buffers > pageSizes. The improvement is only notable if no cache is used (they can not use the cache as they allocate from a lot of different threads).

Here are the details of the algorithm (written down by @pavanka ):
```
Algorithm for poolchunk allocation

allocateRun
We store the complete balanced binary tree in an array (just like heaps)

this is how the tree looks like, with the size of each node being mentioned
depth=0 chunkSize (1 node)
depth=1 chunkSize/2 (2 nodes)
depth=h chunkSize/2^h (2^h nodes)

if we want to allocate a bytebuf of size chunkSize/2^k all we have to do is find the first
node (from left) at height k that is unused

This is how we do it:
1) When we construct the memoryMap array in the beginning we store the depth of a node in each node
memoryMap[id] = x
=> in the subtree rooted at id, the smallest depth which has a unused node

In the beginning, x = depth for that id because we can potentially allocate all of it
As we allocate & free nodes, we update these numbers so that the property is maintained

if memoryMap[id] = depth => it is unallocated
memoryMap[id] > depth => it is a branch page [at least one of its child nodes is allocated]
memoryMap[id] = maxOrder + 1 => the node is fully allocated & none of its children can be allocated

allocateRun(h) => we want to find the first node (from left) at height h that can be allocated
Algorithm:
1) start at root
if value > h => cannot be allocated from this chunk
2) if left node value <= h; we can allocate from left subtree so move to left and repeat until found
else try in right subtree

For allocateSubpage
All subpages allocated are stored in a map at key = elemSize
Algorithm:
1) if subpage at elemSize != null: try allocating from it.
If it fails: allocateSubpageSimple
2) else : just allocateSubpageSimple

allocateSubpageSimple
1) use allocateRun(maxOrder) to find an empty (i.e., unused) leaf (i.e., page)
use this handle to construct the poolsubpage object or if it already exists just initialize it
with required normCapacity
```

And here is the microbenchmark:

master:
```
# Run complete. Total time: 00:29:58

Benchmark (size) Mode Samples Score Score error Units
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 00000 thrpt 20 9824.753 440.050 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 00256 thrpt 20 10917.065 129.038 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 01024 thrpt 20 10549.387 93.710 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 04096 thrpt 20 10336.658 54.765 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 16384 thrpt 20 11049.749 320.725 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 65536 thrpt 20 10475.519 351.349 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 00000 thrpt 20 10432.484 399.464 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 00256 thrpt 20 10229.098 76.816 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 01024 thrpt 20 10429.187 268.470 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 04096 thrpt 20 9840.171 272.099 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 16384 thrpt 20 10951.141 277.530 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 65536 thrpt 20 11091.859 58.675 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 00000 thrpt 20 6857.392 397.553 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 00256 thrpt 20 6326.836 79.369 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 01024 thrpt 20 5793.289 98.991 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 04096 thrpt 20 5980.313 129.175 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 16384 thrpt 20 455.153 11.252 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 65536 thrpt 20 962.117 4.532 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 00000 thrpt 20 7835.567 99.523 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 00256 thrpt 20 6678.297 31.975 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 01024 thrpt 20 6208.095 89.338 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 04096 thrpt 20 6172.657 123.379 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 16384 thrpt 20 459.972 4.810 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 65536 thrpt 20 963.570 6.324 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 00000 thrpt 20 1159.940 23.065 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 00256 thrpt 20 1001.759 18.950 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 01024 thrpt 20 833.887 15.259 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 04096 thrpt 20 436.775 18.341 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 16384 thrpt 20 172.028 2.330 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 65536 thrpt 20 55.251 0.425 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 00000 thrpt 20 12269.097 107.365 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 00256 thrpt 20 6861.052 312.324 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 01024 thrpt 20 2830.463 16.016 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 04096 thrpt 20 788.576 3.252 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 16384 thrpt 20 139.584 2.537 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 65536 thrpt 20 19.342 0.076 ops/ms
[GC 132638K->3521K(492544K), 0.0078330 secs]
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 1,799.177 sec - in io.netty.microbench.buffer.ByteBufAllocatorBenchmark

Results :

Tests run: 1, Failures: 0, Errors: 0, Skipped: 0
```

With this PR:
```
# Run complete. Total time: 00:29:56

Benchmark (size) Mode Samples Score Score error Units
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 00000 thrpt 20 10558.393 128.586 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 00256 thrpt 20 10651.489 240.927 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 01024 thrpt 20 10786.637 73.084 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 04096 thrpt 20 10037.158 273.448 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 16384 thrpt 20 9986.690 387.501 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledDirectAllocAndFree 65536 thrpt 20 10067.789 303.871 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 00000 thrpt 20 10710.797 164.222 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 00256 thrpt 20 10376.529 376.920 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 01024 thrpt 20 10676.458 105.060 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 04096 thrpt 20 9541.564 267.631 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 16384 thrpt 20 9169.813 512.857 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.defaultPooledHeapAllocAndFree 65536 thrpt 20 10046.750 391.020 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 00000 thrpt 20 7537.410 91.468 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 00256 thrpt 20 6526.318 111.116 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 01024 thrpt 20 6171.069 59.633 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 04096 thrpt 20 6061.991 161.058 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 16384 thrpt 20 2930.053 39.659 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledDirectAllocAndFree 65536 thrpt 20 2996.079 31.436 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 00000 thrpt 20 8094.280 37.894 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 00256 thrpt 20 6538.747 142.815 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 01024 thrpt 20 6352.766 67.644 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 04096 thrpt 20 6231.485 43.748 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 16384 thrpt 20 2878.940 25.432 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.pooledHeapAllocAndFree 65536 thrpt 20 3001.949 18.698 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 00000 thrpt 20 1133.578 30.007 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 00256 thrpt 20 1050.525 30.449 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 01024 thrpt 20 837.913 11.251 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 04096 thrpt 20 441.674 8.114 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 16384 thrpt 20 172.224 2.197 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledDirectAllocAndFree 65536 thrpt 20 55.325 0.442 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 00000 thrpt 20 11218.176 203.149 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 00256 thrpt 20 6561.209 325.634 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 01024 thrpt 20 2495.711 30.599 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 04096 thrpt 20 725.909 8.473 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 16384 thrpt 20 129.173 2.655 ops/ms
i.n.m.b.ByteBufAllocatorBenchmark.unpooledHeapAllocAndFree 65536 thrpt 20 18.793 0.484 ops/ms
[GC 132622K->3473K(492544K), 0.0070480 secs]
Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 1,796.792 sec - in io.netty.microbench.buffer.ByteBufAllocatorBenchmark
```

As you see the performance for allocations > pageSize are a lot faster.