Re: Is garbage collection here yet?

On 24 Apr 2006 06:55:25 -0700,
"Sean Woods" <yoda@xxxxxxxxxx> wrote:

In "curbside collection", if an object should be cleaned up when idle
it (or it's container object) "register" the object with a central
collection mechanism. All calls to this node are never direct, but
instead are made by asking the container object for its wherabouts.
If the object already exists, the container passes back a reference.
If not, it creates the node, stuffs it with data, and then returns the
reference. Inside the "reference" call of the container is a call to
the central collector that "touches" the node. Essentially says "hey,
I used it" with a time stamp.

I use it as a poor man's caching mechanism for objects that represent
database records. (Databases with thousands of records, I might add.)
Because they are somewhat expensive to create and destroy, I try to
keep them in memory if they are under constant use.

It IS a cache...! The methods of maintaining the LRU list vary; you
separate objects into one of two lists depending on whether they're OLD,
but it's the same deal.

My favourite is to combine that method with a timer so you only check
when something SHOULD be expiring, and as you go, take note of who'll be
expiring next. Saves a few unnecessary checks. But you still either
end up scanning the whole lot to find the oldest object(s), or
maintaining an LRU list of objects.

If I've only got a smallish number of objects, I generally combine a
time stamp and timeout individually for each object, but I must have
used 1001 other methods over they years. One of my favourites in the
assembly world, was a one-byte shift register; you OR in a 1 each time
you reference the object, and once every ninth of the idle allowance,
you check the register for zero, and destroy it if it is (it's actually
an old key debouncing technique). Otherwise you shift it one bit and
keep looking.


But in any case, you still have a problem with how often to update the
time stamp, compared to the duration of the garbage collection cycle.
For a generic GC mechanism, caching like you suggest won't work because
you have no idea how long the reference will persist. It could well get
stored away in a list for days.

One situation where I had exactly that problem, I used a kind of named
shared locking. Objects were dicts, stored in an array. When a module
needed a reference to an object, it would lock it under the modules
name (creating it first if it wasn't already there). When all
references were released, I'd set an expire timer going (which would
get killed if anything came along and established a new lock). The
time stamp was also used during normal use to spot objects which hadn't
been locked or unlocked in a while, and the modules which were holding
locks on it were sent a "check lock" message to verify that the lock
was still valid (I used a fairly long check period because the checking
was quite expensive). If any reported the lock was invalid, I'd log an
error against the module and cancel the lock.


And speaking of storing references away, you can't reply on ANY fully
automatic reference counting/searching technique either, so long as the
reference can be stringified, or probably even more importantly,
"de-stringified". In these cases you need some way to preserve an
object even when all its obvious references seem to disappear.
Reference counting and caching are two options that deal with this
issue, but in the end you probably need to pick one cheap method that
will handle a lot of cases, and synthesise the others on an as-needed
basis (eg. caching references).


Fredderic
.

Relevant Pages

  • Re: How to do proper locking
    ... >> lock across malloc, so your allocation code isn't safe. ... while you bump the reference count, ... PROC_LOCKwhile doing crhold(). ... > - setting up timers. ...
    (freebsd-hackers)
  • Re: [PATCH] tipc: checking returns and Re: Possible Circular Locking in TIPC
    ... Jarek Poplawski wrote: ... until and unless the latter function has returned a valid reference. ... Is it OK to call it without the lock ... One reference entry points to a subscription instance, ...
    (Linux-Kernel)
  • Re: [PATCH] tipc: checking returns and Re: Possible Circular Locking in TIPC
    ... Jarek Poplawski wrote: ... IMHO lockdep ... until and unless the latter function has returned a valid reference. ... Is it OK to call it without the lock ...
    (Linux-Kernel)
  • Re: How to do proper locking
    ... >> drop the proc lock, so that lock is only held for a very short period of ... You then have your own reference to the cred structure that is ... > destroying an object while the refcount is non-zero. ... > if one routine sleeps, then any callers of this routine must sleep too. ...
    (freebsd-hackers)
  • Re: Is garbage collection here yet?
    ... The archtecture that seems to balance the ease of garbage collection ... EVERYTHING to be a reference call is a strategy I lovingly call ... but instead are made by asking the container ... I used it" with a time stamp. ...
    (comp.lang.tcl)