5 ms·

I know this subject quite well and I will later publish a detailed article. The real run-time cost of memory management done well in a modern game engine writt

I know this subject quite well and I will later publish a detailed article. The real run-time cost of memory management done well in a modern game engine written without OOP features is extremely low. We usually use a few very simple specialized memory allocators, you'd probably be surprised by how simple memory management can be. The trick is to not use the same allocator when the lifetime is different. Some resources are allocated once and basically never freed. Some resources are allocated per level and freed all at once at the end. Some resources are allocated during a frame and freed all at once when a new frame starts. And lastly, a few resources are allocated and freed randomly, and here the cost of fragmentation is manageable because we're talking about a few small chunks (like network packets)

kjeetgill 7y ago
Exactly this. Writing a basic allocator can give you a significant bang for your buck. Hard-coding an application specific arena allocator is trivial. The harder part is being diligent enough to avoid use after free/dangling pointers. I'm a huge Java nerd. I love me some G1/Shenandoah/ZGC/Zing goodness. But once you're writing a program that to the point that you're tuning memory latency in many games anyway, baking in your application's generational hypothesis is pretty easy. Even in Java services you'll often want to pool objects that have odd lifetimes.
zemo 7y ago
as an example point, the Go garbage collector clears heaps of 18gb in sub-millisecond latencies. If I'm understanding the problem at hand (maybe I'm not!), given an engine running at a target framerate of 144 frames per second, you're working with a latency budget of about 7ms per frame. Do you always use all 7ms, or do you sometimes sleep or spin until the next frame to await user input? We can also look at it from the other direction: if your engine is adjusting its framerate dynamically based on the time it takes to process each frame, and you can do the entire work for a frame in 10ms, does that give you a target of 100 fps? If you tack on another half millisecond to run a GC pause, would your target framerate just be 95 fps? And what do you do when the set of assets to be displayed isn't deterministic? E.g., an open world game with no loading times, or a game with user-defined assets?
- stephc_int13 7y ago
  There is no general answer to this question. Frame latency, timing and synchronization is a difficult subject. Some games are double or triple buffered. Rendering is not always running at the same frequency as the game update. The game update is sometimes fixed, but not always. I've had very awful experience with GC in the past, on Android, the game code was full C/C++ with a bit of Java to talk to the system APIs, I had to use the camera stream. At the time (2010) Android was still a hot mess full of badly over engineered code. The Camera API was simply triggering a garbage collect about every 3-4 frames, it locked the camera stream for 100ms (not nanoseconds, milliseconds!) The Android port of this game was cancelled because of that, it was simply impossible to disable the "feature".
  - weberc2 7y ago
    You didn't have a bad experience with GC in the past, you had a bad experience with a single GC implementation, one which was almost certainly optimized for throughput and not latency and in a language that pushes you toward GC pressure by default. :)
    - stephc_int13 7y ago
      This is an example. I never worked with Unity myself but I worked with people using Unity as their game engine, they all had problems with stuttering caused by the GC at some point. You can try to search Unity forums about this subject, you'll find hundreds or thousands of topics. What really bothers me with GC is that it solves a pain I never felt, and creates a lot of problems that are usually more difficult to solve. This is a typical case of the cure being (much) worse than the illness.
      - weberc2 7y ago
        What is Unity’s STW time? Is it optimized for latency? If not, you’re using the wrong collector. The pain point it solves is time spent debugging memory issues and generally a slower pace of development, but of course if you’re using a collector optimized for throughout, you’ll have a bad time. Further, a low-latency GC will pay off more for people who haven’t been using C or C++ for 10 years than those who have.
fluffything 7y ago
+1. We have a large Rust code base, and we forbid Vec and the other collections. Instead, we have different types of global arenas, bump allocators, etc. that you can use. These all pre-allocate memory once at start up, and... that's it. When you have well defined allocation patterns, allocating a new "object" is just a "last += 1;` and once you are done you deallocate thousands of objects by just doing `last -= size();`. That's ~0.3 nanoseconds per allocation, and 0.x nano-seconds to "free" a lot of memory. For comparison, using jemalloc instead puts you at 15-25 ns per allocation and per deallocation, with "spikes" that go up to 200ns depending on size and alignment requirements. So we are talking here a 100-1000x improvement, and very often the improvement is larger because these custom allocators are more predictable, smaller, etc. than a general purpose malloc, so you get better branch prediction, less I-cache misses, etc.
- gpm 7y ago
  Is this code base open source? Or do you know of open source rust code like it?
