This is the README for RetainSimulator.sense.tar.gz [Download] [Browse] [Up]
RetainSimulator.sense Wed May 22 11:22:57 MDT 1996 This HyperSense document provides a simulation demonstrating an algorithm for releasing objects which contain cyclical or other complex references between them. Its creation was inspired by an article posted to the eof mail group (eof@omnigroup.com) titled "Leaky EOs". To the archive administrator: The file RetainSimulator.sense.compressed may be moved to the HyperSense directory. You may also want to place a copy in an area devoted to programming issues, such as sources/programming. Douglas Simons Thoughtful Software doug@thoughtful.com - - - - - - - - - - - - - - - - - - - - - Paul Summermatter's post on the problem of how to reliably release objects when there are cyclical references among them got me thinking about a possible solution which was hinted at in that post. I discussed my idea with Nathan Schroeder here at Thoughtful Software, and together we designed a HyperSense document which implemented a simulation of objects and allowed us to test the algorithm. Other people have probably invented similar schemes, but since we created the simulator, we thought we'd share it (and our approach) with everyone, so you can play with it and get an actual look at how it all works. OVERVIEW The basic approach involves two additional methods, retainFor: and releaseFor: which allow an object to maintain a list of objects which have retained it. We called this the refList. By keeping such a list, when an object is released, it can consult with the known objects which have retained it to see if any of them are being retained by any objects "outside the group". If not, then the object can safely be freed. By implementing the approach in an interpreted mock-up environment we were able to quickly test a variety of simple and more complex inter-relationships among objects. Some of them proved to have tricky interactions which uncovered weak points in the basic approach. As difficult cases were discovered, we refined the algorithm to handle them, and have arrived at what I believe is a robust and general-purpose solution to the problem. PLEASE TRY IT! We have posted the simulator to the archives and invite everyone to play around with it, using cases you are familiar with, to see if there are any other tricky situations we may have overlooked (details on obtaining and using the simulator follow this article). We've tested it with simple binary cycles (two objects retaining each other) and more complex scenarios involving up to 5 objects with various combinations of interconnections. If nothing else, the simulator is fun to watch! :-) Now, some more details, for those who are interested... PROS AND CONS One immediately obvious drawback to this approach is that it requires additional overhead, both in memory (the refList of objects in each participating object) and in cpu time (for messaging related objects when an object is released). In actual practice, I believe both of these will prove to be minimal, except in situations where there is a great deal of interdependency between objects. Another consideration is the necessity for the programmer to choose when to use retainFor: and releaseFor: rather than retain and release. There is a fairly simple answer, though: if your objects are being "leaked" because of cyclic references, then they should use these new methods which deal with that problem! The good news is that the standard retain and release methods can still be used on any of these objects. It's perfectly reasonable for objectA to be retained by objectB using retainFor: and by objectX using the standard retain method. In fact, it's a good idea, as long as there's no chance that objectA (or its friends) know anything about objectX. The really big plus, of course, is that this approach solves the problem of cyclic references in a fairly general way, and is not too difficult to implement. HOW IT WORKS When an object is released, it decrements its refCount and then checks whether the refCount is greater than the number of objects in its refList. If so, that means there are still "outside" references to the object (from unknown retainers) so we simply return. If the refCount goes to zero, there are no references to the object and it may be freed. On the other hand, if the refCount is equal to the number of objects in the refList, that means that we know all of the objects which are retaining us. So we send each of them an isRetainedByOutsiderFor: message to see if any of them are retained by "outsider" objects (those which are not part of our interdependency graph). The implementation of that method checks the receiving object's refCount against the number of objects in its refList, and then in turn calls isRetainedByOutsider: for those objects. In this way, all related objects are checked to see whether they are retained by any object which is outside the group. If none of the objects which are retaining an object are themselves being retained by any unknown "outsider" objects, and all of their known retainers are in the same situation, then it is safe to free the original object, and to release any objects which it retains. Rather than freeing the object directly, it is added to a special pool of objects which will be freed upon return to the main run loop. This is necessary because there are situations in which other objects will send messages to the object after it has determined that it will free itself, as part of the joint release process. So it can't actually be freed until later. Infinite recursion is a problem which had to be dealt with in a couple of situations. In the case of the isRetainedByOutsiderFor: message, we chose to pass a list of objects as an argument, adding each sender to the list as it was forwarded. This list is consulted before forwarding the isRetainedByOutsiderFor: message to other objects. In this way, no object is ever asked to respond to the same request twice. In some other cases, we set a flag in the object indicating that it is already checking whether it can be freed, or will be freed, or is being freed. In the simulator, this is represented by a notation on the refCount line. In a real implementation, a single recursion-prevention flag would suffice for all three cases. UNFINISHED BUSINESS It should be noted that, so far, we have implemented this algorithm only in the HyperSense simulator, not in actual Objective C code. One consequence is that we've totally ignored any implementation for an autoreleaseFor: method, although one will most likely be needed in the real world. A potentially more serious concern will be relevant if the application can in any situation ever re-access an object after it has been released, but before it is freed from the freePool. If this is possible in your application, you should take a very hard look at the implications. It may be possible to add code to the retain method to deal with this situation, but I haven't explored it. Also, I'm not an EOF expert, so there may be other ramifications besides the one mentioned above having to do with the way EOF caches and fetches objects. OBTAINING AND USING THE SIMULATOR The simulator has been posted to the archives at next-ftp.peak.org, in the submissions directory: ftp://next-ftp.peak.org/pub/next/submissions/RetainSimulator.sense.compressed It should migrate to the HyperSense directory and possibly other locations. To use the simulator, you will need a copy of either HyperSense.app or HyperSensePlayer.app. Both of these are available in the HyperSense directory at peak. In order to be able to examine (and experiment with changes to) the SenseTalk scripts which implement the algorithm, you should use the full developer version of HyperSense rather than the Player. Running HyperSense in demo mode will give you full access to the scripts and let you modify them if you like, although changes will not be saved to disk. HyperSensePlayer (including FREE single-user license and sample documents): ftp://next-ftp.peak.org/pub/next/HyperSense/HyperSenseREADME1.00B14a.rtfd.compressed ftp://next-ftp.peak.org/pub/next/HyperSense/HyperSensePlayer.pkg.1.00B14a.NIHS.b.tar HyperSense (full development version and documentation): ftp://next-ftp.peak.org/pub/next/HyperSense/HyperSenseApp.pkg.1.00B14a.NIHS.b.tar ftp://next-ftp.peak.org/pub/next/HyperSense/HyperSenseDocs.pkg.1.00B14a.tar After everything is installed on your disk, launch HyperSense and then open the RetainSimulator document. Click the button labelled "?" for some instructions on using the simulator. You can easily change the inter-dependency relationships between the simulated objects (in either HyperSense or the Player) and play around with referencing and releasing objects in any order. Most of the handlers which implement the functionality are contained in the page script. To edit this script, in HyperSense (not the Player), open the Message Box (from the Tools menu), and type "edit the script of this page". Have fun! We'd be happy to hear any questions or comments (you can reach us at support@thoughtful.com). Using HyperSense to simulate the objects and behavior proved to be a tremendous help in discovering and correcting problems with the algorithm. I highly recommend it as a rapid prototyping tool!!! (note: this should be considered a shameless plug, since I am the chief designer of HyperSense, and I'm not ashamed of it. Nevertheless, everything I said about HyperSense's utility is absolutely true! :-) I hope this is helpful to some of you. Best Regards, Doug Simons Thoughtful Software doug@thoughtful.com
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.