15 Years of Concurrency
joeduffyblog.com
joeduffyblog.com
> Out of the bunch, Rust has impressed me the most. They have delivered on much of what we set out to deliver with Midori, but actually shipped it (whereas we did not). My hat goes off to that team, seriously, because I know first hand what hard, hard, hard work this level of type system hacking is.
> In particular, I’m still conflicted about whether all those type system extensions were warranted. Certainly immutability helped with things far beyond safe concurrency. And so did the side-effect annotations, as they commonly helped to root out bugs caused by unintended side-effects. The future for our industry is a massively distributed one, however, where you want simple individual components composed into a larger fabric. In this world, individual nodes are less “precious”, and arguably the correctness of the overall orchestration will become far more important. I do think this points to a more Go-like approach, with a focus on the RPC mechanisms connecting disparate pieces.
Like, opting out of purity annotations or forced immutability?
I'm not saying these desicions are good or bad, I don't know much about system programming. But I often ask myself what the main motivators for a language are.
On the other hand, I think it is very important that some notion of purity be incorporated, even if only as an opt-in.
Oh, how did you achieve that? :)
I wanted to know how you could get a Rust-job (using it as primary programming language) today :)
I'd hit up these people: https://www.rust-lang.org/en-US/friends.html
Shouldn't it be called `unique` instead?
In the end, we decided that these are two equivalent perspectives, and decided to stick with the more traditional mutable/immutable distinction.
This is what Rust gets right: you can have an object be mutable (in which case you have only one pointer to it), or you can multiply alias pointers, all of which can only read the object. The type system enforces a static RW locking scheme in a manner of speaking; it ensures that only one of those capabilities is available at any one point in time.
In other words, Rust ensures that mutation by itself is not a problem, that passing mutable structures between threads is statically checked for safety. You don't _have_ to make an object immutable in order to share safely by reference.
---------------
It'd have been nice to hear about the "P" language, also from MSR (https://www.microsoft.com/en-us/research/publication/p-safe-...). No pointers, just value types, communicating state machines, produces model-checkable code. What's not to like?
And already used in production, even if in a small use case.
Anyway it's an interesting, if long, series but most of the interest for me has been in reading things from a very different perspective from the one I hear at work every day.
What system do you work with that doesn't have null pointers but also cares about eliminating as many fine-grained locks as possible?
One of those is routine.
The other is a serious logic error that strictly speaking a correct program cannot be said to do.
Is the author saying his standard language is C++? Everything I know about Midori said that it was competitive with C++ on performance in almost every way. Regarding error handling in particular, Midori used a combination of returning values and safe exceptions, both of which seem similar to C++.
It also explicitly doesn't have the aforementioned conflation of bugs and runtime errors.
Because JS has no notion of immutability, sharing is done via copying - but what's worse, copying via full-blown serialization, not just in-memory blitting or COW. At least, that was the state of things when I last checked a year ago.
Besides, the problem with models like those of JS (today, anyway) is that they don't even let you read concurrently, even if there are no mutators.
Node.js (and PHP, for that matter) often don't get enough credit for their scalability in the large. Perhaps this is because the surrounding distributed-systems ecosystem hasn't grown up around them yet the way it has around, say, Erlang or Java or even C++, but architecturally they're pretty sound if you want to build distributed systems that scale across many computers.
We should use all the hardware resources available to us. If our programming models don't allow us to do that, then we should replace them with models that do.
So, we made some:
Isolation is paramount, and we will embrace it wherever possible.
Message passing will connect many such isolated parties through strongly typed RPC interfaces.
Namely, inside of a process, there exists a single message loop, and, by default, no extra parallelism.
A “promises-like” programming model will be first class so that:
Synchronous blocking is disallowed. All asynchronous activity in the system is explicit. Sophsiticated (sic) coordination patterns are possible without resorting to locks and events.
with the exception of trying concurrency primitives on heavy-weight os provided processes, this looks like recreation/rediscovering of erlang primitives once again :)
would one be chastisized for wagering that erlang is the lisp of concurrency world ?
edit-001: slight clarification (hopefully)
Always reminds me of this quote:
"Any sufficiently complicated concurrent program in another language contains an ad hoc informally-specified bug-ridden slow implementation of half of Erlang." - Robert Vriding
The problem is when one tries to make a general purpose solution out of that design.
For example, how would Erlang look like in GPGPU programming, video/audio codecs, graphics programming, GUI,...
yup. go(lang) / rust seems to be exploring some ideas with an almost similar approach, but not _solely_ focussed on n/w programming. are there other languages out there as well ?
and a slightly open ended question as well: in your opinion, do you think a language needs to implement a complete runtime (similar to erlang) with it's own 'process' abstraction, scheduler, i/o etc. etc. to provide concurrency support ?
The main difference across those languages and Erlang/Go is how they expose the runtime to the developers.
It isn't a black box, rather they exposes a default set of behaviors and as set of APIs that allow to fine tune its behaviors.
wasn't it hans-boehm, who famously posited (?) that concurrency needs to be part of the language, rather than bolted on after the fact ? do you think that makes all these other languages kind of poorer w.r.t concurrency ?
edit-001: specifically, this is the paper that i am talking about: http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
What you are missing is that those languages are quite expressive, thanks to generics, operator overloading, trailing lambdas, and APIs into runtime the are available as tools for the programmer.
So you get, for example, async/await built into the language, with a default behavior. But at the same time, the necessary runtime hooks that allow any library writer to fine tune and built other concurrency models on top of it.
For the user of those concurrency models, it is indistinguishable where they are coming from.
Those are design decisions you can't bolt on later. Isolation, prescheduling and message passing without shared memory get you access to all of that.
It is only a matter of making use of the said compiler hooks and underlying machinery.
Mimicking the patterns doesn't replace the VM.
There are for example, distributed agent programming languages built on top of them, including network aware distributed GCs.
So for example, in that paper, 4.1 is about the problem of concurrent modifiability. And indeed, it says
> Indeed, under the implementation strategy we outlined above, in which the compiler is unaware of threads, it is allowed to transform code subject only to sequential cor- rectness constraints and hence could generate the code con- taining a race.
However, in Rust, this re-ordering can't happen: Rust won't let you alias x and y between two threads without some sort of synchronization primitive. But this isn't because Rust knows about concurrency, it's because Rust knows about aliasing. In a sense, Rust-the-language makes this program _impossible to write_, but a library re-enables you to write this program. You need unsafe to do this, but it's all wrapped up inside of the implementation of, for example, Mutex<T>.
From the last part of this section:
> Resolving it essential requires a programming-language-defined and compiler-respected memory model, simply to ensure that the user and compiler can agree on when there is a data race.
We're in agreement here, but the model is built around aliasing, not concurrency.
4.2 is about speculatively executing store instructions. I know less about this, but again, it's built on the idea of two threads accessing data at the same time, unsynchronized. This can't happen in Rust due to the aliasing rules.
4.3 is about register promotion. This cannot happen in Rust, because you don't call a function to acquire the lock, then do whatever you want. Mutex<T> hides the value it's locking inside of itself, unable to be accessed from the outside, and the call to acquire the lock returns a mutable reference to the inner data. The call to acquire the lock is the only way to get said reference, and Rust's aliasing rules will forbid any other kind of access through the returned reference. So this kind of transformation can't happen in Rust either.
Section 5 is about performance. It's true that synchronization primitives are expensive. Rust can again use unsafe code in a disciplined way to provide safe concurrent modification, while ruling out data races entirely. For example, consider a simple map operation. We take an array of integers, and for each element, add one to it. This is an embarrassingly parallel operation, yet, as the paper mentions, with a pthreads-style approach to making it safe, one would need either a single lock around the whole array, which destroys the concurrency entirely, or some set of more fine-grained locks, which introduce cost, as well as limiting the amount of concurrency to some degree.
But with a small utility function [1], which performs a small (ie, non-atomic) check at runtime, we can safety split up our array into as many disjoint chunks as we'd like, and then pass each one off to its own thread, which is free to do the modification with no more synchronization needed. In fact, libraries like Rayon can even determine roughly the correct amount for you, if you don't want to think about it, and it will near-transparently just handle this for you (you change a call from iter() to par_iter() and you're done).
1: https://github.com/rust-lang/rust/blob/f8614c397313db00e4b46...
So yeah. I'm in agreement with the paper that the language needs to do _some_ kind of reasoning, but since aliasing and concurrency are so tightly related, I would argue that the language could understand only aliasing, not concurrency, and then library abstractions are sufficient.
For GPGPU, video/audio codecs and all ... You want single threaded things. And there Erlang says "i'm ok with that" and let you use Native Implemented Functions (NIFs) that enable you to use Rust, C and co. Or to use what is called a Port and let you interface with a program outside of erlang in a safe way. Works quite well.
Then Erlang is used as a "concurrent and distributed glue" between your programs. There are a couple of scientific simulations that use erlang like that in the wild.
1) it was never seen as a problem because the erlang team believe (and i agree with them) that you best let specialists deal with their speciality are.
2) There were never an efficient JIT on the BEAM. This is something that is regularly looked at by the OTP team, but it would be a massive effort, just to try to approach effiency of what other language, that you can easily interact with, could do.
3) The use case are small. Let be honest. The amount of problems that are really only CPU bounded are limited in day to day work.
Parallelism is about performance, and it seems contradictory to do parallelism well on top of a slow language. Yes, Erlang can call out to other languages, but so can shell scripts.
Some other examples are live code loading, which means you can upgrade a system without restarting or interrupting it, the extensive tracing and statistics, etc. All these little things make it very nice to build and maintain a long-running service, but add up to make the VM slower. If you're doing batch jobs and have no realtime requirement, then the trade-off may not be so attractive.
In general, synchronous message passing or RPC can not work. At all. There are too much edge cases where it breaks the laws of physics.
>"Problem here : RPC and promises are radically against message passing."
Christopher is far better than i will ever be at explaining it. In general, RPC have some fundamental problems, among other, they need you to ship the full context.
I'm slightly (very?) jealous that I am not so passionate about any part of software as the author. I am interested in lots of areas but no one piece of the puzzle draws me and its bittersweet sometimes to read the thoughts of someone who seems so passionate about their field.
Because the comment adds nothing to the conversation.
Unsure about implementation details
It was back in 2011 that I first started wrapping my head around the complexities of concurrent programming. Even in single-threaded environments, such as a JavaScript processes, concurrency woes can escalate quickly in terms of the non-determinism introduced by asynchronous operations (timers, I/O) and their callbacks.
My trying to understand and deal with those complexities resulted in an exploration of functional-reactive programming concepts, which in turn led me to make a "deeper dive" into computer programming language design and various computer science topics. Concurrency is still the CS topic that makes my ears perk up the most.
http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-20...
It's written in 1978, but if I interpret it correctly, it's still conceptually ahead of everything mentioned in the article (the closest thing being STM). Anyone else here seen it?
"Shared-memory multithreading really isn’t the future, we thought, and notably absent from all of my prior work was fixing this problem."
I'm thinking about..
Immutability is the way to scale complex systems?
Every system can be implemented as immutable by definition?
We need to look to build new data structures - like Tries - to be Immutable-friendly?
When Immutability doesn't worth it?
However do you agree that is more easy to solve memory (buying new hardware) than handle with race condition? kkkk
Then, Maybe we need to think about optimize our daily data structures.. I have following a few papers about this.. e.g:
http://dl.acm.org/citation.cfm?id=2658763 http://dl.acm.org/citation.cfm?id=2993251
This is especially important on mobile, FPGAs and in cases where sheer volume of data is huge. (GPU and big data)
There is a tradeoff with this kind of immutable oriented programming that you trade off relatively easy parallelism for heinous memory thrashing--and cache misses are already a huge bottleneck on modern architectures. Rust seems to have struck a good balance here, I'm keeping a close eye on it as it continues to mature.
See this blog post for more <https://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-...
I'm not sure there's an immutable language out there that impresses me with its performance at scale. In some ways, GHC works miracles for Haskell, and yet, it can still end up being 2-5x slower than C even if you try to make it fast. I'm not sure if there's anything else out there that's any faster with pervasive immutability. (There are some other "functional programming languages" that are often faster, like OCaml, but they're getting there by letting mutability in.)
As said in the article: "Rust is slightly less opinionated on the overall architecture of your system than Midori was, which means it is easier to adopt piecemeal," emphasis mine. Over the past couple of decades there have been a lot of projects like Midori (though that is one of the better ones) that could solve lots of problems, as long as lots of people dropped everything and adopted it. I've learned from both looking around and my personal experience that while eventually you do have to drop everything and try something new, that if you can to create a system that you can incrementally improve into, it will outcompete the drop-everything one every time. Even if the tradeoffs might make you sick, the reality is stark; the situation must be desparate before a "drop everything" solution can displace an existing one entirely. In Rust's case, in some ways the most exciting thing about it isn't the features its shipping or its capabilities or anything else; it's the way you're seeing people carve out a hunk of Firefox or other programs and replacing one function, one module, one subsystem at a time in Rust. That's what's missing from so many of the other efforts to address the issues Rust is addressing.
You can mathematically try to hide that however you want, but somewhere deep in your language runtime stack will be a shared-memory concurrent mutable algorithm, be it a lock, queue, or otherwise.
The alternative is to ditch shared memory entirely and use e.g. hardware IPC to manage contention. Tilera tried that, they had 64-core processors with a hardware IPC mesh and incoherent cache. But last I checked they switched focus to coherent shared-memory concurrency. Not sure what the driver for the change was but it's telling.
EDIT: Not to mention that half the article focused on promise-style concurrency, which has nothing to do with shared memory or even multicore. Immutability does nothing to address that I/O exists and has latency, and that people try to hide it in frankly bizarre ways. (Really… not pumping the event loop to avoid deadlock? That's a design issue, you should be using queues instead of mutexes and eliminate cycles if you find you have that problem.)
While it is possible for threads in a (modern) GPU to modify shared memory, it's typically very costly. Usually it takes the form of one thread running at the exclusion of all others, to do something like collecting the results from other threads after they're done running.
Re: Tilera, looks like they got bought out by Mellanox and haven't progressed past where I last kept track of them: http://www.mellanox.com/page/products_dyn?product_family=238... It was a shame, because the IPC mesh was easily twice as fast as the shared memory solutions they were pushing in the Gx series.
In addition, immutable data structures tend to be pointer-based. For GPUs (even more so than for CPUs), you want contiguous memory accesses for acceptable performance.
It's a more restricted programming style than common functional programming - in particular, recursion and advanced control flow is out - but that's the name of the game on GPUs, no matter what you do.
That's a bit of a strawman. For example, content addressable memory and message passing will certainly permit "processors ... communicating in [a] meaningful way".
I specialize in lock-free everything mutable programming. It's a bloody nightmare to write correct code in an environment like that - but when done well it performs better than anything else.
You can do local tricks to hide change in state. Consider, many even simple addition operations in your computer are destructive. At the end of the day, though, your application's value is in the state it manages.
There may be a panacea in there some where. However, it often seems that performance is heavily sacrificed in the name of scalability. Which is scary, because performance is the main reason my scalable phone is driving me batty.
(Mentioning Erlang and Haskell because I've shipped solid production systems using both of those, and they work well!)
I have been meaning to re-investigate Join Calculus (the last time I did was in OCaml a long time ago) and to why it never really took off.
Some programming patterns can be found here: https://en.wikipedia.org/wiki/Join-pattern
I tried converting it to ascii and decimal and nothing interesting came out. Anyone know what that is? Maybe a key signature?