On 9/6/2011 14:11, Warp wrote:
>    What I'm wondering is that it's probably way more common for the nodes
> to not being shared (and thus have only one single owner), but how can
> the compiler know that for sure in a complex program?

Right. Consider the "insert" function itself. It calls nothing else that 
mutates the heap except for "insert". So for the duration of the actual 
insert call, it knows the heap isn't shared.  Extend this concept a bit 
(yes, that's fuzzy, I know) and with sufficient analysis, you can figure out 
that when you do something like
    x = insert 27 original
    y = insert 56 x
    z = insert 23 y
that y is an intermediate value that can't be shared with anything else. 
(OK, maybe not in the heap case, but in a fair number of other such 
structures, it's not uncommon it's possible to determine that. Again, I'm 
not familiar with the details of how it's done.)

> and used by several different parts of the program.

If you compile those separately, yes, that can be problematic. If you 
compile it all at the same time, or have more sophisticated linking (like a 
VM, say), then the range over which the compiler can deduce a lack of 
sharing is greater.

Remember, too, that various kinds of GC can tell you whether something is 
shared or not. You could conceive of a copy-on-write sort of thing that only 
does the copy if the reference count is >1.

> It's enough for two different parts of the
> program to modify (or perhaps even just read) the same data container for
> the in-place modifications becoming a program correctness hazard.

True. That's why it's better to leave it to the compiler than the 
programmer. ;-)

-- 
Darren New, San Diego CA, USA (PST)
   How come I never get only one kudo?

Post a reply to this message