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.
I am of course open to suggestions for improvement.
Also I'm much less concerned with absolute line width in my own code than I am with indentation steps or number of arguments something takes without flowing on to multiple lines.
The goal of course is for all identifiers to be as short as possible.
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.
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!
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.
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 :)
What is wrong is not learning from others. This library follows many practices which are well known as "worst practices" in the industry.
Good to know.
In this case, I'm astonished at just how many bad practices the author has engaged in. Do most software projects have structs / functions / whatever where the names are versioned?
It's one thing for TempleOS to invent his own OS, build system, programming language, GUI, etc. He made some odd choices, but at least he's clear he doesn't care (much) about other people using his code. And, it's clear his code works, and does something useful.
The author of this library has invented many of his own programming practices... which are clearly worse than current industry practices. Why? I can't say. But I can say that they are worse.
I just don't understand this attitude that all feedback has to be couched carefully to avoid hurting anyones feelings. If it's bad, it's bad.
Perhaps you could be productive, and post your review of his code. If it's in any way negative, (by your standards), I should jump on the review as being overly negative, and "you're the reason why people don't do open source."
Adults should be able to take criticism. If they can't, I have very little sympathy for them.
>Adults should be able to take criticism. If they can't, I have very little sympathy for them.
Again, your outlook is toxic to newcomers. Yes people should be able to handle criticism but you should be capable of crafting that criticism in a way that isn't mean spirited and rude.
I wish more projects and communities had code of conduct rules similar to the rust language: https://www.rust-lang.org/conduct.html
Which includes rules your comment would obviously violate:
Please be kind and courteous. There’s no need to be mean or rude.> >Adults should be able to take criticism. If they can't, I have very little sympathy for them.
> Again, your outlook is toxic to newcomers. Yes people should be able to handle criticism but you should be capable of crafting that criticism in a way that isn't mean spirited and rude.
I don't think that's a fair statement. If someone has done something badly, they've done it badly and they should be told that. You're not doing anyone any benefit by sugar coating it by first saying "great job on trying". Personally, I prefer getting a frank and honest review of my work rather than having to tease out why someone doesn't like it but they won't state it plainly because they'll "hurt my feelings". We're discussing code, and if code is bad then we should make it clear that it's bad, say how to do it better, and move on.
>This looks like it was written by a 16 year-old student who heard "lock free", and went "cool, I'll write a library!" And he missed the last 40 years of software best practices.
Is not constructive criticism, it's just being rude.
You've been given multiple opportunities to give positive criticism yourself. And you've refused. Your position is entirely negative.
For something where you are more offended than the author of the library. He's an adult, and he can defend himself. You're infantilizing him by protecting him from things where he doesn't want protection.
The code of conduct you linked to would seem to prohibit your overly negative behavior.
i.e. your comments have come across (to use a common phrase here), as toxic.
I disagree.
> you should be capable of crafting that criticism in a way that isn't mean spirited and rude.
As I suggested, perhaps you could give some positive criticism of your own, and give your review. Not doing that means you're demanding I do something which you won't do.
This is not a trivial point. I'll bet that you'll find it difficult to craft a technical review which points out the flaws in his software, without anyone being able to claim it's being "mean and rude".
Try it. Please.
> I wish more projects and communities had code of conduct rules
That's nice. But I wish more projects had code of conduct rules on people asking questions. I've been doing open source for 20+ years. There is a large subset of people who don't read the documentation, don't ask good questions, who ignore all attempts to help them...
... but ...
their behavior is superficially polite. Until they get frustrated that "no one is helping them", and they start complaining that everyone is being mean to them.
That behavior is toxic, and I have no patience for it.
Yet strangely, I've yet to see a "code of conduct" which deals with this issue. It's open source... you shouldn't demand that other people help you, no matter how politely you make that request.
And (as with most such arguments I've had), I'll note that you're more offended by my comments than the author is. Such over-sensitivity seems to me "problematic". The author is an adult. He can clearly take criticism. Perhaps learning from his example would be good.
And having a top comment on HN warning me that the code is pretty bad saves me time, too, because I don't have to read the code or try using it to find that out. So I really appreciate people publicly pointing out that the code is bad.
I'd feel more positive about this code if it had been submitted with a request for code review and feedback rather than being presented as a "a portable, license-free, lock-free data structure library written in C" with a whole website advertising it as being ready for use.
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.
This is what having consistent interfaces is for. Keep your interface consistent, not your implementation.
This is also a strong argument for not releasing code and advertising it on HN if it's not mature.
> 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!
Which begs the question why you included immature implementations in your library.
> That's a bit unfair. The library is eight years old now. It's not a flash in the pan.
Which doesn't negate the criticism in any way.
> 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.
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 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.
> The and the ONLY way in which existing code does not have to be revalidated is if it is completely and wholly unchanged.
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? I'm going to have to test either way when I integrate a new version of your code, so I might as well get any performance improvements or whatever you introduced into the implementation. Versioning your interface does not solve the problem you claim it does.
> 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.
I am saying they're immature because you said they were immature. You said, "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."
> I was thinking of processor support, rather than compiler support.
I was also thinking of both processor support--you're the only one who mentioned any compilers. Given this supports only 2 processors and ConcurrencyKit supports 5, your claim that this is "actually as portable as it is possible for a lock-free library to be" is still provably wrong.
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.
1. Let's say I do things the way you suggest: I use different versions of your code simultaneously. 3 years in I have 5 versions of your code and I find a bug in my code in an area from the second version. Now I have to know 5 libraries to understand the code and I'm constantly getting tripped up by the subtle differences between versions 2 and 3.
2. So to fix this plan I finally persuade my boss to give me a week to address tech debt. With your search-and-replace plan, except I forget to do it in the library that Bob the contractor kept in a separate repo before we fired him. And then there's the separate problem of when I passed it into a function that took a function pointer and so the name is different and not find-and-replacable as being the same function. And then there's the place where Joe, who is a good programmer but kind of inexperienced, poor kid, he thought he'd simplify things by creating a macro that inserts the number, and this got past code review because I reviewed it right after a meeting with the client from hell. So now nothing is working after the find-replace, it takes us the entire week to figure out why, and we don't get to spend any of our tech debt time fixing the place where Bob the contractor decided it would be a good idea to "optimize" the graph generation functions.
For the record, I'm speaking from experience here. The way you wrote this code is an ideology I've worked with before and it's miserable to consume libraries written in this style. You can argue for the "benefits" all you want but I've eaten this dog food before and I'm not going to eat it again.
There's actually rather few alive platforms that don't either have ll/sc or cas. The original i386, armv5, sparcv8 (leon IIRC added cas though), pa-risc come to mind (that's the postgres platforms for which fallback atomics support is used). Once you have CAS it's easy to provide fallback implementation for other atomics. It's also not all that hard to provide a "fallback" implementation for atomics, which guarantees atomicity using some locking mechanism.
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'm not totally convinced about that, cf: https://en.wikipedia.org/wiki/Release_early,_release_often
typedef lfds710_freelist_element freelist_element;
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).
Honest question: why do you think that's a useful usecase? I've never thought of using two versions of the same library, mainly due to fear of nasal demons.
Also, you could do symbol versioning like glibc does and then just keep the old code in the library for backwards compatibility.
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.
Not that I can see (on a quick scan).
So the only way to use his library is to create your own wrapper functions. And update them every time he updates his library.
Thanks, but no thanks.
It get popular, so that Ubuntu packages the application and your library. Millions of people use it.
Now what happens when you release a new version of the library? All of the APIs with 710_foo become 720_foo. Which means that I have to rebuild my application to work with the library. I can't just link to the new version and get the bug fixes.
Even worse, Ubuntu has to rebuild all applications which depend on your library. Every time you release a new version.
This is why no one else puts version numbers into function / struct names. We rely on the C compiler to do type checks at compile time, and we rely on the linker to do symbol checks at run time.
If no one else puts version numbers into function names, it should be a strong hint that you shouldn't do that, either.
Similarly, 80-character symbols / macro names are just too complicated to use / remember. Pretty much no one else does this, either.
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).
As you note, the changes should be minimal. i.e. the versions should be compatible. By changing the names, you are creating massive change, in order to bludgeon users of your library with the knowledge that there might be minor changes in it.
This is counter-productive.
> Swapping a library version under the hood is by that view not good practise.
And re-naming everything is?
Please, get over yourself. Your practice runs counter to 40 years of computer engineering. There are hundreds of thousands of Open Source projects which keep consistent names across minor releases.
Either they're all wrong, every one of the millions of developers, or you are wrong.
I think my review ends here. You're clearly in the camp of "I know better than everyone else".
Why not just use symbol versioning like glibc does.
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?
Because your current method means that your library will never delete old code. Not to mention that I don't know how deep your obsession with versioning goes -- if you slightly change a basic function shared by different library versions what will you do then? Or do you have n copies of the same code everywhere? What do you do if there's a bug in it? And how the hell do you expect a distribution to maintain the code, because you are copying large chunks of code in every version with no net benefit before you even start working on new versions.
If you did major versioning right, then only people who link against version X of your library would use the version X symbols. Glibc uses symbol versioning to extend that further and allow you to change glibc versions under users and they will still be using the old functions because you have symbol versions. Unless you're talking about "changing the library under them at compile time" in which case I think that it's a bad idea to do it that way (people just won't update their code).
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 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.
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.