liblfds

Yes (and yes).

==

(Now done).

I didn't know! thanks! I have a Pi 2 right now for ARM32, I'm completely happy with it.

God, I'm old.

If it does not, how can you concurrently include and link against multiple versions of the library?

Could be. I will look into the choice before I commit - figuring out how one of these complex lock-free data structures works and implmenting it correctly and writing all the tests cases is a major undertaking. It's something you want to make sure you're making the right choice about before you invest the time.

As an aside, binary trees turn out to be really great with lock-free. In the obvious locking implementations, there's one lock per tree. You can use read-writer locks to get parallelism on read, but even so, the mere existance of a single lock of any kind induces memory contention which eliminates scaling as processor counts rise.

I'm sure there are in the locking literature better solutions, but I'm up to speed with lock-free, rather than locking, solutions, so I don't much know about them.

Regarding lock-free, there is no single lock, and btrees are beautiful because they naturally distribute memory accesses throughout the tree. Performance basically scales linearly. There's a gnuplot on the site from a 16 core Amazon VM, and that property can clearly be seen. Every new core simply adds another 200k benchmark ops per second. For the other, non-scaling data structures, new cores are death.

Well, to be fair! the page does say this immediately above the matrix - "The following toolchains and processors are supported out-of-the-box"

However, this is certainly not fully explanitative, and of course is just one line immediately above a large and eye-catching matrix.

I will change it, to make it more clear, and more eye-catching.

Regarding ARM64, it's something I want very much. I will finally have time for it now 7.1.0 is out. I Googled a bit just the other day and there are Pi-like ARM64 dev boards out there now, so I'm going to get one.

Which leaves me needing a SPARC dev board, and a POWERPC dev board, and an x86 dev board, and a MIPS64 dev board, and a... :-)

I think typedefs are almost always harmful. The explanation is longish and not directly related to the library, so I'll leave it at that.

What I will say though is that the struct already has a type, so as far as I can tell, the benefit consists of not having to type the struct keyword?

Also, the typedef in particular you've given would make it impossible to concurrently include and link multiple versions of the library (which is the purpose of having the version in the public entity names).

> 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.

I 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.

When you say "limitations", I'm not sure what you mean. I wonder if there's a misunderstanding here - the matrix describes the toolchains which are supported out-of-the-box, i.e. build files for them are provided, and they have all been tested and should work.

It's not a matrix of the ONLY platforms which CAN work. Is that what you're thinking? Other platforms might well need the porting abstraction layer to be implemented (the Intel compiler might offer a different set of atomic intrinsics, for example), but that's what it's there for.

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.

Indeed. 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.

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.

Could you explain why this is the only way to use the library? why are typedefs essential for use?

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).

Macros are heavily used to avoid making function calls.

I'd glad you find it readable - I hope you're right :-)

Yes. I have seen the white paper for the red-black tree, and the approach used should work for AVL (I've not seen that paper). I've just not had time to implement yet. A full O(log n) data structure is necessary for the library to be really useful piece of work - but there's a lot of other things which are necessary for that, too, and they have so far taken up most of the development time.

About 10% of the effort so far has gone into coding the actual data structures - almost all the work goes into testing, benchmarking, performance tuning, documentation, porting to new platforms, fundamental improvements in the basic design and so on. The benchmark app alone has taken all in all about six full months to write. I thought it'd be simple, it turned out to be a tar-pit!

Yes, some of the identifiers are very long. The aim was to make the APIs self-explanatory. It should be possible to read an API and know what it does. It's challanging to explain an inorder walk, and its direction, in a shorter form.

The goal of course is for all identifiers to be as short as possible.

> 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.

Interesting. Why did it turn you away? do you run code on many of the given platforms?

Yes 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.

That's not the case.

What you get depends only on the processor type.

What does vary is whether or not any given platform has actually been tested - i.e. the code compiled on that platform, and the test programme run.

Currently, only ARM32, MIPS32 and x64 platforms are available, and so the test programme has only been run on those platforms.

Finally, I think you may have been misled in the same way another reader further down was; note that the matrix is the matrix of toolchains which are supported out-of-the-box, i.e. where the library ships with build files for those platforms.

It is NOT the matrix of the ONLY tooclhains which can be used.

Good 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!