5 ms·

> 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

> 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).
- mehrdadn 6y ago
  Going off-topic, but note: C++11 moves are non-destructive.
  - dragontamer 6y ago
    unique_ptr<Blah> foo = make_unique(...); unique_ptr<Blah> bar = std::move(foo); // foo is now effectively destroyed as part of the move; foo->something(); // Will error, probably seg-fault. Foo is now "empty" The value foo used to point at is preserved. But foo itself was destroyed from the std::move(foo); The foo->something() is almost certainly a null-pointer exception or seg-fault in any sane implementation of C++11. --------- Example 2: int main(){ vector<int> foo = {1, 2, 3, 4, 5}; vector<int> bar = std::move(foo); cout << foo.size() << endl; cout << bar.size() << endl; return 0; } Notice: foo.size() is 0. The foo-vector was DESTROYED by the std::move(foo);.
    - mehrdadn 6y ago
      unique_ptr's destructor happens to do nothing in a moved-from state. The fact that some types behave this way does not mean moves are destructive. They're still non-destructive. Indeed you're still supposed to call the destructor after a move, and the destructor very well _could_ do something in general. It's just that it doesn't happen to make any difference for typical implementations of some types like unique_ptr. In fact there are people who have wanted destructive moves in C++, because they found the current non-destructive moves inadequate, but I don't believe the feature has ever been added. Look up destructive moves to find discussions on the issue.
      - dragontamer 6y ago
        I guess I'm being imprecise with terminology then. It seems like Rust has a concept called destructive move, which is not what I'm talking about. In any case, the "foo" vector, and "foo" unique_ptr are _mutilated_ as part of the std::move operation. (Since the word "destroyed" seems to have been taken by the Rust community, I can't use that word anymore... hopefully no other community has taken the word "mutilated")

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

mehrdadn 6y ago
Going off-topic, but note: C++11 moves are non-destructive.
- dragontamer 6y ago
  unique_ptr<Blah> foo = make_unique(...); unique_ptr<Blah> bar = std::move(foo); // foo is now effectively destroyed as part of the move; foo->something(); // Will error, probably seg-fault. Foo is now "empty" The value foo used to point at is preserved. But foo itself was destroyed from the std::move(foo); The foo->something() is almost certainly a null-pointer exception or seg-fault in any sane implementation of C++11. --------- Example 2: int main(){ vector<int> foo = {1, 2, 3, 4, 5}; vector<int> bar = std::move(foo); cout << foo.size() << endl; cout << bar.size() << endl; return 0; } Notice: foo.size() is 0. The foo-vector was DESTROYED by the std::move(foo);.
  - mehrdadn 6y ago
    unique_ptr's destructor happens to do nothing in a moved-from state. The fact that some types behave this way does not mean moves are destructive. They're still non-destructive. Indeed you're still supposed to call the destructor after a move, and the destructor very well _could_ do something in general. It's just that it doesn't happen to make any difference for typical implementations of some types like unique_ptr. In fact there are people who have wanted destructive moves in C++, because they found the current non-destructive moves inadequate, but I don't believe the feature has ever been added. Look up destructive moves to find discussions on the issue.
    - dragontamer 6y ago
      I guess I'm being imprecise with terminology then. It seems like Rust has a concept called destructive move, which is not what I'm talking about. In any case, the "foo" vector, and "foo" unique_ptr are _mutilated_ as part of the std::move operation. (Since the word "destroyed" seems to have been taken by the Rust community, I can't use that word anymore... hopefully no other community has taken the word "mutilated")