4 ms·

A few thoughts and questions by a layman interested in distributed and concurrent programming. I would be very interested to hear back from someone with deep ex

A few thoughts and questions by a layman interested in distributed and concurrent programming. I would be very interested to hear back from someone with deep experience in this area. In my limited perception we are moving further and further away from fine-granular synchronization, and many use cases can be solved efficiently with off-the-shelf synchronization methods like queues. Given that, is thread safety that much of an issue anyway? What are folks' use cases where thread correctness is hard to get right? Where are more complex concurrent data structures needed - like, say, a concurrent hashmap? I gather that in kernels like Linux for example, there is a lot of this because it is attempted to serve as many syscalls as possible in the calling thread. My idea is that complexities like this come partly due to the fact that a running OS is a loose collection of software that wasn't developed by a single entity, so necessarily there was a lack of opportunity to measure requirements and allocating appropriate storage and computing resources ahead of time. In systems where the requirements are clearer cut, maybe appropriate resources can be more easily allocated upfront to achieve simplicity and possibly higher throughput at the cost of a little added latency (communication). It also seems like the fine granular model could become more obsolete over time as shared state becomes costlier with growing core count and the higher synchronization cost that I assume must come with it.

mrfox321 5y ago
Depends on what you are working on? Cross-request cache's naturally require synchronization. Although you could simply get away with thread-local storage. In huge systems, there's always some other thread doing stuff that you may be using in a way that hides the fact that it is thread-safe. I'm no expert, mind you. I avoid concurrency problems if possible, but they are sometimes unavoidable. I touch shared resources that would OOM if made thread-local.
Animats 5y ago
In my limited perception we are moving further and further away from fine-granular synchronization, and many use cases can be solved efficiently with off-the-shelf synchronization methods like queues. Given that, is thread safety that much of an issue anyway? What are folks' use cases where thread correctness is hard to get right? Where are more complex concurrent data structures needed - like, say, a concurrent hashmap? I'm working on a client for a virtual world. This has a whole 3D world, or at least the part you can currently see, in memory. Anything can change, but most of it is static. There are quite a few threads working in coordination to keep the world updated. Some of this is painful in Rust, because Rust really wants an ownership tree. It can be made to work with reference counts (rust "Rc" and "Arc") and their weak forms as backlinks. It's kind of clunky. Single owner with backlinks, along with the static analysis needed to guarantee safety, is needed. That's a hard problem. Much of the "use a queue" thinking comes from the web back end crowd, where you're managing a large number of connections which have very little interaction with each other. Most of the state is in the database, anyway. It also seems like the fine granular model could become more obsolete over time as shared state becomes costlier with growing core count and the higher synchronization cost that I assume must come with it. Now that is a very real problem. The next frontier in language design is support for non-shared-memory systems all working on the same problem. I knew someone who spent too much time on that with the Playstation 3's Cell processors. Sony went back to more traditional architectures after it became clear how hard it was to do anything that way. The supercomputer people have been dealing with this for years, but mostly they want to handle big matrices, where the inner loop is tiny. Same with GPUs - shaders are highly parallel but small programs.
- Hercuros 5y ago
  Another option instead of using Rc/Arc is to use integer indices/handles into (e.g.) a vector holding your objects. Then you can have safety (in the sense of there being no language-level UB) by bounds checking your indices (you can do even better if you use a generational arena and attach a generation counter to your indices), and you can still have arbitrary object graphs that way. I think that this pattern is common in C++ game programming as well (e.g. when using entity component systems), because using pointers or references everywhere and building complicated object graphs is a recipe for object lifetime issues. I would be surprised if anyone could handle the mental complexity of managing ownership in arbitrary object graphs without there being some simplifying idea (like that of an ownership tree) involved, even if it's not enforced at the compiler level (as it is in Rust, but it isn't in C++).
  - jstimpfle 5y ago
    > using pointers or references everywhere and building complicated object graphs is a recipe for object lifetime issues. It's also that indices are the better and cleaner "identities" compared to pointers. Pointer values include runtime baggage, and it shows if one tries to do parallel arrays or serialization.
  - alexchamberlain 5y ago
    On this, have you found any studies in different data structures to support the mapping between integers and the underlying objects? Personally, I'm working on a Hexastore that requires maintaining order of the 2 in parallel.
    - jstimpfle 5y ago
      It's a strange idea to have to maintain the order of the numbers 0 to N-1 :-)
  - Animats 5y ago
    That works in a static environment, but when you're constantly deleting objects, you need a hash or tree. That has more overhead. The basic constraint inside virtual world viewers is that anything can change at any time, but usually it doesn't. The "not changing" case has to be efficient.
