[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
sneaky uses for copy-on-write
- To: <mark>
- Subject: sneaky uses for copy-on-write
- From: Eric Dean Tribble <tribble>
- Date: Mon, 30 Oct 89 00:12:55 PST
- Cc: <xtech>
- In-reply-to: <MarkS.Miller'smessageofSun>,41 PST <8910300131.AA03174@xanadu>
I assume you are not considering restricting the garbage collector to
only finalizing circularities...
Sorry to imply that. The garbage collector collects all garbage. My
note just reflected my concentration on circular garbage.
No. The cost of a regular garbage collector would be to copy when:
1) there exist more than 1 copy-on-write Table sharing the same
2) only one of these is non-garbage.
3) That one is modified.
4) the eventual garbage collector hasn't yet collected its garbage
5) the programmer hasn't explicitly deleted its garbage brothers.
Admittedly #4 is highly probable. I think #3 is the weak link. Also
our motivating example is iterating over Tables. With our new
iteration style, explicitly deleting in time should usually be easy:
Isn't the above idiom in fact most of the cases we are worried about?
Our pass-by-value style for using Steppers makes the above idiom safe.
Not iterating over tables. The example is replacing an ImmuTable with
a variation on that ImmuTable efficiently. This occurs in the Ent
during tree rebalancing and construction. The table of crums will
typically be unshared, but it *might* be shared. The algorithms have
no way to know.
A similar example will come up in frontends: replacing a WordVector
with an altered copy of itself. Typically that WordVector won't be
shared, some pice of the frontend might have grabbed it for caching.
Both these examples satisfy all your criteria in the typical unshared