0

I am trying to implement the Michael-Scott FIFO queue from here. I'm unable to implement their solution for the ABA problem. I get this error.

error: incompatible type for argument 1 of '__sync_val_compare_and_swap'

For reference, I am using a linux box to compile this on an intel architecture. If you need more information on my setup please ask.

It seems that sync_val_CAS handles only up to 32 bit values. So when I remove their counter which is used to eliminate the ABA problem, everything compiles and runs fine.

Does anyone know of the relevant 64-bit CAS instruction I should be using here?

As an additional question, are there better (faster) implementations of lock-free fifo queues out there? I came across this by Nir Shavit et al which seems interesting. I am wondering if others have seen similar efforts? Thanks.

Gray
  • 115,027
  • 24
  • 293
  • 354
Boilermaker
  • 31
  • 1
  • 3
  • Solution ABA yields solution CDC or solution BEB – Jay Jun 05 '12 at 17:12
  • Which language are you using? C? –  Jun 08 '12 at 11:11
  • See http://stackoverflow.com/questions/38984153/implement-aba-counter-with-c11-cas/38991835#38991835 for a C++11 pointer + ABA-counter struct with compare-exchange updates but efficient loads of just the pointer (using a union). – Peter Cordes May 20 '17 at 08:50

3 Answers3

0

Assuming gcc, try using the "march" switch. Something like this: -march=i686

There is also the __sync_bool_compare_and_swap. I don't know if its faster or not.

johnnycrash
  • 5,184
  • 5
  • 34
  • 58
  • `-mcx16` is needed for CMPXCHG16B. – Damon Jun 06 '12 at 17:43
  • We use redhat linux on intel and march=i686 is one of switches that worked for us. We just went with it since it acts like a master switch that turned on other good things too. I recall we got the atomic builtins to work work with other switches too. – johnnycrash Jun 06 '12 at 17:49
  • @Damon. Hey is that a 16 byte CAS? Oooooooh cooool. What would be nice would be one that could do two separate 8 byte locations with two separate 8 byte locations at the same time. So we could do a lot more a lot easier. – johnnycrash Jun 06 '12 at 17:52
  • Thanks for the info johnnycrash, it is helpful but not entirely so. setting -march=i686 gives me the error 'error: CPU you selected does not support x86-64 instruction set'. This would seem to indicate that my CPU does not 64-bit instructions, but that is not the case. 'uname -a' confirms this as it contains x86_64 in its output. This page has some more info. http://gcc.gnu.org/onlinedocs/gcc/i386-and-x86_002d64-Options.html. It seems to suggest -march=native will do the trick but no go on that either. fyi I am using an intel xeon proc. What am I missing here? – Boilermaker Jun 06 '12 at 22:05
  • Try my exact settings: -march=i686 -pipe -m32. Are you compiling 64 or 32 bit? I think I remember an issue there where a different switch might have been required. What kind of xenon is it? http://en.wikipedia.org/wiki/Xeon. It doesn't look like every xenon will have the 64 bit capability, but I don't really know. I am pretty sure that -march switch or a switch on that gcc page is what you want. Play around with them. – johnnycrash Jun 06 '12 at 22:26
  • Have you tried, "__sync_bool_compare_and_swap" <-- BOOL. That might be more supported over different platforms. – johnnycrash Jun 06 '12 at 22:31
  • Are you returning the result of the call to __sync_val_compare_and_swap (return __sync_val_compare_and_swap(a,b,c)) or assigning it to a variable? – johnnycrash Jun 06 '12 at 22:35
  • I am on the 'gulftown' X5670 Xeon. sync_bool has the same error as sync_val. gcc version 4.2.3. The result of cmpxchg is part of an if condition. It does not get assigned or returned. I'll keep trying different options to see if anything works. Thanks again. – Boilermaker Jun 07 '12 at 15:58
0

GCC, last I looked in 2009, does not support contigious double-word CAS. I had to implement in-line assembly.

You can find my implemenation of the M&S queue (including in the abstraction layer the assembly implementation of DCAS) and other lock-free data structures here;

http://www.liblfds.org

Briefly looking at the Nir Shavit et al paper, the queue requires Safe Memory Reclaimation, which I suspect you'll need to implement - it won't be built into the queue. An SMR API will be available in the next release (couple weeks).

  • thanks for the lib. It sounds like it would be very helpful. Unfortunately I was unable to use it. It builds fine, producing a liblfds.a file in the /bin dir. I then simply link against this when I compile my program but the linker is unable to find queue_new. I get this error 'undefined reference to `queue_new(queue_state**, unsigned long long)' Its probably something trivial and I feel like a newb asking this but perhaps you can point out what I am doing wrong? I tried 'g++ myprog.cpp path/to/libflds.a' as well as 'g++ -L/path/to/libflds.a -llfds myprog.cpp' – Boilermaker Jun 11 '12 at 22:28
  • Also out of curiosity, have you come across [this](http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/FIFO_Queues.pdf) version of the Michael Scott queue? It looks very interesting, although a bit complex. I will try to implement it in flds once I have things figured out and see if it gives the performance benefits they claim. – Boilermaker Jun 11 '12 at 22:29
  • I think you may be experiencing name decoration. liblfds is a C library - I compile it with gcc. g++ may be trying to link to it as if it were a C++ library. Have a Google about name decoration. –  Jun 12 '12 at 07:28
  • That version of the M&S queue *is* the M&S queue :-) it's implemented in liblfds. It's pretty simple once you get your head around it. –  Jun 12 '12 at 07:29
  • Nope, i tried gcc, same issue. 'gcc myprog.c path/to/libflds.a' should work afaik should it not? – Boilermaker Jun 12 '12 at 14:39
  • I'm suprised. I had thought [this](http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf) was the M&S queue. But its good to know the newer version is implemented, I was curious how it would perform against the original. – Boilermaker Jun 12 '12 at 14:42
  • Odd. I thought when I clicked on that original link (which points currnetly ot the Shavit paper) it went to the web-page with the corrected version of the M&S queue. The two links as they stand are for different algorithms (AFAIK anyway - I've not read the Shavit paper). –  Jun 12 '12 at 15:00
  • Is gcc a link on your system? perhaps it points still to something which compiles by default in C++ mode. –  Jun 12 '12 at 15:04
  • No, thats not an issue either. Could you tell my why the forum on http://www.liblfds.org is closed? Perhaps we could have a better discussion there? – Boilermaker Jun 12 '12 at 18:00
  • Funnily enough I'm just working to fix the forum. It's closed ATM because of automated spam. If you have a phpBB forum and you let people register (with a captcha) you get tons of successful robot registrations which spam the board. I'm just setting up an email-response-required registration. –  Jun 12 '12 at 18:31
  • Huh. You'd think a captcha would take care of that. Please let me know when this is up. It would be great to talk about a few details of liblfds with you. – Boilermaker Jun 12 '12 at 18:43
  • It's up! it's a fresh board, actually, too - I recently moved from a VM with rackmounted.com to Amazon and phpBB didn't play ball being moved over, so I started a new board. You'll be the first member :-) –  Jun 12 '12 at 19:05
0

Lock-free may not be what you want, since lock-free is not necessarily wait-free. If you need a fast thread-safe queue (not lock-free!), then consider using Threading Building Blocks concurrent_queue.

Brad Werth
  • 371
  • 1
  • 10