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

[Lukas Renggli]

Mariano, you might want to look at Tarjan's (or any of the related)
algorithms to find weakly and strongly connected components in a
graph:

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

Alternatively you might be interested in our recent work on ranking
the importance of objects. We recently submitted a paper on ranking
source artifacts, but the same idea works well on object graphs too.
I've run it on the object-graph of a complete Pharo image and it works
reasonably well, although we haven't described that in the paper. If
you want I can send it to you in private?

Lukas

On 20 July 2010 10: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.
>>
>>
>
>
>



-- 
Lukas Renggli
www.lukas-renggli.ch