- Matthias247 7y ago
  Do you use any public available crate for those allocators? Would love to take a look. I'm currently trying to write a library for no-std which requires something like that. I currently have written a pool of bump allocators. For each transaction you grab an allocator from the pool, allocate as many objects from it as necessary, and then everything gets freed back to the pool. However it's a bit hacky right now, so I'm wondering whether there is already something better out there.
  - minxomat 7y ago
    Seems like lifeguard could solve this: https://github.com/zslayton/lifeguard https://github.com/zslayton/lifeguard
  - fluffything 7y ago
    > Do you use any public available crate for those allocators? Not really, our bump allocator is ~50 LOC, it just allocates a `Box<[u8]>` with a fixed size on initialization, and stores the index of the currently used memory, and that's it. We then have a `BumpVec<T>` type that uses this allocator (`ptr`, `len`, `cap`). This type has a fixed-capacity, it cannot be moved or cloned, etc. so it ends up being much simpler than `Vec`.
markus_zhang 7y ago
This sounds very interesting. Please do write an article abput the topic! Seems like you would introduce specific allocators for maybe different games.
debatem1 7y ago
It would be interesting to see what the impact of adding hints about allocation lifetime to malloc would be. I have to suspect someone has already written that paper and I just don't know the terminology to look for it.
- spc476 7y ago
  Given the problems people have with Rust and the borrow checker, I would guess that people will not accurately predict how long an allocation will live (it's a similar issue with profiling---programmers usually guess wrong about where the time is being spent).
- Gibbon1 7y ago
  I'm reminded of an ancient 8031 C compiler. It didn't support reentrancy. Which seems like a bad thing until you realize that the program could be analyzed as a acyclic graph. The compiler then statically allocated and packed variables based on the call tree. Programs used tiny amounts of memory.
talkingtab 7y ago
I buy this - specialized memory allocators, after all I've used mbufs. So which languages would be good or recommended for coercing types when using memory allocators?
- alexhutcheson 7y ago
  C++ or Rust
yellowapple 7y ago
This is exactly what's continually drawing me to Zig for this sort of thing. Any function that requires memory allocation has to either create a new allocator for itself or explicitly accept an existing one as an argument, which seems to make it a lot easier/clearer to manage multiple allocators for this exact use case.
voldacar 7y ago
> a modern game engine written without OOP features Is there a particular codebase you are thinking of here?
big_chungus 7y ago
+1 for that article, especially the part about OOP downsides at scale and batch memory allocation. Love to see more!

kjeetgill 7y ago

Exactly this. Writing a basic allocator can give you a significant bang for your buck. Hard-coding an application specific arena allocator is trivial. The harder part is being diligent enough to avoid use after free/dangling pointers. I'm a huge Java nerd. I love me some G1/Shenandoah/ZGC/Zing goodness. But once you're writing a program that to the point that you're tuning memory latency in many games anyway, baking in your application's generational hypothesis is pretty easy. Even in Java services you'll often want to pool objects that have odd lifetimes.

zemo 7y ago

as an example point, the Go garbage collector clears heaps of 18gb in sub-millisecond latencies. If I'm understanding the problem at hand (maybe I'm not!), given an engine running at a target framerate of 144 frames per second, you're working with a latency budget of about 7ms per frame. Do you always use all 7ms, or do you sometimes sleep or spin until the next frame to await user input? We can also look at it from the other direction: if your engine is adjusting its framerate dynamically based on the time it takes to process each frame, and you can do the entire work for a frame in 10ms, does that give you a target of 100 fps? If you tack on another half millisecond to run a GC pause, would your target framerate just be 95 fps? And what do you do when the set of assets to be displayed isn't deterministic? E.g., an open world game with no loading times, or a game with user-defined assets?

