Re: [boost] another approach to memory management that solves thereferential cycles problem

Subject: Re: [boost] another approach to memory management that solves thereferential cycles problem
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-02-25 17:18:09

> > I also have the impression that the provided "prototype"
> > implementation can sometimes detect a cycle and conclude from this
> > cycle that an object is collectable, even if the cycle still has a
> > path to a root reference. But again, I might be wrong, or it might
> > simply be a bug in the "prototype" implementation that can easily be
> > fixed.
>
> Can you be a little more specific? the provided example has many circles
> in it, yet all objects are collected.
>
> The function 'collectable()' stops and returns false only if there is a
> path to a root ptr. If there is a cycle, the function returns true, and
> therefore the algorithm continues until all paths are exhausted.

OK, now I see it. The object that returns true when a cycle is detected will still visit all its parents (and return false if it finds a path to a root cell), because it is already in the loop over its parents somewhere up in the call chain.

As I said "I might be wrong"...

> > I have a bit the impression that releasing the reference to an object
> > deep down in the object graph might take O(N) operations, at least
> > for the provided "prototype" implementation. I might be wrong, or it
> > might simply be a bug in the "prototype" implementation that can
> > easily be fixed.
>
> You are correct. That is the reason why a proposed solution is 'lazy'
> disposal: the object is placed in a container and checked later for
> disposal. When checked like this, an object can be marked as reachable
> or unreachable(i.e. the result of the scanning can be cached),
> minimizing even further the number of operations required.

I guess that some sort of laziness is required to arrive at an acceptable amortized worst case bound for the runtime of the pointer/reference operations. So the question for me would be: "Is it possible to achieve an acceptable amortized worst case bound for runtime complexity of the pointer/reference operations". I have no problem if this costs additional memory and involves modification of this memory even for "read only" operations.

The "checked later for disposal" that is proposed above doesn't look "automatic enough" to me, but I haven't yet tried to understand what exactly you are proposing as 'lazy' disposal.

> > Can you be more explicit about the "known" problems of your approach?
>
> Besides the obvious problem of scaling mentioned above,

I would interpret this statement in the way that you think that it will be difficult to solve the scaling problem.