Skip Unnecessary Allocations In Your Collections

Ryan James Spencer

Rust's standard library offers a lot of neat dynamically-sized data structures for use in Rust programs. They are quite performant, but the allocations they conduct behind the scenes to grow may add up and cause performance issues in your programs.

Rust intentionally avoids costly uses of new in a program by having the allocation be empty by default, including types outside ofstd::collections, too, such as String::new.

The backing store usually grows with a doubling strategy, and the growth tends to happen right as it is needed, as is the case for Vec, see here and here for references to code as of this writing, but it may not always be the same story for other collections. I strongly encourage looking at the actual source code for the standard library when you are curious. Rust uses the language of capacity to designate the total possible amount of memory the backing store has room for and length to designate the total number of actual values in the data structure.

One of the core tenants of optimization is to avoid doing needless work. Putting data on the heap isn't necessarily expensive if you've already paid the price upfront for allocating it. Doing work in this way is called amortization. Imagine I have to store 4096 things in a vector. By default, the vector grows in powers of two with capacities of 0, 2, 4, 8, 16, 32, 64, and so on, in that order. That's already six allocations I've mentioned and not done reaching the final size. Avoiding unnecessary work is at the heart of performance optimization and these are intermediate steps are unnecessary!

A fantastic part of the Rust standard library collections is they tend to have common interfaces precisely for this sort of thing! You can avoid these allocations by usingwith_capacity if you know the value or upper bound you need initially. If you already have the data structure hanging around, you can also call reserve to request additional capacity to avoid needless allocation.

The way allocation happens with the doubling strategy is a form of amortization. As the collection grows in powers of two, the number of calls reduces, but the cost of growing the vector increases. Each time the vector grows, it will copy all the values over to a new backing store. In general, any time you think you can use a big chunk of data up front, you should allocate the full capacity, but if the exact amount you are requesting is unknown, isn't that a bit wasteful? An alternative strategy where the amount may only be partly known is to request a large chunk of memory and size it down either with shrink_to_fit or resize, but be careful with resize as it may truncate the collection if you aren't careful!

It is always best to get empirical data on how to reasonably size the collection upfront or while the program is running. If we instead take a chaotic approach to allocations we may do more harm than good. At the end of the day, the reason why these data structures grow on their own is to avoid thinking about them until performance is an issue and we reveal that spending our time on this is important through profiling.