Strong non circular list requirement

[Jacko]

In relation to the following post, compact space list structures and
low space-modify time-run in the garbage collector require that the
tail of a list may NOT be circular. Self reference is possible as an
element of the list.

This prevents certain language constructions. The ( . ) lisp construct
and free object reference assignment via software access to the link
field. The encapsulate this solidly as under the hood link fields,
what forms of language constructs are 'a good' set for the list?

On Jul 15, 7:35 pm, George Neuner <gneun...@comcast.net> wrote:
> On Thu, 15 Jul 2010 09:09:52 -0700 (PDT), jacko <jackokr...@gmail.com>
> wrote:

> >On Jul 15, 4:48 pm, George Neuner <gneun...@comcast.net> wrote:
> >> On Thu, 15 Jul 2010 08:17:44 -0700 (PDT), jacko <jackokr...@gmail.com>
> >> wrote:
>
> >> >Is
>
> >> >http://groups.google.com/group/comp.lang.forth/browse_thread/thread/4...
>
> >> >important for solving the GC problem? Ref FIFOO
>
> >> There isn't enough detail in that conversation to figure out what
> >> problem the structure is trying to solve. What exactly are you
> >> asking?
>
> >> George
>
> >From my own prospective the mark and sweep cache flushing garbage
> >collector problem. Also related to the circular pointer counted
> >reference memory leak problem, and the common tail evaluation of
> >circular structures solution.
>
> I don't see how the "FIFOO" described in the link would help cache
> pollution in GC (any GC). Since marking and copying are both
> read-only (no modify) operations, the best solution is to fetch the
> value(s) into the L1 cache bypassing the other levels, and for copying
> or compacting GC to write it out again bypassing the other levels. I
> don't know of a workable solution for sweeping which does modify
> structures.

Marking involves a WRITE.

> Likewise, I can't see how it fixes circular linking ... all FIFOO
> seems intended to do is provide a way to find the roots of structures
> that share common sub-structure. I didn't see any provision to
> prevent circular linking. It seems to me to be a heavy-weight
> solution to the problem - in the absence of tracing or copying GC,

Tail self linking becomes 'conceptually' impossible/not supported, and
circular linking can be found by common tail => i.e. will be one of
the heads, and so will share a common tail. So an object traversal of
all heads to check not common tail ... a reduction in computation for
self referencing structures, and an easy active head count = 0 test
for complete free, which will keep you in list elements for quite a
while before any complex gc code has to be run. FIFOO does not prevent
self references, but makes it easier to computationally detect if
necessary.

Mark sweep involves marking the whole active list node set. Three
total traversals or two if a binary bool marker is used.

Allocate copy involves handles to every list node or a referer node
list for back poking, and involves full traversal of the active node
list and reallocation and copying of them.

> .. that using an object table to indirectly reference objects with
> multiple parents is a better solution ... delete/sweep of an object
> stops where it chases a pointer into the object table.

Apart from TABLE being associated with heap compaction/fragmentation
issues, could you elaborate. To me it seems like any node which has
more than one referrer, referers to it through a handle in the table.
What of just one referrer and the extra bool? How is in table
detected? How are circular references handled or avoided? (by a handle
of course, but...) How is self reference handled or avoided? If I
understand you it's about kind of a join node inserted transparently
agregated in the table with all the other join nodes, and including a
referer count and a node class indication. So that forces some kind of
count and class per node rather than per structure. So more than 2
machine words per node?

Cheers Jacko

[Jacko]

Just wondered if it was possible to place all method variables which
can be pointers into a list, and create multiple heads, this involves
2 dereferences for each variable, but eliminates any real circularity,
replacing it with self reference.

I'm doing the sums now on the spacetime overheads...

[Jacko]

And think secondary memory bank for the link chains, and possibly an L-
cache, and a cluster of sectors in the serialization format.