[M3devel] FreeSlots/lookup slot locking

[jay.krell at cornell.edu]

Right a lock implies a memory barrier and uncontended locks should be  
very fast but it is also seems unfortunate to have any chance of any  
contention in thread create/destroy. Granted it is not likely  
completely avoidable no matter what.

  - Jay (phone)

On Nov 12, 2009, at 9:44 AM, Tony Hosking <hosking at cs.purdue.edu> wrote:

> 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/a5eeafeb/attachment-0002.html>