3 ms·
> Really? I mean like pretty much every instruction has separate source and destination addresses/registers, memory caches obviously complicate things, but it s
by 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 agoGoing off-topic, but note: C++11 moves are non-destructive.
- dragontamer 6y agounique_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 agounique_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 agoI 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")