4 ms·

In my opinion, shared memory mutability is the actual bad idea that's going to eventually die. It's not just error prone, it doesn't scale; try mutating the sam

In my opinion, shared memory mutability is the actual bad idea that's going to eventually die. It's not just error prone, it doesn't scale; try mutating the same cache line from two threads on an Intel desktop chip and see how that goes. Let alone across mesh buses, chiplets, dual sockets or (God forbid) the network. Garbage collection on immutable data is vastly easier; it's intrinsically non blocking, concurrent and parallel. You can build a garbage collected immutable data store over arbitrary numbers of computers.

arcticbull 7y ago
Am I wrong in thinking that a system comprised of entirely immutable memory doesn't even need a garbage collector? If you built such a system in Rust would not all memory just be deallocated once no longer utilized? The rust principal is (many readers XOR one writer) leads to fully static memory management. This is my point. We need to go back and re-think our language design principals keeping memory management in mind instead of pretending it's a solved problem. IMO you make a good case.
- mafribe 7y ago
  Am I wrong ... Yes. Unless your memory is infinite. Rust also automatically deallocates memory that is no longer used, so it's some kind of GC, but one where the point of deallocation is either statically determined (based on nesting of life-times) or dynamically (using reference-counting). The problem with static dealloc is that the compiler cannot always work out when memory becomes free and must make conservative approximations (see Rice's theorem [1]), the problem with ref-counting is circular data structures (and also the cost in space and time and synchronisation across threads of maintaining an index). [1] https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem
mafribe 7y ago
Au contraire, as memory, and hence workloads, get bigger, the cost of copying increases, and copying rather than sharing becomes ever more expensive. I just spoke with a physicist who told me that his current experiment produces 200 Gigabytes of data per second! Copying that amount of data around for immutability is inconceivable. Indeed the single biggest factor for performance for such workloads is minimising the amount of copying. Erlang-style shared-nothing is brilliant if you can afford it, but it's affordable only for small data.
- reitzensteinm 7y ago
  Erlang style immutable reference counted shared memory is not at all state of the art. Persistent data structures are common and effective. I have implemented several myself, to store and update trees that don't fit in main memory. If you're updating one byte of your physicist's (say) 1 petabyte dataset, it requires ten memory allocations (log[branch factor] of the size of the dataset). If you're updating the whole thing linearly, do consider that updating something in place or creating an updated copy is identical in terms of performance; a storage device doesn't care whether the bits streaming back are overwriting the same locations or new ones. Though of course you end up with both copies at the end.
  - mafribe 7y ago
    Are there high-performance matrix multiplication libraries, e.g. for fluid-dynamics simulations, that are implemented using persistent data structures?
    - deleted 7y ago
      [deleted]
    - reitzensteinm 7y ago
      Are there any where multiple threads are mutating overlapping sections of memory? How exactly do you think a GPU matrix multiply violates my initial assertion?
- McWobbleston 7y ago
  Usually when working with immutable data you don't need to copy it around, you can just pass it around via reference, and the data structure will support cheap "updates". You can see this in F# and Clojure where immutable maps are supported by tree structures, and operations like add/remove return a new reference without touching the original while being reasonably performant.
jandrewrogers 7y ago
In high-performance systems, software architectures have actually been moving toward non-shared mutability. Shared immutability tends to waste a performance-limiting resource (memory bandwidth).
- reitzensteinm 7y ago
  I'm a bit confused by your phrasing. Non-shared mutability makes perfect sense (and is not the thing I believe needs to go), but at some point you have to share the results of a computation. If not shared immutability, how is this done in the systems you're describing? I assume message passing, queues or similar?
  - jandrewrogers 7y ago
    Sorry, I wasn't clear. There are two common software architecture schools for scaling practical concurrency. The first is the copy-on-mutate style commonly used in functional programming paradigms. This is what I assumed was meant by "shared immutability". As you surmised, in the second model individual threads own all mutable state, and operations on that state are requested via message passing (usually SPSC queues within individual servers, which are scalable and extremely efficient). This makes all the code effectively single-threaded. The key technical element for these designs is that there often needs to be a mechanism to sporadically transfer ownership of state between threads to balance load, also arbitrated over the SPSC queues. This has a number of straightforward solutions. The second model has come into favor mostly because it is very memory-friendly, due to excellent natural cache locality and requiring minimal copying of state.
    - reitzensteinm 7y ago
      That's interesting to hear, thanks! My rant was only really aimed at shared mutable memory; passing a piece of it around with one owner at a time is totally fine. One writer, multiple readers has its uses too. I am a fan of persistent data structures and I think that as we keep slapping on cores they're going to be more appealing for general purpose computing, but they're certainly not one size fits all, and the performance tax is substantial.

