[M3devel] FreeSlots/lookup slot locking

[Tony Hosking]

Yuck!

Look, any reasonable implementation of critical sections/mutexes on  
modern multi-cores will use spin locks so uncontended accesses to  
speed the fast path in acquisition.  This will be implemented using  
CAS or LL/SC which on many architectures also have the effect of a  
membar.   This is all just premature optimization!  Measure it!  If it  
is slow, then worry about how to make it fast!  Otherwise, keep it  
simple!

On 12 Nov 2009, at 09:28, hendrik at topoi.pooq.com wrote:

> On Thu, Nov 12, 2009 at 04:17:12AM +0000, Jay K wrote:
>>
>> I do currently still use the critical section "throughout 'all' of  
>> AssignSlot".
>>
>> The memory barrier doesn't replace it there. Just makes it carefully
>> ordered so other readers see things reasonably well.
>
> Just curious:  C had "volatile" variables, meaning variables whose
> writes and reads cannot be reordered or deleted by an optimiser.
> They're intended for things like memory-mapped I/O.  Wouldn't they be
> the kinds of things we need here?  How does the gcc intermediate code
> represent them? By memory barriers? Or by some other means?
>
> -- hendrik
>
>>
>>
>>
>> I DO suspect the locking in AssignSlot can be reduced but haven't  
>> done so yet.
>>
>> Maybe it doesn't work out.
>>
>>
>>
>> - Jay
>>
>>
>>
>>
>> From: hosking at cs.purdue.edu
>> To: jay.krell at cornell.edu
>> Date: Wed, 11 Nov 2009 09:23:59 -0500
>> CC: m3devel at elegosoft.com
>> Subject: Re: [M3devel] FreeSlots/lookup slot locking
>>
>>
>>
>>
>>
>> It's not the allocation I worry about.
>> How do you avoid two threads getting the same slot?
>>
>>
>> On 11 Nov 2009, at 01:11, Jay K wrote:
>>
>> Tony:
>>
>>> Also, I am unconvinced that the current implementation of  
>>> AssignSlot can ever
>>> be correct without the critical section. It requires atomic update  
>>> of both
>>> the slots array pointer (with the new slots) *and* the array  
>>> elements. This
>>> requires a proper CS instead of non-blocking synchronization.
>>
>>
>> I don't see it.
>> I could be wrong.
>>
>> The writes are done within a critical section, to avoid racing with  
>> other writers.
>>
>> Writes interact with readers in that:
>>
>>            SUBARRAY (new_slots^, 0, n) := slots^;
>> finish writing to the array elements
>> MemoryBarrier
>>            slots := new_slots;
>>
>>
>> so readers don't see slots unless it has been fully initialized.
>>
>> AssignSlots should also be able to be lock free via  
>> InterlockedCompareExchangePointer.
>>
>>
>> - Jay
>>
>>
>> 		 	   		

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091112/815c78fe/attachment-0002.html>