Hacker News Reader

Comment by Affric | Hacker News Reader

Interesting discussion there too.

With modern computers I wonder if explicit parallelism is more fundamental to what our computer science will be than is in vogue in textbooks. Perhaps we should always be writing explicitly parallel code at this point.

View on HN

Humans are bad at reasoning about multiple threads simultaneously, so I suspect the more practical shift is the trend we've already been seeing toward more declarative syntax.

eg `for` loops are being replaced by `foreach` loops,`map` and `filter` operations, etc. These tell the compiler/interpreter that you want to do some operation to all the items in your datastructure, leaving it up to the compiler/runtime whether and how to parallelize the work for you.

I would upvote this 100 times if I could.

I've thought this way ever since MacOS added the Grand Central Dispatch [1]. Of course, I thought industry would follow quickly and that tooling would coalesce around this concept pretty quickly. Seems the industry wants to take its sweet time.

[1] - https://en.wikipedia.org/wiki/Grand_Central_Dispatch

I mean, OpenMP dates back to 1997 (1998 for C and C++). Apple, however, has never supported it for what can only be selfish reasons (particularly since Clang has a quite good implementation provided by Intel, which can easily be installed on a Mac if you want). GCD came a decade later.

For basic parallelism, nothing beats OpenMP for ease of adapting existing code (often a single "#pragma omp parallel for" directive is enough). Even for more complex parallelism, particularly where per-thread resources need to be managed, OpenMP still provides a much simpler programming model than the alternatives.

OpenMP and GCD solve different problems. You'd not want to use GCD to parallelize the same tasks you're parallelizing with OpenMP in most cases. GCD is more suited for the one-off cases (toss this task into the queue, toss that task into the queue; or "as we get new items from the user toss the processing into the queue" but we don't know the rate of new items coming in so batching doesn't make as much sense), vice OpenMP which is targeting things like scientific computing/simulations where you know you have a million objects you want to perform a computation on. The GCD version of the same would be slower by a large measure if you spawned a task per work item or you'd recreate parts of OpenMP to divide the work across a smaller number of tasks. And you wouldn't want to use OpenMP for parallelizing the kind of things you toss into a work queue model like GCD offers.

Sure, OpenMP and GCD provide different interfaces around the same concept of a managed threadpool. Given both, one would use them for different tasks (in the same way one actually uses OpenMP and std::async for complementary purposes). But in the context of GP's basic parallelelized for/map/reduce operations, either can be used fine (although OpenMP would probably be more pleasant to write).

I'm not familiar with GCD but after reading the wiki page, I'd say most languages have something like that: a queue that you can add things to, items can then be processed by multiple threads of execution.

I'd also say that most languages have something similar to OpenMP, parallel for loops, etc. Great if you have some read only data in arrays and wish to process it.

However, in my opinion, it doesn't really matter how convenient a parallel / async programming model is to use as the real work is ensuring that there isn't any shared mutable state being updated in parallel. The other issue is, once you have formulated / re-formulated a particular problem to this model, ensuring that it remains this way is pretty challenging on larger teams. Someone can easily unknowingly commit something that breaks such assumptions.

At the end of the day, no matter what kind of code you are writing, you either have tools and processes in place that reduce the risk/mitigate the impacts of bugs, or there is always the risk of serious problems being introduced. An unknowing change that breaks parallelism in another component could just as well be an unknowing change that breaks authentication or defeats a security boundary.

Parallelism introduces an additional class of bugs, but they are fundamentally addressed the same way as any other class of bugs - e.g. testing, tools, and code review. If some_one_ can unknowingly break a system, that means the tools and processes weren't good enough.

One difference from most other classes of bugs is that threading issues can be quite nondeterministic, which makes it harder to automatically disambiguate between flaky tests and real bugs being caught.

Also, the code introducing a race condition may get lucky when your CI system runs the tests and still make it into your main branch.

