5 ms·

Benchmarking Malloc with Doom 3

66 points by zdw 4y ago

smat 4y ago
Not sure what this empirical analysis adds to answer the initial question. Sure, modern computers are fast and modern operating systems are designed to reduce latency. At the same time the “best practices” of not using mutexes and malloc on real-time threads are there for a reason: They potentially trigger a system call, which will add quite some latency (as the measurements show). Because real-time is all about deterministic latency, this is undesired.
- sitkack 4y ago
  > Not sure what this empirical analysis adds to answer the initial question. Why would you discourage someone from doing this? You thinking you already knew the answer doesn't help the OP at all.
  - smat 4y ago
    I did not mean to discourage people from making their own evaluations. Maybe I did not word it correctly. The article starts with questioning best practices for implementing real-time processing threads. The statistical analysis presented in the article is based on a single workload and a single machine, which in my opinion does not help to answer this question.
    - sitkack 4y ago
      Oh, ok, I understand. I agree that the empirical technique could be better, but the experiment is neat even if slightly flawed. If the author wanted to show how much memory allocation could be done in an audio thread, they should construct an audio workload where they can tune the allocation and memory access patterns and then determine exactly how much is too much. But really that was the motivation, then as they admit in the start, they got nerd sniped and started measuring DOOM memory allocations (also fun). We should ignore the original motivation unless one uses a completely different experiment to justify something that wasn't tested.
- deleted 4y ago
  [deleted]
abainbridge 4y ago
"My first attempt at a benchmark involved allocating and freeing blocks of random size. Twitter friends correctly scolded me and said that's not good enough. I need real data with real allocation patterns and sizes." "The goal is to create a "journal" of memory operations. It should record malloc and free operations with their inputs and outputs. Then the journal can be replayed with different allocators to compare performance." I don't think that is sufficient either. You need to mix the malloc/free with the other work, because the other work knocks your allocator data structures out of cache and pollutes your TLB and branch predictor. And loads up the dram interface (eg by the gpu fetching data from it). Etc etc.
- forrestthewoods 4y ago
  Comments like this are not insightful or helpful. > I don't think that is sufficient either. Sounds like you should write a blog post that compares the two methods to see if it's an acceptable approximation or not. :)
