RefCounts are dead. Long live lazy copy-on-write.

[Mark S. Miller <mark>]

Abstract: We can eat our cakes on a Table, and not have to throw away
the garbage immediately too.  Instead of immediate copy-on-write of
shared structure, we can change probable garbage to backwards deltas,
and then copy *them* on use.  By doing so, refCount collection is
unneeded, and normal (eventual) garbage collection suffices.


We seemed to have been stuck between a RefCount and hard
work: For our Table abstractions to be efficient, they needed to be
implemented copy-on-write without unnecessarily copying.  To know
enough to avoid unnecesary copying, they needed to know immediately
when a Table was garbage.  This would necessitate a refCount
collector.  But RefCounts are expensive, and garbage collection is
complicated enough already.  Also, since we frequently point with
generic Heaper pointers, if we're going to RefCount collect anything,
we'll have to RefCount collect everything.

However, when one view of a Table is written, if we optimistically
assume that all other views are garbage, then we can simply modify the
underlying table, and bind all other views to that table plus a
backwards delta.  If one of these other views are *then* used, then we
copy--taking the backwards delta into account.  This way the only
wasted work is in maintaining the backwards deltas for views that we
don't yet know are garbage.  We still copy *only* when we actually
need to, using only an eventual garbage collector.