[e-lang] Lazy Interning Fantasy (was: TraversalKey bug fixed; Equalizer questions)

[Kevin Reid]

On Apr 14, 2007, at 16:57, Mark S. Miller wrote:
> Kevin Reid wrote:
>> 4. It has occurred to me that the equalizer could, having determined
>> that two references are the same but not pointer-equal, replace one
>> of them with the other, thus saving memory and allowing future
>> comparisons to be cheap. Can you think of a good way for the
>> equalizer to communicate this to the objects it uncalls?
>
> Not as an incremental modification to the E-on-Java implementation.  
> But the Weizmann implementation of Flat Concurrent Prolog had a  
> lazy interning idea that did something similar: Since the  
> implementation already knew how to transparently follow forwarding  
> pointers, in order to support incremental migrating collectors and  
> resolved logic variables, whenever two values were successfully  
> unified, one was smashed in place with a forwarding pointer to the  
> other.

Can't we do the same thing in the cases where we have forwarding  
pointers? (E-on-Java SwitchableRef, E-on-CL forwarding-ref.) The  
interesting bit of that system as you've described it isn't that it  
has transparent following -- E implementations do too -- but that it  
can replace any object in place with a forwarding pointer.

Also, I had imagined that individual objects could (audited/ 
primitively) support a protocol for "update the slot that your Nth  
uncall element came from".

All such unification requires either at most one thread per heap,  
atomic slot updates, or a lot of locking, however.

> In an E system where multiple vats share an address space and pass
> DeepPassByCopy objects between vats by pointer sharing, it is  
> interesting to
> ponder whether they should all share one weak lazy interning table,  
> or whether
> they should each have their own. If they share one, it is also  
> interesting to
> wonder whether DeepPassByCopy objects should be always be interned  
> before
> crossing a vat boundary.

"always" can't provide any interesting guarantees as an object might  
become settled and DeepPassByCopy after being passed.

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>