16 ms·
Liblfds, a portable, license-free, lock-free data structure library written in C
- cbd1984 10y agoThey say it's public domain so it is, indeed, license-free. AFAIK, the public domain dedication makes the rest of the section chaff.
- wongarsu 10y agoIn 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.
- deleted 10y ago[deleted]
- llull 10y agoChaff? 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.
- Twirrim 10y agoSQLite is public domain, but they've made licensed versions of it available for people to buy, because: 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
- masklinn 10y ago> public domain is a concept that is far from a world wide legally recognised concept Right, the "continental" (franco-german) IP school having moral rights which the anglo-saxon IP school doesn't have[0][1]. These moral rights tend to be perpetual, non-waivable, non-assignable and inalienable, as a result the concept of public domain in the anglo-saxon sense doesn't really make sense, instead "public domain" is a shorthand for works whose economic rights have lapsed (that is in fact the original meaning of the term as coined by Alfred de Vigny) or works which don't have associated economic rights in the first place (e.g. mathematical proofs, parliamentary transcripts) rather than an actual legal concept, and an author can only waive their economic rights through licensing. [0] the english Crown Copyright has some similarities [1] anglo-saxon copyright roughly matches the continental "economic rights" subset of author's rights
- liblfds 10y agoIndeed. It was with lawyers in mind I went for overkill on the licensing front. I wanted to wholly and completely remove that issue from consideration.
- weinzierl 10y agoThe license is interesting but the discussion is off-topic here. I created another thread about the license: https://news.ycombinator.com/item?id=11807463 https://news.ycombinator.com/item?id=11807463
- Sir_Cmpwn 10y agoI 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.
- ape4 10y agoI guess they are using very specific machine instructions to achieve their ends.
- liblfds 10y agoYes and no. On Linux, the library uses the GCC atomic intrinsics. As such, the library funamentally supports any platform GCC supports with its atomic intrinsics. So the instructions are indeed machine specific, but they're provided by the compiler through a standard API. Of course, actually getting something to work means actually compiling in on a given platform and seeing the test programme pass.
- ape4 10y agoThanks for the info. This is the first time a library has replied to me ;)
- liblfds 10y agoGoogle's huge investment in AI. You'll be hearing a lot more of it in the future :-) ("Do you REALLY want to use that API? I think you should space your comments out a bit more. Hey, your battery is getting low! BTW, I've just emailed your entire source base to Google for assimilation.")
- benbenolson 10y agoYeah, 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.).
- huhtenberg 10y agoFor the lazy, a link to the latest release - https://github.com/liblfds/liblfds/tree/master/liblfds/liblfds7.1.0/liblfds710 https://github.com/liblfds/liblfds/tree/master/liblfds/liblf... 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/liblfds7.1.0/liblfds710/src/lfds710_freelist/lfds710_freelist_push.c https://github.com/liblfds/liblfds/blob/master/liblfds/liblf...
- liblfds 10y agoMacros are heavily used to avoid making function calls. I'd glad you find it readable - I hope you're right :-)
- pantalaimon 10y agoBut wouldn't a static inline achieve the same thing while keeping type-safety?
- liblfds 10y agoYes. As I understand it, this requires either that every to-be-inlined function is present in the public header file, so it can be #included into every user source file which wishes to use those functions, so they turn up in the object file and so can be inlined, or we rely on the compiler and linker to inline across object files, which is not commonly supported. It depends upon the compiler having inlining support - the library is targetting arbitrary compilers on bare metal platforms, so it's not necessarily a valid assumption. Currently, there stil remain two uses of inlining, and I am aiming to get rid of them too in the next release. This also removes a macro from the porting layer, making it simpler.
- misframer 10y agoRelated to this is Concurrency Kit [0], which is BSD-licensed, written in C, and provides concurrency primitives and data structures. [0] http://concurrencykit.org/ http://concurrencykit.org/
- liblfds 10y agoI know the author of CK, and he's very, very good. Better than me, I am sure of that! I believe CK offers a delete-supporting hash, too, so it has a full O(1), which liblfds does not yet have.
- pekk 10y agoWhile your humility is refreshing, why wouldn't people just use CK instead of liblfds?
- liblfds 10y agoThe libraries are not identical; I'm not particularly up to speed with CK, I'm not a user, but there's so much that can be done with any data structure library that there will be things liblfds has done which CK has not, and naturally vis-versa, such that for some one of the libraries will be a better (or possibly the only) choice. What those things might be I cannot much tell you, where I'm not particularly au fait with CK.
- chillacy 10y agoMight want to get acquainted then... if you've got competition for your library and you expect users to pick you, you should know why you're better IMO: http://concurrencykit.org/man.html http://concurrencykit.org/man.html It's free and open source but in some regards it's similar to product design/marketing. If you don't pitch it, some reviewer on the internet will make a stackoverflow post about it, and they won't know your strengths as well as you do. A blog I read recently outlined some things to figure out: https://blog.orangecaffeine.com/the-art-of-saying-no-db012a22cd28#.ejst0wc7t https://blog.orangecaffeine.com/the-art-of-saying-no-db012a2... From the other comments here it sounds like some unique things you have are: * versioned datastructures that won't change during library upgrades * self-documenting code style
- adekok 10y agoThe 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. 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.
- huhtenberg 10y agoWho peed in your espresso this morning?
- adekok 10y agoThe best response to a technical review of software is an ad hominem. Good to know.
- nneonneo 10y agoThis 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_%28bounded,_many_producer,_many_consumer%29 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.
- liblfds 10y agoGood point. 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!
- appleflaxen 10y agoIt looks like you are part of the project. Can you clarify what you mean by "license-free"? If there literally is "no license" and something isn't public domain, then it means you aren't authorized to use it (because the authors have a copyright, even if they have thus far chosen not to assert it). And in order to be public domain, it must be explicitly put there. That may be the case, but your page would be clearer if you said so. And if not, then a license must exist, and you should elaborate it.
- liblfds 10y ago
- abimaelmartell 10y agoThere's a different repository for every version :P https://github.com/liblfds?tab=repositories https://github.com/liblfds?tab=repositories
- liblfds 10y agoYes. 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.
- abimaelmartell 10y agoYeah, that doesn't sound right, if you are already using git, try to use branches, and tags. Also the fact that the whole API uses the version number as some kind of namespace is weird.
- liblfds 10y agoIf it does not, how can you concurrently include and link against multiple versions of the library?
- int_19h 10y agoLook at other popular libraries, and consider how they solve this problem - and whether it even is a problem for them (and if not, why). Usually, this sort of versioning is done if and only if a breaking API change occurs, and such changes are avoided if possible for that very reason. If you only rev the major version number on breaking changes, then you only need to reflect that number in your API (and even then only if/when you actually rev it).
- glibgil 10y agoShouldn't this type of library be done in rust from now on?
- liblfds 10y agoI'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.
- monocasa 10y agoThis library has been around for many years, and predates anything resembling stable rust by more than half a decade.
- liblfds 10y agoGod, I'm old.
- partycoder 10y agoIt would be good to know more about the thread safety of the structures.
- liblfds 10y agoLock-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).
- partycoder 10y agoHow is this guaranteed? by which process was this safety declared?
- liblfds 10y agoTo answer that, I need to basically explain the difference between lock-free and locking data structures. If we consider a locking data structure, say a binary tree using a mutex to serialise access, we see a couple of things; 1. when a thread holds the mutex, no other thread can get any work done 2. if a thread holding the mutex is idled by the operating system, every other thread cannot get any work done on the tree until that thread is finally swapped back in 3. if a thread is holding the mutex when an interrupt occurs, the interrupt handler cannot use the tree, because the tree may be in an invalid state - the mutex holding thread could be right in the middle of adjusting a bunch of pointers The fact that thread can be prevented from working by other threads is what is meant by saying it is a locking dats structure. Lock-free data structures are implemented such that, broadly speaking (there are nuances in this which are not necessary here), all threads can continue with their work, regardless of how many other threads are using the data structure or whether or not they've been idled by the operating system. In short, a lock-free data structure is written in such a way that all possible operations, and any number of them in any order can happen at ANY time, i.e. between the execution of one instruction and the next, and the data structure remains valid at all time. It is this which makes the data structure process, thread and interrupt safe. Typically, lock-free data strutures achieve this though the use atomic operations and careful design. (Superior designs also distribute memory accesses away from just one or a few pointers, an improvement which is necessary but insufficient for scalability).
- p0nce 10y agoNow 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.
- liblfds 10y agoThe 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.
- wahern 10y agoA lock-free self-balancing binary tree (e.g. RedBlack or AVL) would be awesome. But AFAIK that's not possible using commodity hardware. In general, there aren't many places where you can use a regular binary tree when using externally-sourced data because it opens you up to computational complexity attacks. You could using something like SipHash to securely randomize keys, but then it won't be nearly as fast. And of outside of batch processing, who uses a binary tree without deletions? The only lock-free data structure that is practical is a queue. And that's because a lock-free queue is really the only data structure that doesn't require you to re-architect your entire application stack according to the limitations of the lock-free data structure. And if you're going to re-architect your application, better to re-architect it around message passing, which mostly obviates the need for lock-free data structures, with queues, again, being the obvious exception. But it's comparatively trivial to implement a lock-free queue using intrinsics, assuming it's a hot-spot in your application. Library dependencies are extremely costly in terms of the long-term maintenance of software projects. Supplying a lock-free queue in a single C file (or header) using common compiler intrinsics, OTOH, and which automagically can be dropped into most existing projects, might be much more useful.
- liblfds 10y agoLock-free red-black trees now existing in the literature. They were invented recently, about two or three years ago now. > And of outside of batch processing, who uses a binary tree without deletions? IME, it's surprising how often even an add-only data structure is absolutely fine. For example, the benchmark application uses one to store the processor/memory topology, and perform operations upon it, such as generating interesting combinations of cores to execute the benchmarks upon. One other thing which helps a little is that the tree elements have a key and a value, and the value can change at any time. So there's a bit of flexibility there. However, of course, the real solution is proper support for delete. The library must have this, and it's pressing - but there's just so many other things which also need to be done, and which have been being done. For example, it's all very well having a tree, but without e benchmark, I have no idea if I've implemented correctly. Where the benchmark was added in 7.1.0, I was able to see the implementation on ARM was utterly broken - running at about 10% of the speed of locking trees! I investigated, fixed it, they returned to running about 3x that of the next best solution - and that fix also gave about a 25% improvement on all other platforms. > The only lock-free data structure that is practical is a queue. There's quite a few lock-free data structure in the literature. Obviously the stack (it's ancient), then the queue (lots of variants thereof), deques, lists (singly-linked, doubly-linked, ordered, unordered, locality aware), then hashes (of vast importance, as they scale magnificently) and now trees. > And that's because a lock-free queue is really the only data structure that doesn't require you to re-architect your entire application stack according to the limitations of the lock-free data structure. What limitations do you have in mind? as far as I can see, the API for the lock-free queue is identical to the API for the locking queue, you just get more performance. > But it's comparatively trivial to implement a lock-free queue using intrinsics Mmm... I'm not sure I agree. The standard lock-free queue is from Michael and Scott. It takes a while to understand it, and you have to know - really know - all about memory ordering behaviour. I've seen more broken implementations of this data structure than working (although they work fine under low load, of course). My original implementation made the same mistakes. Moreover, today, although I may well be completely wrong, I think I know of two bugs in that queue, both of which are fixed in liblfds. Getting beyond even the white paper implementation to realising there could be issues in the queue is another leap. > Supplying a lock-free queue in a single C file (or > header) using common compiler intrinsics, OTOH, and which > automagically can be dropped into most existing projects, > might be much more useful. To the extent this is true, it's true for all libraries, not just lock-free data structure libraries. It's a question of packaging. Do you have multiple C files and multiple header files, and compile them all up and have the user link, or do you bundle them all together into a single file (in this case so you have a single file per data structure, where the abstraction layers are duplicated between them) and ship that? That single file is going to be some hundreds of kilobyets of code. Maintaining that arrangement would be quite painful (and error prone) for the library developer. What you'd need in fact is to maintain the code in the form of multiple files, and then have a release mechanism bundle them up. In both cases, the users take your source file (or files) and add them to their projects. In the former case, the file is added to their build files. In the latter case, building the library is added to their build files, and then linking also.
- cyphar 10y agoSuch 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.
- liblfds 10y agoNo. 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).
- cyphar 10y agoYou think that the copyright default of "all works are copyrighted essentially forever, and you cannot use, modify or share copyrighted works of any kind" is sane? Seriously? If you want to talk about property rights, we can talk about those. But we're talking about copyright, which is a very different concept to property (despite attempts to create misleading terms like "intellectual property" to muddy the waters). Copyright is supposed to be a method of encouraging creative works. It is not meant to be a method for software developers to maintain control over their users. I never said licenses were not important: YOU SAID THAT. Licenses are incredibly important -- free software couldn't exist without them because of draconian copyright laws funded by special interests that don't give a shit about creative works.
- liblfds 10y ago> I never said licenses were not important: YOU SAID THAT. I thought you were saying I thought licenses were not important. I was trying to make it clear I think they are fundamentally important, by being an aspect of property rights.
- bogomipz 10y agoCan 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?
- liblfds 10y agoI 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?
- bogomipz 10y agoI came across this recently - Treibner's algorithm, mentioned in this: http://people.csail.mit.edu/shanir/publications/Lock_Free.pdf http://people.csail.mit.edu/shanir/publications/Lock_Free.pd...
- liblfds 10y agoI think you mean Treiber, right? typo with the "n". In 1986, on an IBM mainframe, published a white paper describing how to implement a lock-free stack (which is also a freelist, of course). It was the first lock-free data structure. I'm not quite sure why it's being called an algorithm! The scalable version described in that paper is scalable by dint of adding an elimination layer in front of the stack. I've added such a thing, although my own design - I've not read their paper, so I don't know how they did theirs - to the freelist in 7.1.0, but it hasn't worked well. It roughly doubled performance on x64, when there are a large number of cores, but reduces performance for lower numbers of cores and on other platforms. When there are a large number of cores, performance is rock bottom,, so doubling means going from like 1m ops/sec/core to 2m ops/sec/core, when if you run on just one core, you'd be doing say 30mm ops/sec on that core. I'd expect it in principle to permit real scalability - fairly linear performance as the number of cores rises - so I think I've missed something, or done something wrong.