yost@DPW.COM (David A. Yost) (11/27/90)
Garbage collection reclaims memory that is no longer referenced. How about an additional general mechanism which reclaims memory that is still referenced, but is dispensable? (This might be called Stash Collection.) The idea is that when GC can't make enough room to satisfy a request, it invokes SC, which looks around for objects that will volunteer to give up some memory they don't really need, such as cached data or multiple reperesentations of the same data. Has anyone developed such a mechanism? --dave yost yost@dpw.com or uunet!esquire!yost Please don't use other mangled forms you may see in the From, Reply-To, or CC fields above.
barmar@think.com (Barry Margolin) (11/27/90)
In article <2849@esquire.dpw.com> yost@DPW.COM (David A. Yost) writes: >The idea is that when GC can't make enough room to satisfy >a request, it invokes SC, which looks around for objects >that will volunteer to give up some memory they don't really >need, such as cached data or multiple reperesentations of >the same data. Symbolics Lisp Machines provide "before-GC initializations", an extensible list of functions to be called before GC, presumably to allow applications to clear or consolidate their data structures. There is also a second set of "GC Cleanups", which the user may invoke manually and selectively prior to GC, and which applications may extend. The before-GC initializations are generally used for internal data structures; some applications clear caches, while others reorganize to improve paging and/or to cdr-code lists. GC Cleanups are generally used for user-visible data, which is why it must be invoked manually; for instance, window histories can be cleared (this can be quite significant, because windows remember the objects that were printed to them, not just the text), and top-level variables such as *, **, and *** can be cleared. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
Bruce.Hoult@bbs.actrix.gen.nz (11/27/90)
In article <2849@esquire.dpw.com> yost@DPW.COM (David A. Yost) writes: > The idea is that when GC can't make enough room to satisfy > a request, it invokes SC, which looks around for objects > that will volunteer to give up some memory they don't really > need, such as cached data or multiple reperesentations of > the same data. > > Has anyone developed such a mechanism? The memory manager in the Macintosh does this. The user can mark heap blocks as "purgeable", in which case they might not be there the next time you look at them. This means you have to test them and recreate if necessary each time you reference them.
yost@DPW.COM (David A. Yost) (11/28/90)
Peter Deutsch asked me to post this for him. The Agoric Systems folks address this problem by adopting an economic model in which objects pay rent, can be evicted, etc., and can negotiate with their landlords. I think their approach is either revolutionary or crazy (or both), and I find the 'libertarian' political philosophy on which they base their analysis incompatible with my personal sense of morality, but they are the only ones I know who are addressing this problem at a fundamental level. For more information, you might send mail to markm@xanadu.com. They haven't implemented much of this yet. For a less fundamental but commercially available approach, you might want to look at Objectworks\Smalltalk, release 4, from ParcPlace Systems. It includes some unique facilities for allowing user-written code to intervene when the storage manager is about to do certain things such as fire off or continue a garbage collection. (The Ow\ST garbage collector is incremental and interruptible.) I believe this gives you the 'hook' you would need to de-cache less valuable objects at an appropriate time, i.e., when the memory manager is under pressure. Peter Deutsch deutsch@parcplace.com
yost@DPW.COM (David A. Yost) (11/28/90)
I've gotten some interesting mail on this topic, but my point wasn't to get mail but to stimulate discussion here. Someone pointed out that purgeable memory blocks on the Mac are a kind of stash collection. I'd like to see a general facility that is capable of disposing of stashes in LRU order from the pool of all objects. Come to think of it, I've advocated a similar principle for disk file systems and netnews articles. Sort of a FIFO trash can: put it in the trash queue, but it's still available for a while. I use this method on my email messages and my office paper trash. Very nice. --dave yost yost@dpw.com or uunet!esquire!yost Please don't use other mangled forms you may see in the From, Reply-To, or CC fields above.
grp@Unify.com (Greg Pasquariello) (11/28/90)
In article <2855@esquire.dpw.com>, yost@DPW.COM (David A. Yost) writes: > I've gotten some interesting mail on this topic, > but my point wasn't to get mail but to stimulate > discussion here. I would be interesed in someone posting more information about the "economic model" mentioned yesterday, whereby objects pay rent, get evicted, etc. > --dave yost > yost@dpw.com or uunet!esquire!yost > Please don't use other mangled forms you may see > in the From, Reply-To, or CC fields above. -- --- Greg Pasquariello Unify Corporation grp@Unify.Com
lou@cs.rutgers.edu (lou) (11/29/90)
In regard to memory that is accessible unless and until the space is
needed for something else: there was a recent discussion on
comp.lang.lisp of "weak" links (I think that was the term), which are
links that can be followed to access some storage, but which do not
make the collector think the storage is "in use". Thus, when garbage
collecting, the storage looks like it can be reclaimed. (Of course,
the garbage collector has to notice these weak links and reset them to
NIL if to reclaims the storage they point to.) This has the advantage
that the user does not have to write any special code to do the
cleanup.
--
Lou Steinberg
uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou
internet: lou@cs.rutgers.eduburley@pogo.ai.mit.edu (Craig Burley) (11/29/90)
In article <LOU.90Nov28110551@atanasoff.rutgers.edu> lou@cs.rutgers.edu (lou) writes:
In regard to memory that is accessible unless and until the space is
needed for something else: there was a recent discussion on
comp.lang.lisp of "weak" links (I think that was the term), which are
links that can be followed to access some storage, but which do not
make the collector think the storage is "in use". Thus, when garbage
collecting, the storage looks like it can be reclaimed. (Of course,
the garbage collector has to notice these weak links and reset them to
NIL if to reclaims the storage they point to.) This has the advantage
that the user does not have to write any special code to do the
cleanup.
--
Lou Steinberg
uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou
internet: lou@cs.rutgers.edu
That sounds like a neat approach. But it doesn't appear to handle, without
some changes, an approach I call (for lack of a decent education) the
"explode/implode method". Here, information may be represented in a
compacted or source fashion, such as a list of identifier names and pointers
to their corresponding objects, and this is called "imploded form". For
purposes of speed and other things, typically such a list is converted to,
say, a hash table and other information, called "exploded form", which takes
up more space. Keeping both forms around takes up even more space and is
unecessary (especially if there's a copy of the imploded form on disk, but
pretend there isn't). So perhaps the exploded form, once created, should
have the only (and a weak) link to the imploded form so the imploded form
gets gc'ed quickly and easily.
Then if more space is needed, the exploded form somehow needs to be told
to trash itself, and it should only do that if it either sees that it still
has a weak link to its imploded sibling or if it can recreate its imploded
sibling, after which it replaces any references to itself with references
to its imploded sibling, and trashes itself.
--
James Craig Burley, Software Craftsperson burley@ai.mit.edugintera@cs-sun-fsd.cpsc.ucalgary.ca (Andrew Ginter) (11/29/90)
Some object databases do a subset of what you're asking for. These databases cache objects in memory. When things get full up, or at the end of a transaction, or whenever else it makes sense, objects are flushed to the database and references to the objects are "fixed". If anyone tries to chase a "fixed" reference, the indicated object is fetched back into memory. The Postgres system is described in: A Shared Object Hierarchy, by Lawrence A. Rowe. The paper is available via ftp from postgres.berkeley.edu as part of the Postgres papers "tar" file. The Orion system is described in: Integrating an Object-Oriented Programming System with a Database Sytem, by Won Kim, Bat Ballou, Hong-Tai Chou, Jorge F. Garza, Darrel Woelk and Jay Banerjee, OOPSLA '88 Proceedings Andrew Ginter, 403-282-2984, gintera@cpsc.ucalgary.ca, Ginter@uncamult.bitnet
caroma@rice-chex.ai.mit.edu (Carl R. Manning) (11/29/90)
In article <1990Nov28.075224@Unify.com> grp@Unify.com (Greg Pasquariello) writes: >I would be interesed in someone posting more information about the >"economic model" mentioned yesterday, whereby objects pay rent, get >evicted, etc. A basic idea of the Agoric (market) model is that large systems which allocate resources through markets (e.g. economies based largely on capitalism) can often make better use of resources than those where planners try to anticipate ahead of time what the resource needs will be (e.g. command economies; programmers & system operators). The theory is that local market prices reflect the actual (not just anticipated) locally available supplies of, and local needs for, a resource, so resource decisions made according to these prices can make better use of the resource. So, as our computer systems become integrated into larger Open Information Systems, perhaps we can best make use of the resources by setting it up as a Market ecology, which doesn't require anyone to understand the overall system in order for it to evolve toward more efficient use of resources. In order to set up markets for resources, we have to build systems which charge for resource use: processing, storage, communications, etc. Part of the cost of using a resource is the overhead for charging and collecting for use of the resource; part of the cost for using market mechanisms is the transaction cost of negotiating prices in the market system. There's a tradeoff between (a) using the market to allocate resources where they're needed most, but taking on overhead and transaction costs, and (b) using a command-style planning to allocate larger amounts of resources ahead of time and avoid the overhead, but risk less efficient allocation since the decisions are based on anticipated resource conditions rather than actual ones. Therefore, in some situations rent will likely be charged for resources at the `agency', `application', or `server' level rather than at the individual object level, just as your company probably doesn't pay rent (or property taxes) on each office individually. In other situations, the transaction/overhead cost of smaller allocations is worth the benefit in flexibility, e.g. you might pay for an object agent to migrate temporarily to a knowledgebase server to make some queries, or to negotiate protocols for future interactions, just as your company can pay for individual hotel rooms in another city when it sends you to a conference or to negotiate a contract. In such a market system, when local demand for a resource rises, the price for that resource will also rise; those uses of the resource who are renting at the market rate will find their costs rising, and if the costs rise high enough, they will have incentive to cut back on the use of that resource, e.g. put things off until later when the price is lower, get rid of large tables of noncritical cached info, move things to cheaper areas (disk or another machine). The market provides *incentive* for doing these things. The price mechanisms provide the local information for making decisions about what to do. They do not provide actual mechanisms for actually doing these things, just the competitive incentive to do them the best way you can figure out how (or be outperformed by competitors). So to get back to stashes... Markets mechanisms can help a system decide when to stash and when to release the stashed info, but by themselves won't help much in figuring out how to implement the stash itself. Enough rambling. Those who are interested might take a look at The Ecology of Computation B.A. Huberman, editor New York: Elsevier Science Publishers, 1988 In particular at the chapters "Markets and Computation: Agoric Open Systems" by Miller & Drexler "Incentive Engineering for Computational Resource Management" by Drexler & Miller If you find the book interesting, you might also find something interesting in the more recent citations at the end of "Primed for Performance", Tad Hogg, June 1990 BYTE, p241 Cheers, CarlManning@ai.mit.edu
mark@parc.xerox.com (Mark Weiser) (11/29/90)
I came in on the middle of this, but perhaps the following comment is relevent: Some systems have the notion of "finalizable" objects. These are objects for which the user desires one last shot at them before they are collected. Typically this is done by registering with the collector a "finalization routine" which is called when the collector can find no other references to the object (Naturally this call is made in a separate thread so the collector is not blocked for this). Finalization requires some form of weak link, usually, which is flippped to strong during finalization so that the object is not fully collected until the final link goes away. The Cedar and PCedar systems both offer a finalization service. Cedar uses a ref-counted GC, and the weak links are simulated by telling the GC that it should try to collect a finalizable object when the ref count is some specified non-zero value. PCedar uses a Boehm generational conservative parallel collector, and simulated weak links with "disguised" pointers (which are known to the GC). A key use of finalization in these systems is to clean up after a file descripter which has been passed around asynchronously among many threads. It is closed by the finalization routine after the last reference is dropped. -mark -- Spoken: Mark Weiser ARPA: weiser@xerox.com Phone: +1-415-494-4406
jack@cs.glasgow.ac.uk (Jack Campin) (11/29/90)
lou@cs.rutgers.edu wrote: > In regard to memory that is accessible unless and until the space is > needed for something else: there was a recent discussion on > comp.lang.lisp of "weak" links (I think that was the term), which are > links that can be followed to access some storage, but which do not > make the collector think the storage is "in use". Thus, when garbage > collecting, the storage looks like it can be reclaimed. This was used in a garbage collector for PS-algol written by Dave Sparks at ICL around 1986. It got rid of not-recently-referenced persistent objects, "unswizzling" pointers to them back to the persistent form. This didn't affect the semantics of the program at all since the persistent store manager could always find such objects again if they were needed. Made a big difference to performance of large applications. -- -- Jack Campin Computing Science Department, Glasgow University, 17 Lilybank Gardens, Glasgow G12 8QQ, Scotland 041 339 8855 x6044 work 041 556 1878 home JANET: jack@cs.glasgow.ac.uk BANG!net: via mcsun and ukc FAX: 041 330 4913 INTERNET: via nsfnet-relay.ac.uk BITNET: via UKACRL UUCP: jack@glasgow.uucp
thomasw@hpcupt1.cup.hp.com (Thomas Wang) (11/30/90)
Is the market economy model applicable to computer programs? The theory
assumes that individual component be able to figure out what is the least
cost option to complete a task from a mixture of options. Human beings
do this with relative ease. But I would think programs would have
difficulty dealing with this sort of decision making. Maybe the market
economy can work with transations between large computer systems, but I
hardly consider it a general mechanism for dealing with resource
allocations.
-Thomas Wang
(Everything is an object.)
wang@hpdmsjlm.cup.hp.com
thomasw@hpcupt1.cup.hp.comhibbert@xanadu.com (Chris Hibbert) (12/01/90)
thomasw@hpcupt1.cup.hp.com (Thomas Wang) asks: >> Is the market economy model applicable to computer programs? [...] >> Human beings do this with relative ease. But [...] programs would >> have difficulty dealing with this sort of decision making. The simple answer is: read the articles by Miller & Drexler in the collection by Huberman mentioned earlier in this thread. The quicker answer is that Carl Manning was right: most small agents will probably form coalitions to have their resources negotiated as a bundle freeing the individual objects from the overhead. Other small objects that [or whose owners] don't want to live or die with an unrelated cluster will hire an agent that specializes in negotiating for resources. Part of the contract would be that the agent would find a way to save the object's state when the agent decides to stop spending the object's money on computrons. Miller and Drexler can be reached as miller@xanadu.com and drexler@xanadu.com, respectively Chris
ncjuul@diku.dk (Niels Christian Juul) (12/01/90)
thomasw@hpcupt1.cup.hp.com (Thomas Wang) writes: >Is the market economy model applicable to computer programs? The theory >assumes that individual component be able to figure out what is the least >cost option to complete a task from a mixture of options. Human beings >do this with relative ease. But I would think programs would have >difficulty dealing with this sort of decision making. Maybe the market >economy can work with transations between large computer systems, but I >hardly consider it a general mechanism for dealing with resource >allocations. Yeahh, Look at the Stockmarket with all those automatic computerized brookers. What happend last time the market got wierd? Everybody (or should I say everymachine) tried to sell? Making the market-curves really falling, thus more sellings, ... .... ... I don't trust machines when taking market decisions, though they may be a good support in the process of decision making. And it doesn't help to bundle the machines, someone still has to negociate. Still, some kind of ecological model may be feassible. BUT ECOLOGY is not ECONOMICS (or maybe if you are M. Thacher :>, but here I'm back to a point similar to the one made by Peter Deutch that this is not appealing to my view of morality). Now, I better go check the reference, before rambling any more... Niels Chr. -- ------------------------------------------------------------------------------- Niels Christian Juul Email: ncjuul@diku.dk DIKU (aka Dept.Comp.Sci. Univ.Copenhagen) Phone: +45 31 39 64 66 ext.405 Universitetsparken 1 -- DK 2100 Copenhagen Direct: +45 31 39 33 11 -- 405
caroma@rice-chex.ai.mit.edu (Carl R. Manning) (12/02/90)
In article <1990Nov30.184708.18687@xanadu.com> hibbert@xanadu.com (Chris Hibbert) writes: >thomasw@hpcupt1.cup.hp.com (Thomas Wang) asks: >>> Is the market economy model applicable to computer programs? [...] >>> Human beings do this with relative ease. But [...] programs would >>> have difficulty dealing with this sort of decision making. >>> [...] >>> (Everything is an object.) >[...] most small agents will probably >form coalitions to have their resources negotiated as a bundle freeing >the individual objects from the overhead. Other small objects that >[or whose owners] don't want to live or die with an unrelated cluster >will hire an agent that specializes in negotiating for resources. >Part of the contract would be that the agent would find a way to save >the object's state when the agent decides to stop spending the >object's money on computrons. "Everything is an object" can be a useful viewpoint; as Chris Hibbert points out, it can lead to ideas of arranging for objects to delegate complex decisions to business managers or to form coalitions. But it also can be a limiting metaphor if you equate objects with people, who are treated as equals and given the power to make their own decisions. Economic units (e.g. corporations, businesses, families, individuals, etc.) also OWN property and have the responsibility for managing and paying for the resources used by their property; this property can also be viewed as objects. Thus, the economic decisions for most small objects may be made by the economic units which own them, and charges for resource use by an object can be directed to the owner of the object rather than to the object itself. Often these economic units will be organizations of objects; Carl Hewitt has dubbed these units ORGs. However, these ORGs aren't necessarily just large databases and the like; an information system will be structured into smaller ORGs where the usefulness of the accounting and management information outweighs the overhead of keeping it, just as all but the smallest corporations and companies have internal divisions and groups. Another thing to point out is that making the economy work doesn't necessarily require agents with sophisticated human level intelligence; an economy of agents which make decisions based on price information using simple heuristics can still realize the benefits of using local market information. Note that there is a tradeoff between intelligence and resource use: trying to use more information intelligently requires more resources and lengthens reaction time. Drexler and Miller's "Incentives..." paper gives some examples of simple heuristic agents participating in markets. In "Time and Money" (April 90 Byte) Wayner mentions another system built using simple heuristics: in experiments with the Spawn operating system, Xerox people used a simple heuristic where each process received a trickle of money over time, and bet all its money at each auction. So yes, I think the market economy model is applicable to computer programs. Perhaps you won't see objects like cons cells being treated as economic units with the responsibility to pay for their own memory, but it is easier to imagine a small agencies like a hardcopy server, as well as large transaction systems, managing their resources on the market. (e.g., the hardcopy server might purge font caches if memory became too expensive or paying jobs which used them became scarce...) This thread started out discussing how to manage stashes of info which can be purged or compacted if the memory is needed more elsewhere. The economic model provides a distributed, localized mechanism for managing that 'needed more' information through prices. -- CarlManning@ai.mit.edu
pcg@cs.aber.ac.uk (Piercarlo Grandi) (12/03/90)
On 28 Nov 90 04:18:12 GMT, yost@DPW.COM (David A. Yost) said:
yost> Someone pointed out that purgeable memory blocks
yost> on the Mac are a kind of stash collection.
Same goes for OS/2 segments...
yost> Come to think of it, I've advocated a similar principle for disk
yost> file systems and netnews articles. Sort of a FIFO trash can: put
yost> it in the trash queue, but it's still available for a while. I
yost> use this method on my email messages and my office paper trash.
yost> Very nice.
There are a number of systems like this already there. Many UNIX admins
have modified rm(1) not to delete but to move to a trash can directory,
that is periodically purged of file solder than X days. There are some
ready made rm(1) clones that do this in comp.source.{misc,unix}.
Knuth in ACP volume 1 remarks that SLIP, the original Weizenbaum list
processing package in Fortran, used a FIFO free list, which, he says,
tended to make programs that generated dangling references run correctly
for a awhile after the reference had been left dangling :-).
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.ukianr@syma.sussex.ac.uk (Ian Rogers) (12/11/90)
lou@cs.rutgers.edu (lou) writes: > > there was a recent discussion on > comp.lang.lisp of "weak" links (I think that was the term), which are > links that can be followed to access some storage, but which do not > make the collector think the storage is "in use". Thus, when garbage > collecting, the storage looks like it can be reclaimed. (Of course, > the garbage collector has to notice these weak links and reset them to > NIL if to reclaims the storage they point to.) The Poplog AI programming environment does this with "temporary" properties. I've added, to the end of the message, a (fairly longish) section of one of the online reference files which describes this behaviour. Note that these properties are easily accessable from all four of the Poplog languages: Lisp, ML, Prolog, and Pop11 (just like Lisp but with a much richer and more readable syntax). burley@pogo.ai.mit.edu (Craig Burley) writes: > > ... to handle, without > some changes, an approach I call (for lack of a decent education) the > "explode/implode method". Here, information may be represented in a > compacted or source fashion, such as a list of identifier names > ... > > Then if more space is needed, the exploded form somehow needs to be told > to trash itself, and it should only do that if it either sees that it still > has a weak link to its imploded sibling or if it can recreate its imploded > sibling, after which it replaces any references to itself with references > to its imploded sibling, and trashes itself. "Destroy" properties (also described below) could handle this. ! Properties come in two basic types: permanent and temporary (in ! addition to a special 'destroy' type for associating destroy actions ! with objects, see below). The difference between permanent and temporary ! involves the interaction of the property with garbage collection. ! Suppose a property PROP has an entry associating an item VAL (the value) ! with an item ARG (the argument), and suppose that there are no other ! references remaining to the argument ARG elsewhere in the system (i.e. ! ARG is otherwise garbage). Then, if the entry were treated by garbage ! collection like any other record, the presence of ARG in the entry would ! prevent it (i.e ARG) from being garbaged. Similar remarks apply to the ! value VAL if that too has no other references remaining. ! ! For some applications this may be the desired behaviour; for others, ! the property entry may no longer be required at all if either ARG or VAL ! are otherwise garbage. The system's action in this respect can therefore ! be specified for the entries in a given property, by supplying one of ! the following keyword arguments when the property is initially ! constructed (with -newproperty- or -newanyproperty-): ! ! Keyword Meaning ! ------- ------- ! "perm" Permanent: entries are never discarded. ! ! "tmparg" Temporary on the argument: entries are discarded for ! which the ARG items are otherwise garbage. ! ! "tmpval" Temporary on the value: entries are discarded for ! which the VAL items are otherwise garbage. ! ! "tmpboth" Temporary on both: entries are discarded for which ! either the ARG or VAL items are otherwise garbage. ! ! "tmpclr" Temporary cleared: all entries are cleared from the ! property at every garbage collection. ! ! (Note of course that if an entry is kept in any case, then both ARG and ! VAL items are forced to be retained as well, regardless of whether they ! were garbage or not.) ! ! Thus for example, "perm" properties may be used for retaining ! permanent tables of information, and "tmparg" properties for attaching ! ad hoc pieces of information to arbitrary records (which will be garbage ! collected along with the records). "tmpclr" properties are useful for ! short-term caching of computed data. ! ! A 'destroy' property is a special kind of "tmparg" property. Like ! the latter the presence of ARG as the argument of a destroy property ! entry will not stop it from being considered as garbage, but instead of ! simply discarding ARG, the entry containing it is added to a special ! list maintained by the garbage collector. At the end of the garbage ! collection those destroy entries whose argument would otherwise have ! become garbage (i.e. and the entry discarded) are examined. If their ! value slot contains a procedure, or an identifier whose -idval- is a ! procedure, the procedure is run, with ARG passed as argument. Only then ! is ARG discarded in the same manner as with temporary properties. ! ! Destroy properties thus allow arbitrary procedures to be attached to ! objects in such a way that the procedure gets run, with the object as ! argument, at the point at which the object would otherwise have become ! garbage (the point of its destruction). More information about Poplog can be got from popmanager@uk.ac.susx.cogs ttfn, Ian Rogers Poplog Janet/Arpa: ianr@uk.ac.susx.cogs | Cognitive & Computing Sciences uucp: ukc!cogs!ianr | Sussex University, Falmer, voice: +44-(0)273-606755 x2392 | Brighton, England. "Deep in the fundemental heart of mind and Universe," said Slartibartfast, "there is a reason" - Douglas Adams