Detecting objects that point to an object
Locked
12
12
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 |
Re: Detecting objects that point to an object
|
|
Utilities pointersTo: object
From: [hidden email]
Sent: Thursday, July 15, 2010 8:40 AM
To: [hidden email]
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 |
Re: Detecting objects that point to an object
|
|
On Thu, Jul 15, 2010 at 2:42 PM, Rob Withers <[hidden email]> wrote:
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
|
Re: Detecting objects that point to an object
|
|
On 15 Jul 2010, at 14:45, Mariano Martinez Peck wrote: > On Thu, Jul 15, 2010 at 2:42 PM, Rob Withers <[hidden email]> 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 > > -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525 |
Re: Detecting objects that point to an object
|
|
In reply to this post by Mariano Martinez Peck
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 |
Re: Detecting objects that point to an object
|
|
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 <[hidden email]> wrote:
|
Re: Detecting objects that point to an object
|
|
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 <[hidden email]> 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 <[hidden email]> 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. |
Re: Detecting objects that point to an object
|
|
On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko <[hidden email]> wrote:
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.
|
Re: Detecting objects that point to an object
|
|
On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda <[hidden email]> 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 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
|
Re: Detecting objects that point to an object
|
|
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 <[hidden email]> wrote: > > > > On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda <[hidden email]> wrote: >> >> >> >> >> On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 |
Re: Detecting objects that point to an object
|
|
On Tue, Jul 20, 2010 at 11:02 AM, Lukas Renggli <[hidden email]> wrote:
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 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
|
Re: Detecting objects that point to an object
|
|
In reply to this post by Mariano Martinez Peck
On 20.07.2010, at 04:47, Mariano Martinez Peck wrote:
So why not simply use an ImageSegment? IIRC that's how Croquet islands are checked for closedness. - Bert - |
Re: Detecting objects that point to an object
|
|
In reply to this post by Mariano Martinez Peck
On Jul 20, 2010, at 1:48 PM, Mariano Martinez Peck wrote: > > > On Tue, Jul 20, 2010 at 11:02 AM, Lukas Renggli <[hidden email]> 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's_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 ? 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 <[hidden email]> wrote: > > > > > > > > On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda <[hidden email]> wrote: > >> > >> > >> > >> > >> On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 > |
Re: Detecting objects that point to an object
|
|
In reply to this post by Bert Freudenberg
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 <[hidden email]> wrote: >> >> >> >> On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko <[hidden email]> 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 - > > |
Re: Detecting objects that point to an object
|
|
In reply to this post by Bert Freudenberg
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 |
Re: Detecting objects that point to an object
|
|
In reply to this post by Mariano Martinez Peck
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 <[hidden email]> wrote: > > > > On Mon, Jul 19, 2010 at 7:59 PM, Eliot Miranda <[hidden email]> wrote: >> >> >> >> >> On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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. |
Re: Detecting objects that point to an object
|
|
In reply to this post by stephane ducasse-2
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 Miranda<[hidden email]> wrote: >>> >>> >>> >>> On Mon, Jul 19, 2010 at 7:35 AM, Igor Stasenko<[hidden email]> 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 - >> >> > > |
Re: Detecting objects that point to an object
|
|
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: > > 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. 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 |
Re: Detecting objects that point to an object
|
|
In reply to this post by Andreas.Raab
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 |
Re: Detecting objects that point to an object
|
|
In reply to this post by Andreas.Raab
>> > > 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 I see. our problems is that we cannot have 1 for the moment and 2 neither. :-/ But may be we will have. Stef |
«
Return to Squeak VM
|
1 view|%1 views
| Free forum by Nabble | Edit this page |