8 ms·

1. Try process level I/O, such pipes, sockets, and the like. Have Linux deal with the concurrency problem, not you. (Note: the BASH & background job works in so

1. Try process level I/O, such pipes, sockets, and the like. Have Linux deal with the concurrency problem, not you. (Note: the BASH & background job works in so many cases it ain't funny). Also try fork/join parallelism models like OpenMP. These are all far easier than dipping down to a lower level. 2. Try a mutex 3. If that doesn't work, try adding a condition variable. 4. If that still doesn't work, try an atomic in default sequentially consistent mode or equivalent (ex: Java volatile, InterlockedAdd, and the like). Warning: atomics are very subtle. Definitely have a review with an expert if you are here. 5. If that still doesn't work, consider lock free paradigms. That is, combinations of atomics and memory barriers. 6. If that still doesn't work, publish a paper on your problem lol. --------- #1 is my most important piece of advice. There was a Blender render I was doing, like 2.6 or something old a few years ago. Blenders parallelism wasn't too good and only utilized 25% of my computer. So I ran 4 instances of headless Blender. Bam, 100% utilization. Done. Don't overthink parallelism. It's stupid easy sometimes, as easy as a & on the end of your shell command.

chasil 4y ago
The Oracle database has adopted process-level parallelism, utilizing System V IPC. Threading is used on Windows for performance reasons, but each client gets its own server pid by default on UNIX. This architecture expresses the original design intentions of "Columbus UNIX." "CB UNIX was developed to address deficiencies inherent in Research Unix, notably the lack of interprocess communication (IPC) and file locking, considered essential for a database management system... The interprocess communication features developed for CB UNIX were message queues, semaphores and shared memory support. These eventually appeared in mainstream Unix systems starting with System V in 1983, and are now collectively known as System V IPC." This approach has realized some degree of success. https://en.m.wikipedia.org/wiki/CB_UNIX https://en.m.wikipedia.org/wiki/CB_UNIX
- anarazel 4y ago
  Postgres also uses a multi process architecture. But I think that turned out to be a mistake for something like a database, on modern systems. There are other reasons, but the biggest problem is that inter process context switches are considerably more expensive than intra process ones. Far less efficient use of the TLB being a big part of that. It used to be worse before things like process context identifiers, but even with them you're wasting a large portion of the TLB by storing redundant information.
  - chasil 4y ago
    Oracle still managed to be the TPC-C performance leader from 12/2010 until Oceanbase took the crown in 2019 (I don't think that Oracle cares anymore). https://www.tpc.org/tpcc/results/tpcc_results5.asp?print=false&orderby=tpm&sortby=desc https://www.tpc.org/tpcc/results/tpcc_results5.asp?print=fal... https://www.alibabacloud.com/blog/oceanbase-breaks-tpc-c-record-a-dialogue-with-ant-financial-experts_596271 https://www.alibabacloud.com/blog/oceanbase-breaks-tpc-c-rec... They did this with an SGA (Shared Global Area) that (I'm assuming) pollutes the Translation Lookaside Buffer (TLB) with different addresses for this shared memory in every process.
    - anarazel 4y ago
      Yea, it's not something that's going to stop you dead in your tracks. But it does show up noticeably in profiles. There is stuff that you can do to reduce the pain, like using gigantic pages for the shared memory and remapping your executable's read-only sections, at runtime, so that you're using huge pages for your code. But even after that you can see the cost noticeably.
      - twoodfin 4y ago
        Right. One of several bits of architectural friction that didn’t matter while your large DBMS was I/O constrained.
        anarazel 4y ago
        > Right. One of several bits of architectural friction that didn’t matter while your large DBMS was I/O constrained. Yep. Lots of architectural design out there based on IO latency being higher by an order of magnitude or two than now, while memory latency only shrank modestly. To be clear, using one process with loads of threads has its own set of issues. Much easier to hit contention in the kernel, e.g. the infamous mmap_sem in linux.
  - anonymousDan 4y ago
    Wouldn't you just have a process per core and avoid context switches that way? Or does it require a process pool with more processes than that because everything is I/O bound?
- dragontamer 4y ago
  > utilizing System V IPC Hmm, that's a bit more complex than what I'd put at #1. I'd probably put System V IPC closer to #2 ("use a mutex") levels of complications. System V Shared memory + Semaphores is definitely "as complicated" as pthread mutexes and semaphores. But messages, signals, pipes, and other process-level IPC is much simpler. I guess SystemV IPC exists for that shady region "between" the high level stuff, and the complex low-level mutexes / semaphores. Maybe "1.75", if I were to put it in my list above somewhere. Closer to Mutexes in complexity, but still simpler in some respects. Depends on what bits of System V IPC you use, some bits are easier than others. --------- The main benefit of processes is that startup and shutdown behavior is very well defined. So something like a pipe, mmap, and other I/O has a defined beginning and end. All sockets are closed() properly, and so forth. SystemV throws a monkey wrench into that, because the semaphore or shared memory is "owned by Linux", so to speak. So a sem_post() is not necessarily going to be sem_wait(), especially if a process dies in a critical region.
zelphirkalt 4y ago
There is also: Try factoring out pure functions and run those in parallel.
- aleksiy123 4y ago
  This is my favourite technique. Keep state in messages. Keep functions pure. There can be drawbacks but for most types of tasks this works very well.
  - roeles 4y ago
    This sounds interesting. Can you share an example piece of code?
    - dgb23 4y ago
      Not GP but I think the fundamental idea is to think about "who calls who" and have pure functions be called/scheduled by a stateful coordination mechanism. Usually queues/channels/event loops are involved at the top level especially if you're doing async IO. If you're doing parallel computation then you'd probably use fan-in/fan-out/waitgroup logic at the top that calls into pure functions. The general point is "only this piece of code worries about coordinating state". For async IO think Go's concurrency primitives, Clojure's core.async or Erlang/Elixir as examples of coordinating state through messages. For parallelism specifically look at this pretty cool rust crate: https://lib.rs/crates/rayon https://lib.rs/crates/rayon Specifically at the discussion in the FAQ to get a sense of why it's useful to push mutability to the top level: https://github.com/rayon-rs/rayon/blob/master/FAQ.md https://github.com/rayon-rs/rayon/blob/master/FAQ.md As a counterpoint I'd like to link to a discussion about FP where Martin Thompson wrote: https://groups.google.com/g/mechanical-sympathy/c/gSkbc3grzNY https://groups.google.com/g/mechanical-sympathy/c/gSkbc3grzN... > Most FP persistent data structures take the form of a tree and perform a path copy from leaf to root for the change, reusing as much of the tree as possible. What this results in is a single contention point at the root of the tree for CAS operations. Now expand this view to a larger domain model of many entities, e.g. Customers, Orders, Products, etc., all interrelated and that model needs one or more entry points. Each of these entry points become a contention hotspot as the model is mutated. Also with trees and linked lists being the underlying data structures, performance is limited due to indirection causing cache misses. So really it matters a lot what you're doing. FP is not a panacea for concurrency and parallelism. As an application programmer that does mostly IO and very little heavy calculation etc. it's for example great.
JustSomeNobody 4y ago
>Try process level I/O, such pipes, sockets, and the like. This. > Have Linux deal with the concurrency problem, not you. Not just Linux. We did this with our Windows app rewrite. IPC with pipes is fast as hell, just works, and it greatly simplified parallelism for us.
- spacechild1 4y ago
  But why do you need a seperate process? You can do the same with threads and queues. The only advantage I can think of is sandboxing, i.e. preventing a misbehaving task from taking down your whole app.
  - JustSomeNobody 4y ago
    Ease of development. Ease of maintenance. Separation of concerns. Just to name a few. For example, one service is for hardware communication. It's job is to communicate with all the various devices, and forward those messages out. >You can do the same with threads and queues. Yes, but as OP up the chain mentions, you can simplify by letting the OS handle some of that.
    - spacechild1 4y ago
      > Ease of development. Ease of maintenance. Seperation of concerns. I'm not convinced. Managing processes is much more complex than managing threads, particularly if the code should be cross-platform. You need a very good library to hide away all the nasty OS specific details. Same goes for pipes or sockets. Then there is the whole issue of message (de)serialization. I don't see how this can possibly be easier than starting a thread and communicating with concurrent queue. I mean, subprocesses certainly have their use cases, but I would never see them as a drop-in replacement for threads. > you can simplify by letting the OS handle some of that. Processes and threads are both OS resources. For the OS scheduler they are practically equivalent.
      - dragontamer 4y ago
longcommonname 4y ago
Level 0. Use infra like kafka, and eventing to replicas.
- scns 4y ago
  I bet someone else has that link at hand where someone does parallel processing in shell with a fracture of the memory and CPU
bonzini 4y ago
4 is a mistake. The fundamental primitive for multiprocessing is message passing and release/acquire is just that, basically release is send and acquire is receive. If you have to go lock free, there are well-known patterns to communicate from one thread to another, and you should use those instead of just a sequentially consistent atomic. The best solution, however, is just to split your data and use coarse-grained mutexes.
- dragontamer 4y ago
  > and you should use those instead of just a sequentially consistent atomic. Ehhh... sometimes the best solution to the "bank account parallelism" problem is just: atomic_int bobs_bank_account_balance; // Thread#1 bobs_bank_account_balance += 100; // Depositing $100 in a sequentially consistent way. // In Thread#2 bobs_bank_account_balance -= 100; // Withdrawing $100 in a sequentially consistent way. No reason to bring in acquire vs release barriers or anything more complex. Just... atomically add and atomically subtract as needed. Not all cases are this simple, but many cases are. So you might as well try this and see if it is good enough. If not, then yeah, you move onto more complex paradigms. But always try the dumb and simple solutions first, before trying the harder stuff. ---------- This case is super common, that its even optimized in GPU programming. I've seen atomics like this become optimized into a prefix-sum routine by the compiler. Yes, this means you can have thousands of GPU-threads / shaders performing atomic adds / subtracts in GPU-space, and the atomic will be surprisingly efficient. The problem is that this paradigm doesn't always work. It takes skill to know when paradigms fail or succeed, and its sometimes very subtle. (That's why I say: try this, but... speak with an expert when doing so). There might be a subtle race condition. But in the cases where this works, absolutely program in this way.
  - zozbot234 4y ago
    Yes, if you can make do with a single atomic-sized object, you can perform any RMW on it with either a CAS loop or a special-cased atomic operation (like add or subtract) and not need any further synchronization. What the GP commenter described as being potentially dangerous and nedding expert knowledge is going in any way beyond that. It's really easy to e.g. trigger ABA problems and other issues without realizing it. So just use a mutex to synchronize access instead.
bmikaili 4y ago
OpenMP is so dead simple it's insane. Had a class on Parallel Computing (mainly for super computers / scientific computing) and while at the beginning I thought it'd be super hard, in the end it was just slapping #pragma omp parallel on everything

chasil 4y ago

The Oracle database has adopted process-level parallelism, utilizing System V IPC. Threading is used on Windows for performance reasons, but each client gets its own server pid by default on UNIX. This architecture expresses the original design intentions of "Columbus UNIX." "CB UNIX was developed to address deficiencies inherent in Research Unix, notably the lack of interprocess communication (IPC) and file locking, considered essential for a database management system... The interprocess communication features developed for CB UNIX were message queues, semaphores and shared memory support. These eventually appeared in mainstream Unix systems starting with System V in 1983, and are now collectively known as System V IPC." This approach has realized some degree of success. https://en.m.wikipedia.org/wiki/CB_UNIX https://en.m.wikipedia.org/wiki/CB_UNIX

anarazel 4y ago
Postgres also uses a multi process architecture. But I think that turned out to be a mistake for something like a database, on modern systems. There are other reasons, but the biggest problem is that inter process context switches are considerably more expensive than intra process ones. Far less efficient use of the TLB being a big part of that. It used to be worse before things like process context identifiers, but even with them you're wasting a large portion of the TLB by storing redundant information.
- chasil 4y ago
  Oracle still managed to be the TPC-C performance leader from 12/2010 until Oceanbase took the crown in 2019 (I don't think that Oracle cares anymore). https://www.tpc.org/tpcc/results/tpcc_results5.asp?print=false&orderby=tpm&sortby=desc https://www.tpc.org/tpcc/results/tpcc_results5.asp?print=fal... https://www.alibabacloud.com/blog/oceanbase-breaks-tpc-c-record-a-dialogue-with-ant-financial-experts_596271 https://www.alibabacloud.com/blog/oceanbase-breaks-tpc-c-rec... They did this with an SGA (Shared Global Area) that (I'm assuming) pollutes the Translation Lookaside Buffer (TLB) with different addresses for this shared memory in every process.
  - anarazel 4y ago
    Yea, it's not something that's going to stop you dead in your tracks. But it does show up noticeably in profiles. There is stuff that you can do to reduce the pain, like using gigantic pages for the shared memory and remapping your executable's read-only sections, at runtime, so that you're using huge pages for your code. But even after that you can see the cost noticeably.
    - twoodfin 4y ago
      Right. One of several bits of architectural friction that didn’t matter while your large DBMS was I/O constrained.
      - anarazel 4y ago
        > Right. One of several bits of architectural friction that didn’t matter while your large DBMS was I/O constrained. Yep. Lots of architectural design out there based on IO latency being higher by an order of magnitude or two than now, while memory latency only shrank modestly. To be clear, using one process with loads of threads has its own set of issues. Much easier to hit contention in the kernel, e.g. the infamous mmap_sem in linux.
- anonymousDan 4y ago
  Wouldn't you just have a process per core and avoid context switches that way? Or does it require a process pool with more processes than that because everything is I/O bound?
dragontamer 4y ago
> utilizing System V IPC Hmm, that's a bit more complex than what I'd put at #1. I'd probably put System V IPC closer to #2 ("use a mutex") levels of complications. System V Shared memory + Semaphores is definitely "as complicated" as pthread mutexes and semaphores. But messages, signals, pipes, and other process-level IPC is much simpler. I guess SystemV IPC exists for that shady region "between" the high level stuff, and the complex low-level mutexes / semaphores. Maybe "1.75", if I were to put it in my list above somewhere. Closer to Mutexes in complexity, but still simpler in some respects. Depends on what bits of System V IPC you use, some bits are easier than others. --------- The main benefit of processes is that startup and shutdown behavior is very well defined. So something like a pipe, mmap, and other I/O has a defined beginning and end. All sockets are closed() properly, and so forth. SystemV throws a monkey wrench into that, because the semaphore or shared memory is "owned by Linux", so to speak. So a sem_post() is not necessarily going to be sem_wait(), especially if a process dies in a critical region.

zelphirkalt 4y ago

There is also: Try factoring out pure functions and run those in parallel.

aleksiy123 4y ago
This is my favourite technique. Keep state in messages. Keep functions pure. There can be drawbacks but for most types of tasks this works very well.
- roeles 4y ago
  This sounds interesting. Can you share an example piece of code?
  - dgb23 4y ago
    Not GP but I think the fundamental idea is to think about "who calls who" and have pure functions be called/scheduled by a stateful coordination mechanism. Usually queues/channels/event loops are involved at the top level especially if you're doing async IO. If you're doing parallel computation then you'd probably use fan-in/fan-out/waitgroup logic at the top that calls into pure functions. The general point is "only this piece of code worries about coordinating state". For async IO think Go's concurrency primitives, Clojure's core.async or Erlang/Elixir as examples of coordinating state through messages. For parallelism specifically look at this pretty cool rust crate: https://lib.rs/crates/rayon https://lib.rs/crates/rayon Specifically at the discussion in the FAQ to get a sense of why it's useful to push mutability to the top level: https://github.com/rayon-rs/rayon/blob/master/FAQ.md https://github.com/rayon-rs/rayon/blob/master/FAQ.md As a counterpoint I'd like to link to a discussion about FP where Martin Thompson wrote: https://groups.google.com/g/mechanical-sympathy/c/gSkbc3grzNY https://groups.google.com/g/mechanical-sympathy/c/gSkbc3grzN... > Most FP persistent data structures take the form of a tree and perform a path copy from leaf to root for the change, reusing as much of the tree as possible. What this results in is a single contention point at the root of the tree for CAS operations. Now expand this view to a larger domain model of many entities, e.g. Customers, Orders, Products, etc., all interrelated and that model needs one or more entry points. Each of these entry points become a contention hotspot as the model is mutated. Also with trees and linked lists being the underlying data structures, performance is limited due to indirection causing cache misses. So really it matters a lot what you're doing. FP is not a panacea for concurrency and parallelism. As an application programmer that does mostly IO and very little heavy calculation etc. it's for example great.

JustSomeNobody 4y ago

>Try process level I/O, such pipes, sockets, and the like. This. > Have Linux deal with the concurrency problem, not you. Not just Linux. We did this with our Windows app rewrite. IPC with pipes is fast as hell, just works, and it greatly simplified parallelism for us.

spacechild1 4y ago
But why do you need a seperate process? You can do the same with threads and queues. The only advantage I can think of is sandboxing, i.e. preventing a misbehaving task from taking down your whole app.
- JustSomeNobody 4y ago
  Ease of development. Ease of maintenance. Separation of concerns. Just to name a few. For example, one service is for hardware communication. It's job is to communicate with all the various devices, and forward those messages out. >You can do the same with threads and queues. Yes, but as OP up the chain mentions, you can simplify by letting the OS handle some of that.
  - spacechild1 4y ago
    > Ease of development. Ease of maintenance. Seperation of concerns. I'm not convinced. Managing processes is much more complex than managing threads, particularly if the code should be cross-platform. You need a very good library to hide away all the nasty OS specific details. Same goes for pipes or sockets. Then there is the whole issue of message (de)serialization. I don't see how this can possibly be easier than starting a thread and communicating with concurrent queue. I mean, subprocesses certainly have their use cases, but I would never see them as a drop-in replacement for threads. > you can simplify by letting the OS handle some of that. Processes and threads are both OS resources. For the OS scheduler they are practically equivalent.
    - dragontamer 4y ago

longcommonname 4y ago

Level 0. Use infra like kafka, and eventing to replicas.

scns 4y ago
I bet someone else has that link at hand where someone does parallel processing in shell with a fracture of the memory and CPU

bonzini 4y ago

4 is a mistake. The fundamental primitive for multiprocessing is message passing and release/acquire is just that, basically release is send and acquire is receive. If you have to go lock free, there are well-known patterns to communicate from one thread to another, and you should use those instead of just a sequentially consistent atomic. The best solution, however, is just to split your data and use coarse-grained mutexes.

dragontamer 4y ago
> and you should use those instead of just a sequentially consistent atomic. Ehhh... sometimes the best solution to the "bank account parallelism" problem is just: atomic_int bobs_bank_account_balance; // Thread#1 bobs_bank_account_balance += 100; // Depositing $100 in a sequentially consistent way. // In Thread#2 bobs_bank_account_balance -= 100; // Withdrawing $100 in a sequentially consistent way. No reason to bring in acquire vs release barriers or anything more complex. Just... atomically add and atomically subtract as needed. Not all cases are this simple, but many cases are. So you might as well try this and see if it is good enough. If not, then yeah, you move onto more complex paradigms. But always try the dumb and simple solutions first, before trying the harder stuff. ---------- This case is super common, that its even optimized in GPU programming. I've seen atomics like this become optimized into a prefix-sum routine by the compiler. Yes, this means you can have thousands of GPU-threads / shaders performing atomic adds / subtracts in GPU-space, and the atomic will be surprisingly efficient. The problem is that this paradigm doesn't always work. It takes skill to know when paradigms fail or succeed, and its sometimes very subtle. (That's why I say: try this, but... speak with an expert when doing so). There might be a subtle race condition. But in the cases where this works, absolutely program in this way.
- zozbot234 4y ago
  Yes, if you can make do with a single atomic-sized object, you can perform any RMW on it with either a CAS loop or a special-cased atomic operation (like add or subtract) and not need any further synchronization. What the GP commenter described as being potentially dangerous and nedding expert knowledge is going in any way beyond that. It's really easy to e.g. trigger ABA problems and other issues without realizing it. So just use a mutex to synchronize access instead.

bmikaili 4y ago

OpenMP is so dead simple it's insane. Had a class on Parallel Computing (mainly for super computers / scientific computing) and while at the beginning I thought it'd be super hard, in the end it was just slapping #pragma omp parallel on everything