liblfds

> Honest question: why do you think that's a useful usecase?

I worked for three years on software used by telcos. Carrier grade - they were rigourous about change control and validation, because bugs were totally unacceptable. For them, it would have been exactly what they needed.

Before that, I worked once for a while on a huge, unmaintainable code base. Awful code, basically one huge function, with a million lines of code =-) with that code, you should not risk ANY change. For them, it would have been essential.

In general, across all software I think software quality is not high. Developers do not test enough, and are too casual about change. I am taking an approach which I think is necessary, and it certainly deviates from the usual practise.

> Also, you could do symbol versioning like glibc

I'm not sure I properly understand - I need to read up properly on what this offers. However, it's not clear to me how it changes anything from the C code POV - in the C code, the user still needs to use the old versions of prototypes, to call the correct code in the library, so what do they get for symbol versioning? why not just link to the old binary? and it's important, because the old binary is completely unchanged and it is only by that, that revalidation is unnecessary and so does not have to be performed.

On a more practical level though, the library targets arbitrary compilers on bare metal platforms, and symbol versioning from what I read is rarely offered.

Yes.

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.

Make that "one" then :-)

I don't actually know know of others, but I know there are a range of other PRNGs which run on single-word states, so they might be viable.

Thankyou! I see many flaws in the library though - there's so much that I can see to improve or to add. Still, with such things, there's a lot of value in making a release to get new functionality out so it can actually be used, even if there's much else to be improved, or which is not as it could or should be.

> Is it safe to say then that distinctions such as "lock free" and "wait free" always refer to data structures and not algorithms then?

Well, for what my thoughts are worth, I would say no, not inherently and catagorically, but in practise, it's hard to imagine algorithms which are multi-threaded in such a way that threads contend on shared data, such that the design of the algorithm could even be lock-free or wait-free.

Parallelized (i.e. multi-threaded) algorithms tend I think to have multiple threads all running the same code but each being given a separate part of the overall data to process - say an image processing algorithm, where each thread receives an equal portion of the image to process.

A PRNG however I think can (for one or two types of PRNG only, not in general) be implemented as a lock-free algorithm. A PRNG is not a data structure - rather, it maintains some internal state and on requests uses (and updates) that state to generate a new random number. It is an algorithm.

The updating process must be atomic or it is compromised - you can't have one thread half way through the state updates, and then another thread jumping in at that point and using the half-updated internal state.

Good PRNGs hold a lot of internal state - up to a kilobytes - so it's not possible to directly use atomic operation to update that state. However, there is a class of PRNGs called "SplitMix" which have an 8 byte state, where on request for a new random number, that state has a particular (quite large) constant added to it, and the result is then passed through a hashing function.

With this design, an atomic add can be used for the addition, and once that's done, the requesting thread then local to itself runs the hashing function (it's single-threaded, and merely takes an 8 byte number for input), and so the design is lock-free - no matter how many threads are using the PRNG, whether or not they have been idled by the OS, all other threads can still get their work done.

This PRNG is a curiosity though - it has almost no genuine use cases. The performance is poor when compared to the single-threaded version of the same PRNG, and a PRNG being what it is, each thread can easily run its own, thread-local PRNG.

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.

> Well, the solution to that is to maintain branches of your code for each major version change and to only introduce breakages in major versions.

That is what is being done. Versioning is GCC style, "[major].[minor].[bugfix]". When APi breaking changes occur, a new major release is published, and is begins a new line of releases. When non-API breaking changes are made (or backported), a minor release occurs on all previous lines. Bugfix release can occur on previous lines.

So there's 6.0.0, then 6.1.0, and then a few months later 6.0.1 and 6.1.1 came out, with the same bug fix for both releases.

> Because your current method means that your library will never delete old code

Right. That is intentional. The idea is that when a new release is made, there is no change whatsoever in previous versions of the library which are in already in use.

> if you slightly change a basic function shared by different library versions what will you do then?

There are no shared functions, the library is stand-alone.

> If you did major versioning right

It would still require change in the binary being used by application, right? it would mean change, and that means revalidation - the only way it would not mean revalidation is if the application owner decided "what the hell, I'm sure he's got it right and there are no new bugs and it'll all be okay".

