A Novel Dynamically Truncating Object Pool for Game Loops and Other Use Cases in Rust

Abstract

Rust programming language, introduced in 2012, presents a new model of memory management called ownership: each value has an exclusive owner, and values are automatically destroyed when their owner leaves the scope. As adherence to ownership rules is checked during compile-time static analysis, runtime memory safety is guaranteed without sacrificing performance to garbage collection. However, the strict rules of ownership and the rigid memory hierarchy they introduce complicate certain things. Cross-iteration – comparing every element in a collection to every other element in the same collection, possibly mutating their data in the process – is not trivial to implement in Rust. This limitation has made implementing video game loops in Rust generally a complex and difficult task.

This thesis presents a novel collection type, StableList, a simple-to-use and efficient data structure that supports mutable cross-iteration and dynamic truncation, implemented in safe Rust. This thesis introduces its public interface, explains its internal workings, and analyzes its performance against other Rust collections with similar features and purpose through collected benchmark data. As the research data shows, StableList is at least mediocre in its running time for all the essential operations, in the superior subgrouping for cases with highly varying numbers of short-lived elements, and unrivaled for mutable cross-iteration. StableList is a potent data structure for its purpose of powering video game loops and is highly viable for many other use cases, including worker, thread and connection pools.