[Vm-dev] Detecting objects that point to an object

Mariano Martinez Peck marianopeck at gmail.com
Thu Jul 22 09:42:19 UTC 2010


On Wed, Jul 21, 2010 at 4:26 AM, Igor Stasenko <siguctua at gmail.com> wrote:

>
> Mariano, maybe a year ago, i implemented two primitives (in HydraVM,
> however),
> which could help to detect if some object(s) are pointing to given one.
>
> If you interested, take a look
> http://forum.world.st/squeak-dev-ANN-Hydra-now-can-do-mitosis-td80087.html
>
> The primitives not using anything special, so they can be ported to
> ordinary VM or Cog  VM.
>
>
Hi Igor. This seems intersting. I would like to look at them. I read the
thread but I am not sure where I can download such code.
Neither which are the primitives I should look at. which number/name ?

Thanks

Mariano



> On 20 July 2010 11:47, Mariano Martinez Peck <marianopeck at gmail.com>
> wrote:
> >
> >
> >
> > On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda <eliot.miranda at gmail.com>
> wrote:
> >>
> >>
> >>
> >>
> >> On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko <siguctua at gmail.com>
> wrote:
> >>>
> >>> Mariano, can you tell us, why you need to know, how many objects
> pointing to
> >>> a specific one?
> >>> The reference counting is well known solution to this, but it is less
> >>> effective than garbage collection
> >>> (in terms of memory management), since you have to touch the counters
> >>> at each memory write.
> >>
> >> and recursively when objects are freed.
> >> Further, for two reasons one will also need a scan-mark garbage
> collector to collect all garbage.  It is inevitable that one won't waste
> space on a reference count that can hold the max number of references and so
> the system will have to deal with a max count and have some objects with an
> overflowed count.  Reference counting cannot easily deal with circularities
> and so a cycle of references will result in non-zero ref counts for nodes in
> the cycle and prevent garbage collection.
> >>
> >
> > Thanks for the answers. Maybe I should have explained why I needed that.
> What I had in mind, is to be able to detect subgraphs. But not any kind of
> subgraphs, but only those on which ALL objects are ONLY reachable from the
> root of the subgraph. This means, that there are no objects outside the
> graph, pointing to objects inside the graph. In ImageSegment word, would
> mean to detect subgraphs that don't have outPointers.
> >
> > So I was thinking a way to detect them. It is impossible to scan all
> memory for every "possible" subgraph. I thought that only maintaining a
> counter could be enough: if the counter is 1, then it is perfect. If it is
> more than 1, it can be perfect but only if all the pointers are from inside
> the graph. To do this, I need to scan the subgraphs again and count
> objects...
> >
> > So my "solution" sucks. But that's why I got the asking myself if I could
> maintain a counter. Not to replace the actual GC.
> >
> > Thanks
> >
> > Mariano
> >
> >
> >>
> >>
> >>>
> >>> On 19 July 2010 12:55, Mariano Martinez Peck <marianopeck at gmail.com>
> wrote:
> >>> >
> >>> > Ok...thanks for the answers...I think I will have to go in another
> way. But anyway, thanks
> >>> >
> >>> > mariano
> >>> >
> >>> > On Thu, Jul 15, 2010 at 6:43 PM, Andreas Raab <andreas.raab at gmx.de>
> wrote:
> >>> >>
> >>> >> On 7/15/2010 5:40 AM, Mariano Martinez Peck wrote:
> >>> >>>
> >>> >>> Hi folks. I need to know the objects (actually, only how many) that
> are
> >>> >>> pointing to any object. So...I take an object X, and I want to know
> how
> >>> >>> many objects are pointing to X.
> >>> >>>
> >>> >>> The only possible I see in Squeak VM is to do a full mark over all
> >>> >>> objects in memory (or starting by the roots). This is time
> consuming and
> >>> >>> I even need (maybe) to do this check (to know how many objects are
> >>> >>> pointing to an object) for every single object.
> >>> >>>
> >>> >>> So...is there a faster solution for this? The only thing I can
> imagine
> >>> >>> is to modify the object header, maybe create a new type, and add an
> >>> >>> array with the addresses of the objects that are pointing to that
> >>> >>> object. Or maybe just a counter that I can increase or decrease ?
> >>> >>
> >>> >> That's called "reference counting". It's not supported in Squeak.
> >>> >>
> >>> >> Cheers,
> >>> >>  - Andreas
> >>> >
> >>> >
> >>> >
> >>>
> >>>
> >>>
> >>> --
> >>> Best regards,
> >>> Igor Stasenko AKA sig.
> >>
> >>
> >
> >
> >
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20100722/3429b207/attachment-0001.htm


More information about the Vm-dev mailing list