3 ms·

> This is what having consistent interfaces is for. Keep > your interface consistent, not your implementation. I have to disagree. If the underlying library

by 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.
devishard 10y ago
> 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. And when I integrate a new release, how do I verify that you didn't accidentally change one of the older numbered versions of your code? I'm going to have to test either way when I integrate a new version of your code, so I might as well get any performance improvements or whatever you introduced into the implementation. Versioning your interface does not solve the problem you claim it does. > 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. I am saying they're immature because you said they were immature. You said, "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." > I was thinking of processor support, rather than compiler support. I was also thinking of both processor support--you're the only one who mentioned any compilers. Given this supports only 2 processors and ConcurrencyKit supports 5, your claim that this is "actually as portable as it is possible for a lock-free library to be" is still provably wrong.
- liblfds 10y ago
  > And when I integrate a new release, how do I verify that > you didn't accidentally change one of the older numbered > versions of your code? They're only released once. No release is changed after its release. Once it's out, it's out. The archive is never touched again. When a release is made, the source code is exported, archived and uploaded to the library web-site. To accidentally change that code, I would have to accidentally repeat that manual process. It's the same with github - I actually use SVN at home, and I make a new repos per release and upload the code, once, to that repos. Github is a release only, write-once source control system, for me. > I'm going to have to test either way when I integrate a new version of your code Well, now I'm confused. If that's so, what's the problem? you keep using the old code, it's not changed, either the API or the library binary, so you don't have to test that; and for any new code, you can use the new release version. To the extent the APIs are unchanged, moving fully from one release to another is a matter of issuing a global search-and-replace for the string "liblfdsNNN" to "liblfdsMMM". > Given this supports only 2 processors and ConcurrencyKit > supports 5 The library supports on Linux almost every processor GCC offers atomic instrincs for - ARM32, IA64, POWERPC32/64, SPARC32/64, MIPS32/64, x64 and x86. I'm pretty sure the library does not support Alpha, however. Of those platforms, I only have access to actual hardware for ARM32, MIPS32 and x64, so only those platforms actually have the test code compiled and run and being seen to pass. On Windows, support is provided for ARM32, x86, x64 and IA64. Again, of these, I only have access to x64.

by liblfds 10y ago

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.

devishard 10y ago

> 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. And when I integrate a new release, how do I verify that you didn't accidentally change one of the older numbered versions of your code? I'm going to have to test either way when I integrate a new version of your code, so I might as well get any performance improvements or whatever you introduced into the implementation. Versioning your interface does not solve the problem you claim it does. > 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. I am saying they're immature because you said they were immature. You said, "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." > I was thinking of processor support, rather than compiler support. I was also thinking of both processor support--you're the only one who mentioned any compilers. Given this supports only 2 processors and ConcurrencyKit supports 5, your claim that this is "actually as portable as it is possible for a lock-free library to be" is still provably wrong.

liblfds 10y ago
> And when I integrate a new release, how do I verify that > you didn't accidentally change one of the older numbered > versions of your code? They're only released once. No release is changed after its release. Once it's out, it's out. The archive is never touched again. When a release is made, the source code is exported, archived and uploaded to the library web-site. To accidentally change that code, I would have to accidentally repeat that manual process. It's the same with github - I actually use SVN at home, and I make a new repos per release and upload the code, once, to that repos. Github is a release only, write-once source control system, for me. > I'm going to have to test either way when I integrate a new version of your code Well, now I'm confused. If that's so, what's the problem? you keep using the old code, it's not changed, either the API or the library binary, so you don't have to test that; and for any new code, you can use the new release version. To the extent the APIs are unchanged, moving fully from one release to another is a matter of issuing a global search-and-replace for the string "liblfdsNNN" to "liblfdsMMM". > Given this supports only 2 processors and ConcurrencyKit > supports 5 The library supports on Linux almost every processor GCC offers atomic instrincs for - ARM32, IA64, POWERPC32/64, SPARC32/64, MIPS32/64, x64 and x86. I'm pretty sure the library does not support Alpha, however. Of those platforms, I only have access to actual hardware for ARM32, MIPS32 and x64, so only those platforms actually have the test code compiled and run and being seen to pass. On Windows, support is provided for ARM32, x86, x64 and IA64. Again, of these, I only have access to x64.