RFR: FreeSet refactor: bitmaps, cursors, biasing

[Zhengyu Gu]

Okay.

-Zhengyu

On 09/19/2017 12:34 PM, Aleksey Shipilev wrote:
> 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
>