stephc_int13 7y ago
There is no general answer to this question. Frame latency, timing and synchronization is a difficult subject. Some games are double or triple buffered. Rendering is not always running at the same frequency as the game update. The game update is sometimes fixed, but not always. I've had very awful experience with GC in the past, on Android, the game code was full C/C++ with a bit of Java to talk to the system APIs, I had to use the camera stream. At the time (2010) Android was still a hot mess full of badly over engineered code. The Camera API was simply triggering a garbage collect about every 3-4 frames, it locked the camera stream for 100ms (not nanoseconds, milliseconds!) The Android port of this game was cancelled because of that, it was simply impossible to disable the "feature".
- weberc2 7y ago
  You didn't have a bad experience with GC in the past, you had a bad experience with a single GC implementation, one which was almost certainly optimized for throughput and not latency and in a language that pushes you toward GC pressure by default. :)
  - stephc_int13 7y ago
    This is an example. I never worked with Unity myself but I worked with people using Unity as their game engine, they all had problems with stuttering caused by the GC at some point. You can try to search Unity forums about this subject, you'll find hundreds or thousands of topics. What really bothers me with GC is that it solves a pain I never felt, and creates a lot of problems that are usually more difficult to solve. This is a typical case of the cure being (much) worse than the illness.
    - weberc2 7y ago
      What is Unity’s STW time? Is it optimized for latency? If not, you’re using the wrong collector. The pain point it solves is time spent debugging memory issues and generally a slower pace of development, but of course if you’re using a collector optimized for throughout, you’ll have a bad time. Further, a low-latency GC will pay off more for people who haven’t been using C or C++ for 10 years than those who have.

fluffything 7y ago

+1. We have a large Rust code base, and we forbid Vec and the other collections. Instead, we have different types of global arenas, bump allocators, etc. that you can use. These all pre-allocate memory once at start up, and... that's it. When you have well defined allocation patterns, allocating a new "object" is just a "last += 1;` and once you are done you deallocate thousands of objects by just doing `last -= size();`. That's ~0.3 nanoseconds per allocation, and 0.x nano-seconds to "free" a lot of memory. For comparison, using jemalloc instead puts you at 15-25 ns per allocation and per deallocation, with "spikes" that go up to 200ns depending on size and alignment requirements. So we are talking here a 100-1000x improvement, and very often the improvement is larger because these custom allocators are more predictable, smaller, etc. than a general purpose malloc, so you get better branch prediction, less I-cache misses, etc.

gpm 7y ago
Is this code base open source? Or do you know of open source rust code like it?
Matthias247 7y ago
Do you use any public available crate for those allocators? Would love to take a look. I'm currently trying to write a library for no-std which requires something like that. I currently have written a pool of bump allocators. For each transaction you grab an allocator from the pool, allocate as many objects from it as necessary, and then everything gets freed back to the pool. However it's a bit hacky right now, so I'm wondering whether there is already something better out there.
- minxomat 7y ago
  Seems like lifeguard could solve this: https://github.com/zslayton/lifeguard https://github.com/zslayton/lifeguard
- fluffything 7y ago
  > Do you use any public available crate for those allocators? Not really, our bump allocator is ~50 LOC, it just allocates a `Box<[u8]>` with a fixed size on initialization, and stores the index of the currently used memory, and that's it. We then have a `BumpVec<T>` type that uses this allocator (`ptr`, `len`, `cap`). This type has a fixed-capacity, it cannot be moved or cloned, etc. so it ends up being much simpler than `Vec`.

markus_zhang 7y ago

This sounds very interesting. Please do write an article abput the topic! Seems like you would introduce specific allocators for maybe different games.

debatem1 7y ago

It would be interesting to see what the impact of adding hints about allocation lifetime to malloc would be. I have to suspect someone has already written that paper and I just don't know the terminology to look for it.

spc476 7y ago
Given the problems people have with Rust and the borrow checker, I would guess that people will not accurately predict how long an allocation will live (it's a similar issue with profiling---programmers usually guess wrong about where the time is being spent).
Gibbon1 7y ago
I'm reminded of an ancient 8031 C compiler. It didn't support reentrancy. Which seems like a bad thing until you realize that the program could be analyzed as a acyclic graph. The compiler then statically allocated and packed variables based on the call tree. Programs used tiny amounts of memory.

talkingtab 7y ago

I buy this - specialized memory allocators, after all I've used mbufs. So which languages would be good or recommended for coercing types when using memory allocators?

alexhutcheson 7y ago
C++ or Rust

yellowapple 7y ago

This is exactly what's continually drawing me to Zig for this sort of thing. Any function that requires memory allocation has to either create a new allocator for itself or explicitly accept an existing one as an argument, which seems to make it a lot easier/clearer to manage multiple allocators for this exact use case.

voldacar 7y ago

> a modern game engine written without OOP features Is there a particular codebase you are thinking of here?

big_chungus 7y ago

+1 for that article, especially the part about OOP downsides at scale and batch memory allocation. Love to see more!