GC Precision

[Leandro Lucarella]

dsimcha, el 27 de octubre a las 01:34 me escribiste:
> > > 2.  Some concern has been expressed in the past about the possibility of using 4
> > > bytes per block in overhead to store pointers to bitmasks.  IMHO this concern is
> > > misplaced because in any program that takes up enough memory for space efficiency
> > > to matter, false pointers waste more space.  Furthermore, if you're programming
> > > for a toaster oven, elevator controller, etc., you probably aren't going to use
> > > the standard out-of-the-box GC anyhow.
> > This seems reasonable, but I don't see why we can't use a more efficient
> > way to store this information in the GC. Implementation simplicity (to
> > have a better GC now instead of a perfect GC in some point in a far
> > future) is a good enough reason :) I'm just curious if you found any flaws
> > in the scheme proposed by Frits or is just you want a simpler
> > implementation.
> 
> Two things:  Implementation simplicity is one.  As I've been alluding to, worse
> and works in practice is better than better and only exists on paper.  The other

Fair enough.

> is that I don't understand, in Frits's approach, how do you store the size of the
> object so you know how many bits to interpret as the mask?

I guess you don't. You have a bin size, so you use the bin size. I guess
you just mark unused words as being non-pointers, so they wont get
scanned.

... I guess that doesn't work for arrays though. I remember some
discussion about how to handle arrays, but I can't find it now...

> > > 3.  The bitmask pointer would be stored at the end of every GC-allocated block for
> > > which a bitmask pointer is stored.  The reason for using the end of the block
> > > instead of the beginning is just implementation simplicity:  That way, finding the
> > > beginning of a block would work the same whether or not we have a bitmask pointer.
> > Did you even consider storing this information outside the memory block
> > (like the flags)? I think storing them in the memory block can be annoying
> > if they are not stored always because now your fixed sized blocks are not
> > fixed. It might be very easy to overcome this, but maybe thinking about
> > the other option is worthy.
> 
> The flags in the GC are designed to store single bits apparently.  Also, as far as
> weak refs, we could use another high-order bit for that.  I don't think anyone
> cares if (on 32-bit) T.sizeof is limited to about a gigabyte.

I think at first sight it sounds reasonable, but I'm a little affraid of
it; it can sound like "640K ought to be enough for anybody" ;)

I know it almost impossible to have a T.sizeof larger than 1GiB, but what
if you hit that? I guess since you won't be creating more than one or two
objects of that size (3 at most), I guess is pretty reasonable to say
"manage that memory yourself".

> The question is, how many high-order bits do we reserve?  BTW, I'm not
> going to actually implement weak references unless I see an easy way to
> do it, we're only talking about reserving bits here.

I wasn't talking about bitmaps, I was talking more generally. Even if you
want to store a pointer to the array describing the offsets of the
pointers, you could store that pointers in a separated memory block (not
in the block reserved for the object itself).

Again, I didn't thought about it, it was just something that popped in my
mind. I guess is a little irrelevant just now, it's something that should
be moderately easy to change in the future if it's proven to be better to
store it elsewhere.

> I guess the bottom line is that IMHO precise heap scanning is really low-hanging
> fruit where the bang for the buck would be huge.  Improving the GC in other ways
> raises some nasty issues, but in this case I really think the perfect is the enemy
> of the good.  I'm not guaranteeing anything, but I think I might be able to have
> precise heap scanning up and running in a release or two if I really keep it
> simple and stupid.


Agreed. I would like to know very much how things goes.

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
Just because you're paranoid, don't mean they're not after you.