How does ConcurrencyKit compare to this? I've used concurrencykit a bit, and it's great. The only problem I have is that sometimes the documentation is lacking.
I found this a while ago but the compatability matrix turned me away very quickly. This is one of the least portable C libraries for data structures I've ever seen.
Yeah, they refer to it as "portable", but then go on to show that they haven't tested it on anything except x64 and ARM32; not only that, but it also depends on what you use to compile it (kbuild, GNU make, etc.).
This library claims to be license-free, but some of the modules are documented otherwise. For example, the "Queue (bounded, many-producer, many-consumer)" module (http://liblfds.org/mediawiki/index.php?title=r7.1.0:Queue_%2...) has the following license note:
"Dmitry Vyukov granted email permission for the idea to be used and implemented in liblfds, under the MIT license."
Similarly, the unbounded queue has an "unclear" license, rather than the "standard liblfds" license.
It's not clear to me how the library can be license-free when one component is very clearly MIT-licensed, and when others have no clear license status. I would be quite cautious using this code in production or in a lawyer-sensitive environment until the licenses are clarified.
When the library was initially released, back in 2009, and until recently, it's been license-free, or at least thought to be. Recently with the addition of Dmitry's design, and a closer analysis of the possible licensing terms, the picture has become more nuanced - hence the inclusion of per-data structure information regarding licensing and what happened is of course classic computing - there's now a regression bug in the one line description of the library! Where the "license-free" term has been in the one-line description for so long, it was overlooked.
In many jurisdictions there is no concept of public domain, and thus declaring your work as public domain has no effect in many parts of the world.
The author granted a license for all Creative Commons licenses, which includes CC-Zero (public domain where that's possible, the closest possible equivalent everywhere else). That's the real part that makes the rest of the section unnessesary.
Chaff? For a project where one has total control, yes. When one has to get approval and deal with a specific list of approved licenses (which may not include one's particular favourite, no matter how sensible it seems to oneself), then no. It is appreciated.
Can someone comment on lock free data structures vs lock free algorithms. My understanding is that there isn't as much of a symbiosis between the two as there are with other data structures and algorithms. Is it easier to implement a lock free data structure than a lock free algorithm?
I may be wrong, but I think an algorithm could only be considered in terms of locking or lock-free if multiple threads were through that algorithm performing work on the same data at the same time (and so potentially running into each other, in ways which would break the work being done).
I've seen server code like that - all the time of course - but the only algorithm I can think of which has that property is a PRNG, and that can normally be implemented on a per-thread basis, each thread holding its own single-threaded PRNG.
This probably reflects my lack of work with algorthims. Could you give an example?
on other cores. That is one hell of a #define, and it's not even clear from the name what it's doing. It seems like "LFDS710_MISC_SYNC_INITS" or something along those lines would be clearer and easier to remember.
Do you even understand the significance of "lock-free" in the title here? Do you have some basis to think that the weaknesses of the data structures, like unbalanced trees and add-only collections, can be remedied without using locks? If you do then that would be an interesting criticism, but as it is it looks like you just opened the page, looked around for a few things to criticize, and then wrote this sour, shallow, dismissive comment.
> This looks like it was written by a 16 year-old student who heard "lock free", and went "cool, I'll write a library!"
Nothing wrong with that, though. In fact, that's great.
Word to the 16-year-olds (or any-year-olds) doing that: put a disclaimer in your README to avoid this kind of reply being top comment in a HN thread about your work :)
> The documentation is viewed via an embedded frame. So you
> can't save URLs to the documentation. This is a known bad
> practice for web sites.
Yes and no. The site currently is arranged with a set of tabs on the left and a frame on the right. It had to be a frame because some of the web-based apps, such as the mediawiki used for documentation, generate output encapsulated in the "<HTML>" tag. As such, their output cannot be captured and placed into a div; it has to go into its own frame.
However, the documentation can be opened in a new tab (right click, open in new tab) and then where it has its own browser window, the URL is displayed as normal.
Of course, this is not the default behaviour - the user has to do something to get it, and to realise that it is possible. That is a problem. The only obvious solution is to have the documentation automatically open in a new window. That's a bit unpleasent though - new windows popping up unexpectedly is not good for the user experience.
> The API changes with every release. WTF? Really? Just... really? In order to use a newer version this library, you have to change your entire application for the updated function names.
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.
IME, once code is written, and given that it works, it tends quite strongly not to change. It works, so why spend time and effort merely to change it? however, if a new version of a library comes out, anything could have happened - so existing code has to be revalidated. It's extra work. This is avoided by supporting concurrent use of multiple library versions.
> And many of the lock-free structures are add-only. The binary tree is unbalanced. Which makes it not a very
> good binary tree.
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!
Regarding being unbalanced, one way to address this is to hash the key before inserting a new node.
> This looks like it was written by somone who heard "lock free", and went "cool, I'll write a library!"
That's a bit unfair. The library is eight years old now. It's not a flash in the pan.
> The web site is bad, the APIs are bad, the functions aren't very useful, the library isn't very portable,
> etc.
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.
Such an odd way to license free software. It's as though the author honestly thinks that licenses are bad for free software -- copyright has bad defaults and licenses allow us to make free software.
No. Property rights are absolutely, profoundly, completely, totally, utterly central, vital, irreplacable and essential. Licenses are an offshoot of property rights.
However, the arrangement of property rights as they are now being forced upon me - other entities telling me how I must go about managing my rights - this I do object to.
I know what I want to do with the property rights in this case, but I am often told there's all kinds of trouble in achieving this, because of these other entities enforcing their view of property rights upon me and the people who would form a contract with me (by choosing to use the software on the basis I am offering it).
Now we only need more lock-free problems :) Seriously, I'm pretty much content with regular uncontended mutexes and atomics in the vast majority of cases.
The lock-free binary tree on two cores is about 2x faster than the next best method. On sixteen cores, about 20x faster.
Why not use it, if it's packaged up in a library? it's only the difference between typing one API or another, unless there are functionality differences.
Lock-free data structures are process, thread and interrupt safe (i.e. the same data structure instance can be safely used across processes, threads and both inside and outside of interrupt handlers).
Yes. The reason for this is that every version of the library can be concurrently included and linked against. The reason for this is so that when a new version of the library is incorporated, existing code does not even have to be revalidated, because the code it is using is unchanged.
In this latest release, I've actually moved over to a single repo, which will gain a new directory for each new release. The reason for this is that the benchmark app builds and links against earlier version of the library, so it can benchmark them. The gnuplots show not only the performance of locking data strcutures running the same benchmarks, but also of the earlier versions of liblfds.
I've heard of Rust. People seem to like it. However, I am a C programmer and have always been a C programmer, and I write the library for the pleasure of it, so other languages don't really connect.
[+] [-] preetamjinka|9 years ago|reply
[0] http://concurrencykit.org/
[+] [-] liblfds|9 years ago|reply
I believe CK offers a delete-supporting hash, too, so it has a full O(1), which liblfds does not yet have.
[+] [-] sargun|9 years ago|reply
[+] [-] protomyth|9 years ago|reply
[+] [-] Sir_Cmpwn|9 years ago|reply
[+] [-] benbenolson|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
[+] [-] ape4|9 years ago|reply
[+] [-] nneonneo|9 years ago|reply
"Dmitry Vyukov granted email permission for the idea to be used and implemented in liblfds, under the MIT license."
Similarly, the unbounded queue has an "unclear" license, rather than the "standard liblfds" license.
It's not clear to me how the library can be license-free when one component is very clearly MIT-licensed, and when others have no clear license status. I would be quite cautious using this code in production or in a lawyer-sensitive environment until the licenses are clarified.
[+] [-] liblfds|9 years ago|reply
When the library was initially released, back in 2009, and until recently, it's been license-free, or at least thought to be. Recently with the addition of Dmitry's design, and a closer analysis of the possible licensing terms, the picture has become more nuanced - hence the inclusion of per-data structure information regarding licensing and what happened is of course classic computing - there's now a regression bug in the one line description of the library! Where the "license-free" term has been in the one-line description for so long, it was overlooked.
I have to figure out what to do about this now!
[+] [-] huhtenberg|9 years ago|reply
PS. Code has quite a bit of that macro-heavy OpenSSL vibe to it. Definitely not everyone's thing, but it is very readable - https://github.com/liblfds/liblfds/blob/master/liblfds/liblf...
[+] [-] liblfds|9 years ago|reply
I'd glad you find it readable - I hope you're right :-)
[+] [-] cbd1984|9 years ago|reply
[+] [-] wongarsu|9 years ago|reply
The author granted a license for all Creative Commons licenses, which includes CC-Zero (public domain where that's possible, the closest possible equivalent everywhere else). That's the real part that makes the rest of the section unnessesary.
[+] [-] Twirrim|9 years ago|reply
a)public domain is a concept that is far from a world wide legally recognised concept (its roots are in old English law)
b) public domain scares company lawyers and it's easier to give them an actual license :D
[+] [-] llull|9 years ago|reply
[+] [-] weinzierl|9 years ago|reply
[+] [-] unknown|9 years ago|reply
[deleted]
[+] [-] bogomipz|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
I've seen server code like that - all the time of course - but the only algorithm I can think of which has that property is a PRNG, and that can normally be implemented on a per-thread basis, each thread holding its own single-threaded PRNG.
This probably reflects my lack of work with algorthims. Could you give an example?
[+] [-] adekok|9 years ago|reply
The API changes with every release. WTF?
struct lfds710_freelist_element;
Really? Just... really? In order to use a newer version this library, you have to change your entire application for the updated function names.
And many of the lock-free structures are add-only. The binary tree is unbalanced. Which makes it not a very good binary tree.
This looks like it was written by somone who heard "lock free", and went "cool, I'll write a library!"
And he missed the last 40 years of software best practices.
The web site is bad, the APIs are bad, the functions aren't very useful, the library isn't very portable, etc.
People shouldn't use this library for anything.
[edit] Updated the comment about "someone" being a 16 year-old student.
[+] [-] nneonneo|9 years ago|reply
while(lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position(state, &element, LFDS710_BTREE_AU_SMALLEST_IN_TREE, LFDS710_BTREE_AU_INORDER_WALK_FROM_SMALLEST_TO_LARGEST))
It's not going to be possible to remember what names to use when you need to iterate. Or, take the initialization routine. You first call
lfds710_btree_au_init_valid_on_current_logical_core( &state, key_compare_function, LFDS710_BTREE_AU_EXISTING_KEY_FAIL, NULL );
on one core, which is perhaps reasonable, but then you call
LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE()
on other cores. That is one hell of a #define, and it's not even clear from the name what it's doing. It seems like "LFDS710_MISC_SYNC_INITS" or something along those lines would be clearer and easier to remember.
[+] [-] jhpriestley|9 years ago|reply
For example, here is the link to the rationale for the versioned naming scheme:
http://liblfds.org/mediawiki/index.php?title=Introduction#Co...
Do you even understand the significance of "lock-free" in the title here? Do you have some basis to think that the weaknesses of the data structures, like unbalanced trees and add-only collections, can be remedied without using locks? If you do then that would be an interesting criticism, but as it is it looks like you just opened the page, looked around for a few things to criticize, and then wrote this sour, shallow, dismissive comment.
[+] [-] nothrabannosir|9 years ago|reply
Nothing wrong with that, though. In fact, that's great.
Word to the 16-year-olds (or any-year-olds) doing that: put a disclaimer in your README to avoid this kind of reply being top comment in a HN thread about your work :)
[+] [-] huhtenberg|9 years ago|reply
[+] [-] jotux|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
Yes and no. The site currently is arranged with a set of tabs on the left and a frame on the right. It had to be a frame because some of the web-based apps, such as the mediawiki used for documentation, generate output encapsulated in the "<HTML>" tag. As such, their output cannot be captured and placed into a div; it has to go into its own frame.
However, the documentation can be opened in a new tab (right click, open in new tab) and then where it has its own browser window, the URL is displayed as normal.
Of course, this is not the default behaviour - the user has to do something to get it, and to realise that it is possible. That is a problem. The only obvious solution is to have the documentation automatically open in a new window. That's a bit unpleasent though - new windows popping up unexpectedly is not good for the user experience.
> The API changes with every release. WTF? Really? Just... really? In order to use a newer version this library, you have to change your entire application for the updated function names.
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.
IME, once code is written, and given that it works, it tends quite strongly not to change. It works, so why spend time and effort merely to change it? however, if a new version of a library comes out, anything could have happened - so existing code has to be revalidated. It's extra work. This is avoided by supporting concurrent use of multiple library versions.
> And many of the lock-free structures are add-only. The binary tree is unbalanced. Which makes it not a very > good binary tree.
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!
Regarding being unbalanced, one way to address this is to hash the key before inserting a new node.
> This looks like it was written by somone who heard "lock free", and went "cool, I'll write a library!"
That's a bit unfair. The library is eight years old now. It's not a flash in the pan.
> The web site is bad, the APIs are bad, the functions aren't very useful, the library isn't very portable, > etc.
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.
[+] [-] erichdongubler|9 years ago|reply
typedef lfds710_freelist_element freelist_element;
[+] [-] cyphar|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
However, the arrangement of property rights as they are now being forced upon me - other entities telling me how I must go about managing my rights - this I do object to.
I know what I want to do with the property rights in this case, but I am often told there's all kinds of trouble in achieving this, because of these other entities enforcing their view of property rights upon me and the people who would form a contract with me (by choosing to use the software on the basis I am offering it).
[+] [-] p0nce|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
Why not use it, if it's packaged up in a library? it's only the difference between typing one API or another, unless there are functionality differences.
[+] [-] partycoder|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
[+] [-] abimaelmartell|9 years ago|reply
https://github.com/liblfds?tab=repositories
[+] [-] liblfds|9 years ago|reply
In this latest release, I've actually moved over to a single repo, which will gain a new directory for each new release. The reason for this is that the benchmark app builds and links against earlier version of the library, so it can benchmark them. The gnuplots show not only the performance of locking data strcutures running the same benchmarks, but also of the earlier versions of liblfds.
[+] [-] glibgil|9 years ago|reply
[+] [-] liblfds|9 years ago|reply
[+] [-] monocasa|9 years ago|reply