Lock-free ParallelQueue version 1.1 ...


Hello all,


My Lock-free ParallelQueue algorithm have been updated
- my new algorithm avoids false sharing - , the new version
have scored 17 millions of pop() transactions per second
- the old score was 7 millions - on an Intel Core 2 Quad Q6600


There are three ways to reduce lock contention:

1- Reduce the duration for which locks are held
2- Reduce the frequency with which locks are requested

or

3- Replace exclusive locks with coordination mechanisms that
permit greater concurrency.

With low , moderate AND high contention, my ParallelQueue algorithm
offers better scalability - and i am using it inside my Thread Pool
Engine -


Because my lock-free ParallelQueue algorithm uses a hash based
method - and lock striping - and using just a LockedInc() , so, i am
REDUCING the duration for which locks are held AND REDUCING the
frequency with which locks are requested, hence i am REDUCING A LOT
the contention, so it's very efficient.

And i can state the following law or theorem:


[1] If there is LESS contention THEN the algorithm will scale
better.
Due to the fact that S (the serial part) become smaller with less
contention ,
and as N become bigger, the result - the speed of the program/
algorithm...
- of the Amdahl's equation 1/(S+(P/N)) become bigger.

So, since my lock-free ParallelQueue algorithm is REDUCING A LOT
the contention, it's very efficient and it scales well..

Also, i can state another law or theorem like this:


[2] If there is false sharing THEN the algorithm will not scale
well. Due to
the fact that S (the serial part) of the Amdahl's equation 1/(S+
(P/N)) will
become bigger, so, this is not good for scalability.

It's why i am also avoiding false sharing in my lock-free
ParallelQueue algorithm.

So, my new lock-free ParallelQueue algorithm reduces a lot the
contention
and avoids false sharing, it's why it scored 17 millions of pop()
transactions
per second... better than flqueue and RingBuffer.

Please look at the benchmarks here:

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

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



Sincerely,
Amine Moulay Ramdane.


.

Relevant Pages

  • Lock-free ParallelQueue version 1.1 ...
    ... 2- Reduce the frequency with which locks are requested ... With low, moderate AND high contention, my ParallelQueue algorithm ... Because my lock-free ParallelQueue algorithm uses a hash based ...
    (alt.comp.lang.borland-delphi)
  • Lock-free ParallelQueue version 1.1 ...
    ... 2- Reduce the frequency with which locks are requested ... With low, moderate AND high contention, my ParallelQueue algorithm ... Because my lock-free ParallelQueue algorithm uses a hash based ...
    (comp.programming.threads)
  • Lock-free ParallelQueue version 1.1 ...
    ... 2- Reduce the frequency with which locks are requested ... With low, moderate AND high contention, my ParallelQueue algorithm ... Because my lock-free ParallelQueue algorithm uses a hash based ...
    (comp.lang.ada)
  • Lock-free ParallelQueue 1.1 ...
    ... 2- Reduce the frequency with which locks are requested ... With low, moderate AND high contention, my ParallelQueue algorithm ... Because my lock-free ParallelQueue algorithm uses a hash based method ...
    (comp.parallel)