Anyway, you must alao remember the library targets bare metal platforms on arbitrary compilers. As it is for example the library is for example wholly independent of the standard library - it doens't even require a freestanding implementation. Symbol versioning is a luxury, high-end, rarely provided functionality. If the library relied on it, it would greatly limit the range of supported platforms.

> Alternatively, you could allow users to set a macro before including your headers. This macro sets the version of the library they want to use. Then you don't require people to specify the version in every single symbol.

That would defeat the very goal being aimed for. The idea is that existing code does not change when a new version of the library si released. The idea that when a new version is release, that all existing code should automatically use that new version, is to be avoided. You are trying to find ways in which it can happen, when that's the very thing which I'm trying to have not happen. That change should be controlled, should be consciously and deliberately chosen at a particular time, and to whatever extent is decided, by the maintainer of the application using the library.

Consider. Say an application is using the queue from 7.0.0 in say six different places. The code works. Why change it? but then there's a performance problem. One of those queues would really benefit from going faster. In this situation, why change all of the queues? those queues could be in completely different sub-components of the overall ssytem. When you update one of those queues, you have to revalidate that part of the system. You don't want to do it - you have limited developer resources, a to-do list the length of your arm and customers screaming for new features and other bugfixes.

Because until recently, the library was license-free.

Licenses are important as a concept. Licenses can exist, and when they do, they must be honoured. They are an aspect of the property rights of the owner of the software.

That doesn't mean you have to use one, and the library was not using one, so it was license-free.

There might be some confusion here in that when I speak of licensing being important, I mean the concept - I do not particularly mean licensing as it exists today in practise.

As was pointed out in an early post in this discussion, the matter is now not so clear cut. I've added per data-structure information on licensing, and it's no so straightfoward a situation now as to be able to say, in a blanket fashion, "license-free". I'm thinking about what to do about that. The library is much closer to license-free than anything else, but it's hard to explain the situation in the one-line description while keeping it short and to the point.

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

> On Linux and maybe Solaris you can use ELF symbol versioning.

Remember that the library supports bare metal platforms. It is intended to be used in the absence of an operating system.

I'm afraid I'm not sure I undersand what you've written.

My aim is to ensure that for applications using the library, that when a new release comes out, that they can use it while seeing absolutely no change in the code they are already using (header files, the binary being linked to, etc), as this is the and the only way to know that existing code will be wholly unaffected.

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

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.

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

Thankyou! I hope you're right :-)

It depends though where you're coming from.

I write the library for the pleasure of it. I'm aiming to create something I think beautiful - for better or for worse, from other people's point of view :-)

I'm not actually looking for it to be used as such. It may well be, if my idea of beautiful is any good, it will come to be used, but that's... it's like a side effect.

When you paint a picture, or sculpt a sculpture, or write a song, you're not competing with other artists to make what other people will judge to be the better picture, sculpture or song.

I went full-on, for documentation.

Many, many years ago, back at Uni, a friend of mine received 100% for his Uni project. I could code many years before I went to Uni, but I was shallow in all other ways - all the ways in which we actually produce quality, reliable, usable software. He showed me some of his project, and I saw his docs. What he'd done was absolutely fantastic - a page per API function, documenting the standard set of information that you need to use an API function. The approach you see in all the major projects today, the MS API docs, for example - this from a twenty year old!

That experience permanently set my expectations for documentation, and is reflects in the library docs. One page per function, per enum, per struct, etc, etc, etc. It's ALL documentated. Painstakingly, exhaustively.

There's absolutely no point in writing an API which people cannot use, for whatever reasons.

When I come to make a release, and I'm done (or rather, I think I'm done) with development, I write the docs.

This induces, always, a large final round of development work, as I come to realise, from attempting to document them, that some of what I've done is simply too complex or too awkward or too inherently confusing to use, and has to be rewritten.

I am of the view from my experiences that all developers should write their own documentation, because of the improvement in code quality that is induced by the code changes which come from keeping the docs comprehendable.

You have to remember what I'm looking to achive here is that a new version can be released, and used, while the existing codebase using the old versions is utterly unchanged. The APIs are unchanged, the library they link to is unchanged - totally, utterly, unchanged, not one single byte of difference.

