Re: [Caml-list] How to write a GC for size > memory

[Goswin von Brederlow <goswin-v-b@web.de>]

Richard Jones <rich@annexia.org> writes:

> On Fri, Nov 13, 2009 at 06:10:03AM +0100, Goswin von Brederlow wrote:
>> Normaly the GC would switch between defrag and freeing chunk
>> mode. Both would be concurrent to normal filesystem
>> operations. Possibly only run when the filesystem is idle. The
>> compation mode would only happen in situations where the FS would
>> otherwise have to return ENOSPC.
>> 
>> To further improve this I would like to add a generational component
>> into the GC. I have no mutables (except the roots) so an old chunk (or
>> an old B-Tree node) can hold no references to a newer chunk. Also new
>> files are far more likely to be deleted again than old files and new
>> B-Tree nodes more likely to be modified again than old B-Tree
>> nodes. Seems to screem for a generational approach. A generational
>> approach should allow the GC to only scan a fraction of the B-Tree for
>> its sweep. But I'm not quite sure how to go about that.
>> 
>> Comments, Ideas, Improvements, Urls welcome.
>
> As I said on IRC I still think ocaml-ancient is a good fit to this,
> unless you are planning to modify the OCaml GC itself.

I'm not trying to use the OCaml GC. This is totaly impossible for the
simple reason that a 32bit cpu can not mmap 8 TiB of disk space and
use that as Ocaml heap. I could use ocaml-ancient to map selected
blocks of the disk into memory but I'm already using libaio and
Bigarray for this. The ocaml GC itself can cope fine with mapped
blocks. What I need to do is grabage collect the disk blocks
itself. And, as said, even using 1 bit of memory per disk block is too
much.

> ocaml-ancient essentially converts parts of the heap to use manual
> memory allocation, on top of which you can write a more suitable GC in
> OCaml for your long-lived rarely-changing blocks (eg. one based on
> reference counting).  The invariants you describe above are exactly
> the ones which ocaml-ancient needs.
>
> Rich.

Even if that where possible that would change absolutely nothing. I
still need to write the GC. So the question of how to do that best
remains.

As a side node: I considered doing reference counting on the
blocks. Since I have no loops that would be free of leaks. But would
require verry frequent change in the reference count and that count
would have to be stored in a different location than the data
itself. For every B-Tree block written I would have to inrement the
counter for every block it points to, which can be each in a different
block on disk. So instead of writing 4k I need to write maybe 500k,
which is an unacceptable slowdown.

The reference counting described in my last mail would only be to
prioritize chunks where probably the least amount of used blocks are.

MfG
        Goswin