Eliot Miranda wrote:

> Yes, this is a cool radical idea that I haven't got my head around yet.
>  I need to think about this at length.  The obvious approach to the
> duplication is copy-on-write where any modifications to the root
> Array class get propagated to the copies, assuming there is some
> hierarchical control organization.  I think this approach is taken in
> Alex's worlds where modifications to a parent world are seen my
> children.  But then the merge problem rears its head when trying
> to propagate modifications to a child that has made its own local
> modifications in the same region.

I have some papers about this (1992 and 1993) but since they are in
Portuguese it makes no sense for me to point them out. The basic idea is
the MESI cache coherence protocol from bus based multiprocessors
(network based multiprocessors normally use directory based schemes
which are closer to what we want but harder to explain so I will start
out with MESI).

Any given cache line, or object in our case, can be either Invalid
(meaning the local node doesn't have a copy), Exclusive (the local node
has a copy and knows that nobody else does), Shared (there is a local
copy and possibly other nodes also have copies) and Modified (the local
copy has been changed and must be saved to main memory).

- You can go from I to either E or S (which one depends on what the
other caches say) by fetching a copy.
- You can go from E to S if you see anybody else fetch a copy.
- You can go from S to E by asking everybody else go from S to I and
inform you they have done so.
- You can go from E to M by writing to your copy.
- You can go from M to E by saving your copy to main memory.
- You can go from E or S to I if you need to reuse the cache line for
other data.

No other transitions are allowed (perhaps this would be far easier to
understand as a drawing?). This scheme doesn't need to merge since there
is at most one changed copy at any given time. This restricts
parallelism compared to multiple worlds, but is compatible with our
current semantics.

Note that David Ungar showed something very similar to this actually
running in Squeak on 56 processors at least year's OOPSLA and the movie
of his demo (thanks, Göran!) is available online (at
http://siliconsqueak.org among other places).

-- Jecel