I've not thought about (or really come across - I think I have seen it on Windows) symbol versioning, but from what I've understood (from a pretty terrible explanation online) it would mean the library ends up with a single library file, which gains new members as new releases of the library occur.

This still has the problem of imposing unvalidated change on the user - the library changes under him. What if I introduced new bugs?

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?

> I can't just link to the new version and get the bug fixes.

I think this isn't quite right, by omitting the down side - that you will be getting the not just the bug fixes, but new bugs. It's not all roses!

What has occurred between 710 and 720 is change. Ideally, hopefully, intended to be, positive change only. Bug fixes only. Improvements only. We all as software developers know there will in fact be new bugs introduced. Regression testings exists for that reason, and it is an imperfect method.

So I guess what I'm saying is this : nothing, NOTHING, should change for a given application, without revalidation. Swapping a library version under the hood is by that view not good practise. By and large of course this is type of change is absolutely normal practise, because most of the time it seems to work, and it less costly and time consuming.

(Really, it happens I think because humans are optimists and writing code is hard work and time consuming, so we involuntarily hope it's all fine and don't look hard for the bugs we've not found).

That could work. ASCENDING and DESCENDING. I'll think it over (in the morning - I'm about comatose right now).

It's not very polite :-)

"Licensing with attitude!"

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.

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

I an of the view that it is a problem, but one which is almost wholly ignored and as such, not addressed.

Generally, software projects version as you have described, based on breaking the external API. If the API is unchanged, the library is deemed to be effectively unchanged.

I am not happy with this. ANY change in a library requires revalidation - and so the only way to deal with this is to have no change at all, not even in the library binary. To do otherwise is to assume correctness, which as we know, given the nature of software, this is something which is never always true.

This level of care about change is I think almost never used and normally software libraries take for themselves the advantages of fixing versioning at the API-breaking level - it makes development easier, at some of cost to the users of reliability (if the users accept the changes without revalidation) or at some cost to the users of work (if the users revalidate).

I think a library should act as a factorization - it should take into itself all possible work which would otherwise have to be performed by ALL its users, so that that multiplicity of work is converted into a single instance of that work, performed by the library authors.

OTOH, you do know exactly what it does, without having to read any docs.

I am of course open to suggestions for improvement.

My view is that all these, ah, parameters for licensing - what is or is not, copyright, public domain existing in some countries and not others, etc, etc - none of these are things I have chosen. They are being imposed upon me. This is not okay. I feel no need to go along with it all, just because other entities force it upon me.

This is why I say license-free. It is rejection of these imposed parameters. I know what I want here - for other people to be able to use the library as they wish for whatever they wish, simple as that. No charges, no catches, go use it.

However, in practise, companies and individuals must abide by all this stuff, and so you see about the code being in the public domain, a license of your choice being granted if you wish for one, etc. This is to address the practical problems involved.

Regarding public domain, I think you've overlooked where it is explicitly placed in the public domain - it's the end of a couple of sentences, so it's understandable;

"If however for legal reasons a licence is required, the license of your choice will be granted, and license is hereby granted up front for a range of popular licenses : the MIT license, the BSD license, the Apache license, the GPL and LPGL (all versions thereof) and the Creative Commons licenses (all of them). Additionally, everything is also placed in the public domain."

Google'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.")

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

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

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.

I hope so.

I applied to the GCC compiler farm late last year, but received a reply only after so long a time that I'd deleted the key pair I'd submitted because I thought nothing was going to happen - and my efforts to get back in have yet been unanswered.

The GCC compile farm isn't for intensive testing or benchmarking, though (which is what you need for lock-free, to try to catch race conditions) - that test lab sounds more interesting.

I have to say though having your own dev boards which are yours and only yours and which you can hammer endlessly is very convenient. It's actually just occurred to me I can leave all the devs boards permanently running the test suite...

OTOH, I don't think I can get small, portable dev boards for all the platforms I care about, so at least for some architectures, a third-party farm is probably the only way.

Probably the most pressing requirement though is access to a Mac. Right now there are no build files for that platform.

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