6 ms·

Multi-Threading and Mutation

88 points by chmaynard 3y ago

hedora 3y ago
Rust’s borrow checker does a nice job of formalizing the ideas in this post with & and &mut (shared reference and exclusive/mutable reference, respectively). The unsafe keyword (and the interior mutability pattern) provides exactly the right escape hatch for things like TableInsert and the join operation in the post. People like to talk about its memory safety, but it’s the fact that the compiler checks for data-race freedom that really sells rust for me. Languages like Java claim to be memory safe and type safe, but what does that actually mean if a concurrency bug means you have multiple CPUs stomping over your objects’ internal state in race?
- jjtheblunt 3y ago
  Java doesn’t claim quite to be type safe considering type erasure is built into its spec, so that, by runtime, containers (for example) might be surprised by a runtime appearance of an object type not checked for or known at compile time.
  - lmm 3y ago
    > Java doesn’t claim quite to be type safe considering type erasure is built into its spec, so that, by runtime, containers (for example) might be surprised by a runtime appearance of an object type not checked for or known at compile time. Erasure has nothing to do with type safety; ultimately almost all types are "erased at runtime" since we have Von Neumann architecture where effectively everything is a byte/word, but this does not mean mechanical computers cannot run typesafe languages. Java reflection is arguably less safe due to type erasure, but reflection is almost inherently type-unsafe in the first place. (Java does have type unsafety via e.g. covariant arrays, but that's a design choice, not a fundamental limitation)
    - ackfoobar 3y ago
      > type unsafety via e.g. covariant arrays It's ironic when you think about it. The compiler enforced type safety is often argued as not type safe because they are erased at runtime; but the actual type unsafety has a runtime check.
      - lmm 3y ago
        > The compiler enforced type safety is often argued as not type safe because they are erased at runtime; but the actual type unsafety has a runtime check. Were you trying to make the point that the biggest type safety hole in Java is in the one part where you have collections with unerased types? Because yeah that's kind of ironic.
  - saghm 3y ago
    This isn't due to type erasure though, it's due to allowing fallible subtyping; in particular, it shouldn't be possible to assign an array of a subtype to a variable of an array of a supertype. For example: class Animal {} class Dog extends Animal {} class Cat extends Animal {} ... Animal[] animals = new Dog[1]{}; animals[0] = new Cat(); The compiler could easily stop this issue by making the assignment of the `Dog` array to the `Animal` array an error because after the assignment, it's already impossible to add anything that's not a `Dog` to the array anyhow. Type erasure doesn't change this because regardless of any knowledge of the type at runtime, there's nothing reasonable to do but throw an exception because a `Cat` can't be put into a `Dog` array. I think the focus on type erasure is also a bit of a red herring because Java _does_ actually allow introspection of types at runtime via reflection, whereas Rust doesn't provide this. What information is available at runtime isn't really a factor because type safety is a property that's enforced at compile time.
- gpderetta 3y ago
  Java gives enough concurrency guarantees in the face of data races to maintain the integrity of the runtime and memory safety.
  - pornel 3y ago
    But not integrity of the program itself. You can still have data loss and garbage results. I really like the borrow checker and Rust's Send/Sync thread-safety markers, because they nudge towards cleaner thread-safe architecture, and give compile-time guarantees that work even across complex code, all kinds of collections, and 3rd party dependencies.
    - riku_iki 3y ago
      > But not integrity of the program itself. You can still have data loss and garbage results. curious what do you mean here? Java has many utils for concurrent programming, e.g. atomic variables, synchronize blocks etc.
      - dwattttt 3y ago
        The distinction they might be going for is the difference between guarantees and helpful utilities; good utilities can provide guarantees, but there's a lot to be said for default-safe and a safety culture
      - pornel 3y ago
        Java only promises to protect integrity of JVM itself, not your data. If you accidentally write to a non-concurrent collection from multiple threads, it's not a program-corrupting Undefined Behavior like in C/C++/golang, but it can still misbehave by corrupting the collection itself, causing it to mangle or lose data, or in the best case throw an exception. Either way you don't get the intended program behavior, and you may be unaware of using a wrong collection type until you create an invalid access at compile time. This is different from Rust, where thread-safety is part of the type system, so multi-threaded code that could write to a shared HashMap instead of a ConcurrentHashMap just won't compile with a type error.
- Verdex 3y ago
  To me, I don't even need a multi-threaded system to want Rust's ownership system. Too many defects that I've encountered in the past have been centered around the detective work that goes into whether or not you happen to want spooky action at a distance. Ah, in this instance we've created a list with objects in it and someone somewhere else is modifying it. This is causing the defect. But in this instance we've created a list with objects in it and then someone is creating new deep copies of those objects so that someone somewhere else can no longer modify it. And THAT is causing the defect. Rust makes this process significantly more explicit (although, I suppose someone could go a little crazy with RefMut and/or &mut and you end up back in the same place where you started with other lang). The fact that this also makes threading much easier is very much welcome to me.
  - johnnyjeans 3y ago
    It's a nice idea, but I find the conceptualization/implementation of it to be rather inelegant. It feels like it overcomplicates and goes a long distance to achieve the same effect as an affine type system. It makes reading and writing and conceptualizing about the code that much more annoying. I don't want to be forced into thinking about imperative code in terms of objects and ownerships, that's way too opinionated for my tastes. I find it much comparable to how modern C++ template metaprogramming goes to great lengths to achieve the same capability as a dependent type system, but again it's somehow even more annoying and grating to read and write than the most proof-laden example of something like Idris. I don't want to use a language that feels like an amateurish hackjob. Just give me something approximate to ocaml syntax with low level memory control and an affine type system. Please. That's what I want Rust to be. Not a frankenstein's monster that seems in direct competition with C++ to be the most needlessly complicated and ugly language possible.
    - Verdex 3y ago
      > It's a nice idea, but I find the conceptualization/implementation of it to be rather inelegant. Everyone is welcome to their own opinion and sense of style. Our world is better off for the one that you hold. > Just give me something approximate to ocaml syntax with low level memory control and an affine type system. Eh, the beggar cannot also be a chooser. Your desire may be good, but no one is compelled to make it a reality. Our environment experiences a glut of frontend and backend libraries for building your own programming language. As well as guides aplenty to show you the way.
didgetmaster 3y ago
I learned multi-threaded programming on OS/2 back in the late 80s. Ever since, I have designed any code I have written to handle multiple threads, even if I thought only a single thread would execute it. That has saved me many rewrites over the years when other threads were introduced. When I began writing my new data management system, multi-threading was designed into every component. It is thrilling when your code runs nearly twice as fast simply because you run it on a CPU with twice as many cores.
- agumonkey 3y ago
  Any tips or books you'd suggest?
  - cogman10 3y ago
    Tips: Don't mutate. Prefer pure functions over functions that mutate state and parameters. Ideally you interact with your system by giving it input and having it return results, not change some state somewhere. For example, It's not uncommon to see code that looks something like this void process(vector<int>& stuff, vector<Foo>& values_to_compute) { for (auto value_to_compute : values_to_compute) { stuff.push_back(compute(value_to_compute)); } } In the rush to try and avoid copying values or allocating, this program is now hard to multithread safely. You might want `stuff` to be shared and filled up across threads but that's not possible to safely do without a bunch of locks. The better solution looks something like this vector<int> process(vector<Foo>& values_to_compute) { vector<int> values; for (auto value_to_compute : values_to_compute) { values.push_back(compute(value_to_compute)); } return values; } Now to get threading, it's easy to split `values_to_compute` up to manageable chunk sizes and send them pinging down the system for as many cores as you have available. Then you can aggregate the results at the end. The way to think about these things is primarily about limiting shared mutable state among functions as much as possible. A rule of thumb is if you have functions which return `void` you are potentially making a headache for concurrency down the road.
    - stephc_int13 3y ago
foofie 3y ago
Great article. I think it would benefit from a sentence or paragraph on Amdahl's law to help drive the point home about potential performance improvements of serial code, which I would classify synchronization as one type. https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law
- nyanpasu64 3y ago
  In the article, wouldn't the runtime of the "join operations" step limit how much performance can be gained by parallelizing computation (due to Amdahl's Law as you brought up)?