bluGill 5y ago
CPUs stopped getting faster about 20 years ago. There have been minor improvements, but up until 20 years ago you could count on the a doubling of MHz every couple years, today clocks are not faster. Unstead we are given SIMD and more core cores. Both can greatly increase the speed of your code, but only if you can take advantage of them. SIMD requires specific data structures. Cores need threads. As such how to take advantage of threads is a critical question for any program that isn't fast enough. If your code is fast enough then don't worry about it. If your code isn't then you need to to deal with hard areas of programming.
- deleted 5y ago
  [deleted]
geofft 5y ago
I think this is an interesting question and I'm not sure why it was downvoted. One argument here is that the whole mental model of Rust is that yes, most things can be solved with off-the-shelf synchronization methods. What the Rust type system gives you is a way for library authors to write those methods and say "Yes, this hashmap is actually a concurrent hashmap, safely usable from multiple threads" - and in turn for these types to compose, and to see if the data stored in the hashmap is itself thread-safe. Then the application author doesn't need to worry about any of this. As long as the code compiles (and the library authors weren't going out of their way to lie about types and make the Rust compiler ignore it), you know there are no thread-safety issues and you can just treat synchronization as a problem for someone else to solve. That's the ideal - just like the average application shouldn't have its own crypto implementation, it shouldn't have its own concurrency implementation. A simple case where you need a concurrent hashmap (at least conceptually) is writing a multi-threaded web server or similar. When a thread wakes up, it gets told that there's data on some particular connection. It then needs to look up that connection in a table and manipulate the request object associated with that connection. Any thread could be woken up for any incoming traffic, so this table needs to be cross-thread. You could do one thread per connection, and arguably more people should, but people very often find that they hit scaling limit with that approach. But yes, most of the time you should avoid shared mutable state. The Rust type system is designed around making it hard to accidentally have shared mutable state. Anecdotally, that feels like the most common cause of thread-safety issues - not people thinking up front about how they need to design their program around a concurrent hashmap.
- jstimpfle 5y ago
  Thanks for commenting :-). I probably would have classified what you describe as a coarse-grained synchronization problem though. There needs to be a little runtime-y support for the connection and request object handling, but that can live in a central place and be exposed as a simple (blocking?) function call. It's almost an "off-the-shelf" situation. Individual request handlers can be programmed without any concern for synchronization (at least with regards to the request object, and apart from that most request handlers are rather isolated from each other). Any particular request is never handled by more than 1 thread at once. It's only 1 logical thread, as is evidenced by the existence of thread-per-connection implementations. I am starting to think that this is a good example of what I wanted to express in my parent post - maybe synchronization issues can more often than not constrained to a few central places, maybe we don't have to litter code with locks and unlocks so much? Maybe web request processing architecture is not that primitive and other domains can learn from it? Maybe a lot of nitty-gritty synchronization could be centralized if the "it needs to happen right here, right now" constraint is lifted?
alexchamberlain 5y ago
I think that's fair to a certain extent - a queue is the simplest form of message passing or work distribution. There are many other data structures that have been developed that work well with multiple threads. I think what _is_ out of vogue is just protecting an arbitrary data structure with a mutex and calling it thread safe.

mrfox321 5y ago

Depends on what you are working on? Cross-request cache's naturally require synchronization. Although you could simply get away with thread-local storage. In huge systems, there's always some other thread doing stuff that you may be using in a way that hides the fact that it is thread-safe. I'm no expert, mind you. I avoid concurrency problems if possible, but they are sometimes unavoidable. I touch shared resources that would OOM if made thread-local.

Animats 5y ago

In my limited perception we are moving further and further away from fine-granular synchronization, and many use cases can be solved efficiently with off-the-shelf synchronization methods like queues. Given that, is thread safety that much of an issue anyway? What are folks' use cases where thread correctness is hard to get right? Where are more complex concurrent data structures needed - like, say, a concurrent hashmap? I'm working on a client for a virtual world. This has a whole 3D world, or at least the part you can currently see, in memory. Anything can change, but most of it is static. There are quite a few threads working in coordination to keep the world updated. Some of this is painful in Rust, because Rust really wants an ownership tree. It can be made to work with reference counts (rust "Rc" and "Arc") and their weak forms as backlinks. It's kind of clunky. Single owner with backlinks, along with the static analysis needed to guarantee safety, is needed. That's a hard problem. Much of the "use a queue" thinking comes from the web back end crowd, where you're managing a large number of connections which have very little interaction with each other. Most of the state is in the database, anyway. It also seems like the fine granular model could become more obsolete over time as shared state becomes costlier with growing core count and the higher synchronization cost that I assume must come with it. Now that is a very real problem. The next frontier in language design is support for non-shared-memory systems all working on the same problem. I knew someone who spent too much time on that with the Playstation 3's Cell processors. Sony went back to more traditional architectures after it became clear how hard it was to do anything that way. The supercomputer people have been dealing with this for years, but mostly they want to handle big matrices, where the inner loop is tiny. Same with GPUs - shaders are highly parallel but small programs.

