4 ms·
> DO NOT EVER MUTATE STATE! This is counterproductive. Mutating state is by far, the most efficient operation on the computer. Copying state means (usually) c
by dragontamer 6y ago
> DO NOT EVER MUTATE STATE!
This is counterproductive.
Mutating state is by far, the most efficient operation on the computer. Copying state means (usually) calling the memory allocator, which (usually) must be done in a sequential manner. There are optimizations to allow memory-allocation to occur in parallel, but... things start to get inefficient (use of thread-local storage, which makes many pointer-indirections, etc. etc.).
-------
Why do people program parallel code, despite its overwhelming complexity?
Simple: to be faster. That's it. Its an optimization, arguably premature, but the programmer reaching for the "parallel" button is going for optimization for a reason.
------
Sequential code with state-mutations could very well be more efficient than parallel code with tons of unnecessary copies. Registers are fast, L1 cache is fast, etc. etc. Doing an operation, then undoing it (entirely inside of register space) is so incredibly fast, it will make your head spin.
-------
1: Write code.
2. If code isn't fast enough, single-thread optimize it. This usually means mutating state in an intelligent manner.
3. If code is STILL not fast enough, multithread it. You make a copy of the state, and then have multiple threads (each with their own copy of the state) doing... whatever you're trying to do.
- Arelius 6y ago> Mutating state is by far, the most efficient operation on the computer. Really? I mean like pretty much every instruction has separate source and destination addresses/registers, memory caches obviously complicate things, but it seems that processing data from one location to another is the most efficient operation. > Copying state means (usually) calling the memory allocator Sure, I guess if the main conception of moving data around involves not really knowing where it needs to go, and having to figure that out, that's somewhat true. But there are many ways to structure computation that minimizes or avoids allocator usage. > unnecessary copies I think this is the issue, if you have to copy first then do in place mutations, of course it'll be slower, but you can instead structure your entire computation to process your data from one location to another, then all your points about registers, and L1 cache being fast, holds true while still being able to handle immutable data
- dragontamer 6y ago> Really? I mean like pretty much every instruction has separate source and destination addresses/registers, memory caches obviously complicate things, but it seems that processing data from one location to another is the most efficient operation. I can't think of any algorithm where copying is faster than mutating. * Chess Bitboards: Make / Unmake is a methodology for a reason. * Mergesort: In-place mergesort is far faster than copy-merge sort. Its much harder to write in-place mergesort, but it really makes a big difference. * Quicksort: In-place quicksort is faster than copy quicksort. Every "pure functional" recursive / copy quicksort has been... subpar... in my experience. * C++11 created a "destructive move", the entire R-value references system, because of the hugely more efficient concept of destructive / mutating moves. Destroying the old data while copying the data to a new location (aka: std::move) is far more efficient than making a safe copy (aka: copy-constructor). ------- Side note: The SIMD "Mergepath" Mergesort is absolutely brilliant. It uses absolutely no mutexes (and only uses thread-barriers) to guarantee that all writes are independent and correct. Furthermore, "Mergepath" mergesort parallelizes maximally (one-element per processor), while retaining O(n * log(n)) sort speeds. Because thread-barriers are no-ops on a SIMD computer (like AVX512), the thread-barriers in the MergePath concept are maximally efficient. :-) ------- What algorithms are you thinking of where copying is faster than mutating? At best, a copy ties mutation in speed. In a huge number of applications, mutation (aka: std::move) just faster. But std::move cannot be done across multiple threads: that's innately thread-unsafe and must be synchronized (at least for typical objects). --------------- Or maybe the above is too abstract? Lets go down to a very simple, but specific, algorithm. The Fisher-Yates (aka: Knuth) Shuffle. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle As far as I know, there is no copy-based algorithm that can beat the Knuth Shuffle's O(n) computation complexity. It is extremely difficult to write a O(n) speed shuffle without mutating the array in place. The fastest "copy" methodologies for the Shuffle problem I've seen involved generating a random number for each location, then copy-sorting the results: O (n * log(n)), which is asymptotically more complex than the Fisher Yates shuffle (and therefore: work-inefficient. If you parallelize to O(n*log(n)), there will be a size where the Fisher Yates shuffle is faster).
- 6y ago