- stephc_int13 3y ago
  I think that Amdahl Law is the reason why many engineers follow the full concurrency route instead of exploring parallelism more extensively, and that is a shame because while the theoretical limit of concurrency is higher, in practice the many, complex and sometimes mind boggling problems related to synchronisation can prevent such gains, and the problems don’t scale in a nice way, to put it mildly. On the other hand, parallelism scales nicely, and is mostly simple with a few rules.
LAC-Tech 3y ago
Enjoying this article. It's an area of computing I am very weak on, and it's really good to see an intelligent formulation of the why and how of multi-threaded computing in a broader context.
barrenko 3y ago
Tackling this myself atm, as a self-taught CS enthusiast reasoning about multiprocessing in python.
- lkrubner 3y ago
  Are you aware how difficult this is? Python has a complicated and messy history regarding concurrency, and even as recently as 2012 the most common advice was "avoid threads and use processes." Python was late to come up with any story around concurrency.
  - lewispollard 3y ago
    > even as recently as 2012 the most common advice was "avoid threads and use processes." Ok, I know in the grand scheme of things this may seem recent, but that was 12 years ago. Has the story really not changed since then?
    - galbar 3y ago
      Not really, multi-threaded parallelism is still limited by the GIL and it is best to use multiple processes instead. Unless you are using threads for I/O, or anything not using the CPU. What has changed since then is that Python now supports single-threaded concurrency, through async-await semantics.
    - jerf 3y ago
      Adding threading to a dynamic scripting language that had a multi-decade run as a single-threaded runtime turns out to be really, really difficult, especially if the language had C extensions. They all have had one form or another of very hard time about it, because it is a legitimately difficult problem.