Hercuros 5y ago
Another option instead of using Rc/Arc is to use integer indices/handles into (e.g.) a vector holding your objects. Then you can have safety (in the sense of there being no language-level UB) by bounds checking your indices (you can do even better if you use a generational arena and attach a generation counter to your indices), and you can still have arbitrary object graphs that way. I think that this pattern is common in C++ game programming as well (e.g. when using entity component systems), because using pointers or references everywhere and building complicated object graphs is a recipe for object lifetime issues. I would be surprised if anyone could handle the mental complexity of managing ownership in arbitrary object graphs without there being some simplifying idea (like that of an ownership tree) involved, even if it's not enforced at the compiler level (as it is in Rust, but it isn't in C++).
- jstimpfle 5y ago
  > using pointers or references everywhere and building complicated object graphs is a recipe for object lifetime issues. It's also that indices are the better and cleaner "identities" compared to pointers. Pointer values include runtime baggage, and it shows if one tries to do parallel arrays or serialization.
- alexchamberlain 5y ago
  On this, have you found any studies in different data structures to support the mapping between integers and the underlying objects? Personally, I'm working on a Hexastore that requires maintaining order of the 2 in parallel.
  - jstimpfle 5y ago
    It's a strange idea to have to maintain the order of the numbers 0 to N-1 :-)
- Animats 5y ago
  That works in a static environment, but when you're constantly deleting objects, you need a hash or tree. That has more overhead. The basic constraint inside virtual world viewers is that anything can change at any time, but usually it doesn't. The "not changing" case has to be efficient.

bluGill 5y ago

CPUs stopped getting faster about 20 years ago. There have been minor improvements, but up until 20 years ago you could count on the a doubling of MHz every couple years, today clocks are not faster. Unstead we are given SIMD and more core cores. Both can greatly increase the speed of your code, but only if you can take advantage of them. SIMD requires specific data structures. Cores need threads. As such how to take advantage of threads is a critical question for any program that isn't fast enough. If your code is fast enough then don't worry about it. If your code isn't then you need to to deal with hard areas of programming.

deleted 5y ago
[deleted]

geofft 5y ago

I think this is an interesting question and I'm not sure why it was downvoted. One argument here is that the whole mental model of Rust is that yes, most things can be solved with off-the-shelf synchronization methods. What the Rust type system gives you is a way for library authors to write those methods and say "Yes, this hashmap is actually a concurrent hashmap, safely usable from multiple threads" - and in turn for these types to compose, and to see if the data stored in the hashmap is itself thread-safe. Then the application author doesn't need to worry about any of this. As long as the code compiles (and the library authors weren't going out of their way to lie about types and make the Rust compiler ignore it), you know there are no thread-safety issues and you can just treat synchronization as a problem for someone else to solve. That's the ideal - just like the average application shouldn't have its own crypto implementation, it shouldn't have its own concurrency implementation. A simple case where you need a concurrent hashmap (at least conceptually) is writing a multi-threaded web server or similar. When a thread wakes up, it gets told that there's data on some particular connection. It then needs to look up that connection in a table and manipulate the request object associated with that connection. Any thread could be woken up for any incoming traffic, so this table needs to be cross-thread. You could do one thread per connection, and arguably more people should, but people very often find that they hit scaling limit with that approach. But yes, most of the time you should avoid shared mutable state. The Rust type system is designed around making it hard to accidentally have shared mutable state. Anecdotally, that feels like the most common cause of thread-safety issues - not people thinking up front about how they need to design their program around a concurrent hashmap.

jstimpfle 5y ago
Thanks for commenting :-). I probably would have classified what you describe as a coarse-grained synchronization problem though. There needs to be a little runtime-y support for the connection and request object handling, but that can live in a central place and be exposed as a simple (blocking?) function call. It's almost an "off-the-shelf" situation. Individual request handlers can be programmed without any concern for synchronization (at least with regards to the request object, and apart from that most request handlers are rather isolated from each other). Any particular request is never handled by more than 1 thread at once. It's only 1 logical thread, as is evidenced by the existence of thread-per-connection implementations. I am starting to think that this is a good example of what I wanted to express in my parent post - maybe synchronization issues can more often than not constrained to a few central places, maybe we don't have to litter code with locks and unlocks so much? Maybe web request processing architecture is not that primitive and other domains can learn from it? Maybe a lot of nitty-gritty synchronization could be centralized if the "it needs to happen right here, right now" constraint is lifted?

alexchamberlain 5y ago

I think that's fair to a certain extent - a queue is the simplest form of message passing or work distribution. There are many other data structures that have been developed that work well with multiple threads. I think what _is_ out of vogue is just protecting an arbitrary data structure with a mutex and calling it thread safe.