I am trying to use Vec::sort_unstable_by_key periodically. From my understanding, it is sorting-in-place; So it moves elements within the vector.
I wonder:
If the size of the element is large, will it becomes expensive? In that case, will wrapping large data in pointers like Rc and then store pointers in the vector helps?
Copying memory takes, very rougly estimated, around 0.04 nanoseconds per byte. Source.
A full cache miss to RAM takes around 65 nanoseconds. Source.
Both of these are very rough estimates but should give you an idea of the difference in order of magnitudes.
If you use indirection via a Box or a Rc, swapping will become very fast, but actually checking the contents to compare them will require fetching a distant area from memory which which is more likely to miss the cache. Also you need to check the data much more often than you swap objects to sort an array.
Thus the data needs to be extremely large before using a Box or Rc becomes worth it. I generally start considering using indirection if the object is more than a few kilobytes in size. Optimization is very complex and the only way to really know which is faster for your specific use case is to measure.