Hacker News Reader

Comment by mcqueenjordan | Hacker News Reader

It's my own weird little take, but I'll share it.

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.

View on HN

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.

Maybe providing a diagram to explain the structure would help? Representing queues and workers as arrows between queues.

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.

Sounds like you wrote all of the stuff that wasn't io bound in to your concurrent logic, rather than

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

Good perspective, I agree.

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.

"If one starts adding a thread here and a mutex there..." -- precisely 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.

[0]. For example: https://github.com/golang/go/issues/14592.

Managed concurrency like Node.js and Go are fundamentally different from Rust and C/C++'s minimal runtime concurrency.

As always the problem is the specification. Once you sit down and write the formal specification, suddenly the implementation becomes much clearer.

I wish this was a more widely held understanding.

Document first, code later. Makes nearly all problems easy.

Jumping to writing code first is a future disaster in the making.

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.

[1] http://spockframework.org

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.

> formal specification

Do you mean a written spec, or a proper formal specification?

https://en.wikipedia.org/wiki/Formal_specification

For concurrency related specs i was alluding to spin/TLA+.

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.

> Confused concurrency.

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?

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

so how do you know which model to use? How do you know what rules guarentee what outcome? How do you compare them against each other?

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.

> so how do you know which model to use?

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.

lock-free code is free of deadlocks, but it is not free of livelocks and usually there's no guarantee of progress...

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

> usually there's no guarantee of progress

I think lock free guarantees that at least 1 thread will make progress.

https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-fr...

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.

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.

I like to think of mutation as a performance optimisation. Correctness first, then optimisation.

Unless performance is a problem, don't ever mutate state.

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 lose conciseness with mutable state. What you seem to think is lost can be regained through abstraction.

Just think about the complexity behind the assignment operator, all the way to the logic gates in RAM.

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.

Please post the lens code here so that we may judge how expressive it is :)

With zero effort

    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.

I suggest you check out efficient mutable data-structures which are safe by default. Clojure and ClojureScript come to mind.

They are still less efficient. Compare even modern stuff like HAMTs to ordinary sets. Close, but no cigar.

> DO NOT EVER MUTATE STATE!

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.

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

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

Going off-topic, but note: C++11 moves are non-destructive.

    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.

---------

Example 2:

    int main(){
      vector<int> foo = {1, 2, 3, 4, 5};
      vector<int> bar = std::move(foo);

      cout << foo.size() << endl;
      cout << bar.size() << endl;

      return 0;
    }

Notice: foo.size() is 0. The foo-vector was DESTROYED by the std::move(foo);.

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 "moved-from" already captures what you are trying to say.

The theoretical destructive move is understood not leave an object behind at all, i.e. nothing to call a destructor on.

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

> DO NOT EVER MUTATE STATE!

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.

Reply on news.ycombinator.com