Re: implementation idea for infinite cons lists aka scon(e)s lists.

[Ian Grant]

On Sat, Sep 13, 2014 at 7:13 AM, Stefan Israelsson Tampe <address@hidden> wrote:

it is saved from gc by havinga special reference and that we also can see if the cons cell have been referenced outside of the 

special references. Then in the sweep phase one can decide to modify the cons list to set the cdr to null in say 1000 cons from the

head. But this modding is only done if there is now referncing of it outside the special references. This means that the rest of the tail

will gc normally and be reclaimed. If however a function wants to analyze a part of the list it just references the head and by that the gc

will not mod any part of the rest of the list and the algorithm can safely do it's work. It's in the gc's sweep phase that the list is cut with a setcdr!

I think I am beginning to get the picture. This sounds a little like something I started trying to do with the CAML gc. I called it "recycling garbage" or "resurrection" because the idea is to have a process whereby one can reclaim "weak" references which were not really dead. The theological difficulties with this idea might be considerable, but I thought this would be good thing to do because some structures are expensive to allocate: double-precision floats and GMP mpzs, for example. And in evaluating arithmetic expressions the  CAML runtime repeatedly throws intermediate values away, and immediately does a far malloc call to allocate another. I thought if we could keep an array of weak references and recycle some or all of them between the mark and sweep phases, then these could make a 'pool' of pre-allocated objects that could reclaimed just by pointing at them.

Does this fit with your idea? Could we combine these as two reasons to do this change?

I implemented it, but you may not be too interested in the horrible details of the ancient CAML gc.  https://github.com/IanANGrant/red-october/commit/1e76f6746eab2f0afa7dbbcd78d3013029e8187b

On a related theme, I have a suggestion for Guile's memory allocation strategy, which is to document a method of preallocating a page-sized block of cons cells, for example, Then when one has a fragment of machine code that is constructing s-exp representations of something or other, that code can do its own memory management just by switching pointers. I think this is a sort of simple-minded slab allocator maybe? I had a brief look at the way the BDW collector does things, and it seemed to me that this could be done right now, just by directly calling GC_MALLOC from the machine code, and SCM references which were pointers to the inside of the GC_ALLOCed block would be enough to keep it from being swept up.  And it looks as if whatever memory was optimistically allocated this way, and unused at the end of the construction process, could be freed. Provided it was a contiguous region, which it usually will be, the BDW collector would split the block, and free the unused part.

So I don't think there's anything we would need to do to actually implement this. The only thing is that if it is not enshrined in the Guile API spec, then it is vulnerable to being 'patched out' without warning one day. So maybe it only needs a comment in the code somewhere, and a paragraph in the manual.

Since you've also  spent some time down there in the garbage chute, maybe you can confirm/deny this?

Ian