Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3793 > unrolled thread

About lockfree queues ...

Back to article view | Back to comp.programming

Contents

  About lockfree queues ... aminer <aminer@toto.net> - 2013-09-24 19:16 -0700
    Re: About lockfree queues ... aminer <aminer@toto.net> - 2013-09-24 21:09 -0700
    Re: About lockfree queues ... aminer <aminer@toto.net> - 2013-09-24 21:34 -0700

#3793 — About lockfree queues ...

Hello,


I have wrote before this:

"I have come to an interresting subject about lockfree queues,
if you take a look at those lockfree queues, like in transactional 
memory, if the data have changed those lockfree queue retries and loop 
again, but this (lockfree) mechanism generates a lot of cache-coherence 
traffic, so i will not advice this lockfree mechanism, so how
can we do it ? you can take a look at the MCS queue Lock , i
think they are doing it like a waitfree linklist that doesn't spin and
that reduces a lot the cache-coherence traffic, other than that
if your memory manager is not optimal and uses a lockfree mechanism and 
generates a lot cache-coherence traffic, so you have to use a freelist 
to lower the cache coherence traffic."


But you have to know even that you are using spin waits inside lockfree 
algorithms that genrates a lot of cache-coherence traffic , you have
to know that you can avoid this problem and make your lockfree queue 
more efficient by adding an exponential backoff to you lockfree 
mechanism using a PAUSE asm instruction followed by a Sleep(0) to not 
freeze the computer and this way , like with the Spinlock, it will 
reduce the cache-coherence traffic and make your lockfree queue more 
efficient,.




Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#3794

Hello,

I have come to a more interresting subject, it's the
exponential backoff mechanism that we use inside the Spinlock,
this backoff mechanism lower the contention, but i was thinking more
about it, and what does we mean by lower the contention ?
when you are spining inside a Spinlock you are testing also
for a flag/variable, but when you test for this variable to
equal for example 1 to be able to enter the locked region
you are generating cache-coherency traffic, cause when a thread
leaves a locked region it will set the flag to 1 for example,
but when the thread sets to 1 the variable , the variable is not
in the L2 cache of others threads, so the variable must be
transfered to the other threads and this is costly/expensive
and this generate a lot of cache-coherence  traffic, but
the problem with the Spinlock is that when a lot of cache-coherence
is generated this will slow the threads that enters the Spinlock
and slows the threads globally in your computer, so this will slow the 
threads , now there is still a problem if we use a Sleep() function 
inside the backoff mechanism this will slow a lot the threads, so as i 
told you before the solution is to use the PAUSE asm instruction inside 
the backoff mechanism followed by a sleep(0), but about the lockfree 
queues , even though a lot cache-coherence traffic is generated by the 
threads when there is high contention , this will not slow the threads
inside the CAS , as in the case of the Spinlock, cause the CAS uses a 
LOCK asm instruction that lock the Bus, so this is better than the 
Spinlock, but even though it will not slow the thread inside the CAS
you have to use a PAUSE instruction inside an exponential backoff 
mechanism to not slow globally the other threads and applications on 
your computer when there is high contention.



Thank you,
Amine Moulay Ramdane,








On 9/24/2013 7:16 PM, aminer wrote:
> Hello,
>
>
> I have wrote before this:
>
> "I have come to an interresting subject about lockfree queues,
> if you take a look at those lockfree queues, like in transactional
> memory, if the data have changed those lockfree queue retries and loop
> again, but this (lockfree) mechanism generates a lot of cache-coherence
> traffic, so i will not advice this lockfree mechanism, so how
> can we do it ? you can take a look at the MCS queue Lock , i
> think they are doing it like a waitfree linklist that doesn't spin and
> that reduces a lot the cache-coherence traffic, other than that
> if your memory manager is not optimal and uses a lockfree mechanism and
> generates a lot cache-coherence traffic, so you have to use a freelist
> to lower the cache coherence traffic."
>
>
> But you have to know even that you are using spin waits inside lockfree
> algorithms that genrates a lot of cache-coherence traffic , you have
> to know that you can avoid this problem and make your lockfree queue
> more efficient by adding an exponential backoff to you lockfree
> mechanism using a PAUSE asm instruction followed by a Sleep(0) to not
> freeze the computer and this way , like with the Spinlock, it will
> reduce the cache-coherence traffic and make your lockfree queue more
> efficient,.
>
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>

[toc] | [prev] | [next] | [standalone]

#3795

Hello,

That's not the end of the story, there is still a problem
with the Spinlock with an exponential backoff, i think you have
to undertand something important, the backoff mechanism has
to be set correctly to lower the cache-coherence traffic,
but how to set it correctly ? cause the locked region has
a variable size , so of for example your locked region
takes much more time and it's bigger you have to set the
backoff mechanism with the PAUSE asm instruction(followed by a
sleep(0)) correctly so that it will be bigger than  what it
takes to execute the locked region , so this is the problem with
the Spinlocks with backoff , so how can we you do that efficiently?
that's the big question ! and i think it's not easy to do it, for
the lockfree queues, the time to execute a CAS is already known,
so you can set the backoff mechanism of the lockfree queue correctly
so that it become efficient under high contention.



Thank you,
Amine Moulay Ramdane.


















On 9/24/2013 7:16 PM, aminer wrote:
> Hello,
>
>
> I have wrote before this:
>
> "I have come to an interresting subject about lockfree queues,
> if you take a look at those lockfree queues, like in transactional
> memory, if the data have changed those lockfree queue retries and loop
> again, but this (lockfree) mechanism generates a lot of cache-coherence
> traffic, so i will not advice this lockfree mechanism, so how
> can we do it ? you can take a look at the MCS queue Lock , i
> think they are doing it like a waitfree linklist that doesn't spin and
> that reduces a lot the cache-coherence traffic, other than that
> if your memory manager is not optimal and uses a lockfree mechanism and
> generates a lot cache-coherence traffic, so you have to use a freelist
> to lower the cache coherence traffic."
>
>
> But you have to know even that you are using spin waits inside lockfree
> algorithms that genrates a lot of cache-coherence traffic , you have
> to know that you can avoid this problem and make your lockfree queue
> more efficient by adding an exponential backoff to you lockfree
> mechanism using a PAUSE asm instruction followed by a Sleep(0) to not
> freeze the computer and this way , like with the Spinlock, it will
> reduce the cache-coherence traffic and make your lockfree queue more
> efficient,.
>
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web