RFR: 8234328: VectorSet::clear can cause fragmentation

[Thomas Stüfe]

Hi Claes,

I was curious how much space we actually waste this way, so I did a little
test. Very simple, counted waste due to not-in-place reallocation, and on
Arena destruction I printed it out.

For a simple java -version -Xcomp, I had ~6000 arenas reporting waste on
destruction, with a median waste of about 2K, outliers of about 250K. This
is just the final waste, I did not count how many separate reallocation
steps were involved.

So, not sure how indicative this result is. I have seen scenarios in the
past where this kind of "reallocation" gets excessive, albeit not in the
compiler.

On Thu, Nov 21, 2019 at 2:19 PM Claes Redestad <claes.redestad at oracle.com>
wrote:

> Hi Thomas,
>
> On 2019-11-19 20:31, Thomas Stüfe wrote:
> > Hi Claes,
> >
> > Not that this is wrong, but do we have to live in resource area? I fell
> > over such problems several times already, e.g. with resource-area-backed
> > StringStreams. Maybe it would be better to just forbid resizing of
> > RA-allocated arrays altogether.
>
> this all gets a bit out of scope, but what alternatives do you see to
> living in the resource area in general for something like this?
>

In general, I'd say if we rely on fine granular realloc, Arenas are not a
good option.

For VectorSet in particular, how about a two-layered sparse array instead.
This only works if you know the max number of bits you'll ever need, e.g.
the NodeLimit for the compiler.

Let the first layer be a pointer array of size N to uint32 blocks of size
M, which are to be allocated on demand. If M and N are powers of 2 access
can be simple.

Something like this:

class VectorSet {
  struct bitblock_t { uint32_t bits[M]; }
  bitblock_t* _blocks[N];

  void set_bit(int i) {
     int block_idx = i >> log2(M)
     if (_blocks[block_idx] == NULL) allocate-block
     _blocks[block_idx]->bits[i % M] = 1;
   }

   bool is_set(int i) {
     int block_idx = i >> log2(M)
     return (_blocks[block_idx] != NULL && _blocks[block_idx]->bits[i % M]
== 1);
   }
};

Advantages would be that the blocks would not need reallocating; no copying
data around; you use less memory if the memory is sparse and not all
bitblocks are populated, which also makes VectorSet::size() faster since
you can omit counting NULL blocks; you might have better locality too since
once a block is allocated it never changes position in memory..

Disadvantages would be a bit more memory overhead for the top pointer array
and, on access, one indirection more to resolve.

One could make this more involved for initially-smaller-sets, e.g. first
allocate just a bitblock_t and use this as a small fixed sized VectorSet;
then, should we outgrow it, change to a two-layered VectorSet with the
initial bitblock_t as first block.

I hope this makes any sense :)


>
> >
> > Then there is also the problem with passing RA-allocated arrays down the
> > stack and accidentally resizing them under a different ResourceMark. I
> > am not sure if this could happen with VectorSet though.
>
> AFAICT there's a ResourceMark at the entry point of compilation,
> then all others are restricted to a local scope around logging and
> similar, so it doesn't _look_ like there's any potential issues around.
>
> I guess it'd be nice in general with some sort of debug-only
> ProhibitResourceMark(Arena*) you could wrap around calls into utilities
> out of your control which would assert if any code tries to
> allocate/reallocate/free in a specific resource arena.
>
>
That would be good to have, yes.


> Thanks /Claes
>

Cheers, Thomas


>
> >
> > Thanks, Thomas
> >
> > On Tue, Nov 19, 2019 at 11:16 AM Claes Redestad
> > <claes.redestad at oracle.com <mailto:claes.redestad at oracle.com>> wrote:
> >     Webrev: http://cr.openjdk.java.net/~redestad/8234328/open.00/
>