[M3devel] REFANY-keyed tables?

JC Chu jcchu at acm.org
Fri Feb 28 18:40:55 CET 2014


>> In general, the implementation of REFANY = would have to work whether a concurrent copying collector is being used or not.

> ... after the collector has moved P^.link^ and updated P^.link but hasn't yet updated Q^.link? ...

... So do we actually have that for r1, r2: REFANY, r1 = r2 # NIL implies r1^ = r2^?  I was hoping that at least REFANY-valued lists would still be safe to use....

— JC Chu

-----Original Message-----
From: Rodney M. Bates [mailto:rodney_bates at lcwb.coop] 
Sent: Friday, February 28, 2014 23:11
To: Antony Hosking
Cc: m3devel at elegosoft.com
Subject: Re: [M3devel] REFANY-keyed tables?



On 02/27/2014 02:07 PM, Antony Hosking wrote:
> [Your prior e-mail is a great description of why REFANY does not have 
> a hash, and hence why Refany.T raises an exception for Refany.Hash.  
> Short answer is there is nothing about a REFANY that can conceivably 
> be used as a hash.  We could choose to implement an invariant hash 
> code for REFANY, much as Java does for Object, but it would impose a 
> space cost to store the hash.]
>
> In general, the implementation of REFANY = would have to work whether a concurrent copying collector is being used or not.  == in Java is much the same.  A copying collector implementation can use a number of techniques to ensure this, but in our case pointer equality is sufficient because the mostly-copying collector does not move heap objects that are referenced from the stacks.  Thus, while the REFANY = operation is being performed neither target will move and pointer equality suffices.
>

OK, that makes sense.  But then what about this code:

IF P^.link = Q^.link ...

getting executed after the collector has moved P^.link^ and updated P^.link but hasn't yet updated Q^.link?  (And assuming no stack pointers equal to P^.link exist, or it wouldn't happen.)

> On Feb 26, 2014, at 10:35 PM, Rodney M. Bates <rodney_bates at lcwb.coop> wrote:
>
>> Tony, I see that Refany.Equal does not raise an exception, but rather 
>> just checks pointer equality.  Is it true, as this would require, 
>> that parallel GC prevents a mutator from executing this during the 
>> period when some but not all of the pointers to a being-moved heap object have been updated?
>>
>> On 02/26/2014 11:08 AM, JC Chu wrote:
>>> Hi,
>>>
>>> I need a REFANY-to-INTEGER table in my program but RefIntTbl.Default is giving me runtime errors.  Apparently Table(Key, Value) uses Key.Equal() and Key.Hash(), but those procedures in Refany, which is use to instantiate RefIntTbl, both raise a fatal exception.
>>>
>>> I’m a bit confused since a number of REFANY-keyed tables are shipped with CM3.  Is this actually the expected behavior or am I doing anything wrong?
>>>
>>> Thanks.
>>>
>>> — JC Chu
>>>
>>
>
>




More information about the M3devel mailing list