Menu
How much am I losing in terms of performance when using a vector versus an array in Rust?
By performance I mean: speed of element access or speed of iteration.
806
A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.
Arrays are faster with less functionality, and vectors are slower with more functionality. (Of course, Rust is always very fast so vectors are not slow, just slower than arrays.) The type is written Vec , and you can also just call it a "vec".
Vector is faster for insertion and deletion of elements at the end of the container. Set is faster for insertion and deletion of elements at the middle of the container.
An array is faster and that is because ArrayList uses a fixed amount of array. However when you add an element to the ArrayList and it overflows. It creates a new Array and copies every element from the old one to the new one.
They both store data in a linear contiguous array where accessing or iterating is both an O(1) operation so there's no difference in performance. The only case when vector is slower is probably for some small lists because array is stored on stack in the current stack frame, hence their data is highly probably already loaded to the CPU cache. Vector OTOH stores data on the heap so data will not be available in cache before they're first accessed
Vector also has one more level of redirection because you need to load the address of the array first so the first memory access may also be slower, but that's just negligible
The other time when vector is much worse is when you use a vector of vector vs a multidimensional array because each vector is allocated separately and lies all around memory which is not good for caching. See Access time of vec vs array
See also Difference between array vs. vec for memory and cpu usage
50
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
