4 ms·

This is why it isn’t called Amdahl's suggestion. The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding

This is why it isn’t called Amdahl's suggestion. The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Better solutions abound with concurrent sequential processes, or the Actor architecture.

jeffbee 4y ago
It will only bring your application to a grinding halt if it's on the critical path. Most data in most programs can be protected with a plain old mutex and everyone is happy with the performance. Even on the hot path you may get trivial scaling to 2 or 4 threads with a global mutex protecting critical data, as we see with memcached. Sharing doesn't start to offend Amdahl until you have many threads and the critical section is relatively costly compared to the rest of the program.
- lumost 4y ago
  Worth calling out that the introduction of multiple locks can lead to deadlocks etc. It would actually make for a nice library to have lock acquisition decoupled from lock scope in the caller. Eg every call to lock acquire passes some identifier, and the lock implementation decides what it will do with that identifier eg global lock, scoped lock etc
  - jeffbee 4y ago
    I find that thread safety annotations in clang help prevent deadlocks when there’s a tricky section.
paskozdilar 4y ago
Agreed. The problem with mutex is that it's often hard to get right, since it's a low-level primitive for serializing access to shared memory, and it does not compose (cannot atomically lock two mutexes). CSP/Actor model simply takes the problem that mutex solves on the low level - concurrency - and makes the whole world concurrent-by-default, so that mutexes are not needed. Note the 1st Go proverb [0]: "Don't communicate by sharing memory, share memory by communicating." [0] https://www.youtube.com/watch?v=PAAkCSZUG1c&t=168s https://www.youtube.com/watch?v=PAAkCSZUG1c&t=168s
- vore 4y ago
  Sure you can compose mutexes: https://en.cppreference.com/w/cpp/thread/lock https://en.cppreference.com/w/cpp/thread/lock In practice, if you have a global total ordering of mutexes, it's safe to lock any number of them provided you lock them in order. CSP is interesting but it doesn't apply in a lot of cases, e.g. designing a lock striping mechanism over a database as described in the article would not be very fun with CSP or actors, as the article calls out at the bottom.
  - paskozdilar 4y ago
    > In practice, if you have a global total ordering of mutexes, it's safe to lock any number of them provided you lock them in order. Very interesting! Such a simple and elegant solution.
arinlen 4y ago
> The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Not necessarily. It really depends on your problem domain and how you architected your solution. For example, a basic producer-consumer can suffer if you implement it with a common non-thread safe task queue where all consumers and producers have to lock a mutex to push/pop. However, adopting a queue whose pushes and pops can be performed independently without any contention, and using work-stealing consumers that manage their own work queue are enough to eliminate contention to a residual level. It all depends on your problem domain and how much time and effort and thought you're willing to invest in a problem.
vardump 4y ago
Yes. What's often ignored is that inter-CPU communication mutexes rely on is a limited resource in itself. So heavy use of mutexes can slow down other unrelated processes as well.
dragontamer 4y ago
Anyone studying Amdahl's law should also study the inverse, literally 1/(Amdahl's law), which leads to Gustafson's law. Its really strange what a simple reciprocal does to the entire equation. Instead of trying to cut your time down and perform work faster, Gustafson's law holds "time as constant" and measures the "amount of work done". Lo and behold: the parallel-portion of work grows the more-and-more work is available. That is to say, if you double-the-data to process, you can almost always double-the-parallelism in the same amount of time. ------------ So, you have some model (neural net?) that's difficult to parallelize? No problem, simple solution. Double, triple, quadruple the size of the model. Done. Suddenly more of it can be performed in parallel. Shrinking time (ie: Ahmdal's law) is an exercise in futility, and uselessness. It turns out that a lot of people's work days are measured in hours, and going from 30-seconds of wait time to 10-seconds of wait time is not really a crazy benefit. Instead, going from "Analyzed 2-GBs of data in 30-seconds" into "Analyzed 6GBs of data in 30-seconds" does lead to improvements. > The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Better solutions abound with concurrent sequential processes, or the Actor architecture. This is a separate issue. Contention is O(n), where n is the amount of contention. 1000 threads writing the same variable can only be done one-at-a-time. So it will take O(1000) time to perform all those reads/writes. It doesn't matter if you use mutexes, atomic-compare-and-swap, or anything. You can't "beat" the laws of physics. 1000 updates requires 1000x time. You "solve" this by splitting up your variables and minimizing contention. Instead of 1000x writes to 1x variable, you can perform 1000x writes to 1000x variables, then read the 1000x variables in parallel one step later.
yakubin 4y ago
Amdahl's law applies regardless of whether you use shared memory synchronization, CSP or Actors. CSP and Actors are easier to think about, but they aren't inherently faster.
adwn 4y ago
> The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Better solutions abound with concurrent sequential processes, or the Actor architecture. I might be misunderstanding what you mean, but if heavy contention around a specific resource becomes a bottleneck, then putting it in an actor won't help you at all, because you've replaced the contention around the mutex with contention around accessing the actor's input queue. The solution to contention is usually some kind of replication. So for example, if you have a shared hashmap which is protected by a mutex, the solution isn't to put the hashmap into an actor, but to split it off into, say, 16 hashmaps, and partition the entries according to the lower 4 bits of the hash.