JonChesterfield 3y ago
Coherent post. Could draw more attention to the most probable consequence of adding multithreading to a program - a marked decrease in reliability and moderate decrease in performance. There's something pessimistic to be said on the maintenance properties of multithreaded programs. Even if the original design is sound, it's unlikely to remain so under subsequent patches by various people. I don't know of a way to create a correct program that remains correct under subsequent mutation if it's built on mutex/semaphore/atomic operations. Maybe it could be done with a really aggressive type system and only allowing message passing, but that'll still pick up livelock/deadlock behaviours when threads wait on messages.
- andyferris 3y ago
  Doesn’t rust ensure your multithreaded code remains safe under mutation when refactoring the code?
  - klabb3 3y ago
    Yes, but not against deadlocks, leaks and atomic ref count locking overhead etc. Depending on how you write your code, (and the runtime if you’re using async) you usually need to abandon a certain subset of the key selling points of Rust (eg RAII, compile time borrow checks, and other zero-cost things). It’s bulky but yes, memory safe.
spintin 3y ago
Or you just go with "arrays of 64 byte multiple atomic structures" and you get parallelism and cache!
stephc_int13 3y ago
Very good article, I use mostly similar design ideas around multi-threaded code in my framework and projects. The main take is to avoid concurrency and instead use parallelism as much as possible. Also, a carefully engineered gameState or appState structure can help, my design is based around buffering the full state, so the work done during one step (typically a frame) is given as reference to the previous, frozen and immutable state as input, and can only write on the next state, with split/join of containers (my own generalized flavor of arena) when parallel work is done. I think that full concurrency is possible and has been proven to work, but IMO is a very costly and risky tradeoff, and unlikely to achieve much higher performance.