arcticbull 7y ago

Am I wrong in thinking that a system comprised of entirely immutable memory doesn't even need a garbage collector? If you built such a system in Rust would not all memory just be deallocated once no longer utilized? The rust principal is (many readers XOR one writer) leads to fully static memory management. This is my point. We need to go back and re-think our language design principals keeping memory management in mind instead of pretending it's a solved problem. IMO you make a good case.

mafribe 7y ago
Am I wrong ... Yes. Unless your memory is infinite. Rust also automatically deallocates memory that is no longer used, so it's some kind of GC, but one where the point of deallocation is either statically determined (based on nesting of life-times) or dynamically (using reference-counting). The problem with static dealloc is that the compiler cannot always work out when memory becomes free and must make conservative approximations (see Rice's theorem [1]), the problem with ref-counting is circular data structures (and also the cost in space and time and synchronisation across threads of maintaining an index). [1] https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem

mafribe 7y ago

Au contraire, as memory, and hence workloads, get bigger, the cost of copying increases, and copying rather than sharing becomes ever more expensive. I just spoke with a physicist who told me that his current experiment produces 200 Gigabytes of data per second! Copying that amount of data around for immutability is inconceivable. Indeed the single biggest factor for performance for such workloads is minimising the amount of copying. Erlang-style shared-nothing is brilliant if you can afford it, but it's affordable only for small data.

reitzensteinm 7y ago
Erlang style immutable reference counted shared memory is not at all state of the art. Persistent data structures are common and effective. I have implemented several myself, to store and update trees that don't fit in main memory. If you're updating one byte of your physicist's (say) 1 petabyte dataset, it requires ten memory allocations (log[branch factor] of the size of the dataset). If you're updating the whole thing linearly, do consider that updating something in place or creating an updated copy is identical in terms of performance; a storage device doesn't care whether the bits streaming back are overwriting the same locations or new ones. Though of course you end up with both copies at the end.
- mafribe 7y ago
  Are there high-performance matrix multiplication libraries, e.g. for fluid-dynamics simulations, that are implemented using persistent data structures?
  - deleted 7y ago
    [deleted]
  - reitzensteinm 7y ago
    Are there any where multiple threads are mutating overlapping sections of memory? How exactly do you think a GPU matrix multiply violates my initial assertion?
McWobbleston 7y ago
Usually when working with immutable data you don't need to copy it around, you can just pass it around via reference, and the data structure will support cheap "updates". You can see this in F# and Clojure where immutable maps are supported by tree structures, and operations like add/remove return a new reference without touching the original while being reasonably performant.

jandrewrogers 7y ago

In high-performance systems, software architectures have actually been moving toward non-shared mutability. Shared immutability tends to waste a performance-limiting resource (memory bandwidth).

reitzensteinm 7y ago
I'm a bit confused by your phrasing. Non-shared mutability makes perfect sense (and is not the thing I believe needs to go), but at some point you have to share the results of a computation. If not shared immutability, how is this done in the systems you're describing? I assume message passing, queues or similar?
- jandrewrogers 7y ago
  Sorry, I wasn't clear. There are two common software architecture schools for scaling practical concurrency. The first is the copy-on-mutate style commonly used in functional programming paradigms. This is what I assumed was meant by "shared immutability". As you surmised, in the second model individual threads own all mutable state, and operations on that state are requested via message passing (usually SPSC queues within individual servers, which are scalable and extremely efficient). This makes all the code effectively single-threaded. The key technical element for these designs is that there often needs to be a mechanism to sporadically transfer ownership of state between threads to balance load, also arbitrated over the SPSC queues. This has a number of straightforward solutions. The second model has come into favor mostly because it is very memory-friendly, due to excellent natural cache locality and requiring minimal copying of state.
  - reitzensteinm 7y ago
    That's interesting to hear, thanks! My rant was only really aimed at shared mutable memory; passing a piece of it around with one owner at a time is totally fine. One writer, multiple readers has its uses too. I am a fan of persistent data structures and I think that as we keep slapping on cores they're going to be more appealing for general purpose computing, but they're certainly not one size fits all, and the performance tax is substantial.