6 ms·

> No. All versions of the library can concurrently be included and linked against. The reason for this is so that any code which using an existing version of th

> No. All versions of the library can concurrently be included and linked against. The reason for this is so that any code which using an existing version of the library does not have to be modified at all - and so does not need to be revalidated - when a new version is published. This is what having consistent interfaces is for. Keep your interface consistent, not your implementation. This is also a strong argument for not releasing code and advertising it on HN if it's not mature. > The add-onlys were thrown together in a week or so many months ago, just to get those classes of data strutures out there, as writing the full versions of them will take some time. There is in fact for eaxmple a full, balanced binary tree, in the literature. That's on the list! Which begs the question why you included immature implementations in your library. > That's a bit unfair. The library is eight years old now. It's not a flash in the pan. Which doesn't negate the criticism in any way. > It's actually as portable as it is possible for a lock-free library to be. Only a fairly few platforms provide atomic instrinsics. As far as GCC provides support, they are all suppoted, and I believe GCC supports all of them. There are working examples (ConcurrencyKit) of lock-free data structures that target more architectures and more compilers, so "It's actually as portable as it is possible for a lock-free library to be." is provably false.

liblfds 10y ago
> This is what having consistent interfaces is for. Keep > your interface consistent, not your implementation. I have to disagree. If the underlying library used has changed, then the code which uses the library has to be revalidated. You cannot assume it simply continues to work - to do so is to fully rely on the library provider getting it right, introducing no bugs, or anything unexpected. This is not viable for serious projects. The and the ONLY way in which existing code does not have to be revalidated is if it is completely and wholly unchanged. > Which begs the question why you included immature implementations in your library. There's nothing immature about them, and I don't know why you are saying there is. They were written about a year ago and writing them means also writing their test suite, which they pass. The choices you disagree with in the library seem to be being taken to justify the charge of "code immaturity". Those choices may be right, or they may be wrong, and so could potentially be mistakes, but this is an entirely different matter to maturity. > There are working examples (ConcurrencyKit) of lock-free data > structures that target more architectures and more compilers, so > "It's actually as portable as it is possible for a lock-free > library to be." is provably false. 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.
- anarazel 10y ago
  > 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.
  - liblfds 10y ago
    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_then_pop1_smp_Raspberry%20Pi%202%20Model%20B%20%28ARM32%29.1200x1800.png http://liblfds.org/pages/images/liblfds710_freelist_push1_th... http://liblfds.org/pages/images/liblfds710_freelist_push1_then_pop1_numa_Core%20i5%20%28x64%29.1200x1800.png 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.
Joky 10y ago
> This is also a strong argument for not releasing code and advertising it on HN if it's not mature. I'm not totally convinced about that, cf: https://en.wikipedia.org/wiki/Release_early,_release_often https://en.wikipedia.org/wiki/Release_early,_release_often
Joky 10y ago
> This is also a strong argument for not releasing code and advertising it on HN if it's not mature. I'm not totally convinced about that, cf: https://en.wikipedia.org/wiki/Release_early,_release_often https://en.wikipedia.org/wiki/Release_early,_release_often
Joky 10y ago
> This is also a strong argument for not releasing code and advertising it on HN if it's not mature. I'm not totally convinced about that, cf: https://en.wikipedia.org/wiki/Release_early,_release_often https://en.wikipedia.org/wiki/Release_early,_release_often

liblfds 10y ago

> This is what having consistent interfaces is for. Keep > your interface consistent, not your implementation. I have to disagree. If the underlying library used has changed, then the code which uses the library has to be revalidated. You cannot assume it simply continues to work - to do so is to fully rely on the library provider getting it right, introducing no bugs, or anything unexpected. This is not viable for serious projects. The and the ONLY way in which existing code does not have to be revalidated is if it is completely and wholly unchanged. > Which begs the question why you included immature implementations in your library. There's nothing immature about them, and I don't know why you are saying there is. They were written about a year ago and writing them means also writing their test suite, which they pass. The choices you disagree with in the library seem to be being taken to justify the charge of "code immaturity". Those choices may be right, or they may be wrong, and so could potentially be mistakes, but this is an entirely different matter to maturity. > There are working examples (ConcurrencyKit) of lock-free data > structures that target more architectures and more compilers, so > "It's actually as portable as it is possible for a lock-free > library to be." is provably false. 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.

anarazel 10y ago
> 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.
- liblfds 10y ago
  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_then_pop1_smp_Raspberry%20Pi%202%20Model%20B%20%28ARM32%29.1200x1800.png http://liblfds.org/pages/images/liblfds710_freelist_push1_th... http://liblfds.org/pages/images/liblfds710_freelist_push1_then_pop1_numa_Core%20i5%20%28x64%29.1200x1800.png 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.

Joky 10y ago

> This is also a strong argument for not releasing code and advertising it on HN if it's not mature. I'm not totally convinced about that, cf: https://en.wikipedia.org/wiki/Release_early,_release_often https://en.wikipedia.org/wiki/Release_early,_release_often

Joky 10y ago