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

[Ian Grant <ian.a.n.grant@googlemail.com>]

[-- Attachment #1: Type: text/plain, Size: 3374 bytes --]

On Sat, Sep 13, 2014 at 7:13 AM, Stefan Israelsson Tampe <
stefan.itampe@gmail.com> 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

[-- Attachment #2: Type: text/html, Size: 4029 bytes --]