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

Groups > comp.programming.threads > #2153 > unrolled thread

Bakery algorithm

Back to article view | Back to comp.programming.threads

Contents

  Bakery algorithm aminer <aminer@toto.net> - 2014-04-13 19:28 -0700
    Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:44 -0700
      Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-13 19:46 -0700
        Re: Bakery algorithm "Chris M. Thomasson" <no@spam.invalid> - 2014-04-14 13:49 -0700

#2153 — Bakery algorithm

Hello,

Here is the Bakery algorithm of the FIFO queue of Chriss Thomasson

==

{ Queue Ops }
procedure producer(state:long);
     var ver:longword;
     var c:^cell;
begin
     ver := ATOMIC_XADD(@head, 1);
     c := @cells[ver and (N - 1)];
     while ATOMIC_LOAD(@c^.ver) <> ver do backoff;
     c^.state := state;
     ATOMIC_STORE(@c^.ver, ver + 1);
end;


function consumer():long;
     var ver:longword;
     var c:^cell;
begin
     ver := ATOMIC_XADD(@tail, 1);
     c := @cells[ver and (N - 1)];
     while ATOMIC_LOAD(@c^.ver) <> ver + 1 do backoff;
     consumer := c^.state;
     ATOMIC_STORE(@c^.ver, ver + N);
end;


===


As you have noticed if i want to use this FIFO queue
inside my scalable FIFO fair lock, i don't need synchronization
on the pop() side , so even if i delete the  ATOMIC_XADD()
inside the consumer() method there will still be two cache-lines 
transfers ionside the consumer methoid,  one when you want to increment 
the "tail" and another one since the "@c^.ver" is changed every time and 
it will incur a cache-line transfer , so it will be slower than my array 
based queue and this has been confirmed on my benchmarks.




Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#2158

> "aminer"  wrote in message news:lif6if$gdp$1@news.albasani.net... Hello,
> Here is the Bakery algorithm of the FIFO queue of Chriss Thomasson

[...]

I came up with this algorithm as a tweak from Dmitry Vyukov's original 
beauty:

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue


Here is some further context, and a complete implementation in the form
of a unit test that runs under Relacy Race Detector.

https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion

AFAICT, its about as good as one can get wrt atomic operations on a MPMC 
queue.

No CAS, only a single XADD per side... Can't get better for a general 
purpose MPMC
100% fair and strict FIFO data-structure. 

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

#2159

"Chris M. Thomasson"  wrote in message 
news:lifi20$joi$1@speranza.aioe.org...

> "aminer"  wrote in message news:lif6if$gdp$1@news.albasani.net... Hello,
> Here is the Bakery algorithm of the FIFO queue of Chriss Thomasson

[...]

I came up with this algorithm as a tweak from Dmitry Vyukov's original
beauty:

http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue


Here is some further context, and a complete implementation in the form
of a unit test that runs under Relacy Race Detector.

https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion

AFAICT, its about as good as one can get wrt atomic operations on a MPMC
queue.

No CAS, only a single XADD per side... Can't get better for a general
purpose MPMC 100% fair and strict FIFO data-structure. 

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

#2167

> "Chris M. Thomasson"  wrote in message 
> news:lifi7d$k7v$1@speranza.aioe.org... "Chris M. Thomasson"  wrote in 
> message news:lifi20$joi$1@speranza.aioe.org...
> > "aminer"  wrote in message news:lif6if$gdp$1@news.albasani.net... Hello,
> > Here is the Bakery algorithm of the FIFO queue of Chriss Thomasson
> [...]
> I came up with this algorithm as a tweak from Dmitry Vyukov's original
> beauty:
> http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue
> [...]
> https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion

BTW aminer, exactly how are you implementing my bakery algorithm wrt
data-structure padding and alignment? Remember, if you allocate a bunch
of data structures, each one should be padded to a cache line multiple, and
the base address of the memory for said data-structures should be aligned on 
a
cache line boundary. This helps avoid the evil false sharing demon from
injecting its wicked artifacts into the performance factors!

;^)



Also, exactly how you implementing the conditional blocking? I am using
a distributing a simple eventcount with a so-called waitbit, similar to a
futex.


As for the dynamic node based MPMC, well, it requires some form of object
lifetime management for the nodes. Read-copy update, garbage collection, 
PDR,
detecting Page faults, SHE handler, or segfault handler. So, if you did 
implement it,
how did you handle the lifetime of the nodes? 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web