A collection of object pools, for more efficient dynamic memory allocation.
This library provides 2 data structures to deal with dynamic memory allocation more efficiently :
- An object pool for single-threaded contexts
- An object pool for multi-threaded contexts
This library is available on crates.io
An Object Pool is a structure maintaining a collection of reusable objects.
When the pool is instantiated, a given number of objects are allocated on the Heap. Those objects manage an usage-state, this state have the value not used when the objects are instantiated.
When the user want to create a new object, he asks the pool for one. The pool will return the first not used object in its pool, and set the object as used.
When the object is dropped, the object return to its original state and is set to not used.
It can be faster: Allocations have been made in advance, when the user create objects with an object pool, a pointer to a pre-allocated non-used object is returned. When an object is dropped, the pointer is dropped and the object (which is not dropped) goes back to a non-used state.
It prevents memory fragmentation: We allocate a big chunk of memory full of ready-to-use objects. Even though the user is creating and dropping/destroying objects, no allocations and frees are occurring.
Time-constrained programs, like video-games, need to be as fast as possible.
A video-game, in its game loop, needs to :
- Read the player's input at frame n.
- Update the world state (AI, physics, object states, sounds...) at frame n.
- Draw the scene at frame n in the back buffer.
- Swap the back buffer (frame n) with the current buffer (frame n - 1).
In order to display 60 frames per second, this loop needs to be completed in 16 milliseconds (0.016 seconds).
One possible bottleneck is dynamic memory allocation (allocation on the heap). Even though Rust sometimes uses jemalloc, a fast general-purpose memory allocator (see this RFC), heap memory allocation can be a slow operation.
Moreover, memory can become fragmented over time :
Even though we have enough total memory, this memory is not contiguous so we can't
allocate anything.
Custom memory allocators can help with both problems.
We can distinguish 3 types of memory allocation :
-
Persistent memory allocation: data is allocated when the program is started, and freed when the program is shut down. The arena crate is perfect for that.
-
Dynamic memory allocation: data is allocated and freed during the lifetime of the program, but we can't predict when this data is allocated and freed. This library deals with this type of memory allocation
-
One-Frame memory allocation: Data is allocated, consumed and freed in a loop. stack-based allocators can be a good solution to this type of allocation.
Game Engine Architecture, chapter 5.2
Stack Overflow answer about memory fragmentation
Stack Overflow answer about stack-based allocators
SwedishCoding blogpost about custom memory allocators
Game Programming Patterns, Chapter 19, about Object Pools
Wikipedia article about Object Pools
Wikipedia article about free lists
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.