I think Go adds even more complexity to concurrency by pushing the CSP model. CSP is hard for many problems where classic shared-memory using locks and atomics are well defined (think of classic concurrency programming textbooks).
Go provides all of that, you have sync.Mutex and sync.Cond, and you are of course free to use them. People do use them in practice, precisely because some code is easier to write that way.
Saying that Go "adds even more complexity to concurrency" doesn't scan. It lets you write code using whichever model you prefer--CSP or mutexes.
It is definitely true that CSP is hard for many problems... but locks and shared memory is also hard for many problems. There is no silver bullet, so you need both.
Pretty much every time I’ve pulled out a channel in Go I end up rewriting it to just use a mutex, or even easier, write to individual indices in a slice.
You forgot to quote the most relevant part of my statement: "...by pushing the CSP model."
Of course you can do whatever you want, but Go is a very opinionated language and there's an opinionated community behind it. Which it's fine. But then when you ask "how to do X using locks," the only thing people respond is the mantra of "don't communicate by sharing, share by communicating". Which doesn't help in any way. Then people ask complex questions about using channels and others say "why don't you just use locks?" That's why I think Go adds more instead of alleviating the complexity of writing concurrent programs.
> You forgot to quote the most relevant part of my statement: "...by pushing the CSP model."
I didn't quote that part because it's the most nonsensical part of the comment.
You've apparently been frustrated by your interactions with the members of the community and that's a fair complaint, but you haven't translated that complaint into a criticism of the Go language itself.
My experience is--CSP is a reasonable default, and "select" is a really nice language feature to have around, and mutexes / condition variables are still available when you need them. Mutexes aren't a good substitute for CSP and CSP isn't a good substitute for mutexes. You should have both available.
That's exactly my criticism. You don't need both. You only add confusion by having both. Just stick to one and improve it. Most successful languages don't have native support for two concurrency models and people have built amazing concurrent software with them. Now with Go, you have this extra problem of "should I be using channels or locks?"
In my experience, you definitely want to have both options available. Like you said:
> CSP is hard for many problems where classic shared-memory using locks and atomics are well defined (think of classic concurrency programming textbooks).
This isn't a problem with Go's particular flavor of CSP, this is just a fact--it can be hard to translate simple modules that use locks into modules that use a CSP paradigm.
> Now with Go, you have this extra problem of "should I be using channels or locks?"
I think you're arguing against yourself here... if it's important to answer the question "should I be using channels or locks?" correctly, then wouldn't you be in a bad situation if the language only provided channels or only provided locks?
This is no different from the problem of "should I use recursion or iteration?" or "should I use a tree or a hash table?" Some times, either option is workable, but at other times, one of the options is better than the other. CSP versus locks is the same thing, it's just another decision you have to make when programming.
No they are not. You can easily do concurrency with a fork-join approach on just on thread (no parallel execution). fork-join in the browser with e.g. V8 as the runtime is a good example of that.
Look up 'forking web server'. It predates common multiprocessors. Why do you think that is? Because it's useful for concurrency even when there is no parallelism.
> Isn't that a natural, expected part of concurrent programming?
No races aren't an inherent part of concurrent programming - you can make it safe.
> If it has to happen in a particular order, you can't do it concurrently.
I didn't say things had to happen in a particular order, just that their results are merged in a well-defined order. Otherwise you could test against one particular ordering that happens by chance, and then in production you get another order by chance that you didn't test against and it doesn't work! That's what you get with Go.
Messages coming out of order are a cause of race conditions.
> You just want to structure your messages in a way that the order doesn't matter
Right... just program without bugs and you won't have any bugs! The problem is people forget to do this, or think they're doing it when they aren't, and they get a failure one in a million. I've done it myself! Why not use a system where it's impossible to depend on message order in the first place?
If you've got a system that makes concurrent programming just as easy as non-concurrent programming I'm sure people are willing to throw a lot of money at you. I'm not aware of any way of doing it that frees you from structuring things so that the order that operations happen in is not important.
In theory I like channels, in practice I find them challenging to program with. The fact that only the sender can safely close a channel is frequently frustrating.
I think the Go docs can be more discerning about when to use channels and when to use shared memory. The broad advice of "share by communicating" is too broad, too many people learn Go and think they need to use channels and CSP everywhere, and then quickly realize that they've over-engineered their program.
I typically use shared memory by default (mostly mutexes and waitgroups), and generally only use channels when I'm working with task queues, which is where they really shine.
I know this is an excerpt, but there are a lot more reasons that concurrency is hard. One of the biggest ones is that your concurrency can look like it works, until it doesn't. Made worse by the fact that real-world concurrency can be hard to test locally.
I would suggest a change in wording. Concurrency is not hard, its asynchronous updates that are hard. That's why digital logic circuits use a clock, and it's also why mixing logic into event driven user interfaces eventually gets out of hand.
Everything gets synchronized at some point. There is no sense splitting hairs on labels just because you don't have to do the synchronization yourself. Those independent tasks are going to have to have their output go somewhere.
In some cases, perhaps most cases, this gets hard.
In other cases this is still easy. For example, when the ordering of the output doesn't matter. I'm dealing with such a case in a data conversion program.
A super simple example for when ordering doesn't matter is when you do parallel addition.
I'm not sure exactly what you are saying, but not all synchronization is about ordering. Addition is still synchronization since eventually multiple numbers will need to be merged into one output.
Sure, and that can cause issues potentially. But since addition is commutative [1], you don't have to wait on an exact ordering and synchronize for that. All you have to synchronize for is waiting until all the numbers are added.
[1] for HN'ers that don't know the word, it means a + b is the same as b + a.
Not everything shares the same global state. Two completely independent computer systems that are not in communication with each other will never become synchronized, nor would it be expected that their state is merged in any way. This line of thinking can extend into abstractions existing on the same physical host.
You don't even have to share global state to work towards the successful outcome of some common objective. There are many problems that can be solved with actors operating in parallel with absolutely zero coordination between them. This might seem like its a place where only trivial cases live, but I have found some fairly complex concurrency scenarios that can be refactored into this trivial case by decoupling actors/state and reorganizing other parts of the system.
For example - Assume you were to develop a database engine that uses sequential integers for the primary key. You would probably have to develop a complex synchronization mechanism so that sequences are dealt out uniquely to concurrent callers. Or, you could sidestep the problem altogether by switching to GUIDs (V4 - Random) and allowing each participant to key its own entities. I feel these sorts of decisions should be considered as a primary measure before reaching for any form of shared state.
> Two completely independent computer systems that are not in communication with each other will never become synchronized,
This is not what is being talked about when people discuss parallelism and concurrency since it is trivial. In that example all the tricky stuff has already happened. Lots of people looking at a painting is easy. Lots of people painting a single picture is hard.
Not handling the synchronization explicitly in your own program doesn't mean it isn't happening.
If you write to a disk, to a network or even just display pixels from multiple threads on a monitor, the synchronization is being handled for you.
> sidestep the problem altogether by switching to GUIDs (V4 - Random) and allowing each participant to key its own entities
That would be a concurrent hash map which doesn't side step synchronization, since you still have to deal with collisions, space allocation, ownership and lifetimes.
It also isn't the same as integer keys since you lose the ordering and lose the ability to do ranged queries.
Where synchronization is happening and how it is happening is important, but the idea that it is being avoided is nonsense. Letting something else do it can be sound advice. This however, is like saying that garbage collection means that allocating and freeing memory doesn't happen.
In my experience, simple concurrency is easy. Confused concurrency is exceptionally hard.
I think about this in the same way I think about C++. C++ is quite nice, if your teams limit themselves to a reasonable subset of the language. But it can become an absolute monster of cumbersome complexity, if these guardrails go away.
Concurrency feels the same. If you take a certain view on concurrency, which is "do it as simply as possible, don't break certain rules, don't try to be too clever," I find it fairly straightforward to reason about.
At the same time, 9 out of 10 of the hardest things I've debugged have always been nasty, awful concurrency bugs. The reason it was so hard? The concurrency was complicated, interwoven, assumption-laden, and absolutely impossible for anyone to reason about. Implicit contracts between calls required entire whiteboards of non-trivial state to understand, and even then, with all that work, it was a needle in a haystack.
I guess I would just say: It doesn't have to be hard. It's only hard if you don't respect it from the beginning.
Several different lists. You have to pick a concurrency model. Within that concurrency model, you pick some set of rules to follow which has the guarantees you want.
That's like asking, "How do you know what algorithm to use?" You can come up with a justification for why a particular algorithm may be suitable for your purposes, but you'd be hard-pressed to explain how you go about choosing an algorithm. It's the same way with rules for a codebase... you can justify why you are using a specific set of rules, but explaining the decision process that led you to choose those rules is much more difficult.
That's why tech leads don't grow on trees.
I'll add to what the original comment (about "confused concurrency") was saying, because it matches with my experiences. The good lead developers are the ones who are able to get the job done (design systems) and keep the concurrency model simple. It's often possible to keep concurrency mostly simple and mostly safe.
I worked on a large extremely high performance system (dozens of developers) that’s almost entirely lock free, and constantly mutates shared state. Concurrency issues weren’t really a big problem in that code base. Developers took a long time to ramp up, but that’s an OK tradeoff in my book.
None of this would have been possible without lead developers that designed and continuously refined the guard rails that our internal “standard library” implemented.
Oddly, I now find it easier to reason about lock free algorithms than mutex based code (and I wrote the latter for 15 years before working on the lock free system)
>Oddly, I now find it easier to reason about lock free algorithms than mutex based code
That is because lock free code composes. Mutex based code does not compose. With lock free code, I can freely call another function, knowing I cannot deadlock. With mutex based code, I have to be really careful about the state of my mutexes and think if the code I am calling will attempt to lock one of the mutexes I am holding, thereby causing a deadlock.
thanks for the correction. I thought even with that guarantee, there is no bound on progress (so progress can in fact be very slow). lock-free algorithms are not used much because of the slowness, AFAIK.
Lock free means that at least one thread is guaranteed to make progress. You might be confusing this with atomics, which could still be used in a spinlock and would then not be lock free.
I find this is nonsense. Code is the best documentation; I've watched people spend hours debating a spec that becomes obviously broken as soon as you spend 5 minutes writing it up in something with a typechecker.
Write the specification as code - make sure it's something that can actually be checked. Then you'll know whether it's actually any good.
Documentation is written in a human language, can include other media like graphics and is addressed to humans. We write documentation for the same reason that we don't produce maps at a 1:1 scale: documentation offers a higher-level description that can be grasped without having to understand all the code.
Not only is code not the best documentation, it's not documentation at all, outside of special cases where the entire code describes e.g. an algorithm and is encapsulated into one function.
Code should have a hierarchical structure, so one could read it on the high level of abstraction and also zoom in gradually, as necessary — this is what they usually mean by “code is the documentation”, plan the reading process as you plan the functionality.
It is a very important aspect of the readability, otherwise you will just sink in details when reading. But it is not easy to formally validate with tools, so naturally it is better to have both code and a picture and have discipline to keep them in sync.
> Code should have a hierarchical structure, so one could read it on the high level of abstraction and also zoom in gradually, as necessary
I agree with this. Some of the best code I've read and written was done in this style. Properly separating out components into a hierarchy of modules.
> this is what they usually mean by "code is the documentation"
I disagree with this. I don't think this is what people mean at all, because I don't think that most people do the first part. If they did, there wouldn't be so many problems with "code is the documentation". But most code is not written in a clear hierarchical fashion. Logic is weirdly commingled, and depending on the language you have an assortment of low-level bookkeeping mixed with high-level logic.
I think they literally just mean "code is the documentation". One of the best/worst programmers I ever worked with is a perfect example of this. He'd always insist on the "code is the documentation", and his code always worked. But his code was absolutely awful to read for anyone but him. By way of analogy, I don't have a file system for physical papers. I have a literal chronological (by access time) stack. No one but me can make use of it, but it's very effective for me because I have a really good memory (though not as good as it was 20 years ago, I don't actually do this anymore because I have to work with others). That's his code. No one else can go into it and actually understand it (at least not easily), but he can jump in and make exactly the necessary changes. The code is not the documentation until it's properly organized, and maybe not even then.
> I find this is nonsense. Code is the best documentation
Strangely, I find both gp and your claims to be nonsense. :-)
I've definitely experienced what you've experienced -- until you actually have code, you don't know what works and what doesn't work.
But it's frequently not at all obvious what code does, even in the normal case; and even code which looks obviously correct often has hidden complexities that you wouldn't have thought of.
I find trying to explain in a comment why the code I've written is correct is pretty good in wheedling out all the ways in which it's not actually correct.
So when things are really complicated, you need both: You need to have code that actually works, and you need to have text that attempts to prove that the code actually works.
> I find trying to explain in a comment why the code I've written is correct is pretty good in wheedling out all the ways in which it's not actually correct.
I found that well written, expressive tests accomplish that really well.
I use Spock[1] to write complex tests and I just can't recommend it enough if you're working with the JVM (Java, Kotlin, Groovy, Scala, Clojure).
We have several thousands of Spock tests and it's amazing how they have scaled with us... they've grown to support extremely complex workflows that have nearly zero accidental complexity and are easily readable even if you have no experience with it.
With Clojure, are you writing tests in the Spock DSL (or is that Groovy?) or are you writing the tests in Clojure and importing Spock as a library and extending its classes etc?
Spock tests must be written in Groovy, but they can call helpers from any JVM language, so we normally have lots of test helpers (traits) which we use to write tests with one-liners per action/assertion.
If you write your app in any JVM language, you can use Spock to t test it because Groovy really has excellent interop with Java, hence JVM languages in general.
"make sure it's something that can actually be checked" -- I'd love to find out about a sane (not purely academic, financially viable) way to do it. Since university days I know that a piece of paper is an irreplaceable tool - cheap and universal. I usually just draw it on paper, then code, then fix the code, then update the painting, and do it over again until both match each other and work. Never fails me.
That's the key difference between forward engineering and hacking shit together.
There is nothing wrong with prototypes but some people mistake them as production ready items because it looks like a whole load of work has been done.
I disagree in the general. It's very easy to write a spec that contradicts itself and is impossible to actually implement.
Some things do have to be designed, and not just thrown together though. That may be through spec, but it could also be working things through on paper. Concurrency is certainly one of these. Other things need to be iterated on in code. I'd hate to play a platformer where the movement mechanics were specced out by a comitee before any code was made.
This is incredibly vague. There is no "set of rules" that just magically works without thought.
There is just SOOOO much that can go wrong. But one general rule crystallizes itself pretty quickly:
DO NOT EVER MUTATE STATE!
I.e. when you write concurrent code that builds on state mutation, you are opening Pandorra's box. If you want concurrency that people can understand and maintain, write immutable, functionally pure code (same data in, same result out, no exceptions). That is relatively easy to police and enforce, while still flexible enough to solve most use cases. It may however, not be the most performant.
Mutation is not merely a performance optimization, but makes code more concise and expressive. Mutation makes things like `cfg.tabs[2].title = "Suspended"` possible to write in one line. Trying to achieve the same thing with only immutable data structures forces you to clone title, then clone cfg.tabs[2] with a new title, then clone cfg.tabs with a new [2], then clone cfg with a new tabs.
You don't need mutation to write that expressively; you can achieve the same thing with lenses. With the advantage that if you ever get confused about what's happening you can break the lens down into what it's "really" doing and reason about that, in a way that you just can't with language-level mutation.
Syntax shortcuts are good when they're built on a rigorous foundation. But if you build a shortcut directly into the language, you'll never be able to retrofit a reasonable model for how it works.
cfg.lens(tabs).composeOptional(index(2)).lens(_.title) set "Suspended"
You could certainly define a shortcut to simplify the `composeOptional` part, but doing it explicitly like this makes it clear that we actually have to make an important choice: what do you want to happen when there is nothing at index 2?
Thank you. To me that seems significantly more verbose, is it possible at least to pack it into a generic function and apply it to most/all assignments?
The mixing of the array access (which is another piece of language-level special-case syntax) with the properties is what makes it verbose - "normally" you could just do something like
config.lens(tabs[2].title) set "Suspended"
Admittedly that relies on a macro, but the macro is pretty lightweight syntax sugar - if you wanted to do it in 100% vanilla code you'd need a .lens at every step and a slightly more explicit way to name the "properties", i.e.
config.lens(_.tabs).lens(_(2)).lens(_.title) set "Suspended"
> is it possible at least to pack it into a generic function and apply it to most/all assignments?
I don't quite understand? You can certainly write generic functions that work for any lens whose "target" is a given type.
I've heard about lenses, but never actually worked with them. This syntax seems to construct a "path" of sorts from the root to a field. What language is this? What type does the `set` operator/keyword return?
It's Scala with Monocle (and it's off the top of my head, so apologies for any mistake). `set` usually returns a function for transforming values of the root type, but this simplified syntax will apply it immediately to `config`, so it'll return a copy of config with the modification applied to it.
Mutating state is by far, the most efficient operation on the computer. Copying state means (usually) calling the memory allocator, which (usually) must be done in a sequential manner. There are optimizations to allow memory-allocation to occur in parallel, but... things start to get inefficient (use of thread-local storage, which makes many pointer-indirections, etc. etc.).
-------
Why do people program parallel code, despite its overwhelming complexity?
Simple: to be faster. That's it. Its an optimization, arguably premature, but the programmer reaching for the "parallel" button is going for optimization for a reason.
------
Sequential code with state-mutations could very well be more efficient than parallel code with tons of unnecessary copies. Registers are fast, L1 cache is fast, etc. etc. Doing an operation, then undoing it (entirely inside of register space) is so incredibly fast, it will make your head spin.
-------
1: Write code.
2. If code isn't fast enough, single-thread optimize it. This usually means mutating state in an intelligent manner.
3. If code is STILL not fast enough, multithread it. You make a copy of the state, and then have multiple threads (each with their own copy of the state) doing... whatever you're trying to do.
> Mutating state is by far, the most efficient operation on the computer.
Really? I mean like pretty much every instruction has separate source and destination addresses/registers, memory caches obviously complicate things, but it seems that processing data from one location to another is the most efficient operation.
> Copying state means (usually) calling the memory allocator
Sure, I guess if the main conception of moving data around involves not really knowing where it needs to go, and having to figure that out, that's somewhat true. But there are many ways to structure computation that minimizes or avoids allocator usage.
> unnecessary copies
I think this is the issue, if you have to copy first then do in place mutations, of course it'll be slower, but you can instead structure your entire computation to process your data from one location to another, then all your points about registers, and L1 cache being fast, holds true while still being able to handle immutable data
> Really? I mean like pretty much every instruction has separate source and destination addresses/registers, memory caches obviously complicate things, but it seems that processing data from one location to another is the most efficient operation.
I can't think of any algorithm where copying is faster than mutating.
* Chess Bitboards: Make / Unmake is a methodology for a reason.
* Mergesort: In-place mergesort is far faster than copy-merge sort. Its much harder to write in-place mergesort, but it really makes a big difference.
* Quicksort: In-place quicksort is faster than copy quicksort. Every "pure functional" recursive / copy quicksort has been... subpar... in my experience.
* C++11 created a "destructive move", the entire R-value references system, because of the hugely more efficient concept of destructive / mutating moves. Destroying the old data while copying the data to a new location (aka: std::move) is far more efficient than making a safe copy (aka: copy-constructor).
-------
Side note: The SIMD "Mergepath" Mergesort is absolutely brilliant. It uses absolutely no mutexes (and only uses thread-barriers) to guarantee that all writes are independent and correct. Furthermore, "Mergepath" mergesort parallelizes maximally (one-element per processor), while retaining O(n * log(n)) sort speeds.
Because thread-barriers are no-ops on a SIMD computer (like AVX512), the thread-barriers in the MergePath concept are maximally efficient. :-)
-------
What algorithms are you thinking of where copying is faster than mutating? At best, a copy ties mutation in speed. In a huge number of applications, mutation (aka: std::move) just faster.
But std::move cannot be done across multiple threads: that's innately thread-unsafe and must be synchronized (at least for typical objects).
---------------
Or maybe the above is too abstract? Lets go down to a very simple, but specific, algorithm. The Fisher-Yates (aka: Knuth) Shuffle.
As far as I know, there is no copy-based algorithm that can beat the Knuth Shuffle's O(n) computation complexity. It is extremely difficult to write a O(n) speed shuffle without mutating the array in place.
The fastest "copy" methodologies for the Shuffle problem I've seen involved generating a random number for each location, then copy-sorting the results: O (n * log(n)), which is asymptotically more complex than the Fisher Yates shuffle (and therefore: work-inefficient. If you parallelize to O(n*log(n)), there will be a size where the Fisher Yates shuffle is faster).
unique_ptr<Blah> foo = make_unique(...);
unique_ptr<Blah> bar = std::move(foo);
// foo is now effectively destroyed as part of the move;
foo->something(); // Will error, probably seg-fault. Foo is now "empty"
The value foo used to point at is preserved. But foo itself was destroyed from the std::move(foo); The foo->something() is almost certainly a null-pointer exception or seg-fault in any sane implementation of C++11.
unique_ptr's destructor happens to do nothing in a moved-from state. The fact that some types behave this way does not mean moves are destructive. They're still non-destructive. Indeed you're still supposed to call the destructor after a move, and the destructor very well _could_ do something in general. It's just that it doesn't happen to make any difference for typical implementations of some types like unique_ptr.
In fact there are people who have wanted destructive moves in C++, because they found the current non-destructive moves inadequate, but I don't believe the feature has ever been added. Look up destructive moves to find discussions on the issue.
I guess I'm being imprecise with terminology then. It seems like Rust has a concept called destructive move, which is not what I'm talking about.
In any case, the "foo" vector, and "foo" unique_ptr are _mutilated_ as part of the std::move operation. (Since the word "destroyed" seems to have been taken by the Rust community, I can't use that word anymore... hopefully no other community has taken the word "mutilated")
I think you have a good point about sorts, in that case mutation is almost always faster, but it seems to me that a large contributor, is that often much data doesn't need to be moved. So clearly no work is better than some work.
Having said that, I hardly see a sort being the majority of time spent in real-world code.
> Because thread-barriers are no-ops on a SIMD computer
My understanding is that only holds true across the SIMD lane, and the algorithm doesn't hold up so generally to general purpose concurrency. But agreed, a sort is something I'd likely try to optimize on a single core, and express program concurrency outside that specific operation.
> What algorithms are you thinking of where copying is faster than mutating? At best, a copy ties mutation in speed.
My main point is it's actually the case that a copy ties mutation in speed quite often if you structure the flow of your data correctly. If you're operating on a value, writing it somewhere else is often close to free.
Having said that as an example, I've seen filtering a list run faster doing a move, highly dependent on the details of the cache of course.
> that can beat the Knuth Shuffle's O(n) computation complexity.
I haven't considered shuffles specifically. But getting into the rut of complexity evaluation alone dismisses important aspects of the machine and the data you are actually operating on, and can lead you very far from the fastest solution for the problem you are actually trying to solve.
> I think you have a good point about sorts, in that case mutation is almost always faster, but it seems to me that a large contributor, is that often much data doesn't need to be moved. So clearly no work is better than some work.
I disagree. Even for a simple situation:
[9 1 2 3 4 5 6 7 8] -> [1 2 3 4 5 6 7 8 9]
All 9 elements have to move to a different memory location!! In fact, assuming a randomly shuffled array with all different values, I'd assume that the most common situation is all elements being forced to move somewhere else. But I don't feel like doing the rigorous math to prove it. I'll so something simpler:
If there are N locations in an array, the probability that a random element is in the right spot is 1/N (I think anyway). With N elements, that would be an average of 1-element in the correct spot (assuming uniform random arrays). There is only one-sorted array, but factorial(n-1) array without any element in the correct spot.
> I haven't considered shuffles specifically. But getting into the rut of complexity evaluation alone dismisses important aspects of the machine and the data you are actually operating on, and can lead you very far from the fastest solution for the problem you are actually trying to solve.
Sure. But Knuth shuffle uses nothing aside from "Swap" instructions and a 32-bit (or 64-bit) RNG. Its really simple and fast. That's why that algorithm has stood the test of ~40 or 50 years of use, its probably the optimal algorithm for shuffling on a single-thread.
> My main point is it's actually the case that a copy ties mutation in speed quite often if you structure the flow of your data correctly. If you're operating on a value, writing it somewhere else is often close to free.
So, here's something. I think that a copying-based methodology can be fast, but more importantly, a copying-based methodology can be easier to parallelize.
If a mutating state is too hard to parallelize, I think rewriting things to be copy-based, and then using that copy-based methodology as a basis for parallel code, is a good idea.
What's difficult is that "mutating state" is a local maximum so to speak: probably the fastest that any single-thread can get to. From this perspective, finding parallelism from a "higher level" can be more useful than trying to parallelize a well-optimized single-threaded program.
----------
Case in point: Multithreaded producer-consumer queues are difficult to write and even define. But multithreaded producer-producer queues (and consumer-consumer queues) are very easy: just an obvious "atomic_add(tail, 1)" (Producer) and "atomic_subtract(tail, 1)" (for consumers) kind of thing.
I call it a "producer-producer" queue, because you need assurances that no one is consuming from the queue for it to work. But if you synchronize your threads to all copy to a queue (and no one consumes from it), its really fast, and actually very parallelized. Ditto for the reverse (the consume phase).
I recently wrote some of the type of code that you would be upset to read, so maybe someone can sympathize with this a bit.
The task at hand wasn’t easy at all, it required both:
1. Making numerous network requests (some endpoints support batching, so do that as much as possible)
2. The entire main loop needs to be as fast as reasonably possible
The only real way to satisfy both, given that serially executing the network activity would waste tons of time, was some fairly tricky concurrent logic. I ended up using a few queue structures to collect day before making batch network calls, and stitching together all of the results at the end (block on all work threads, collect, report, then start next iteration)
Every step along the way made sense, every addition of complexity felt justified. And the first person to come to me asking how the fuck it got so complicated is frustrated, so my knee jerk reaction is to get frustrated back saying well how else could we satisfy complex requirements with a complex solution.
We should always be challenging ourselves and others to keep solutions simple, but remember that the simplest solution may itself still be complex.
Could you not have used a simple thread pool model in your case? That would be a trivial parallelization of your network requests with limiting on the resources (number of parallel connections)
Otherwise when the logic gets complex I try to model it as independent threads each having a well-defined role (e.g. exclusive write access to SQLite) communicating with channels. Although I tend to code these things in Rust, the language who taught me that philosophy is Go.
IMO the key is always to be compositional. E.g. here you should be able to separate the batching up requests from the performing network calls, and then you can test and reason about both pieces separately. I find the iteratee model is really good for this.
Always have a drawn picture, if you cannot draw it you will fail to explain it to others (and to see design gaps) and inevitably everyone will think it’s an over engineered complex shit.
Design-wise:
The IO multiplexing — event loop(s), the completion callbacks go to the "Processing".
Processing — usually beneficial to model as a processing graph (tree/pipeline being specific examples of a graph without feedback loops). It's a clean, low overhead abstraction, easy to visualise (and thus discuss with others), easy to change structurally or in the "aspect oriented" way.
Examples in JVM world: Netty pipelines, AKKA actors, streams, and graphs, in C++ world ASIO & its executors sub-framework.
Queues/Threads is still a sufficiently low level to comfortably operate on.
One needs to pick the concurrency model and design up front. Document it before writing a single line of code. Then stick to the plan. It takes discipline, but it's not difficult.
I mostly write in C with pthreads and as long as one is willing to apply discipline to the task, there's no reason to fear concurrency.
If one starts adding a thread here and a mutex there and some shared structures over there without any prior plan then yes, absolutely, that leads to a world of hurt and a deep hole that is very difficult to get out of. So, don't do that.
> "do it as simply as possible, don't break certain rules, don't try to be too clever,"
This has to be a universal rule of programming. It's equally true for Ruby and Perl, which are extremely effective languages, but devolve quickly because of their uncanny ability to power cleverness. It's the whole premise of Go, by being boring by design.
Complex is easy, simple is hard, but it seems mostly because we fail to be able to resist the allure of cleverness.
I will argue that Go's concurrency model is fundamentally flawed[0] precisely because its underlying mechanism is hidden from the user. If it wasn't for this model I would be using Go instead of C and probably instead of a lot of other alternatives.
Yes Go the language is boring and I like this idea, but the runtime is a black box, that I don't like so much.
You just sum up the entire raison d'être of reactjs and the stores ecosystem around it: force all the team to "do it as simply as possible, don't break certain rules, don't try to be too clever".
It's not that react, redux and cie are something new or disruptive. It just enforces a set of design rules that turns a lot of concurrent inputs and outputs into a linear workflow.
The best way to make concurrency easier is to avoid it in the first place. This requires you to think about how correct your data really needs to be.
For example, a bank balance. Most people would assume that bank balances must always be correct. But this isn't really true. Back in the days when people wrote checks, your bank balance was almost never accurate -- it was on you to keep a local register and know your balance, and if you shared the account with someone else, to reconcile with them frequently. ATMs also use eventual consistency. When you take out $300 from the ATM, it attempts to update the balance, but it will let you take the money out if the bank is unavailable. Because the bank is willing to risk $300 that you aren't overdrawn. In most cases the "eventual" part is nearly instantaneous so you don't notice, but it doesn't actually have to be.
So the number one way to make concurrency easy is to avoid it altogether.
Delayed syncing is not the same as "avoiding concurrency altogether" or having data be 'less correct'. Those aren't even simplifications for relaxing the latency of synchronization, they aren't correct descriptions at all.
My point was that your simplifications were not correct. Also synchronization is going to happen at some point or there wouldn't be any problems to talk about. Synchronization is what it all comes down to.
Yet your example is not one of them - with accounts, the sequence of states must converge on a consistent history as they recede into the past.
Eventual consistency comes with it own set of counter-intuitives, and is a multiplier of possible states a system could be in. it is generally not a complication we would choose, but something we must cope with to do things that would otherwise not be feasible.
One of the unfortunate consequences of Go "making concurrency easy" is that many more concurrent programs are now being written by amateurs, with predictable results. This feels like a Hickey-an "simple vs. easy" dichotomy -- what would a language look like that tried to make concurrency simple, rather than easy?
I’ve found Elixir (+Erlang/OTP) to have some incredibly powerful primitives that make it fairly simple to develop concurrent programs.
OTP underpins WhatsApp, Facebook Messenger, and Discord. People have been building very cool high availability embedded Linux projects using the Nerves framework. It’s very good for certain types of concurrent programs.
It won’t take over HPC simulation any time soon, but most of us aren’t working at Sandia, Oak Ridge, etc. Its great for systems that should naturally scale out but don’t map naturally to a GPU. For systems that want to scale up but are forced to scale out due to frequency limits, it’s not as good as C++ written with uArch in mind.
I like Erlang/Elixir but I still see a lot of code with obvious race conditions.
The difficult part I find with Elixir is that processes have a lot of roles: fault isolation, concurrency, synchronization, garbage isolation, maybe more. I've had projects where it's difficult to line these up - one design would be ideal for fault isolation, but it forces expensive copies to be made, so I can't use that design because it completely tanks performance.
> I like Erlang/Elixir but I still see a lot of code with obvious race conditions.
Race conditions? Are you sure? AFAIK, that's pretty much impossible in Erlang/Elixir.
I do get with what you are saying with the second part of your post. That can indeed become an issue sometimes. Certainly one that I've struggled with myself, especially when things were still new to me.
But in my experiences, all those (apparent) conflicts/challenges can be mitigated/solved with proper architecture. Granted, that takes experience, which not all programmers may have (yet).
At the end of the day, programming is a skill and (inexperienced) programmers can always dig themselves a hole, in any language. Elixir is not a silver bullet, that magically solves problems without having to work (hard) on finding the right solution/architecture for a given (complex) problem. Still, in my experience, Elixir makes large/complex distributed systems, and in particular concurrency, a heck of a lot easier than it used to be (for me).
Anytime the validity of an operation depends upon the state of multiple processes you need to make sure you aren't creating a race condition, and depending upon your solution you might introduce a chance of deadlocks or timeouts.
If it's just 2 processes then it's pretty easy: process 1 asks process 2 to modify itself, then process 1 modifies itself. However, this can lead to deadlocks/timeouts if both P1 and P2 are attempting to perform this operation at the same time.
And once you're into 3 or more processes, message passing as a method of synchronization breaks down.
Ideally you avoid this stuff with your design. But since processes fill so many roles you can't always avoid it.
I will have to agree with this. Until I started working with Erlang/Elixir, I would probably have agreed with the OP article instead. Or at least its title, for reading about concurrency problems has become rather obsolete (for me).
For years, I certainly made my own share of concurrency horrors, in everything from C and Python to Java and JS. Eventually I (sort of) got it right in each, mostly by building up experience in approaching it the right way. But it always remained a source of easy to make mistakes (and sometimes near-impossible to solve complexities, with larger systems).
However, since working with Erlang/Elixir, I sometimes wonder what the F#$& I was doing all that time. Many ideas were certainly a bit challenging to wrap my head around at first, but once they clicked there (kind of) was no way back.
This will probably sounds arrogant, and it's okay with me if I get down-voted because of it. But the more I work with Erlang/Elixir (and a few others in the FP field), the more it becomes clear to me how much the languages I used to program in (and their typical challenges), now most of all look like a (rather sick) joke to me. Again, I know this might sound pretentious, if not offensive. But it is sincerely what I feel. In my defense: I'm not some kind of hipster, still wet behind the ears. I've been programming for nearly 3 decades and in well over a dozen different language. I'm one of those kids that were ripping apart assembly code of "protected" games and desktop software, and hacked around on micro-controllers, during the nineties.
While Erlang/Elixir may have shortcomings too (although I personally have not found any), it is one of the best things I've encountered for a long, long time. I'm also charmed by ClojureScript, but for totally different reasons. However, I do like it for when I'm forced to build something more complex for browser/front-end. But that's a whole different story, and not much relevant to this concurrency "issue".
> I will have to agree with this. Until I started working with Erlang/Elixir, I would probably have agreed with the OP article instead. Or at least its title, for reading about concurrency problems has become rather obsolete (for me).
That summarizes the problem with most of the articles and discussions on concurrency. People talking past each other because those who don't do much concurrency, especially complex concurrent software, haven't reinvented Erlang yet and don't understand what the fuss is about, and those who do can't explain in relatable terms how the actor model helps them organize concurrent code, preserve local reasoning, abstract, compose it, tolerate faults, etc. and eventually they stop bothering and so poor concurrency articles and comments continue to dominate the infospace.
One thing to realize here though is that this isn't the language that is solving your problems here, it is architecture and methodology, probably combined with being able to leave some performance on the table.
Libraries and tools could replicate this in C++. A lot of people love erlang/elixir and have success with them, but I think it's a mistake to attribute it to the languages themselves and not the beam VM + the ecosystem around it because it misses the deeper understanding of concurrency techniques that work.
I get what you’re saying but it’s not fully right. In c++, the language allows you to have infinite loops. In erlang/elixir you can’t - you need to do recursion instead. This language feature makes sure that one piece of code doesn’t lock a core indefinitely.
That’s why Java/scala’s akka is crazily complicated. They encourage you to use futures so you don’t lock a core! So suddenly you’re still dealing with concurrency but with even more complicating layers.
Your example has no overlap with what I was talking about.
What you are saying is about iteration in the language and does not have anything to do with concurrency or architecture.
There is also nothing difficult about avoiding infinite loops in C++. There is a for loop to iterate through a data structure, or you just can just make a macro to iterate a number of times. This is not something that would cause anyone to feel like a big problem has been solved. Recursion for iteration only has advantages when compared to loose while loops. Once more structured iteration came about, using recursion for iteration is just an awkward and overcomplicated hack that obscures something simple.
> What you are saying is about iteration in the language and does not have anything to do with concurrency or architecture.
> There is also nothing difficult about avoiding infinite loops in C++.
I don't know how to explain it to you if you think you get it already but you don't. Please come into the discussion with an open mind.
Making sure every library you use won't ever block a core is not trivial. If it's a feature of the platform, then it becomes trivial. On Erlang it's a feature of the platform, in c++ it is not.
I've written about it elsewhere, but I think that concurrency is easier if you really stick to a methodology.
Fork-join is the simplest methodology, and supported in a very wide number of languages. In fact, its so stupidly easy, you probably are going to over-think it the first time you use it.
1. Fork when you need concurrency (aka: speed)
2. Join when you need consistency
That's it. Don't write mutexes, don't write barriers. Just join. That's all you need: if you ever need "synchronized" access, do it in the "single" or "master" thread, when all other threads are joined.
You _cannot_ have a race-condition if you only have one thread. Joins ensure that only one thread is running. What else do you want?
Fork-join parallelism has relatively low utilization. Its not the fastest approach, but its the "easiest" approach in my eyes.
------------
The #1 issue with parallelism books, in my eyes, is that we start with mutexes and threads, which are a very hard way to do parallelism.
I argue instead: beginners should start with easy (but inefficient) forms of parallelism, and then work their way towards complicated tools as performance becomes more-and-more of a consideration.
and then there was a follow up to it saying the measurements were wrong IIRC, and then a further article showing, more or less that getting your own mutex replacement correct is so tricky that for 99.99% of programmers, just don't bother.
Concurrency is hard because we invented a bunch of theoretical machinery (semaphores, mutexes, condition variables,...) and embedded it in languages such that most of the programs one can express are bad: racey or deadlock prone. Compare with modern sequential languages which have near-perfect denotational semantics: anything which compiles means something.
If you want practical guidance, my best is to avoid all of the concurrency constructs that are taught in schools. Use log-structured single-writer multiple reader, wait-free, processes and shared memory.
A simple way to avoid the problems highlighted in the article is to use immutable data-structures.
If you need to update that across threads, am atom with CAS logic will usually be sufficient.
If you like it erlang style: an agent can serialize changes nicely.
If you need coordinated changes, use software transactions.
Of course: next we'll introduce deadlocks with DB transactions. Fun!
Good point. But as we know multi-tasking is really not truly parallelism, it just means interleaving and keeping the state of multiple sequential lines of thought in our "head-stack".
Async is difficult I believe because "thinking" in inherently sequential because it is based on mentally reciting some (serial linear single-dimensional) language in our head.
An alternative could be some visual language where parallel and even 3D lines can be drawn. A mental image of it can be in our head. So I think async inherently needs some kind of visual language to make it easier to grok.
For all running threads, imagine that every operation can interleave in any possible way. Since the permutations grows in factorial time, the only way to manage concurrency is through well-defined interaction points with no more than a few interesting parts of execution. Are there only 4 possible sequences of significant instructions? Cool. Almost any more and it gets hard to reason about because there are so many paths that aren't obviously enumerable.
Problem of getting the concurrency right is very much identical to the problem of getting the system design right.
In both cases it takes a lot of hard work to learn how to not produce "dead-borns" or "genetically pre-disposed".
In both cases the course of "least resistance" (using intuition instead of logical reasoning) used by many as the default will most likely fail you. To develop an intuition of what is easy and what is hard with both system design and concurrency design is a matter of years of hard work of trial and error.
The actual question is why the complexity is so counterintuitive. I think this is to do with the Dunning-Kruger effect (the less you know the more confident you are).
In both cases the solution seems to be to keep beginners away from this and to have the same consistent, peer reviewed, approach across the system, and a process of improving it in a structured way. And of cause prefer higher level abstractions -> computation graph, pipeline, event loop, etc. over just hacking an ad-hoc Frankenstein out of low level primitives (which seem totally "simpler" if you ask a beginner).
Modern, sane and productive languages usually come with strong abstractions for concurrent usage, e.g. atomic reference wrappers, thread safe wrappers (AtomicInteger) or special methods (Interlocked.increment) for numbers and concurrent collections.
With them and a basic understanding of single system concurrency, single system concurrency is and always will be trivial.
They are low level abstractions and they don't save from the hardest to debug and fix problems - race conditions and inconsistent states, especially in distributed applications.
No mainstream languages give you a solid high level abstraction to build on. Some frameworks, kind of, do: ASIO in C++, AKKA Typed Actors and Reactive Streams and JDK CompletableFuture in JVM world, etc.
133 comments
[ 4.9 ms ] story [ 101 ms ] threadSaying that Go "adds even more complexity to concurrency" doesn't scan. It lets you write code using whichever model you prefer--CSP or mutexes.
It is definitely true that CSP is hard for many problems... but locks and shared memory is also hard for many problems. There is no silver bullet, so you need both.
Of course you can do whatever you want, but Go is a very opinionated language and there's an opinionated community behind it. Which it's fine. But then when you ask "how to do X using locks," the only thing people respond is the mantra of "don't communicate by sharing, share by communicating". Which doesn't help in any way. Then people ask complex questions about using channels and others say "why don't you just use locks?" That's why I think Go adds more instead of alleviating the complexity of writing concurrent programs.
I didn't quote that part because it's the most nonsensical part of the comment.
You've apparently been frustrated by your interactions with the members of the community and that's a fair complaint, but you haven't translated that complaint into a criticism of the Go language itself.
My experience is--CSP is a reasonable default, and "select" is a really nice language feature to have around, and mutexes / condition variables are still available when you need them. Mutexes aren't a good substitute for CSP and CSP isn't a good substitute for mutexes. You should have both available.
> CSP is hard for many problems where classic shared-memory using locks and atomics are well defined (think of classic concurrency programming textbooks).
This isn't a problem with Go's particular flavor of CSP, this is just a fact--it can be hard to translate simple modules that use locks into modules that use a CSP paradigm.
> Now with Go, you have this extra problem of "should I be using channels or locks?"
I think you're arguing against yourself here... if it's important to answer the question "should I be using channels or locks?" correctly, then wouldn't you be in a bad situation if the language only provided channels or only provided locks?
This is no different from the problem of "should I use recursion or iteration?" or "should I use a tree or a hash table?" Some times, either option is workable, but at other times, one of the options is better than the other. CSP versus locks is the same thing, it's just another decision you have to make when programming.
Are you suggesting that one should strive to solve concurrency problems with parallel computing approaches?
No races aren't an inherent part of concurrent programming - you can make it safe.
> If it has to happen in a particular order, you can't do it concurrently.
I didn't say things had to happen in a particular order, just that their results are merged in a well-defined order. Otherwise you could test against one particular ordering that happens by chance, and then in production you get another order by chance that you didn't test against and it doesn't work! That's what you get with Go.
Messages coming out of order are a cause of race conditions.
> You just want to structure your messages in a way that the order doesn't matter
Right... just program without bugs and you won't have any bugs! The problem is people forget to do this, or think they're doing it when they aren't, and they get a failure one in a million. I've done it myself! Why not use a system where it's impossible to depend on message order in the first place?
I typically use shared memory by default (mostly mutexes and waitgroups), and generally only use channels when I'm working with task queues, which is where they really shine.
If everyone is working in parallel, but on independent tasks, there are no issues.
In other cases this is still easy. For example, when the ordering of the output doesn't matter. I'm dealing with such a case in a data conversion program.
A super simple example for when ordering doesn't matter is when you do parallel addition.
[1] for HN'ers that don't know the word, it means a + b is the same as b + a.
You started talking about ordering and addition unprompted. Are you sure you meant to reply to this thread?
The indices for each chunk are given to the body of the loop automatically and waiting for all forks to finish is done automatically.
You don't even have to share global state to work towards the successful outcome of some common objective. There are many problems that can be solved with actors operating in parallel with absolutely zero coordination between them. This might seem like its a place where only trivial cases live, but I have found some fairly complex concurrency scenarios that can be refactored into this trivial case by decoupling actors/state and reorganizing other parts of the system.
For example - Assume you were to develop a database engine that uses sequential integers for the primary key. You would probably have to develop a complex synchronization mechanism so that sequences are dealt out uniquely to concurrent callers. Or, you could sidestep the problem altogether by switching to GUIDs (V4 - Random) and allowing each participant to key its own entities. I feel these sorts of decisions should be considered as a primary measure before reaching for any form of shared state.
This is not what is being talked about when people discuss parallelism and concurrency since it is trivial. In that example all the tricky stuff has already happened. Lots of people looking at a painting is easy. Lots of people painting a single picture is hard.
Not handling the synchronization explicitly in your own program doesn't mean it isn't happening.
If you write to a disk, to a network or even just display pixels from multiple threads on a monitor, the synchronization is being handled for you.
> sidestep the problem altogether by switching to GUIDs (V4 - Random) and allowing each participant to key its own entities
That would be a concurrent hash map which doesn't side step synchronization, since you still have to deal with collisions, space allocation, ownership and lifetimes.
It also isn't the same as integer keys since you lose the ordering and lose the ability to do ranged queries.
Where synchronization is happening and how it is happening is important, but the idea that it is being avoided is nonsense. Letting something else do it can be sound advice. This however, is like saying that garbage collection means that allocating and freeing memory doesn't happen.
Shared mutable data concurrency is hard because it removes ability to locally reason about code.
can now fail.In my experience, simple concurrency is easy. Confused concurrency is exceptionally hard.
I think about this in the same way I think about C++. C++ is quite nice, if your teams limit themselves to a reasonable subset of the language. But it can become an absolute monster of cumbersome complexity, if these guardrails go away.
Concurrency feels the same. If you take a certain view on concurrency, which is "do it as simply as possible, don't break certain rules, don't try to be too clever," I find it fairly straightforward to reason about.
At the same time, 9 out of 10 of the hardest things I've debugged have always been nasty, awful concurrency bugs. The reason it was so hard? The concurrency was complicated, interwoven, assumption-laden, and absolutely impossible for anyone to reason about. Implicit contracts between calls required entire whiteboards of non-trivial state to understand, and even then, with all that work, it was a needle in a haystack.
I guess I would just say: It doesn't have to be hard. It's only hard if you don't respect it from the beginning.
I’m not sure I know what you mean by that.
> If you take a certain view on concurrency, which is "do it as simply as possible, don't break certain rules, don't try to be too clever,"
Is there a list of those rules?
Several different lists. You have to pick a concurrency model. Within that concurrency model, you pick some set of rules to follow which has the guarantees you want.
All of those things mentioned in the original reply is vague, and can only come from having experience in the subject matter.
That's why concurrency is hard.
That's like asking, "How do you know what algorithm to use?" You can come up with a justification for why a particular algorithm may be suitable for your purposes, but you'd be hard-pressed to explain how you go about choosing an algorithm. It's the same way with rules for a codebase... you can justify why you are using a specific set of rules, but explaining the decision process that led you to choose those rules is much more difficult.
That's why tech leads don't grow on trees.
I'll add to what the original comment (about "confused concurrency") was saying, because it matches with my experiences. The good lead developers are the ones who are able to get the job done (design systems) and keep the concurrency model simple. It's often possible to keep concurrency mostly simple and mostly safe.
None of this would have been possible without lead developers that designed and continuously refined the guard rails that our internal “standard library” implemented.
Oddly, I now find it easier to reason about lock free algorithms than mutex based code (and I wrote the latter for 15 years before working on the lock free system)
That is because lock free code composes. Mutex based code does not compose. With lock free code, I can freely call another function, knowing I cannot deadlock. With mutex based code, I have to be really careful about the state of my mutexes and think if the code I am calling will attempt to lock one of the mutexes I am holding, thereby causing a deadlock.
In mutex-based code, usually you want only open calls (i.e. calls with no mutex held, so you only ever hold one mutex at a time).
I think lock free guarantees that at least 1 thread will make progress.
https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-fr...
Document first, code later. Makes nearly all problems easy.
Jumping to writing code first is a future disaster in the making.
Write the specification as code - make sure it's something that can actually be checked. Then you'll know whether it's actually any good.
Not only is code not the best documentation, it's not documentation at all, outside of special cases where the entire code describes e.g. an algorithm and is encapsulated into one function.
It is a very important aspect of the readability, otherwise you will just sink in details when reading. But it is not easy to formally validate with tools, so naturally it is better to have both code and a picture and have discipline to keep them in sync.
I agree with this. Some of the best code I've read and written was done in this style. Properly separating out components into a hierarchy of modules.
> this is what they usually mean by "code is the documentation"
I disagree with this. I don't think this is what people mean at all, because I don't think that most people do the first part. If they did, there wouldn't be so many problems with "code is the documentation". But most code is not written in a clear hierarchical fashion. Logic is weirdly commingled, and depending on the language you have an assortment of low-level bookkeeping mixed with high-level logic.
I think they literally just mean "code is the documentation". One of the best/worst programmers I ever worked with is a perfect example of this. He'd always insist on the "code is the documentation", and his code always worked. But his code was absolutely awful to read for anyone but him. By way of analogy, I don't have a file system for physical papers. I have a literal chronological (by access time) stack. No one but me can make use of it, but it's very effective for me because I have a really good memory (though not as good as it was 20 years ago, I don't actually do this anymore because I have to work with others). That's his code. No one else can go into it and actually understand it (at least not easily), but he can jump in and make exactly the necessary changes. The code is not the documentation until it's properly organized, and maybe not even then.
Strangely, I find both gp and your claims to be nonsense. :-)
I've definitely experienced what you've experienced -- until you actually have code, you don't know what works and what doesn't work.
But it's frequently not at all obvious what code does, even in the normal case; and even code which looks obviously correct often has hidden complexities that you wouldn't have thought of.
I find trying to explain in a comment why the code I've written is correct is pretty good in wheedling out all the ways in which it's not actually correct.
So when things are really complicated, you need both: You need to have code that actually works, and you need to have text that attempts to prove that the code actually works.
I found that well written, expressive tests accomplish that really well.
I use Spock[1] to write complex tests and I just can't recommend it enough if you're working with the JVM (Java, Kotlin, Groovy, Scala, Clojure).
We have several thousands of Spock tests and it's amazing how they have scaled with us... they've grown to support extremely complex workflows that have nearly zero accidental complexity and are easily readable even if you have no experience with it.
[1] http://spockframework.org
If you write your app in any JVM language, you can use Spock to t test it because Groovy really has excellent interop with Java, hence JVM languages in general.
There is nothing wrong with prototypes but some people mistake them as production ready items because it looks like a whole load of work has been done.
Some things do have to be designed, and not just thrown together though. That may be through spec, but it could also be working things through on paper. Concurrency is certainly one of these. Other things need to be iterated on in code. I'd hate to play a platformer where the movement mechanics were specced out by a comitee before any code was made.
Do you mean a written spec, or a proper formal specification?
https://en.wikipedia.org/wiki/Formal_specification
There is just SOOOO much that can go wrong. But one general rule crystallizes itself pretty quickly:
DO NOT EVER MUTATE STATE!
I.e. when you write concurrent code that builds on state mutation, you are opening Pandorra's box. If you want concurrency that people can understand and maintain, write immutable, functionally pure code (same data in, same result out, no exceptions). That is relatively easy to police and enforce, while still flexible enough to solve most use cases. It may however, not be the most performant.
Unless performance is a problem, don't ever mutate state.
Just think about the complexity behind the assignment operator, all the way to the logic gates in RAM.
Syntax shortcuts are good when they're built on a rigorous foundation. But if you build a shortcut directly into the language, you'll never be able to retrofit a reasonable model for how it works.
I don't quite understand? You can certainly write generic functions that work for any lens whose "target" is a given type.
This is counterproductive.
Mutating state is by far, the most efficient operation on the computer. Copying state means (usually) calling the memory allocator, which (usually) must be done in a sequential manner. There are optimizations to allow memory-allocation to occur in parallel, but... things start to get inefficient (use of thread-local storage, which makes many pointer-indirections, etc. etc.).
-------
Why do people program parallel code, despite its overwhelming complexity?
Simple: to be faster. That's it. Its an optimization, arguably premature, but the programmer reaching for the "parallel" button is going for optimization for a reason.
------
Sequential code with state-mutations could very well be more efficient than parallel code with tons of unnecessary copies. Registers are fast, L1 cache is fast, etc. etc. Doing an operation, then undoing it (entirely inside of register space) is so incredibly fast, it will make your head spin.
-------
1: Write code.
2. If code isn't fast enough, single-thread optimize it. This usually means mutating state in an intelligent manner.
3. If code is STILL not fast enough, multithread it. You make a copy of the state, and then have multiple threads (each with their own copy of the state) doing... whatever you're trying to do.
Really? I mean like pretty much every instruction has separate source and destination addresses/registers, memory caches obviously complicate things, but it seems that processing data from one location to another is the most efficient operation.
> Copying state means (usually) calling the memory allocator
Sure, I guess if the main conception of moving data around involves not really knowing where it needs to go, and having to figure that out, that's somewhat true. But there are many ways to structure computation that minimizes or avoids allocator usage.
> unnecessary copies
I think this is the issue, if you have to copy first then do in place mutations, of course it'll be slower, but you can instead structure your entire computation to process your data from one location to another, then all your points about registers, and L1 cache being fast, holds true while still being able to handle immutable data
I can't think of any algorithm where copying is faster than mutating.
* Chess Bitboards: Make / Unmake is a methodology for a reason.
* Mergesort: In-place mergesort is far faster than copy-merge sort. Its much harder to write in-place mergesort, but it really makes a big difference.
* Quicksort: In-place quicksort is faster than copy quicksort. Every "pure functional" recursive / copy quicksort has been... subpar... in my experience.
* C++11 created a "destructive move", the entire R-value references system, because of the hugely more efficient concept of destructive / mutating moves. Destroying the old data while copying the data to a new location (aka: std::move) is far more efficient than making a safe copy (aka: copy-constructor).
-------
Side note: The SIMD "Mergepath" Mergesort is absolutely brilliant. It uses absolutely no mutexes (and only uses thread-barriers) to guarantee that all writes are independent and correct. Furthermore, "Mergepath" mergesort parallelizes maximally (one-element per processor), while retaining O(n * log(n)) sort speeds.
Because thread-barriers are no-ops on a SIMD computer (like AVX512), the thread-barriers in the MergePath concept are maximally efficient. :-)
-------
What algorithms are you thinking of where copying is faster than mutating? At best, a copy ties mutation in speed. In a huge number of applications, mutation (aka: std::move) just faster.
But std::move cannot be done across multiple threads: that's innately thread-unsafe and must be synchronized (at least for typical objects).
---------------
Or maybe the above is too abstract? Lets go down to a very simple, but specific, algorithm. The Fisher-Yates (aka: Knuth) Shuffle.
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
As far as I know, there is no copy-based algorithm that can beat the Knuth Shuffle's O(n) computation complexity. It is extremely difficult to write a O(n) speed shuffle without mutating the array in place.
The fastest "copy" methodologies for the Shuffle problem I've seen involved generating a random number for each location, then copy-sorting the results: O (n * log(n)), which is asymptotically more complex than the Fisher Yates shuffle (and therefore: work-inefficient. If you parallelize to O(n*log(n)), there will be a size where the Fisher Yates shuffle is faster).
---------
Example 2:
Notice: foo.size() is 0. The foo-vector was DESTROYED by the std::move(foo);.In fact there are people who have wanted destructive moves in C++, because they found the current non-destructive moves inadequate, but I don't believe the feature has ever been added. Look up destructive moves to find discussions on the issue.
In any case, the "foo" vector, and "foo" unique_ptr are _mutilated_ as part of the std::move operation. (Since the word "destroyed" seems to have been taken by the Rust community, I can't use that word anymore... hopefully no other community has taken the word "mutilated")
The theoretical destructive move is understood not leave an object behind at all, i.e. nothing to call a destructor on.
Having said that, I hardly see a sort being the majority of time spent in real-world code.
> Because thread-barriers are no-ops on a SIMD computer
My understanding is that only holds true across the SIMD lane, and the algorithm doesn't hold up so generally to general purpose concurrency. But agreed, a sort is something I'd likely try to optimize on a single core, and express program concurrency outside that specific operation.
> What algorithms are you thinking of where copying is faster than mutating? At best, a copy ties mutation in speed.
My main point is it's actually the case that a copy ties mutation in speed quite often if you structure the flow of your data correctly. If you're operating on a value, writing it somewhere else is often close to free.
Having said that as an example, I've seen filtering a list run faster doing a move, highly dependent on the details of the cache of course.
> that can beat the Knuth Shuffle's O(n) computation complexity.
I haven't considered shuffles specifically. But getting into the rut of complexity evaluation alone dismisses important aspects of the machine and the data you are actually operating on, and can lead you very far from the fastest solution for the problem you are actually trying to solve.
I disagree. Even for a simple situation:
[9 1 2 3 4 5 6 7 8] -> [1 2 3 4 5 6 7 8 9]
All 9 elements have to move to a different memory location!! In fact, assuming a randomly shuffled array with all different values, I'd assume that the most common situation is all elements being forced to move somewhere else. But I don't feel like doing the rigorous math to prove it. I'll so something simpler:
If there are N locations in an array, the probability that a random element is in the right spot is 1/N (I think anyway). With N elements, that would be an average of 1-element in the correct spot (assuming uniform random arrays). There is only one-sorted array, but factorial(n-1) array without any element in the correct spot.
> I haven't considered shuffles specifically. But getting into the rut of complexity evaluation alone dismisses important aspects of the machine and the data you are actually operating on, and can lead you very far from the fastest solution for the problem you are actually trying to solve.
Sure. But Knuth shuffle uses nothing aside from "Swap" instructions and a 32-bit (or 64-bit) RNG. Its really simple and fast. That's why that algorithm has stood the test of ~40 or 50 years of use, its probably the optimal algorithm for shuffling on a single-thread.
So, here's something. I think that a copying-based methodology can be fast, but more importantly, a copying-based methodology can be easier to parallelize.
If a mutating state is too hard to parallelize, I think rewriting things to be copy-based, and then using that copy-based methodology as a basis for parallel code, is a good idea.
What's difficult is that "mutating state" is a local maximum so to speak: probably the fastest that any single-thread can get to. From this perspective, finding parallelism from a "higher level" can be more useful than trying to parallelize a well-optimized single-threaded program.
----------
Case in point: Multithreaded producer-consumer queues are difficult to write and even define. But multithreaded producer-producer queues (and consumer-consumer queues) are very easy: just an obvious "atomic_add(tail, 1)" (Producer) and "atomic_subtract(tail, 1)" (for consumers) kind of thing.
I call it a "producer-producer" queue, because you need assurances that no one is consuming from the queue for it to work. But if you synchronize your threads to all copy to a queue (and no one consumes from it), its really fast, and actually very parallelized. Ditto for the reverse (the consume phase).
Mutating state is what computers are all about.
You can be super inefficient about it by copying everything on every operation. But avoidance is not the road to optimal solutions.
The task at hand wasn’t easy at all, it required both:
1. Making numerous network requests (some endpoints support batching, so do that as much as possible) 2. The entire main loop needs to be as fast as reasonably possible
The only real way to satisfy both, given that serially executing the network activity would waste tons of time, was some fairly tricky concurrent logic. I ended up using a few queue structures to collect day before making batch network calls, and stitching together all of the results at the end (block on all work threads, collect, report, then start next iteration)
Every step along the way made sense, every addition of complexity felt justified. And the first person to come to me asking how the fuck it got so complicated is frustrated, so my knee jerk reaction is to get frustrated back saying well how else could we satisfy complex requirements with a complex solution.
We should always be challenging ourselves and others to keep solutions simple, but remember that the simplest solution may itself still be complex.
Otherwise when the logic gets complex I try to model it as independent threads each having a well-defined role (e.g. exclusive write access to SQLite) communicating with channels. Although I tend to code these things in Rust, the language who taught me that philosophy is Go.
Design-wise:
The IO multiplexing — event loop(s), the completion callbacks go to the "Processing".
Processing — usually beneficial to model as a processing graph (tree/pipeline being specific examples of a graph without feedback loops). It's a clean, low overhead abstraction, easy to visualise (and thus discuss with others), easy to change structurally or in the "aspect oriented" way.
Examples in JVM world: Netty pipelines, AKKA actors, streams, and graphs, in C++ world ASIO & its executors sub-framework.
Queues/Threads is still a sufficiently low level to comfortably operate on.
group -> make concurrent calls and wait -> sort
which would have been very straightforward, and probably faster too because you don't let any one step interrupt the other
One needs to pick the concurrency model and design up front. Document it before writing a single line of code. Then stick to the plan. It takes discipline, but it's not difficult.
I mostly write in C with pthreads and as long as one is willing to apply discipline to the task, there's no reason to fear concurrency.
If one starts adding a thread here and a mutex there and some shared structures over there without any prior plan then yes, absolutely, that leads to a world of hurt and a deep hole that is very difficult to get out of. So, don't do that.
This has to be a universal rule of programming. It's equally true for Ruby and Perl, which are extremely effective languages, but devolve quickly because of their uncanny ability to power cleverness. It's the whole premise of Go, by being boring by design.
Complex is easy, simple is hard, but it seems mostly because we fail to be able to resist the allure of cleverness.
Yes Go the language is boring and I like this idea, but the runtime is a black box, that I don't like so much.
[0]. For example: https://github.com/golang/go/issues/14592.
It's not that react, redux and cie are something new or disruptive. It just enforces a set of design rules that turns a lot of concurrent inputs and outputs into a linear workflow.
For example, a bank balance. Most people would assume that bank balances must always be correct. But this isn't really true. Back in the days when people wrote checks, your bank balance was almost never accurate -- it was on you to keep a local register and know your balance, and if you shared the account with someone else, to reconcile with them frequently. ATMs also use eventual consistency. When you take out $300 from the ATM, it attempts to update the balance, but it will let you take the money out if the bank is unavailable. Because the bank is willing to risk $300 that you aren't overdrawn. In most cases the "eventual" part is nearly instantaneous so you don't notice, but it doesn't actually have to be.
So the number one way to make concurrency easy is to avoid it altogether.
Eventual consistency comes with it own set of counter-intuitives, and is a multiplier of possible states a system could be in. it is generally not a complication we would choose, but something we must cope with to do things that would otherwise not be feasible.
OTP underpins WhatsApp, Facebook Messenger, and Discord. People have been building very cool high availability embedded Linux projects using the Nerves framework. It’s very good for certain types of concurrent programs.
It won’t take over HPC simulation any time soon, but most of us aren’t working at Sandia, Oak Ridge, etc. Its great for systems that should naturally scale out but don’t map naturally to a GPU. For systems that want to scale up but are forced to scale out due to frequency limits, it’s not as good as C++ written with uArch in mind.
The difficult part I find with Elixir is that processes have a lot of roles: fault isolation, concurrency, synchronization, garbage isolation, maybe more. I've had projects where it's difficult to line these up - one design would be ideal for fault isolation, but it forces expensive copies to be made, so I can't use that design because it completely tanks performance.
Race conditions? Are you sure? AFAIK, that's pretty much impossible in Erlang/Elixir.
I do get with what you are saying with the second part of your post. That can indeed become an issue sometimes. Certainly one that I've struggled with myself, especially when things were still new to me.
But in my experiences, all those (apparent) conflicts/challenges can be mitigated/solved with proper architecture. Granted, that takes experience, which not all programmers may have (yet).
At the end of the day, programming is a skill and (inexperienced) programmers can always dig themselves a hole, in any language. Elixir is not a silver bullet, that magically solves problems without having to work (hard) on finding the right solution/architecture for a given (complex) problem. Still, in my experience, Elixir makes large/complex distributed systems, and in particular concurrency, a heck of a lot easier than it used to be (for me).
#jm2c
If it's just 2 processes then it's pretty easy: process 1 asks process 2 to modify itself, then process 1 modifies itself. However, this can lead to deadlocks/timeouts if both P1 and P2 are attempting to perform this operation at the same time.
And once you're into 3 or more processes, message passing as a method of synchronization breaks down.
Ideally you avoid this stuff with your design. But since processes fill so many roles you can't always avoid it.
having lightweight isolated processes and no (or little) shared mutable state matters a lot. :)
For years, I certainly made my own share of concurrency horrors, in everything from C and Python to Java and JS. Eventually I (sort of) got it right in each, mostly by building up experience in approaching it the right way. But it always remained a source of easy to make mistakes (and sometimes near-impossible to solve complexities, with larger systems).
However, since working with Erlang/Elixir, I sometimes wonder what the F#$& I was doing all that time. Many ideas were certainly a bit challenging to wrap my head around at first, but once they clicked there (kind of) was no way back.
This will probably sounds arrogant, and it's okay with me if I get down-voted because of it. But the more I work with Erlang/Elixir (and a few others in the FP field), the more it becomes clear to me how much the languages I used to program in (and their typical challenges), now most of all look like a (rather sick) joke to me. Again, I know this might sound pretentious, if not offensive. But it is sincerely what I feel. In my defense: I'm not some kind of hipster, still wet behind the ears. I've been programming for nearly 3 decades and in well over a dozen different language. I'm one of those kids that were ripping apart assembly code of "protected" games and desktop software, and hacked around on micro-controllers, during the nineties.
While Erlang/Elixir may have shortcomings too (although I personally have not found any), it is one of the best things I've encountered for a long, long time. I'm also charmed by ClojureScript, but for totally different reasons. However, I do like it for when I'm forced to build something more complex for browser/front-end. But that's a whole different story, and not much relevant to this concurrency "issue".
That summarizes the problem with most of the articles and discussions on concurrency. People talking past each other because those who don't do much concurrency, especially complex concurrent software, haven't reinvented Erlang yet and don't understand what the fuss is about, and those who do can't explain in relatable terms how the actor model helps them organize concurrent code, preserve local reasoning, abstract, compose it, tolerate faults, etc. and eventually they stop bothering and so poor concurrency articles and comments continue to dominate the infospace.
Libraries and tools could replicate this in C++. A lot of people love erlang/elixir and have success with them, but I think it's a mistake to attribute it to the languages themselves and not the beam VM + the ecosystem around it because it misses the deeper understanding of concurrency techniques that work.
That’s why Java/scala’s akka is crazily complicated. They encourage you to use futures so you don’t lock a core! So suddenly you’re still dealing with concurrency but with even more complicating layers.
What you are saying is about iteration in the language and does not have anything to do with concurrency or architecture.
There is also nothing difficult about avoiding infinite loops in C++. There is a for loop to iterate through a data structure, or you just can just make a macro to iterate a number of times. This is not something that would cause anyone to feel like a big problem has been solved. Recursion for iteration only has advantages when compared to loose while loops. Once more structured iteration came about, using recursion for iteration is just an awkward and overcomplicated hack that obscures something simple.
> There is also nothing difficult about avoiding infinite loops in C++.
I don't know how to explain it to you if you think you get it already but you don't. Please come into the discussion with an open mind.
Making sure every library you use won't ever block a core is not trivial. If it's a feature of the platform, then it becomes trivial. On Erlang it's a feature of the platform, in c++ it is not.
It has a delightful idea: to ensure the current thread isn’t preempted, set a global “lock” variable to true.
The scheduler checks “lock”. If it’s true, the current thread is added to the front of the threads list. Otherwise it’s added to the back.
Then the scheduler runs the first thread in the threads list.
So by setting “lock” to true, you are essentially instructing the scheduler never to switch threads.
Fork-join is the simplest methodology, and supported in a very wide number of languages. In fact, its so stupidly easy, you probably are going to over-think it the first time you use it.
1. Fork when you need concurrency (aka: speed)
2. Join when you need consistency
That's it. Don't write mutexes, don't write barriers. Just join. That's all you need: if you ever need "synchronized" access, do it in the "single" or "master" thread, when all other threads are joined.
You _cannot_ have a race-condition if you only have one thread. Joins ensure that only one thread is running. What else do you want?
Fork-join parallelism has relatively low utilization. Its not the fastest approach, but its the "easiest" approach in my eyes.
------------
The #1 issue with parallelism books, in my eyes, is that we start with mutexes and threads, which are a very hard way to do parallelism.
I argue instead: beginners should start with easy (but inefficient) forms of parallelism, and then work their way towards complicated tools as performance becomes more-and-more of a consideration.
and then there was a follow up to it saying the measurements were wrong IIRC, and then a further article showing, more or less that getting your own mutex replacement correct is so tricky that for 99.99% of programmers, just don't bother.
If you want practical guidance, my best is to avoid all of the concurrency constructs that are taught in schools. Use log-structured single-writer multiple reader, wait-free, processes and shared memory.
If you like it erlang style: an agent can serialize changes nicely.
If you need coordinated changes, use software transactions.
Of course: next we'll introduce deadlocks with DB transactions. Fun!
https://www.bbc.com/news/science-environment-24645100
Async is difficult I believe because "thinking" in inherently sequential because it is based on mentally reciting some (serial linear single-dimensional) language in our head.
An alternative could be some visual language where parallel and even 3D lines can be drawn. A mental image of it can be in our head. So I think async inherently needs some kind of visual language to make it easier to grok.
In both cases it takes a lot of hard work to learn how to not produce "dead-borns" or "genetically pre-disposed".
In both cases the course of "least resistance" (using intuition instead of logical reasoning) used by many as the default will most likely fail you. To develop an intuition of what is easy and what is hard with both system design and concurrency design is a matter of years of hard work of trial and error.
The actual question is why the complexity is so counterintuitive. I think this is to do with the Dunning-Kruger effect (the less you know the more confident you are).
In both cases the solution seems to be to keep beginners away from this and to have the same consistent, peer reviewed, approach across the system, and a process of improving it in a structured way. And of cause prefer higher level abstractions -> computation graph, pipeline, event loop, etc. over just hacking an ad-hoc Frankenstein out of low level primitives (which seem totally "simpler" if you ask a beginner).
With them and a basic understanding of single system concurrency, single system concurrency is and always will be trivial.
No mainstream languages give you a solid high level abstraction to build on. Some frameworks, kind of, do: ASIO in C++, AKKA Typed Actors and Reactive Streams and JDK CompletableFuture in JVM world, etc.