Liblfds, a portable, license-free, lock-free data structure library written in C

Re:Liblfds, a portable, license-free, lock-free data structu... by anarazel on Tuesday May 31, 2016 @02:43PM (#11808961)

> I was thinking of processor support, rather than compiler support. Processor support is the main part of the work - all of the code has to be written with it in mind. Compiler support is much easier; it's just a matter of porting their atomic instrinsics, which basically means writing about a dozen straightfoward macros.

There's actually rather few alive platforms that don't either have ll/sc or cas. The original i386, armv5, sparcv8 (leon IIRC added cas though), pa-risc come to mind (that's the postgres platforms for which fallback atomics support is used). Once you have CAS it's easy to provide fallback implementation for other atomics. It's also not all that hard to provide a "fallback" implementation for atomics, which guarantees atomicity using some locking mechanism.

[ Parent | on HN ]

Re:Liblfds, a portable, license-free, lock-free data structu... by liblfds on Tuesday May 31, 2016 @03:25PM (#11809380)

CAS or LL/SC is straightforward enough (although you have to be aware in your use of them of the differences between processors in terms of whether they lock cache lines, or have exclusive reservation granules, or per logical-core locks, etc, and there is one other minor complication to consider, the presence or absence of contigious double-word CAS or LL/SC), but memory ordering behaviour and support varies significantly across processors.

Intel in that regard are a pain, because they have a mandatory, built-in full memory barrier in their atomic operations. ARM does not, and I see the freelist on ARM running about 25% faster (relatively speaking) than Intel, because of it.

If you look at the first two bars (first is the new GCC atomic instrincs, second the old GCC sync intrinsics) in the one-core chart from these two gunplots, the first gnuplot being ARM32 and the second a Core i5,

http://liblfds.org/pages/images/liblfds710_freelist_push1_th...

You will see on Intel they're level, and on ARM, the atomic bar (the first bar) is about 25% higher.

The new GCC atomic instrincs only issue memory barrier when told to, whereas the old sync instrincs normally (e.g. on most platforms - the docs are a little nebulous) issue memory barriers.

The freelist doesn't need a memory barrier on pop, but on Intel, you get one anyway, and on ARM, with the sync instrincs, you get one anyway. The atomic instrinics also issue on Intel, because Intel forces it to happen, but they do not issue on ARM. I think this gives the 25% performance improvement.

[ Parent | on HN ]