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.
Sure... Let me test in the lab

> Am 20.06.2014 um 11:38 schrieb Trustin Lee <notifications@github.com>:
> 
> In buffer/src/main/java/io/netty/buffer/PoolChunk.java:
> 
> >  
> >      final PoolArena<T> arena;
> >      final T memory;
> >      final boolean unpooled;
> >  
> > -    private final int[] memoryMap;
> > +    private final byte[] memoryMap;
> > +    private final byte[] depths;
> I wonder if merging these two arrays into one will increase the cache coherency. Care to test?
> 
> —
> Reply to this email directly or view it on GitHub.