88 points by chmaynard 3y ago

Rust’s borrow checker does a nice job of formalizing the ideas in this post with & and &mut (shared reference and exclusive/mutable reference, respectively). The unsafe keyword (and the interior mutability pattern) provides exactly the right escape hatch for things like TableInsert and the join operation in the post. People like to talk about its memory safety, but it’s the fact that the compiler checks for data-race freedom that really sells rust for me. Languages like Java claim to be memory safe and type safe, but what does that actually mean if a concurrency bug means you have multiple CPUs stomping over your objects’ internal state in race?

jjtheblunt 3y ago
Java doesn’t claim quite to be type safe considering type erasure is built into its spec, so that, by runtime, containers (for example) might be surprised by a runtime appearance of an object type not checked for or known at compile time.
- lmm 3y ago
  > Java doesn’t claim quite to be type safe considering type erasure is built into its spec, so that, by runtime, containers (for example) might be surprised by a runtime appearance of an object type not checked for or known at compile time. Erasure has nothing to do with type safety; ultimately almost all types are "erased at runtime" since we have Von Neumann architecture where effectively everything is a byte/word, but this does not mean mechanical computers cannot run typesafe languages. Java reflection is arguably less safe due to type erasure, but reflection is almost inherently type-unsafe in the first place. (Java does have type unsafety via e.g. covariant arrays, but that's a design choice, not a fundamental limitation)
  - ackfoobar 3y ago
    > type unsafety via e.g. covariant arrays It's ironic when you think about it. The compiler enforced type safety is often argued as not type safe because they are erased at runtime; but the actual type unsafety has a runtime check.
    - lmm 3y ago
      > The compiler enforced type safety is often argued as not type safe because they are erased at runtime; but the actual type unsafety has a runtime check. Were you trying to make the point that the biggest type safety hole in Java is in the one part where you have collections with unerased types? Because yeah that's kind of ironic.
- saghm 3y ago
  This isn't due to type erasure though, it's due to allowing fallible subtyping; in particular, it shouldn't be possible to assign an array of a subtype to a variable of an array of a supertype. For example: class Animal {} class Dog extends Animal {} class Cat extends Animal {} ... Animal[] animals = new Dog[1]{}; animals[0] = new Cat(); The compiler could easily stop this issue by making the assignment of the `Dog` array to the `Animal` array an error because after the assignment, it's already impossible to add anything that's not a `Dog` to the array anyhow. Type erasure doesn't change this because regardless of any knowledge of the type at runtime, there's nothing reasonable to do but throw an exception because a `Cat` can't be put into a `Dog` array. I think the focus on type erasure is also a bit of a red herring because Java _does_ actually allow introspection of types at runtime via reflection, whereas Rust doesn't provide this. What information is available at runtime isn't really a factor because type safety is a property that's enforced at compile time.
gpderetta 3y ago
Java gives enough concurrency guarantees in the face of data races to maintain the integrity of the runtime and memory safety.
- pornel 3y ago
  But not integrity of the program itself. You can still have data loss and garbage results. I really like the borrow checker and Rust's Send/Sync thread-safety markers, because they nudge towards cleaner thread-safe architecture, and give compile-time guarantees that work even across complex code, all kinds of collections, and 3rd party dependencies.
  - riku_iki 3y ago
    > But not integrity of the program itself. You can still have data loss and garbage results. curious what do you mean here? Java has many utils for concurrent programming, e.g. atomic variables, synchronize blocks etc.
    - dwattttt 3y ago
      The distinction they might be going for is the difference between guarantees and helpful utilities; good utilities can provide guarantees, but there's a lot to be said for default-safe and a safety culture
    - pornel 3y ago
      Java only promises to protect integrity of JVM itself, not your data. If you accidentally write to a non-concurrent collection from multiple threads, it's not a program-corrupting Undefined Behavior like in C/C++/golang, but it can still misbehave by corrupting the collection itself, causing it to mangle or lose data, or in the best case throw an exception. Either way you don't get the intended program behavior, and you may be unaware of using a wrong collection type until you create an invalid access at compile time. This is different from Rust, where thread-safety is part of the type system, so multi-threaded code that could write to a shared HashMap instead of a ConcurrentHashMap just won't compile with a type error.
Verdex 3y ago
To me, I don't even need a multi-threaded system to want Rust's ownership system. Too many defects that I've encountered in the past have been centered around the detective work that goes into whether or not you happen to want spooky action at a distance. Ah, in this instance we've created a list with objects in it and someone somewhere else is modifying it. This is causing the defect. But in this instance we've created a list with objects in it and then someone is creating new deep copies of those objects so that someone somewhere else can no longer modify it. And THAT is causing the defect. Rust makes this process significantly more explicit (although, I suppose someone could go a little crazy with RefMut and/or &mut and you end up back in the same place where you started with other lang). The fact that this also makes threading much easier is very much welcome to me.
- johnnyjeans 3y ago
  It's a nice idea, but I find the conceptualization/implementation of it to be rather inelegant. It feels like it overcomplicates and goes a long distance to achieve the same effect as an affine type system. It makes reading and writing and conceptualizing about the code that much more annoying. I don't want to be forced into thinking about imperative code in terms of objects and ownerships, that's way too opinionated for my tastes. I find it much comparable to how modern C++ template metaprogramming goes to great lengths to achieve the same capability as a dependent type system, but again it's somehow even more annoying and grating to read and write than the most proof-laden example of something like Idris. I don't want to use a language that feels like an amateurish hackjob. Just give me something approximate to ocaml syntax with low level memory control and an affine type system. Please. That's what I want Rust to be. Not a frankenstein's monster that seems in direct competition with C++ to be the most needlessly complicated and ugly language possible.
  - Verdex 3y ago
    > It's a nice idea, but I find the conceptualization/implementation of it to be rather inelegant. Everyone is welcome to their own opinion and sense of style. Our world is better off for the one that you hold. > Just give me something approximate to ocaml syntax with low level memory control and an affine type system. Eh, the beggar cannot also be a chooser. Your desire may be good, but no one is compelled to make it a reality. Our environment experiences a glut of frontend and backend libraries for building your own programming language. As well as guides aplenty to show you the way.

didgetmaster 3y ago

I learned multi-threaded programming on OS/2 back in the late 80s. Ever since, I have designed any code I have written to handle multiple threads, even if I thought only a single thread would execute it. That has saved me many rewrites over the years when other threads were introduced. When I began writing my new data management system, multi-threading was designed into every component. It is thrilling when your code runs nearly twice as fast simply because you run it on a CPU with twice as many cores.

agumonkey 3y ago
Any tips or books you'd suggest?
- cogman10 3y ago
  Tips: Don't mutate. Prefer pure functions over functions that mutate state and parameters. Ideally you interact with your system by giving it input and having it return results, not change some state somewhere. For example, It's not uncommon to see code that looks something like this void process(vector<int>& stuff, vector<Foo>& values_to_compute) { for (auto value_to_compute : values_to_compute) { stuff.push_back(compute(value_to_compute)); } } In the rush to try and avoid copying values or allocating, this program is now hard to multithread safely. You might want `stuff` to be shared and filled up across threads but that's not possible to safely do without a bunch of locks. The better solution looks something like this vector<int> process(vector<Foo>& values_to_compute) { vector<int> values; for (auto value_to_compute : values_to_compute) { values.push_back(compute(value_to_compute)); } return values; } Now to get threading, it's easy to split `values_to_compute` up to manageable chunk sizes and send them pinging down the system for as many cores as you have available. Then you can aggregate the results at the end. The way to think about these things is primarily about limiting shared mutable state among functions as much as possible. A rule of thumb is if you have functions which return `void` you are potentially making a headache for concurrency down the road.
  - stephc_int13 3y ago

foofie 3y ago

Great article. I think it would benefit from a sentence or paragraph on Amdahl's law to help drive the point home about potential performance improvements of serial code, which I would classify synchronization as one type. https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law

nyanpasu64 3y ago
In the article, wouldn't the runtime of the "join operations" step limit how much performance can be gained by parallelizing computation (due to Amdahl's Law as you brought up)?
stephc_int13 3y ago
I think that Amdahl Law is the reason why many engineers follow the full concurrency route instead of exploring parallelism more extensively, and that is a shame because while the theoretical limit of concurrency is higher, in practice the many, complex and sometimes mind boggling problems related to synchronisation can prevent such gains, and the problems don’t scale in a nice way, to put it mildly. On the other hand, parallelism scales nicely, and is mostly simple with a few rules.