I agree that tooling (like static analysis, Rust's borrow-checker, etc) can play a big role here though.

That is the issue. It is very hard to write tests that ensure correct parallel code as it can easily work 99.9% of the time. This is not the case with typical functional requirements.

It is much the same case with security requirements, though. You can have all the tests of intended behavior, but they won't necessarily tell you anything about unintended behavior. You need better tooling and specifically focused tests to have confidence the code is correct and safe.

Please elucidate. Concretely, what tools and testing methods are you referring to?

For parallel code, the obvious answers are static and dynamic analyzers. E.g. for C and C++ you'd use TSAN and MSAN. The Rust borrow checker is essentially a memory/thread safety static analyzer baked into the compiler.

Particularly for dynamic analysis, you need to have test cases that usefully cover the design behavior. E.g. if you design a component to be safely shared, you need tests that exercise that sharing where the static/dynamic analyzer(s) will identify unsafe sharing. Likewise, if you know something is unsafe, you should probably have tests that demonstrate that the static/dynamic analyzer(s) do detect the unsafe usage.

I've played around with actors in Swift for shared mutable state, which enforces async access patterns.

https://www.swiftbysundell.com/articles/swift-actors/

It’s been a while but isn’t GCD an OS global queue rather than local to the process?

Each process has its own GCD queue hierarchy that are executed by an in-process thread pool. Though it has some bits coupled with the kernel for stuff like Queue/Task QoS class -> Darwin thread QoS class and relatedly priority inversion.

Back then it wasn't even sure its adoption would take off.

My HPC programming lectures were done on PVM, and I bet only grey beards know what it stands for.

> Seems the industry wants to take its sweet time.

We're inching towards an in vogue way to do what erlang had figured out in the 80's. We'll pick up the pace any day now. Surely.

Grand Central Dispatch is famous for breaking tons of old programs for the grave sin of trying to `fork` a child process.

>eg `for` loops are being replaced by `foreach` loops,`map` and `filter` operations, etc. These tell the compiler/interpreter that you want to do some operation to all the items in your datastructure, leaving it up to the compiler/runtime whether and how to parallelize the work for you.

There's difference between doing it in order 1, 2, 3 and 3, 1, 2.

foreach will not be replaced behind the scenes into multithreaded version since it changes behaviour.

for is replaced with foreach because usually you dont need index and foreach is just handier and safer, that's it.

.NET's std lib has Parallel.ForEach for such a thing.

We really don't need magic to write multithreaded code. All we need is just really, really well designed APIs and primitives.

>foreach will not be replaced behind the scenes into multithreaded version since it changes behaviour.

It only (meaningfully) changes behavior if you're both iterating over an odered datastructure and the body of your loop has direct or indirect side-effects. (like printing, writing to a file, making network requests, etc)

>nd the body of your loop has direct or indirect side-effects

So like... huge % of the real world code bases

Unfortunately yes. That being said, the hottest loops that would benefit the most from added parallelism tend to have fewer side effects already in my experience so things aren't quite so bleak.

> It only (meaningfully) changes behavior if you're both iterating over an odered datastructure and the body of your loop has direct or indirect side-effects.

Right, and not always even then, because that depends on what the consumer is concerned with as well. But the fact that it can means it's not a safe automatic substitution.

I agree to a large extent but I am referring more to our teaching of Computer Science. For our teaching of Software Engineering I think you're largely correct.

> Humans are bad at reasoning about multiple threads simultaneously

I am not so sure this is true, I do believe that people are poorly practiced. My experiences have led me to believe Universities silo explicit parallel programming too much. It's generally it's own non-compulsory subject in a Comp-Sci major.

C++ has had std::execution_policy for a long time now - you pass that with an algorithm like sort, for_each, etc. and it will choose a way to parallelize that for you.

I like the way you word this. Similar to the product I make, I describe my mind as an asynchronous queue. I can only reason about one thing at a time, but when I do that is fairly random.

How this has played out in my life gives me caution about making this standard in computing.

Considering the developments in data engineering land I wonder if we'll be describing our operations as a DAG rather than maps and folds specifically.

It is more like the mainstream world is finally catching up with the world promised by functional programming since Lisp and parallel computing exists.

Only now I can enjoy in modern hardware what I had to imagine when reading papers about Star Lisp and the Connection Machine, alongside other similar approaches.

Yep! The only thing that remains is to focus on that code being properly functional; i.e. avoiding side-effects. Side-effects and parallelism don't mix well. Wonder if this will give rise to more functional languages.

There will still be cases where more fine tuned control is warranted. Rust has done this very intelligently by moving data race controls to the compiler level.

How about some HDL semantics with implicit pipelining...

Every statement in a HDL language runs in parallel but you can still write implicitly sequential code in VHDL processes.

Is the difficulty reasoning about threads a bit more specific than that? I think it is reasoning about threads with shared mutable state.

>"Humans are bad at reasoning about multiple threads simultaneously"

Humans are bad at reasoning about way too many things. I think mostly because many are lazy and do not want to learn. The ones who do have little problems. I do not find thread management particularly hard for the most parts (there are some exceptions but those are very uncommon).

I love when people want to brag so much that they basically end up claiming to have transcended the human condition.

Fine then. Your compiler is bad at reasoning about multiple threads simultaneously.

So how my compiler reasons about multiple threads?

> Reads and writes do not always happen in the order that you have written them in your code, and this can lead to very confusing problems. In many multi-threaded algorithms, a thread writes some data and then writes to a flag that tells other threads that the data is ready. This is known as a write-release. If the writes are reordered, other threads may see that the flag is set before they can see the written data.

> Reordering of reads and writes can be done both by the compiler and by the processor. Compilers and processors have done this reordering for years, but on single-processor machines it was less of an issue.

https://learn.microsoft.com/en-us/windows/win32/dxtecharts/l...

>"In many multi-threaded algorithms, a thread writes some data and then writes to a flag that tells other threads that the data is ready. This is known as a write-release. If the writes are reordered, other threads may see that the flag is set before they can see the written data."

This is why we have things like WaitForSingleObject and many other that deal properly with the chance of reordering and other concurrency related issues. All is fine with the reasoning on CPU, OS, Compiler and my own level. One just have to understand what is going on and know the tools. Those who are setting boolean flag to indicate the data is ready should not be programming for modern CPU's and have a basic knowledge first.

When the brightest minds in computer science, who've spent literal man-centuries developing the theory behind some of the various multiprocessing frameworks currently used, tell you multithreading is hard, I tend to go with those over J Random Hacker News Poster claiming it's easy-peasy and everyone else is lazy.

Developing good framework (does not have to be multi processing) is generally hard. Having decent subject understanding and knowing how to use said frameworks is not a rocket science. And there is a difference between "easy-peasy (tm)" and not being lazy and learning some basics

I’m sorry but I spent two semesters studying the theory behind concurrent data structures and formalizations of concurrent state machines and there is no way you can tell me that reasoning about multithreaded program state is easy.

In fairness, concurrent data structures generally don’t represent what gp is talking about. Yes, very, very difficult to write a solid concurrent ring buffer. Writing Java’s concurrent hashmap - hard. Using it to implement a simple in memory kv store: not that hard.

But ensuring some parallelism while maintaining thread safety is straightforward in many contexts - an uncontended mutex is close to zero overhead. Languages like Rust make it harder to struggle with some of the thornier issues (data races which cannot be simulated by stepping threads).

E.g. in Java a typical system looks like a thread per request with some shared underlying data structures like caches or connection pools. Relatively easy to use these safely, or to guard some shared object with a synchronized.

Likewise with parallelism - a lot of problems just boil down to ‘do a few map reduces’ and the parallelism is pretty trivial.

Obviously, concurrent systems are fiendish to reason through - but there are a lot of cases where the complexity can be side stepped. Doesn’t seem to stop people writing scary code on the daily though.

I spent lifetime (since the end of the 80s) programming concurrent systems among many other things. Think I can draw my own conclusions.

It shows; something that needs a lifetime to master is definitely not on my list of Easy(TM) things.

This reads like satire.

Shades of clojure's transducers

Parallelism ended up going off in a few different directions.

For things like running a web service, requests are fast enough, and the real win from parallelism is in handling lots of requests side-by-side. This is where No-GIL comes in.

Within handling a single request, if there are a lot of sub-requests, that's usually handled by async code, but not so much for the async performance win as much as spinning up threads is either expensive or thread pools are a hassle. Remember that async is better for throughput, but worse for latency, and if you're parallelizing a service request, you're probably more worried about latency. Async won mostly on ergonomics.

The other place you see parallelism is large offline jobs. Things like Map-reduce and Presto. Those tend to look like divide-and-conquer problems. GPU model training looks something like this.

What never happened is local, highly parallel algorithms. For a web service, data size is too small to see a latency win, they're complicated, and coordination between threads become costly. The small exceptions are vectorized algorithms, but these run one one core, so there isn't coordination overhead, and online inference, but again, this is heavily vectorized.

> What never happened is local, highly parallel algorithms.

GPUs maybe? Also, excellent answer.

Parallelism in CS is a bit like security in CS. People know it matters in the abstract senses but you really only get into it if you look for the training specifically. We're getting better at both over time: just as more languages/libraries/etc. are secure by default, more now are parallel by default. There's a ways to go, but I'm glad we didn't do this prematurely, because the technology has improved a lot in the last decade. Look for example at what we can do (safely!) with Rayon in Rust vs (unsafely!) with OpenMP in C++.

And there are things even further afield like what I work on [1][2][3].

[1]: https://legion.stanford.edu/

[2]: https://regent-lang.org/

[3]: https://github.com/nv-legate/cunumeric

See also

https://github.com/cupy/cupy

https://github.com/inducer/pyopencl

What's the difference between Legion and Regent, by the way?

I noticed the Regent code is inside the Legion repo. Is Legion the system, and Regent the language?

Can Legion be used without Regent, or vice versa?

Legion is a C++ runtime system. It exposes APIs in C++ and C. You can write code directly to it with C++ (and CUDA/HIP/SyCL if you want to use GPUs). But the only requirement is a C++ compiler and standard build system (Make/CMake).

Regent is a programming language. The compiler for Regent generates Legion code. Semantically, Regent is mostly a simplification of Legion. There are fewer moving pieces, so fewer things you need to worry about. Many of the "gotchas" that exist in Legion are taken care of by the language/compiler so idiomatic code usually "just works". It also does GPU code generation for you so you don't need to hand-write CUDA/HIP/etc. The tradeoff is that you're using a new programming language, so you have to be willing to take that risk.

> Look for example at what we can do (safely!) with Rayon in Rust

"Safely" for a certain kind of definition of safety: https://github.com/search?q=repo%3Arayon-rs%2Frayon+unsafe&t...

The library uses `unsafe` so the consumer doesn't have to. But more to the point, to say "it uses the `unsafe` keyword, therefore it can't be safe" would be disingenuous, or at least very ignorant. The "certain kind of definition of safety" you're looking for would be 'soundness'[1]: a library using `unsafe` is considered 'sound' iff calling into it from safe Rust can never corrupt memory.

When people say Rust is better for memory safety than e.g. C++, it's not because you can't write a provably-safe library with C++—you can do that with some effort. It's because the Rust language differentiates compiler-asserted safety from programmer-asserted safety via the `unsafe` keyword, an opt-in.

[1]: https://rust-lang.github.io/unsafe-code-guidelines/glossary....

(edit: Sniped, but I believe I've expanded upon the sibling comment.)

> "it uses the `unsafe` keyword, therefore it can't be safe"

> ... would be disingenuous, or at least very ignorant.

That's quite literally what it means - there is a "safe" Rust code that never uses the "unsafe" but the example given by the parent comment is just not the example of that. I am not sure why would my comment come out as ignorant - it's factual state of things.

> it's not because you can't write a provably-safe library with C++

Hm, you really can't? Neither you can with safe or unsafe Rust. None of the compilers for those languages are formally verified.

The point is that the "unsafe" code is written and checked once, and then everyone can benefit from that. It's the same concept as encapsulation applied to memory/thread safety.

As I see it, parallelism is in the same vein as memory management. Most of what we program can, and should, use some form of automatic management, and manual management is reserved for the areas where it is needed for performance.

It's an implementation detail, and if we can abstract it away to make it easier to utilize, we should.

LMAX Disruptor has on their wiki that average latency to send a message from one thread to another at 53 nanoseconds. For comparison a mutex is like 25 nanoseconds and more if Contended but a mutex is point to point synchronization.

The great thing about the disruptor it is that multiple threads can receive the same message without much more effort.

https://github.com/LMAX-Exchange/disruptor/wiki/Performance-...

https://gist.github.com/rmacy/2879257

I am dreaming of language that is similar to Smalltalk that stays single threaded until it makes sense to parallise.

I am looking for problems for parallelism that are not big data. Parallelism is like adding more cars to the road rather than increasing the speed of the car. But what does a desktop or mobile user need to do locally that could take advantage of the mathematical power of a computer? I'm still searching.

I am thoughtful of the Itanium and VLIW architecture for parallelism ideas.

> I am looking for problems for parallelism that are not big data. Parallelism is like adding more cars to the road rather than increasing the speed of the car. But what does a desktop or mobile user need to do locally that could take advantage of the mathematical power of a computer? I'm still searching.

The things we currently let servers do but it would mean we can keep user data local and not hand it over to service providers. I believe that is a worthy end goal.

Pervasive parallelism could make massive efficiency gains in computation possible. If we could move many work loads to hundreds or thousands of threads we could run it much lower clock frequencies and thus lower power. It could also enable the use of cheap, small in order cores, further boosting core counts.

Multithreading doesn’t always have to be around increasing speed, it can also reduce power

It sounds like you are thinking about concurrency more than parallelism. The answer to your question is very general at a high level. Any task that can be broken up into chunks benefits. In the simplest terms, tasks that can be computed in buckets with a final result computed from those buckets will benefit from concurrency. Think of a video game as a good example. Environment calculations are happening in the background while the main game loop is processing. There are almost infinite use cases and examples, so I won’t try to enumerate them all.

I am more of a fan of finding implicit parallelism. You could think of a given problem as a heap of spaghetti. If you can untangle the mess, then each noodle might still be sequential, but you can process them in parallel.

If you can find enough independent sequential problems in your programs then you can easily fill up cores, mostly because we don't have that many. I only have eight.

The problem is that this requires additional graph processing and there it makes your programs slower, which kind of defeats the point. The goal is to find the right tradeoff.

Do you mean implicit parallelism? Because what we have now is typically explicit paralellism. Creating a thread or forking a subprocess is explicit parallelism, the programmer chooses that option. A function like `map` that can utilize a parallel or sequential implementation depending on circumstances the runtime or compiler are aware of without direct input from the programmer would be implicit parallelism. If the `map` function takes an execution context that signifies parallel or sequential execution then we're back to explicit.

Reasoning about parallel execution is hard. You need high level language and library support for that unless you want to spend the rest of your life in tricky debugging territory.

I think this is why I'm a huge advocate of the Actor Model.

Likewise, it is one of the best solutions to this problem. And it also nicely maps onto language constructs, much nicer than the other options that I've worked with.

Perhaps it can be Actors turn to have some hype this decade?

It seems serious parallel programming has mostly gone with shader/ISPC style data-parallel computation with low-level languages and the old school threads & locks model has been relegated to a side support role lost except on the CPU side.

There's interesting stuff going on in the VHLL world with languages like Futhark, Jax, Mojo, etc that would be a better peer group for Python and its high level of abstraction.

Can you talk about the difference between what you're calling explicit parallelism and said textbooks?

As soon as computers had 4+ cores we should have been going hard on it.

Aren't we already?

The formalisms for nondeterminism are over half a century old now. This is fundamentally a solved problem, although the typical case analysis technique many programmers tend to prefer falls down hard. Incidentally that’s why unix signals suck.

Reply on news.ycombinator.com