Multi-Threading and Mutation

https://www.rfleury.com/p/multi-threading-and-mutation

by chmaynard • 2 years ago

88 43 2 years ago

hedora• 2 years 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• 2 years 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.

lmm2• 2 years 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)

saghm• 2 years 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• 2 years ago

Java gives enough concurrency guarantees in the face of data races to maintain the integrity of the runtime and memory safety.

pornel2• 2 years 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.

Verdex2• 2 years 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.

johnnyjeans2• 2 years 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.

didgetmaster2• 2 years 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• 2 years ago

Any tips or books you'd suggest?

cogman103• 2 years 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.

david422• 2 years ago

I've done some threaded code - and certainly not an expert, but my tips would be:

1. don't use global variables

2. when sharing data between threads - use message queues, not objects

3. if you do have shared objects, make your public methods thread safe by using mutexes and your internal methods don't need mutexes

stephc_int135• 2 years ago

Always favor parallelism over concurrency, if your design need to lock, there is likely a problem.

Don’t try to do the work in a magical fashion, that is hidden in the low level code and trying to be universal.

didgetmaster2• 2 years ago

My system is designed to handle large amounts of data. For example, it might have a relational table with a billion rows. The values for each column are stored in such a way that separate threads can operate on different segments of the data.

For example: if a query wants to find all addresses in an 'address' column that end in 'Avenue' and there are a billion unique addresses; then 10 separate threads might each look through 100 million values.

The code has each thread gather its own set of results and only adds them to the final result set (shared) when the search completes. The shared object only needs to be locked once by each thread as it appends its results to the list. This avoids contention that might occur if each thread tried to add a single value to the shared list as it found it.

foofie• 2 years 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

nyanpasu64• 2 years 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_int135• 2 years 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• 2 years 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• 2 years ago

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

lkrubner• 2 years 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• 2 years 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?

JonChesterfield• 2 years 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• 2 years ago

Doesn’t rust ensure your multithreaded code remains safe under mutation when refactoring the code?

klabb3• 2 years 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.

stephc_int135• 2 years 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.

spintin• 2 years ago

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

Multi-Threading and Mutation

Related Stories