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

Groups > comp.programming.threads > #2247

A new and very fast concurrent FIFO queue...

Cross-posted to 2 groups.

Show all headers | View raw

Hello,

Chriss Thomasson have not allowed me to make his concurrent FIFO queue
that uses the bakery algorithm available to the Object pascal community,
but don't worry i have thought all the day about that , and i have 
finally been able to invente a new and very fast concurrent FIFO queue 
that is better than the two locks algorithm and that is better than my 
other concurrent FIFO queue that uses a Ticket mechanism on the pop() 
side, my new algorithm and invention eliminates the Ticket mechanism and 
uses only an atomic increment on the push() side, this allows my new 
concurrent FIFO queue to scale even if the number of threads are greater 
than the number of cores, on the pop() side it uses only a CAS and i 
have benchmarked it and it's very fast, it is as fast as the Chriss 
Thomasson concurrent FIFO queue that uses the bakery algorithm,
and you have to know that my new  and very fast concurrent FIFO queue
have more parallelism that the two locks algorithm, so that's a much
better invention than the two locks algorithm.

A very fast concurrent FIFO Queue version 1.0

Authors: Amine Moulay Ramdane

Description:

A very fast concurrent FIFO queue that satisfies many requirements: it 
has more parallelism than the two locks algorithm, it is FIFO fair, it 
minimizes efficiently the cache-coherence traffic and it is energy 
efficient on the pop() side if you set the wait parameter to true in the 
construtor: when there is no items in the queue it will not spin-wait , 
but it will block wait on my SemaMonitor, and when the wait parameter of 
the constructor is set to false it uses only an atomic increment on the 
push() side and a CAS on the pop() side, so it's very fast.

You have 3 options for setting the kind of locks, just look inside 
defines.inc , if you want to set it for my array based lock called 
AMLock just uncomment the option AMLock inside defines.inc, if you want 
to set it for Ticket Spinlock just uncomment the option TicketSpinlock 
,If you want to set it for Spinlock just uncomment the option Spinlock, 
the Spinlock gives better performance under contention it scored 6.4 
millions of transactions per second on my 2.4 GHz Quadcore, the Ticket 
Spinlock option scored 2.6 millions of transactions per second on my 2.4 
GHz Quadcore, the Spinlock scaled even if the number of threads are 
greater than the number of cores, the TicketSpinlock and AMLock don't 
scale when the number of threads are greater than the number of cores, 
the Ticket Spinlock
and scalable AMLock are optimal when the number of threads are equal to 
the number of cores, and when the wait parameter of the constructor is 
false it scales even if the number of threads are greater than the 
number of cores.

The size of the queue must be passed to the constructor and it must be a 
power of 2.

You can download my this new invention and new algorithm of a very fast 
concurrent FIFO queue from:

http://pages.videotron.com/aminer/

Please take a look a the test.pas Object Pascal demo inside the zipfile, 
compile and run it...

Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

Operating Systems: Windows, Mac OSX , Linux , Unix...


Required FPC switches: -O3 -Sd -dFPC -dFreePascal

-Sd for delphi mode....

{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems


Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next | Find similar | Unroll thread

Thread

A new and very fast concurrent FIFO queue... aminer <aminer@toto.net> - 2014-04-24 17:54 -0700

csiph-web