← Back to context

Comment by dragontamer

4 years ago

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.

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

  • 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.

  • > 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.

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.

  • > 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.

    • The question is what the invariants are around those operations. It is rarely the case that you can get away with simple RMW operations, because they don't guarantee any invariants. Also, sequentially consistent RMW atomic operations don't order with non-sequentially consistent atomics (the exception being the seqcst fence) so it's hard to construct send/receive operations using seqcst atomics—if you can use them, chances are that even relaxed could be enough!

      Going deeper into the atomic add example, are you sure that the cache line bouncing will not be an issue? can you perhaps make the code just update something that you already have exclusive access to, and sum multiple values when you do a read (hopefully it's rare, e.g. reading a statistic once a second)? So again the solution could be to use a mutex and split the data so that the mutex is mostly uncontended.

      1 reply →

    • 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.

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

>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.

  • 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.

    • 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.

      19 replies →

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

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