The Scalable and lock-free first-in-first-out queue implementation of Mark Moir, Ori Shalev, Nir Shavit is patented

[amin...@gmail.com]

Hello..

The Scalable and lock-free first-in-first-out queue implementation of
Mark Moir, Ori Shalev, Nir Shavit is patented:

Here is there patent:

http://www.google.sr/patents/US7836228

And here is there paper:

http://people.csail.mit.edu/shanir/publications/SPAA2005.pdf


But my scalable FIFO queues that i have just invented are freewares , and i think they are better:

This is Scalable FIFO queues version 1.0, this is the windows version, the Linux version and C++ version for Windows and Linux are coming..

Those are two scalable FIFO queues, one is bounded and the other unbounded, they use a distributed technic over many FIFO queues and they use scalable counting networks so that to be scalable, you can test them on NUMA systems to notice that they are truly scalable.

And counting networks are truly scalable and are a special type of balancer networks which count.

Look at my port to Delphi and FreePascal of scalable counting networks here:

https://sites.google.com/site/aminer68/scalable-counting-networks-for-delphi-and-freepascal

You can download my Scalable FIFO queues from:

https://sites.google.com/site/aminer68/scalable-fifo-queues



Thank you,
Amine Moulay Ramdane.

[Chris M. Thomasson]

Already been there, done that. Created networks of
single-producer/consumers queues, along with networks of
multi-producer/consumers queues, all in between. Even wrote about some
of them in the past over on comp.programming.threads. Now, this actually
can be quite scalable indeed, especially for certain types of workloads.
Have not really looked at your code yet, sorry. Will do, at first glance
I see a lot of:

{$IFDEF TicketSpinlock}
lock1,lock2:TTicketSpinlock;
{$ENDIF TicketSpinlock}
{$IFDEF AMLock}
lock1,lock2:TALOCK;
{$ENDIF AMLock}
{$IFDEF Spinlock}

How can that be lock-free? Fwiw, check this out:

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


Also, why do you have an mfence in:

procedure TTicketSpinLock.Leave;

begin
mfence;
inc(FCount3^.FCount3);
//sleep(0);
end;

Why would you do that? Why sleep(0)? We only really need release
semantics here.

Also, why are you using Intel TBB binaries? You should add that to your
README?

[Chris M. Thomasson]

At you put the membar in the right place wrt release. However, a mfence
should not be needed to release a spinlock in x86 because, non-temporal
stores aside for a moment, normal atomic stores already have implied
release semantics in x86. An atomic store using a release barrier in x86
does not need any explicit membar or LOCK'ed RMW instruction.

Now, on something like SPARC in RMO mode, well, you better put in a
#LoadStore | #StoreStore for release, and have a matching #LoadStore |
#LoadLoad for the damn acquire part of the spinlock.

[Intelli2]

Hello,


My scalable FIFO queues use "Scalable" counting networks etc.

https://github.com/stephentu/counting-networks

[Intelli2]

Hello,


Read the following (the counting network is truly scalable, please look
at the graph inside the paper):

http://people.csail.mit.edu/shanir/publications/HLS.pdf

My scalable FIFO queues use "Scalable" counting networks etc.

https://github.com/stephentu/counting-networks

[Chris M. Thomasson]

On 10/31/2017 5:45 AM, Intelli2 wrote:
> Hello,
>
>
> Read the following (the counting network is truly scalable, please look
> at the graph inside the paper):
>
> http://people.csail.mit.edu/shanir/publications/HLS.pdf
>
> My scalable FIFO queues  use "Scalable" counting networks etc.
>
> https://github.com/stephentu/counting-networks

That can most definitely be a decent way to set them up. Fwiw, some
experimental fractal networks can work as well. Forests, ect...

On a side note wrt building a network from the ground up, actually, I
can experimentally simulate some quasi-pseudo "fairly natural networks"
via vector fields and DLA, here is a crude dynamic online simulation:

http://funwithfractals.atspace.cc/ct_fdla_anime_dynamic_test

You can add new attractors in real time by clicking within the square.
Let it run for around 5 minutes, click on some points in the square,
then let it run for another 10 minutes...

A very helpful, and smart friend of mine over on comp.lang.javascript
ported it to ES6:

https://groups.google.com/d/topic/comp.lang.javascript/vza2sChC2MY/discussion
(some more context...)

And put it up on CodePen:

https://codepen.io/mlhaufe/project/editor/XNGeEv

Fwiw, I also have some very crude C++ code for the basic process here:

https://github.com/ChrisMThomasson/CT_fieldDLA/blob/master/cairo_test_penrose/ct_field.hpp

uses Cairo graphics lib:

https://cairographics.org/

and the very nice:

https://glm.g-truc.net/0.9.2/api/a00001.html


Anyway, The field DLA can build a fairly efficient network wrt the
starting conditions, and does pretty good with any new mutations...

Now, for fun, we can insert the most compatible queue:

Single-Producer Single-Consumer (SPSC)
Multi-Producer Single-Consumer (MPSC)
Single-Producer Multi-Consumer (SPMC)
Multi-Producer Multi-Consumer (MPMC)

For every node in the dynamically "growing and evolving" DLA cluster.

> Thank you,
> Amine Moulay Ramdane.

Okay, so Intelli2 is you right? For some reason I thought the first
response was from:

https://github.com/stephentu posting as Intelli2.

;^/

[Intelli2]

I think you are a smart person, and you have understood my work.

[Chris M. Thomasson]

Thank you. :^)