34 ms·

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 tho

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
    The functional style is nice and all, but once you’ve reaped the low hanging fruits some problems are very hard or cumbersome to tackle in a stateless fashion. I think this is bad advice, the lead to multiple dead ends. Especially in the fields I know, video games and embedded software, state and mutation are everywhere. Embrace the state, parallelise your code instead of making it concurrent. Easier, almost always faster and more robust.
    - cogman10 3y ago
      This could very much be that different applications have different strategies that are applicable. For games and embedded systems, memory and CPU cycles are at a premium. My strat works best in languages with a GC where memory is abundant and cheap to allocate and there's not strict CPU time requirements. For the field I'm familiar with, microservices and backends, this works really well and mutation can generally be controlled (usually the only permanent state is the database). I agree shared state is probably faster, I'm not sure I agree with it being robust. Parallel code with shared state can be deceptively tricky to get right, especially when trying to hold multiple locks at the same time (which you have to do if you want to be fast). Nobody likes debugging why an app suddenly freezes for no apparent reason (deadlock).
      - stephc_int13 3y ago
        No, I am talking about lockless design. Split/join style. It is almost like a single threaded code, except that all heavy work is done as fast as possible in parallel, the single threaded part is almost free in practice, less than 1ms in total per frame, often 10 times less.
        cogman10 3y ago
        Split/join is also what I was talking about but storing the values in immutable temporary heap locations rather than in a common lockless queue. If you have the memory and allocation speed, that can be much faster than a lockless queue (especially if that queue is under high contention). However, for a game and embedded system I'd imagine the impact on heap fragmentation would be a pretty significant reason not to do this. For a GCed language, those heap allocations are fairly cheap, quiet a bit cheaper than what you pay for in a managed memory language (In GCed languages, the majority of memory allocations are 1 or 2 conditional checks with a pointer bump. It's very nearly the same speed as stack allocation). When I was talking about mutable state (and my example is perhaps bad), I'm more talking about system or process wide mutable state.
- david422 3y 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_int13 3y 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.
- didgetmaster 3y 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.

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
  The functional style is nice and all, but once you’ve reaped the low hanging fruits some problems are very hard or cumbersome to tackle in a stateless fashion. I think this is bad advice, the lead to multiple dead ends. Especially in the fields I know, video games and embedded software, state and mutation are everywhere. Embrace the state, parallelise your code instead of making it concurrent. Easier, almost always faster and more robust.
  - cogman10 3y ago
    This could very much be that different applications have different strategies that are applicable. For games and embedded systems, memory and CPU cycles are at a premium. My strat works best in languages with a GC where memory is abundant and cheap to allocate and there's not strict CPU time requirements. For the field I'm familiar with, microservices and backends, this works really well and mutation can generally be controlled (usually the only permanent state is the database). I agree shared state is probably faster, I'm not sure I agree with it being robust. Parallel code with shared state can be deceptively tricky to get right, especially when trying to hold multiple locks at the same time (which you have to do if you want to be fast). Nobody likes debugging why an app suddenly freezes for no apparent reason (deadlock).
    - stephc_int13 3y ago
      No, I am talking about lockless design. Split/join style. It is almost like a single threaded code, except that all heavy work is done as fast as possible in parallel, the single threaded part is almost free in practice, less than 1ms in total per frame, often 10 times less.
      - cogman10 3y ago
        Split/join is also what I was talking about but storing the values in immutable temporary heap locations rather than in a common lockless queue. If you have the memory and allocation speed, that can be much faster than a lockless queue (especially if that queue is under high contention). However, for a game and embedded system I'd imagine the impact on heap fragmentation would be a pretty significant reason not to do this. For a GCed language, those heap allocations are fairly cheap, quiet a bit cheaper than what you pay for in a managed memory language (In GCed languages, the majority of memory allocations are 1 or 2 conditional checks with a pointer bump. It's very nearly the same speed as stack allocation). When I was talking about mutable state (and my example is perhaps bad), I'm more talking about system or process wide mutable state.
david422 3y 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_int13 3y 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.
didgetmaster 3y 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.