Week 8: Rust Performance

When working with Rust during my 10-week research project, I was more than impressed with Rust in the performance department. From compilation time to run-time, Rust just seemed to keep up.

Garbage Collection

Because of Rust’s guaranteed memory safety, ownership model, and robust checks from the compiler, the language has no need for a garbage collector.

A garbage collector is a program that automatically frees up memory that is no longer being used by a program. It identifies and removes objects that are no longer needed, allowing the program to reclaim memory that can be used for other purposes. Garbage collection is used in Java and Python to manage memory automatically, but it can come with performance costs; ever so often, the program must be paused to reclaim memory that is not in use. Especially in a graphics context, that small delay may be unacceptable. If we are rendering frames to create a smooth view for the user and a garbage collector decides to pause even for a few milliseconds, our app may hitch around, which is obnoxious. Even if the garbage collector is in a different thread, this adds more overhead to the consumers CPU and uses more energy.

Search

In the context of prof-viewer, an expensive computation that I was afraid would cause bottlenecks was search.

Every time a user adds a character to the search box, I have to recompute the entire search state of the app. While it would be acceptable to have a small delay in the search and add a smaller loader / skeleton while the computation and search was being performed, this wouldn’t be as simple to create as if we were in event-driven model. I wanted to see what Rust was capable of so I decided to shoot for a 60+ FPS target even while searching through 100,000+ elements in state. That’s 6 million string searches a second! I ended up implementing search using the Aho-Corasick algorithm to build a finite-state machine based on the patterns that we wanted to match (i.e. each word the user was searching for).

This state machine would then be applied on each of the metadata strings for each task, detecting the number of matches in the state-machine. This allows us to run each title search in O(n) time. With this algorithm, Rust was able to provide a near instantaneous search for an entire profile with a large number of tasks on a single thread, all while rendering the GUI too. Mighty impressive!