jeffbee 4y ago

It will only bring your application to a grinding halt if it's on the critical path. Most data in most programs can be protected with a plain old mutex and everyone is happy with the performance. Even on the hot path you may get trivial scaling to 2 or 4 threads with a global mutex protecting critical data, as we see with memcached. Sharing doesn't start to offend Amdahl until you have many threads and the critical section is relatively costly compared to the rest of the program.

lumost 4y ago
Worth calling out that the introduction of multiple locks can lead to deadlocks etc. It would actually make for a nice library to have lock acquisition decoupled from lock scope in the caller. Eg every call to lock acquire passes some identifier, and the lock implementation decides what it will do with that identifier eg global lock, scoped lock etc
- jeffbee 4y ago
  I find that thread safety annotations in clang help prevent deadlocks when there’s a tricky section.

paskozdilar 4y ago

Agreed. The problem with mutex is that it's often hard to get right, since it's a low-level primitive for serializing access to shared memory, and it does not compose (cannot atomically lock two mutexes). CSP/Actor model simply takes the problem that mutex solves on the low level - concurrency - and makes the whole world concurrent-by-default, so that mutexes are not needed. Note the 1st Go proverb [0]: "Don't communicate by sharing memory, share memory by communicating." [0] https://www.youtube.com/watch?v=PAAkCSZUG1c&t=168s https://www.youtube.com/watch?v=PAAkCSZUG1c&t=168s

vore 4y ago
Sure you can compose mutexes: https://en.cppreference.com/w/cpp/thread/lock https://en.cppreference.com/w/cpp/thread/lock In practice, if you have a global total ordering of mutexes, it's safe to lock any number of them provided you lock them in order. CSP is interesting but it doesn't apply in a lot of cases, e.g. designing a lock striping mechanism over a database as described in the article would not be very fun with CSP or actors, as the article calls out at the bottom.
- paskozdilar 4y ago
  > In practice, if you have a global total ordering of mutexes, it's safe to lock any number of them provided you lock them in order. Very interesting! Such a simple and elegant solution.

arinlen 4y ago

> The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Not necessarily. It really depends on your problem domain and how you architected your solution. For example, a basic producer-consumer can suffer if you implement it with a common non-thread safe task queue where all consumers and producers have to lock a mutex to push/pop. However, adopting a queue whose pushes and pops can be performed independently without any contention, and using work-stealing consumers that manage their own work queue are enough to eliminate contention to a residual level. It all depends on your problem domain and how much time and effort and thought you're willing to invest in a problem.

vardump 4y ago

Yes. What's often ignored is that inter-CPU communication mutexes rely on is a limited resource in itself. So heavy use of mutexes can slow down other unrelated processes as well.

dragontamer 4y ago

Anyone studying Amdahl's law should also study the inverse, literally 1/(Amdahl's law), which leads to Gustafson's law. Its really strange what a simple reciprocal does to the entire equation. Instead of trying to cut your time down and perform work faster, Gustafson's law holds "time as constant" and measures the "amount of work done". Lo and behold: the parallel-portion of work grows the more-and-more work is available. That is to say, if you double-the-data to process, you can almost always double-the-parallelism in the same amount of time. ------------ So, you have some model (neural net?) that's difficult to parallelize? No problem, simple solution. Double, triple, quadruple the size of the model. Done. Suddenly more of it can be performed in parallel. Shrinking time (ie: Ahmdal's law) is an exercise in futility, and uselessness. It turns out that a lot of people's work days are measured in hours, and going from 30-seconds of wait time to 10-seconds of wait time is not really a crazy benefit. Instead, going from "Analyzed 2-GBs of data in 30-seconds" into "Analyzed 6GBs of data in 30-seconds" does lead to improvements. > The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Better solutions abound with concurrent sequential processes, or the Actor architecture. This is a separate issue. Contention is O(n), where n is the amount of contention. 1000 threads writing the same variable can only be done one-at-a-time. So it will take O(1000) time to perform all those reads/writes. It doesn't matter if you use mutexes, atomic-compare-and-swap, or anything. You can't "beat" the laws of physics. 1000 updates requires 1000x time. You "solve" this by splitting up your variables and minimizing contention. Instead of 1000x writes to 1x variable, you can perform 1000x writes to 1000x variables, then read the 1000x variables in parallel one step later.

yakubin 4y ago

Amdahl's law applies regardless of whether you use shared memory synchronization, CSP or Actors. CSP and Actors are easier to think about, but they aren't inherently faster.

adwn 4y ago

> The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Better solutions abound with concurrent sequential processes, or the Actor architecture. I might be misunderstanding what you mean, but if heavy contention around a specific resource becomes a bottleneck, then putting it in an actor won't help you at all, because you've replaced the contention around the mutex with contention around accessing the actor's input queue. The solution to contention is usually some kind of replication. So for example, if you have a shared hashmap which is protected by a mutex, the solution isn't to put the hashmap into an actor, but to split it off into, say, 16 hashmaps, and partition the entries according to the lower 4 bits of the hash.