On Tue, Jul 30, 2013 at 8:15 PM, David Jeske <[email protected]> wrote:
> On Tue, Jul 30, 2013 at 4:08 PM, Jonathan S. Shapiro <[email protected]>wrote: > >> 1. Typing support for deep immutability. It would be really useful to >> know which subgraphs are deeply immutable and therefore can be accessed >> concurrently without any locking at all. It's even possible to imagine >> schemes in which phase changes are possible in both directions between >> normal and deeply immutable states. This helps a lot in some fork/join >> style concurrency, but it's certainly not a cure-all. >> > > I'm intrigued by deep-immutability with easy deep COW semantics, that or > STM. Something that enables the simplicity of immutability for concurrency, > and the ability to have efficient COW snapshots with roll-forward/back (say > for undo). Needs a way to construct cyclic immutable structures though. > I never said anything about COW or STM. I don't know how to do COW without hardware support, and the results I know about from STM research have been pretty disappointing so far. Concerning deep immutability, here are the key observations: 1. At any point where I have my hands on some reference that is exclusively held by me (in the linear type sense), and that reference is the sole reference preserving the liveness of an object graph, I can safely cast that reference to a deep-frozen reference. 2. If I can show through alias and use analysis or linear typing that the "mutate permitting" reference is not used while the deep-frozen reference[s] into the graph are reachable, I can ping-pong back and forth. So in particular, I can pass a mutate-permitting linear type restricted reference as a *borrowed, transitively non-escaping *deep-frozen parameter to a non-escaping procedure, or even to a procedure that returns its results in a region that is known not to overlap with the deep-frozen region. Once that procedure returns, I know that the deep-frozen reference is no longer live, and that the deep-frozen contract no longer needs to be honored. *The borrowing procedure is free to perform thread fork/join*, provided all of those threads transitively satisfy the non-escape requirement. > >> 2. Lock labeling (which I sometimes think of as lock regions). ...It >> seems mostly possible to document the relationship between locks and the >> things they govern by suitable labeling,and to use some form of >> acquire/release discipline to ensure that locks are acquired before their >> associated fields are sourced or mutated. Separately, it seems >> straightforward to label those fields that can only be sourced/sinked by >> CAS or atomic operations. >> > > Yes, please. It won't handle all cases, but I think a big surface area > could be covered. > That was more or less my thought as well. In Coyotos, this kind of labeling would have covered all but four or five of the locks in the system, which would have gone a long way toward shrinking the haystack when a needle got lost. :-) shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
