[liblfds]

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.

[wahern]

A 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]

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

[p0nce]

Sure, but I somehow never encounter a problem where I need a real lockfree data structure other than a ringbuffer or a variation thereof. Interlocked queues are almost giving me enough.

[liblfds]

What do you mean by interlocked queue?

On Windows, the atomic instrinsic APIs all begin with "interlocked", and although I'm not sure what you mean, it's making me think of that.