Liblfds: portable lock-free data structures in C.

http://www.liblfds.org/

36 13 16 years ago

It'd be interesting to see these compared to locking versions. The benchmarks, particularly on windows, show that the library is young and still needs some algorithmic tweaks, but in any case it's great that there's an open source implementation of algorithms that have a reputation of being difficult to get correct.

liblfds-admin5• 16 years ago

Presumably the benchmarks would indicate immaturity by being slow; but it's not obvious what the benchmarks can be compared with. Are there other implementations of the same algorithm, with identical benchmarks?

liblfds-admin5• 16 years ago

That's a good suggestion; I can make locking versions of the same benchmarks. I'll add that to the list...

martincmartin• 16 years ago

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?

papaf• 16 years ago

The java JDK lockless queue is also compare and swap. I don't know the reasoning behind it though.

dumael• 16 years ago

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.

jasonwatkinspdx3• 16 years ago

How can one implement a lock on x86 without cas/ll-sc? Lamport's Bakery?

liblfds-admin5• 16 years ago

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.

e40• 16 years ago

See "Wikipedia" for documentation? I think they mean "the wiki".

jasonwatkinspdx3• 16 years ago

Yeah, and I find the way they load the documentation and blog in a frame quite annoying.

liblfds-admin5• 16 years ago

I wanted it to be a seamless page, but the forum and wiki emit full-page XHTML/HTML - not something you can emit into a placeholder element.

liblfds-admin5• 16 years ago

Will fix that...

Liblfds: portable lock-free data structures in C.

Related Stories