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 ?
Thanks for any tip.
Mariano
Utilities pointersTo: object
---- http://www.noharmmeansnofoul.org
From: Mariano Martinez Peck Sent: Thursday, July 15, 2010 8:40 AM To: Squeak Development Discussion Virtual Machine Subject: [Vm-dev] Detecting objects that point to an object
--------------------------------------------------------------------------------
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 ?
Thanks for any tip.
Mariano
On Thu, Jul 15, 2010 at 2:42 PM, Rob Withers reefedjib@yahoo.com wrote:
Utilities pointersTo: object
Thanks Rob. But that implementation does a someObject and then loops with nextObject. Thus, it does a full memory scan. I want to avoid that. So the only way is storing somewhere such pointers or at least a counter I think.
Thanks agian
mariano
http://www.noharmmeansnofoul.org
*From:* Mariano Martinez Peck marianopeck@gmail.com *Sent:* Thursday, July 15, 2010 8:40 AM *To:* Squeak Development Discussion Virtual Machinevm-dev@lists.squeakfoundation.org *Subject:* [Vm-dev] Detecting objects that point to an object
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 ?
Thanks for any tip.
Mariano
On 15 Jul 2010, at 14:45, Mariano Martinez Peck wrote:
On Thu, Jul 15, 2010 at 2:42 PM, Rob Withers reefedjib@yahoo.com wrote:
Utilities pointersTo: object
Thanks Rob. But that implementation does a someObject and then loops with nextObject. Thus, it does a full memory scan. I want to avoid that. So the only way is storing somewhere such pointers or at least a counter I think.
If you need it to be accurate and available all time, you will probably need the basic mechanisms of a reference counting GC.
Best regards Stefan
Thanks agian
mariano
http://www.noharmmeansnofoul.org
From: Mariano Martinez Peck Sent: Thursday, July 15, 2010 8:40 AM To: Squeak Development Discussion Virtual Machine Subject: [Vm-dev] Detecting objects that point to an object
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 ?
Thanks for any tip.
Mariano
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
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@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
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.
On 19 July 2010 12:55, Mariano Martinez Peck marianopeck@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@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
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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.
On 19 July 2010 12:55, Mariano Martinez Peck marianopeck@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@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.
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.comwrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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.
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%27s_strongly_connected_components_algori...
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@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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.
On Tue, Jul 20, 2010 at 11:02 AM, Lukas Renggli renggli@gmail.com wrote:
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%27s_strongly_connected_components_algori...http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
Hi Lukas. Yes, I also come to this stuff of graphs. What I need seems to be to detect eakly connected components. I have checked the algorithm you said, but it seems it is only for strongly connected components. Maybe I can adapt it for weak ?
Do you know another implementation for WCC ?
Do you know an Smalltalk implementation of this Tarjan's 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?
Yes, please do. Send it and I read it because I didn't undertand too much what it is about.
Thanks a lot Lukas.
Mariano
Lukas
On 20 July 2010 10:47, Mariano Martinez Peck marianopeck@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com
wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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
On Jul 20, 2010, at 1:48 PM, Mariano Martinez Peck wrote:
On Tue, Jul 20, 2010 at 11:02 AM, Lukas Renggli renggli@gmail.com wrote:
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%27s_strongly_connected_components_algori...
Hi Lukas. Yes, I also come to this stuff of graphs. What I need seems to be to detect eakly connected components. I have checked the algorithm you said, but it seems it is only for strongly connected components. Maybe I can adapt it for weak ?
Do you know another implementation for WCC ?
Do you know an Smalltalk implementation of this Tarjan's algorithm ?
there is one in moose done by jannik but this is not what you want since your subgraph objects are not strongly connected.
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?
Yes, please do. Send it and I read it because I didn't undertand too much what it is about.
Thanks a lot Lukas.
Mariano
Lukas
On 20 July 2010 10:47, Mariano Martinez Peck marianopeck@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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
On 20.07.2010, at 04:47, Mariano Martinez Peck wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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 why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness.
- Bert -
bert
the idea was to use imagesegment but to see if we could then grow the graph to include under the root the outpointers and sawp everything at once witohut having a part of the subgraph not swapped. The problem with imagesegment (netsyle guys discovered it badly) is that if you have outpointers you may end up have to kill the curretn process and other friends to get rid of outpointers so that you can save your complete rooted graphs. For seaside for example fork an image kill everything save the graph without outpointers throw away the image.... not that friendly at the end.
Stef
On Jul 20, 2010, at 8:20 PM, Bert Freudenberg wrote:
On 20.07.2010, at 04:47, Mariano Martinez Peck wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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 why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness.
- Bert -
On 7/20/2010 1:45 PM, stephane ducasse wrote:
the idea was to use imagesegment but to see if we could then grow the graph to include under the root the outpointers and sawp everything at once witohut having a part of the subgraph not swapped. The problem with imagesegment (netsyle guys discovered it badly) is that if you have outpointers you may end up have to kill the curretn process and other friends to get rid of outpointers so that you can save your complete rooted graphs. For seaside for example fork an image kill everything save the graph without outpointers throw away the image.... not that friendly at the end.
That is exactly what Croquet does: Launch an image, instantiate an island, run some stuff, then create a snapshot of the island, send this to another image, instantiate it there. Rinse and repeat for every new participant. It works perfectly fine if and only if:
1) You can control the pointers into the object graph. This is required since otherwise you are unable to ensure that you cover the full set of objects required for the object graph (island).
2) You don't use global mutable state. Global mutable state introduces sharing violations in Croquet since I haven't found a way to implement island-relative globals efficiently (they're just too slow for everyday use).
3) You can assume identical code bases in your images. If you have different code or shape changes between your image all bets are off.
Cheers, - Andreas
Stef
On Jul 20, 2010, at 8:20 PM, Bert Freudenberg wrote:
On 20.07.2010, at 04:47, Mariano Martinez Peck wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Mirandaeliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenkosiguctua@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 why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness.
- Bert -
On 2010-07-21, at 1:08 AM, Andreas Raab wrote:
That is exactly what Croquet does: Launch an image, instantiate an island, run some stuff, then create a snapshot of the island, send this to another image, instantiate it there. Rinse and repeat for every new participant. It works perfectly fine if and only if:
You can control the pointers into the object graph. This is required since otherwise you are unable to ensure that you cover the full set of objects required for the object graph (island).
You don't use global mutable state. Global mutable state introduces sharing violations in Croquet since I haven't found a way to implement island-relative globals efficiently (they're just too slow for everyday use).
You can assume identical code bases in your images. If you have different code or shape changes between your image all bets are off.
For what it's worth, 2) and 3) are kind of soft. If you follow them strictly, things will work well. But sometimes you can cheat and get away with it.
For example, DabbleDB uses ImageSegments to deploy new versions of the app without having to compile the code in thousands of images. Each image dumps its data out as an ImageSegment, and an image with the new code reads the data in. That clearly violates 3), but with a little care about shape changes and some post-load code to tweak state here and there, it works.
Colin
That is exactly what Croquet does: Launch an image, instantiate an island, run some stuff, then create a snapshot of the island, send this to another image, instantiate it there. Rinse and repeat for every new participant. It works perfectly fine if and only if:
You can control the pointers into the object graph. This is required since otherwise you are unable to ensure that you cover the full set of objects required for the object graph (island).
You don't use global mutable state. Global mutable state introduces sharing violations in Croquet since I haven't found a way to implement island-relative globals efficiently (they're just too slow for everyday use).
You can assume identical code bases in your images. If you have different code or shape changes between your image all bets are off.
Cheers,
- Andreas
I see. our problems is that we cannot have 1 for the moment and 2 neither. :-/ But may be we will have.
Stef
On 7/20/2010 11:20 AM, Bert Freudenberg wrote:
On 20.07.2010, at 04:47, Mariano Martinez Peck wrote:
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 why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness.
No, it's the other way around. Croquet can use ImageSegments because it can prove (constructively) that it tracks all the pointers into the object graph of an island. Since Mariano hasn't said what he's trying to do other than "detecting subgraphs" it's difficult to give any advice here but if the goal is to use ImageSegments for something similar to Croquet (i.e., dumping the bits of a well-defined set of objects) then the only way I know to do that is constructively, via message passing. And I'd recommend to check out [T]FarRef in Croquet and [T]IslandArgumentCopier to get an idea of how that can work. In addition, I'd recommend having a look at [T]IslandReader and [T]IslandWriter which do the actual checkpointing and instantiation for an island using ImageSegments (there are some interesting subtleties in this code :-)
Cheers, - Andreas
Thanks for the pointer. What mariano is trying to do is to get a roboust mechanism to manage large chunk of memory. And we were thinking that also having an object which contains (opaquely: without outpointers) could also another alternative. So we will look at Island.
Stef
On Jul 20, 2010, at 11:51 PM, Andreas Raab wrote:
On 7/20/2010 11:20 AM, Bert Freudenberg wrote:
On 20.07.2010, at 04:47, Mariano Martinez Peck wrote:
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 why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness.
No, it's the other way around. Croquet can use ImageSegments because it can prove (constructively) that it tracks all the pointers into the object graph of an island. Since Mariano hasn't said what he's trying to do other than "detecting subgraphs" it's difficult to give any advice here but if the goal is to use ImageSegments for something similar to Croquet (i.e., dumping the bits of a well-defined set of objects) then the only way I know to do that is constructively, via message passing. And I'd recommend to check out [T]FarRef in Croquet and [T]IslandArgumentCopier to get an idea of how that can work. In addition, I'd recommend having a look at [T]IslandReader and [T]IslandWriter which do the actual checkpointing and instantiation for an island using ImageSegments (there are some interesting subtleties in this code :-)
Cheers,
- Andreas
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 why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness.
Bert, the idea as Stef said is to use ImageSegment, but just to write subgraphs to disk, but not to DETECT them. For ImageSegment you need to give it a graph. But what I want is to identify all these good subgraphs in the whole memory. ImageSegment does a mark and sweep in the whole image just to detect the oputPointers...imagine if I do this for every single object in the image ;)
Thanks
Mariano
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.
On 20 July 2010 11:47, Mariano Martinez Peck marianopeck@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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.
On Wed, Jul 21, 2010 at 4:26 AM, Igor Stasenko siguctua@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@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com
wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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.
you should also have a look at the island points mentioned by andreas.
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@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko siguctua@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@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@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.
vm-dev@lists.squeakfoundation.org
-
Andreas Raab -
Bert Freudenberg -
Colin Putney -
Eliot Miranda -
Igor Stasenko -
Lukas Renggli -
Mariano Martinez Peck -
Rob Withers -
Stefan Marr -
stephane ducasse