Use lockless queue

[soumagne]

Currently mercury_queue requires lock/unlock on push/pop operations. We could make use of atomics to add a lockless queue. For reference: http://stackoverflow.com/questions/6089029/lock-free-queue

[JohnPJenkins]

Should note that we specifically need a multi-producer, multi-consumer queue under the current progress/trigger model.

[soumagne]

Just for reference:

• http://www.boost.org/doc/libs/1_61_0/doc/html/lockfree.html
• http://www.boost.org/doc/libs/1_61_0/doc/html/boost/lockfree/queue.html is a multi-producer multi-consumer queue
• http://natsys-lab.blogspot.com/2013/05/lock-free-multi-producer-multi-consumer.html

[soumagne]

I think that eventually we could restrict ourselves to multi-producer single consumer queues, plugins may do different things but in general the only place where we dequeue is in HG_Trigger() or NA_Trigger(). So far we never allow multiple threads to call trigger at the same time...

[roblatham00]

Halim Amer's Izem project (https://github.com/pmodels/izem) might do this for us -- and as with argobots, you get someone else to fix bugs.

[soumagne]

Thanks for the pointer, I didn't know about it. Looked at it quickly, not sure which queue models are which though. They also do the same mistake as us before, i.e. they do an allocation on every insert, bad start :)

[roblatham00]

good news! halim intends to either remove the mallocs or provide malloc-free routines. https://github.com/pmodels/izem/issues/8

[halimamer]

@soumagne: one starts with simple :) Apart from our plan to fix the double allocation issue, the MPMC lock-free queue that is currently working is Micheal Scott's nonblocking queue (at https://github.com/pmodels/izem/blob/master/src/queue/zm_msqueue.c). I know it is one of the worst in the literature and we plan to port faster ones in the near future. I cannot estimate when this feature will be available though.

[soumagne]

@roblatham00 thanks for the follow-up. @halimamer :) yes we did the same. OK. I'm also thinking a multi-producer single consumer queue might be sufficient for the time being, assuming we only have one thread at the same time going into trigger on a specific context. Do you have a queue for that as well? Main issue is ABA problem but we could probably be fine with a bounded queue.

[halimamer]

Working on mpsc queues is part of our high priority items. We have what seems to be a working prototype called SWPQueue at https://github.com/pmodels/izem/blob/master/src/queue/zm_swpqueue.c. I am being defensive because we are still working on the theoretical proof for that queue. It is unbounded, uses only a SWAP operation on the critical path of enqueues, but still suffers the double allocation problem. In practice, that queue worked fine without any special memory reclamation problem. Once we have the theoretical proof, if memory reclamation problems occur, we have at least a hazard pointers infrastructure in place for a quick fix. You are welcome to try out this queue; it should be significantly faster than the MSQueue (Michael Scott's).

[soumagne]

Fixed in f49751f92a42b274f636a770721fa9cf490d2009 and c0afa142ac464f629480e4dce1343397af5b9335