- sitkack 4y ago
  I would have measured the time directly inside of the Doom allocator and the OP could produce the same charts directly from the measured data without replaying the allocation log. And IF I were going to collect that data, I'd grab the call stack as well to see where the allocations were coming from. There might be a chance to retro fit an arena allocator, but would think Carmack code is already probably optimal? Yes it is, for the reason we can even have this discussion about it. The other change I would make to the experiment, is to have the traces be taken from a timedemo and not via regular gameplay so that hypothesis can be tested. At the very least, one could precisely time the impact of instrumentation.
  - thxg 4y ago
    > I would have measured the time directly inside of the Doom allocator Exactly! The author already has all the infra necessary (rdtsc for each call). Measuring time inside the game would be more accurate and simpler. Why did the author do things this way? I must be missing something. (By the way, the author even seems to know about this issue since they added code that simulates using the allocated blocks (touching one byte for every allocated 4k), but that does not feel like it's nearly enough.) > grab the call stack as well Maybe this part could be done with no code with VTune / Linux perf? Sure, those only gather stochastic measurements (so not ideal for the original latency measurement). But to get a rough idea of where the costly allocations come from, it could be an easy way.
trasz 4y ago
>The goal is to create a "journal" of memory operations. Hm, I wrote something like this once - https://github.com/CTSRD-CHERI/cmt/blob/master/README.md https://github.com/CTSRD-CHERI/cmt/blob/master/README.md
dwdz 4y ago
Please don't use Jet color scheme. Matplotlib uses excellent viridis by default. There's no reason not to use it. [0][1] [0] https://stats.stackexchange.com/questions/223315/why-use-colormap-viridis-over-jet https://stats.stackexchange.com/questions/223315/why-use-col... [1] https://www.youtube.com/watch?v=xAoljeRJ3lU https://www.youtube.com/watch?v=xAoljeRJ3lU
- forrestthewoods 4y ago
  It uses nipy_spectral.
nemetroid 4y ago
Eleven million mallocs over seven minutes of gameplay at 60 fps comes out at an average of 437 mallocs per frame (this includes "load level" and "die and reload", so the average during gameplay is likely even lower). The author writes "Doom 3 hits 60fps in debug and calls malloc all over the place.", but to me those stats suggest malloc-averse code.
fisherjeff 4y ago
I wonder how many of the longer execution times are just thread pre-emptions?
- jeffbee 4y ago
  The fact that all the allocators have the same tail performance suggests the measurement is polluted by something like thread preemption or processor power state transitions.
  - forrestthewoods 4y ago
    This is not correct. TLSF has a worst-case of about 30 microseconds. Second best is 200 microseconds, which is shared by 3 allocators (HeapAlloc, dlmalloc, and rpmalloc). Which implies something inside the OS call is occasionally very slow. TLSF is the only tested allocator that uses a pre-allocated pool and stays in user space. And it has noticeably better tail performance. https://www.forrestthewoods.com/blog/benchmarking-malloc-with-doom3/assets/img/percentile_alloc_zoomed_large.png https://www.forrestthewoods.com/blog/benchmarking-malloc-wit...
tomovo 4y ago
See also - Arma 3 benchmarks comparing different malloc implementations here: https://www.youtube.com/watch?v=kNmeMxEel4M https://www.youtube.com/watch?v=kNmeMxEel4M
Syzygies 4y ago
Back in the 1980's I co-wrote a computer algebra system, that ran for example on many colleagues' first computer: The first Macintosh. Resources were scarce, everything mattered. Malloc attempts to work acceptably well under diverse scenarios. Specific programs such as ours can adopt simpler memory disciplines, supported by an interface with malloc. Almost all of our memory needs could be served by pools of fixed-size slugs of memory. Each pool experienced considerable churn and reuse, but the total memory needed by each pool was unimodal, growing to a peak then subsiding until the pool was no longer needed. We chose a universal fixed-size block to be served by malloc. We kept these blocks on a master stack, to assign to pools as needed. We kept the slugs in each pool on stacks, to reuse as needed. Closing a pool returned its blocks to the master stack. There's nothing novel here; this is about as dumb a protocol as one can imagine, and correspondingly faster than anything else we tried. I still believe the lesson today: One's core algorithms need to be crafted to cooperate with the fastest memory protocols. The doctor can't do everything without the patient's cooperation. For example, I believe that the approach taken by Rust will ascend as we better learn how to work with it.
- throwawaymaths 4y ago
  You mean zig, right? Zig is allocator-agnostic. It's hard (but not impossible) to implement type-specific allocators in Rust, and if you want the same type to take context-dependent allocator types, or context-dependent allocator instances, it's much , much harder, if I'm not mistaken. And the default way of programming Rust doesn't really tolerate allocation failures (which you might run up against with fixed memory slabs)
Shadonototra 4y ago
the biggest enemy is non-predictable performance, otherwise you get visible stutters but nowadays nobody gives a shit anymore since most games are made using unreal/unity wich ship with a shitty GC generation of developers who think pumping more hardware will fix all their problems, little do they know wich is why most games using these engines have troubles porting their game to resource constrained devices like smartphones/switch frame budget for 120fps is just 8ms
AtlasBarfed 4y ago
How do people log hyperfast data like this without impacting the thing you're measuring? ... preallocate storage? (is this actual, real irony?)
ultrahax 4y ago
Game dev here ( with significant experience in engines with significant idTech ancestry ) - the goal is, generally, to avoid mallocs _during_ a frame - you alloc everything you need during startup. I'm surprised there's that much ongoing allocation.
SleepyMyroslav 4y ago
i have anecdata of regular free taking worst case 30ms circa 2016. Of course, platform/compiler/etc should not be named but i think it gives a picture how much work can heap management require under load.

66 points by zdw 4y ago

smat 4y ago

Not sure what this empirical analysis adds to answer the initial question. Sure, modern computers are fast and modern operating systems are designed to reduce latency. At the same time the “best practices” of not using mutexes and malloc on real-time threads are there for a reason: They potentially trigger a system call, which will add quite some latency (as the measurements show). Because real-time is all about deterministic latency, this is undesired.

sitkack 4y ago
> Not sure what this empirical analysis adds to answer the initial question. Why would you discourage someone from doing this? You thinking you already knew the answer doesn't help the OP at all.
- smat 4y ago
  I did not mean to discourage people from making their own evaluations. Maybe I did not word it correctly. The article starts with questioning best practices for implementing real-time processing threads. The statistical analysis presented in the article is based on a single workload and a single machine, which in my opinion does not help to answer this question.
  - sitkack 4y ago
    Oh, ok, I understand. I agree that the empirical technique could be better, but the experiment is neat even if slightly flawed. If the author wanted to show how much memory allocation could be done in an audio thread, they should construct an audio workload where they can tune the allocation and memory access patterns and then determine exactly how much is too much. But really that was the motivation, then as they admit in the start, they got nerd sniped and started measuring DOOM memory allocations (also fun). We should ignore the original motivation unless one uses a completely different experiment to justify something that wasn't tested.
deleted 4y ago
[deleted]

abainbridge 4y ago

"My first attempt at a benchmark involved allocating and freeing blocks of random size. Twitter friends correctly scolded me and said that's not good enough. I need real data with real allocation patterns and sizes." "The goal is to create a "journal" of memory operations. It should record malloc and free operations with their inputs and outputs. Then the journal can be replayed with different allocators to compare performance." I don't think that is sufficient either. You need to mix the malloc/free with the other work, because the other work knocks your allocator data structures out of cache and pollutes your TLB and branch predictor. And loads up the dram interface (eg by the gpu fetching data from it). Etc etc.

forrestthewoods 4y ago
Comments like this are not insightful or helpful. > I don't think that is sufficient either. Sounds like you should write a blog post that compares the two methods to see if it's an acceptable approximation or not. :)
sitkack 4y ago
I would have measured the time directly inside of the Doom allocator and the OP could produce the same charts directly from the measured data without replaying the allocation log. And IF I were going to collect that data, I'd grab the call stack as well to see where the allocations were coming from. There might be a chance to retro fit an arena allocator, but would think Carmack code is already probably optimal? Yes it is, for the reason we can even have this discussion about it. The other change I would make to the experiment, is to have the traces be taken from a timedemo and not via regular gameplay so that hypothesis can be tested. At the very least, one could precisely time the impact of instrumentation.
- thxg 4y ago
  > I would have measured the time directly inside of the Doom allocator Exactly! The author already has all the infra necessary (rdtsc for each call). Measuring time inside the game would be more accurate and simpler. Why did the author do things this way? I must be missing something. (By the way, the author even seems to know about this issue since they added code that simulates using the allocated blocks (touching one byte for every allocated 4k), but that does not feel like it's nearly enough.) > grab the call stack as well Maybe this part could be done with no code with VTune / Linux perf? Sure, those only gather stochastic measurements (so not ideal for the original latency measurement). But to get a rough idea of where the costly allocations come from, it could be an easy way.

trasz 4y ago

>The goal is to create a "journal" of memory operations. Hm, I wrote something like this once - https://github.com/CTSRD-CHERI/cmt/blob/master/README.md https://github.com/CTSRD-CHERI/cmt/blob/master/README.md

dwdz 4y ago

Please don't use Jet color scheme. Matplotlib uses excellent viridis by default. There's no reason not to use it. [0][1] [0] https://stats.stackexchange.com/questions/223315/why-use-colormap-viridis-over-jet https://stats.stackexchange.com/questions/223315/why-use-col... [1] https://www.youtube.com/watch?v=xAoljeRJ3lU https://www.youtube.com/watch?v=xAoljeRJ3lU

forrestthewoods 4y ago
It uses nipy_spectral.

nemetroid 4y ago

Eleven million mallocs over seven minutes of gameplay at 60 fps comes out at an average of 437 mallocs per frame (this includes "load level" and "die and reload", so the average during gameplay is likely even lower). The author writes "Doom 3 hits 60fps in debug and calls malloc all over the place.", but to me those stats suggest malloc-averse code.

fisherjeff 4y ago

I wonder how many of the longer execution times are just thread pre-emptions?

jeffbee 4y ago
The fact that all the allocators have the same tail performance suggests the measurement is polluted by something like thread preemption or processor power state transitions.
- forrestthewoods 4y ago
  This is not correct. TLSF has a worst-case of about 30 microseconds. Second best is 200 microseconds, which is shared by 3 allocators (HeapAlloc, dlmalloc, and rpmalloc). Which implies something inside the OS call is occasionally very slow. TLSF is the only tested allocator that uses a pre-allocated pool and stays in user space. And it has noticeably better tail performance. https://www.forrestthewoods.com/blog/benchmarking-malloc-with-doom3/assets/img/percentile_alloc_zoomed_large.png https://www.forrestthewoods.com/blog/benchmarking-malloc-wit...

tomovo 4y ago

See also - Arma 3 benchmarks comparing different malloc implementations here: https://www.youtube.com/watch?v=kNmeMxEel4M https://www.youtube.com/watch?v=kNmeMxEel4M

Syzygies 4y ago

Back in the 1980's I co-wrote a computer algebra system, that ran for example on many colleagues' first computer: The first Macintosh. Resources were scarce, everything mattered. Malloc attempts to work acceptably well under diverse scenarios. Specific programs such as ours can adopt simpler memory disciplines, supported by an interface with malloc. Almost all of our memory needs could be served by pools of fixed-size slugs of memory. Each pool experienced considerable churn and reuse, but the total memory needed by each pool was unimodal, growing to a peak then subsiding until the pool was no longer needed. We chose a universal fixed-size block to be served by malloc. We kept these blocks on a master stack, to assign to pools as needed. We kept the slugs in each pool on stacks, to reuse as needed. Closing a pool returned its blocks to the master stack. There's nothing novel here; this is about as dumb a protocol as one can imagine, and correspondingly faster than anything else we tried. I still believe the lesson today: One's core algorithms need to be crafted to cooperate with the fastest memory protocols. The doctor can't do everything without the patient's cooperation. For example, I believe that the approach taken by Rust will ascend as we better learn how to work with it.

throwawaymaths 4y ago
You mean zig, right? Zig is allocator-agnostic. It's hard (but not impossible) to implement type-specific allocators in Rust, and if you want the same type to take context-dependent allocator types, or context-dependent allocator instances, it's much , much harder, if I'm not mistaken. And the default way of programming Rust doesn't really tolerate allocation failures (which you might run up against with fixed memory slabs)

Shadonototra 4y ago

the biggest enemy is non-predictable performance, otherwise you get visible stutters but nowadays nobody gives a shit anymore since most games are made using unreal/unity wich ship with a shitty GC generation of developers who think pumping more hardware will fix all their problems, little do they know wich is why most games using these engines have troubles porting their game to resource constrained devices like smartphones/switch frame budget for 120fps is just 8ms

AtlasBarfed 4y ago

How do people log hyperfast data like this without impacting the thing you're measuring? ... preallocate storage? (is this actual, real irony?)

ultrahax 4y ago

Game dev here ( with significant experience in engines with significant idTech ancestry ) - the goal is, generally, to avoid mallocs _during_ a frame - you alloc everything you need during startup. I'm surprised there's that much ongoing allocation.

SleepyMyroslav 4y ago

i have anecdata of regular free taking worst case 30ms circa 2016. Of course, platform/compiler/etc should not be named but i think it gives a picture how much work can heap management require under load.