LAC-Tech 3y ago

Enjoying this article. It's an area of computing I am very weak on, and it's really good to see an intelligent formulation of the why and how of multi-threaded computing in a broader context.

barrenko 3y ago

Tackling this myself atm, as a self-taught CS enthusiast reasoning about multiprocessing in python.

lkrubner 3y ago
Are you aware how difficult this is? Python has a complicated and messy history regarding concurrency, and even as recently as 2012 the most common advice was "avoid threads and use processes." Python was late to come up with any story around concurrency.
- lewispollard 3y ago
  > even as recently as 2012 the most common advice was "avoid threads and use processes." Ok, I know in the grand scheme of things this may seem recent, but that was 12 years ago. Has the story really not changed since then?
  - galbar 3y ago
    Not really, multi-threaded parallelism is still limited by the GIL and it is best to use multiple processes instead. Unless you are using threads for I/O, or anything not using the CPU. What has changed since then is that Python now supports single-threaded concurrency, through async-await semantics.
  - jerf 3y ago
    Adding threading to a dynamic scripting language that had a multi-decade run as a single-threaded runtime turns out to be really, really difficult, especially if the language had C extensions. They all have had one form or another of very hard time about it, because it is a legitimately difficult problem.

JonChesterfield 3y ago

Coherent post. Could draw more attention to the most probable consequence of adding multithreading to a program - a marked decrease in reliability and moderate decrease in performance. There's something pessimistic to be said on the maintenance properties of multithreaded programs. Even if the original design is sound, it's unlikely to remain so under subsequent patches by various people. I don't know of a way to create a correct program that remains correct under subsequent mutation if it's built on mutex/semaphore/atomic operations. Maybe it could be done with a really aggressive type system and only allowing message passing, but that'll still pick up livelock/deadlock behaviours when threads wait on messages.

andyferris 3y ago
Doesn’t rust ensure your multithreaded code remains safe under mutation when refactoring the code?
- klabb3 3y ago
  Yes, but not against deadlocks, leaks and atomic ref count locking overhead etc. Depending on how you write your code, (and the runtime if you’re using async) you usually need to abandon a certain subset of the key selling points of Rust (eg RAII, compile time borrow checks, and other zero-cost things). It’s bulky but yes, memory safe.

spintin 3y ago

Or you just go with "arrays of 64 byte multiple atomic structures" and you get parallelism and cache!

stephc_int13 3y ago

Very good article, I use mostly similar design ideas around multi-threaded code in my framework and projects. The main take is to avoid concurrency and instead use parallelism as much as possible. Also, a carefully engineered gameState or appState structure can help, my design is based around buffering the full state, so the work done during one step (typically a frame) is given as reference to the previous, frozen and immutable state as input, and can only write on the next state, with split/join of containers (my own generalized flavor of arena) when parallel work is done. I think that full concurrency is possible and has been proven to work, but IMO is a very costly and risky tradeoff, and unlikely to achieve much higher performance.