RFR: FreeSet refactor: bitmaps, cursors, biasing

[Aleksey Shipilev]

On 09/19/2017 04:24 PM, Aleksey Shipilev wrote:
> http://cr.openjdk.java.net/~shade/shenandoah/freeset-bitmaps/webrev.01/
> 
> This is actually 3-in-1 patch, because there is a fair amount of cohesion between all of them. Brief
> tour of changes:
> 
>  *) Allocation code moved from ShenandoahHeap to ShenandoahFreeSet. This will soon become the
> ShenandoahHeapRegionManager, if you see where it goes. The API is cleaned up a bit, and privately
> used methods are now really private.
> 
>  *) FreeSet now maintains the bitmap instead of collection of regions. This allows maintaining the
> sorted view of free regions, which is important when asynchronous recycling works. Async recycling
> may add regions in random order, and humongous allocation would be unhappy about that. The bitmap
> also allows resuming the allocation at the "earlier" region once it is added, making footprint story
> easier.
> 
>  *) FreeSet maintains two boundary cursors, "leftmost" and "rightmost", that bound the bitmap. This
> serves as the optimization for allocation path, because it can look up either boundary and see the
> free region there. We could, in principle, use the optimized bitmap scans in future to make the
> allocation in ragged heap even faster.
> 
>  *) Two boundary cursors also allow _biasing_ the allocations to either end. Biasing application
> allocations help to optimize allocation path even further, because we clean up the beginning of heap
> most of the time.

Turns out, I blew the allocation performance a bit by assuming we can leave the non-full region
alone in case we might have the allocation that fit later. This gives an interesting side effect for
update-counter code that assumes that allocation further from the boundary is the allocation in "new
region", and forces the counter update. This does make allocation slower for non-TLAB cases by order
of magnitude, but affects TLAB case as well.

Fixed, and retested, and added asserts, and added TODO:
  http://cr.openjdk.java.net/~shade/shenandoah/freeset-bitmaps/webrev.02/

Thanks,
-Aleksey