News for hackers. Stuff that matters.
Re:Liblfds: portable lock-free data structures in C. by martincmartin on Friday October 01, 2010 @07:30AM (#1746693)
According to the paper for their queue:

http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues....

It uses either compare_and_swap or load_linked/store_conditional. I thought compare_and_swap had a horrible (i.e. very slow) implementation on x86. Any idea whether load_linked/store_conditional is any better?

Re:Liblfds: portable lock-free data structures in C. by dumael on Friday October 01, 2010 @11:02AM (#1747236)
CAS is slow because it acts as a serializing instruction. If you depend on success or fail the instructions after it have to wait until it has been resolved. Also, the update has to be pushed out to the cache at least.

So yes, slow but otherwise it would be of no use.

load_linked and store_conditional are not much better. Depending on implementation they can spuriously fail because something poked the cache, there was memory traffic etc.

Re:Liblfds: portable lock-free data structures in C. by jasonwatkinspdx on Friday October 01, 2010 @03:33PM (#1748287)
How can one implement a lock on x86 without cas/ll-sc? Lamport's Bakery?
Re:Liblfds: portable lock-free data structures in C. by lzimm on Friday October 01, 2010 @06:51PM (#1749093)
so zen: cas slow, locks slower.
Re:Liblfds: portable lock-free data structures in C. by liblfds-admin on Sunday October 03, 2010 @06:30PM (#1753818)
CAS on platforms which provide CAS for lock-free (x86/x64), LL/SC on platforms which provide LL/SC for lock-free (ARM).

AFAIK, platforms provide one or the other; not both. So you have to use what you're given.

Re:Liblfds: portable lock-free data structures in C. by papaf on Friday October 01, 2010 @10:12AM (#1747059)
The java JDK lockless queue is also compare and swap. I don't know the reasoning behind it though.