8 ms·
Lockfree Algorithms (2010)
- chrsig 4y agoFedor Pikus has given a number of great talks on the subject at cppcon over the years some links, in no particular order: CppCon 2017: Fedor Pikus “C++ atomics, from basic to advanced. What do they really do? https://www.youtube.com/watch?v=ZQFzMfHIxng https://www.youtube.com/watch?v=ZQFzMfHIxng CppCon 2016: Fedor Pikus “The speed of concurrency (is lock-free faster?)" https://www.youtube.com/watch?v=9hJkWwHDDxs https://www.youtube.com/watch?v=9hJkWwHDDxs CppCon 2015: Fedor Pikus PART 1 “Live Lock-Free or Deadlock (Practical Lock-free Programming)" https://www.youtube.com/watch?v=lVBvHbJsg5Y https://www.youtube.com/watch?v=lVBvHbJsg5Y CppCon 2015: Fedor Pikus PART 2 “Live Lock-Free or Deadlock (Practical Lock-free Programming)” https://www.youtube.com/watch?v=1obZeHnAwz4 https://www.youtube.com/watch?v=1obZeHnAwz4 CppCon 2017: Fedor Pikus “Read, Copy, Update, then what? RCU for non-kernel programmers” https://www.youtube.com/watch?v=rxQ5K9lo034 https://www.youtube.com/watch?v=rxQ5K9lo034 Tony Van Eerd has also given some talks on lock free queues, I'll leave it as an exercise to the reader to search youtube :)
- pgt 4y agoTigerbeetle uses LMAX: https://tigerbeetle.com/ https://tigerbeetle.com/
- zackmorris 4y agoThis is great! I learned networking back in the late 90s reading Beej's Guide to Network Programming: https://beej.us/guide/bgnet/ https://beej.us/guide/bgnet/ Which is great and everything, but there was an overlooked alternative then called OpenTransport (OT) from Apple (warning, PDF): https://developer.apple.com/library/archive/documentation/mac/NetworkingOT/NetworkingOpenTransport.pdf https://developer.apple.com/library/archive/documentation/ma... Now, OT was frankly a terrible way to do networking. I learned it because this was in the Mac OS 9 days before protected memory and multitasking, so if you wrote games, you often had to deal with interrupts. OT got lost in the weeds with its complete lack of understanding of UNIX sockets (everything is a file). So I went several years thinking in terms of packets instead of streams. Once I saw the enormous benefits of synchronous blocking streams, I threw OT away and never looked back, as did Apple. But OT had fantastic atomic primitives and FIFO/LIFO lock-free queues (see pages 657, 641, 645 of the PDF). That stuff was so vastly better than anything I had seen in Windows that it made me sad inside to see people still using mutexes. The use of locking primitives generally sets one up for a number of failure modes like poor performance and deadlocks. Unfortunately, many of those bad habits show up today in asynchronous web programming and even patterns as fundamental as locking database transactions. It's too hard to explain where I'm coming from in a forum post. But there really is this whole other way of doing things that's been all but dead for over two decades. And it ties in with my frustration around the lack of a true multicore CPU with perhaps 1024 cores (I like the article's URL!). Basically we could be using self-parallelizing code where instead of putting special "concurrent" keywords or intrinsics around loops etc, compilers could analyze loops for side effects and unroll them internally into a sequence of operations that get sent to all cores simultaneously. That would be analogous to how shaders work (and potentially MATLAB, Julia, maybe Clojure), but on the CPU itself so we wouldn't need GPUs anymore. We would just download a library that provides an OpenGL interface or whatever, but runs in ordinary userland code without having to worry about manually passing data around in vertex buffers. I'd really like to see this done in perhaps a small microcontroller for under $100, that would run circles around the most expensive processors for certain workloads. I was also thinking that maybe someone could make 1 core that provides a roughly 90s level of performance like a MIPS or PowerPC 601, or even DEC Alpha, running at perhaps 1 GHz with no cache, for under $1. Then a grid of those cores could be laid out on a board with self-organized mesh networking using content-addressable memory and copy-on-write to automagically ensure data locality. Then we'd have a scalable architecture and wouldn't have to rely on video card manufacturers. Moore's law allows for just exactly what I'm saying here, it's just that nobody's done it, because we're used to centralized control of the supply chain, and we all spend all of our time making rent, because the open source funding model is broken, etc etc etc. I've ranted about this endlessly in previous comments.
- memco 4y agoTangentially related, but I’m interested in doing file system traversal for finding some paths in Python: using a simple scandir to process takes minutes on the data I’m working with: shelling out to find is faster but still takes minutes. I know ‘fd’ exists and does parallel traversal, but I’d like to learn more about how to implement something like that: what structures do file systems use and how do you know what limitations should be considered when working with files?
- deleted 4y ago[deleted]
- keepquestioning 4y agoLockfree algorithms are a misnomer. The lock is an atomic instruction.
- SighMagi 4y agoThat was my take away from "lock-free" talks, as well as needing a deep understanding of the machine's memory model and instruction set.
- Thiez 4y agoA "lock" in programming generally refers to a mutex, semaphore, or similar mechanism implemented mostly in software, e.g. see here https://en.wikipedia.org/wiki/Lock_(computer_science) https://en.wikipedia.org/wiki/Lock_(computer_science) . The distinction between such locks and atomic instructions is useful, since atomic instructions have various nice properties that locks (or "other locks", if you want to count atomic instructions as locks) do not, such as having no chance of deadlocks, guarantee of (eventual) progress, no chance of interruption, and no chance of blocking other threads forever when a thread executing an atomic instruction gets unlucky and is never scheduled again. Naturally lockfree algorithms built with atomic instructions may not have (all) of these nice properties. What better name would you suggest for lockfree algorithms?
- duped 4y agoIf you're being pedantic, atomic instructions are a misnomer. But "Lock free" is a property of parallel algorithms where if there's N > 1 processors evaluating an algorithm, there is no state where the algorithm cannot make progress ("locked" meaning "all N processors are waiting") Whether you want to debate if a physical system can realize a lock-free algorithm is a different debate. Hell, half the "well known" lock-free algorithms assume memory allocation/reclamation isn't blocking.
- dang 4y agoRelated: Lockfree algorithms - https://news.ycombinator.com/item?id=4103921 https://news.ycombinator.com/item?id=4103921 - June 2012 (14 comments)
- reitzensteinm 4y agoI was about to post here that with the upcoming Zen 96 core chip we're now 40% of the way there to the name of the site. Then I clicked on your link and ten years ago I was making basically the same point about Haswell EP. See you all in ten more years.
- moonchild 4y agoAzul boxes had 768 cores...
- reitzensteinm 4y agoYeah, I didn't realize that until somebody corrected me on the linked thread. But it turned out to be an evolutionary dead end.
- int08h 4y agoDmitry Vyukov has forgotten more about non-blocking synchronization (lock- and wait-free algorithms) that most developers presently remember.
- kasey_junk 4y agoHe’s invented more of them than most people know…
- snakey 4y agoThanks for this! I've been diving into the basics of lock-free datastructures recently. Some posts that I've been working through which I've found useful: - https://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-c++ https://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-... - https://drdobbs.com/parallel/lock-free-queues/208801974?pgno=1 https://drdobbs.com/parallel/lock-free-queues/208801974?pgno...
- bsaul 4y agoSide question : could anyone recommend exercises for mid-experienced developer that really has troubles spotting potential race conditions, and generally struggle with concurrency ? I’ve realized i’m spending a lot of time reviewing his PR, and i’d like to help him improve faster on that topic.
- neilparikh 4y agoI enjoyed http://deadlockempire.github.io/ http://deadlockempire.github.io/
- avgcorrection 4y agoBased on the dragon this Deadlock Empire must be Wales.
- maldev 4y agoIt's actually really easy. Traditional threading has a very obvious design pattern, where if someone isn't doing this you can be sure there's an issue. TL;DR, if you don't have a "getter/setter" you're doing it wrong and it's a sign of bad code. Firstly, make sure that there's only ONE place to write. Write being changing the variable in anyway(Obviously make sure you have a lock or other primitive here). If there's multiple places, that's a big smell for a race condition, and a massive turd for a shitty design pattern. Secondly, just like the write, all reads should be done from a single place. And then for the advance developer, you also may need to make sure that the cache is synchronized. Pretty much all libraries will do this for you, but if you ever need to dive into internals that alot of "guides" or papers DON'T cover, you need Fences or whatever your architecture provides. I have this page bookmarked for when I need a quick refresher https://stackoverflow.com/questions/27627969/why-is-or-isnt-sfence-lfence-equivalent-to-mfence https://stackoverflow.com/questions/27627969/why-is-or-isnt-...
- gpderetta 4y agoSorry but it is not easy at all. Getter and setters do not help and can give a false sense of security. And caches do not need to be explicitly synchronized. On all common platforms the hardware will do it for you without user intervention. Fences have a different purpose.
- bob1029 4y agoI would also recommend this article to anyone who struggles with making many threads do useful amounts of work: https://lmax-exchange.github.io/disruptor/disruptor.html https://lmax-exchange.github.io/disruptor/disruptor.html
- anonymousDan 4y agoIn a similar vein, this is also an interesting approach to avoiding synchronisation overhead that works for many data structures: https://www.cs.bgu.ac.il/~hendlerd/papers/flat-combining.pdf https://www.cs.bgu.ac.il/~hendlerd/papers/flat-combining.pdf
- bob1029 4y agoThis sounds very similar indeed. The central thesis of the paper seems to be that the grain of locking is the concern, which is what Disruptor directly touches on as well. In a Disruptor implementation, you are typically processing batches of things, and locks can be acquired along lines of batches.
- gpderetta 4y agoThat's very interesting, thanks.
- shultays 4y agoIsn't the very first example error prone? The one under Wait-freedom https://www.1024cores.net/home/lock-free-algorithms/introduction https://www.1024cores.net/home/lock-free-algorithms/introduc... A thread can easily decrease the reference count to zero and delete the object while another thread is trying to add reference
- pkhuong 4y agoReference counting algorithms usually assume that code increments through a strong reference.
- gpderetta 4y agoFor another thread to be able to add a reference, it must already have a reference to that object, so the reference count can't be less than two. Two threads can't be both operating on the same pointer object. Reference counted pointers themselves are usually not atomic, only the reference count updates are. To atomically access the reference counted pointer itself, you need either a different algorithm (using hazard pointers for example), or some form of mutual exclusion.
- shultays 4y agoAha, makes sense. Thanks for the explanation
- pdpi 4y ago> Reference counted pointers themselves are usually not atomic, only the reference count updates are. Fun way to start an argument where everybody is wrong: ask a group of C++ programmers whether std::shared_ptr is thread-safe.
- TillE 4y agoshared_ptr's thread safety is simple: it's perfectly thread-safe as long as each thread has its own copy. It of course does not provide any synchronization for the object it's pointing to.
- sylware 4y ago"lockfree"? You mean "heavy lockfree" I guess since atomic depends on implicit hardware locking for proper operations. And those algos are so much critical and dangerous, a mathematical proof must be provided and peer-reviewed. For example, as far as I can remember, reader-writer ring buffer with atomic read/write pointers. You have such ring buffers in USB xHCI, and AHCI and NVMe.
- CyberDildonics 4y agoLockfree means one thread is always making progress. If two threads contend over an atomic operation, one succeeds and one fails. If you spend some time using atomics they might not seem so scary anymore.
- sylware 4y agoboth threads can make progress at the same time.
- CyberDildonics 4y agoLockfree means at least one thread is always making progress and atomics allow that trivially. If an atomic operation fails it means that a different thread's atomic operation succeeded. I didn't make up this definition. https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-fr...
- sylware 4y ago