4 ms·

"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

"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.
  - imron 4y ago
    > Why did the author do things this way? I must be missing something. Likely because it's easier to test against different allocators with a small replay tool than it is to try and get Doom3 to compile against dlmalloc, jemalloc, mimalloc, rpmalloc and tlsf.
    - mcronce 4y ago
      I would also bet that getting the game to perform the exact same series of allocations would be an intractable problem to solve. I don't think Doom 3 has a benchmark mode; the author just recorded themselves loading the game, loading a level, doing a bit of gameplay, etc.
      - sitkack 4y ago
        Carmack is a great empiricist, meaning he pays a lot of attention to how things work in a running system. All of his engines provide rich facilities for record and replay as well as running benchmarks. timedemo <demo file> uscache The DOOM3 source is here https://github.com/id-Software/DOOM-3 https://github.com/id-Software/DOOM-3 There are lots of facilities for recording and playing back demos. The author could record their own gameplay and play it back in realtime vs running timedemo (which plays back as fast as possible). https://github.com/id-Software/DOOM-3/blob/master/neo/framework/Session.cpp https://github.com/id-Software/DOOM-3/blob/master/neo/framew... 2865: cmdSystem->AddCommand( "recordDemo", "records a demo" ); 2866: cmdSystem->AddCommand( "stopRecording", "stops demo recording" ); 2867: cmdSystem->AddCommand( "playDemo", "plays back a demo", 2868: cmdSystem->AddCommand( "timeDemo", "times a demo", 2869: cmdSystem->AddCommand( "timeDemoQuit", "times a demo and quits", https://www.youtube.com/watch?v=CLA42q3myCg https://www.youtube.com/watch?v=CLA42q3myCg https://www.youtube.com/watch?v=9KIhRmdz2cI https://www.youtube.com/watch?v=9KIhRmdz2cI
      - nym375 4y ago
        > I don't think Doom 3 has a benchmark mode id Tech games have "timedemo" mode, where they replay a pre-recorded demo as fast as possible, and report how many FPS it was able to process. These were very popular benchmarks long ago.
- abainbridge 4y ago
  > I would have measured the time directly inside of the Doom allocator Yeah, that'd be much better. It'd still only tell us how the allocator performed when having to share cache, memory B/W etc with Doom 3 though. Performance of similar allocations in a different application could be different. Even changing the screen resolution of Doom 3 might be enough to change the performance of the allocator. To get anywhere we need to understand what all the hardware components that alter performance are, the limits of their various resources and the penalties for running out of those resources. I normally find it is easier to remove the allocs from my program's main loop than to do this kind of analysis. In fact, I think this analysis is impossible. What happens when some background process like a virus checker decides to run? Doing less work in your program is almost always better. Moving the allocations out of the main loop normally makes the ownership easier to understand too, so helps to minimise code complexity.
- moomin 4y ago
  I suspect you’d find Carmack’s code was “good enough that there was something more important to work on” rather than necessarily “optimal”. So it’s entirely possible there’s still some fruit to find, just no low-hanging ones.
deleted 4y ago
[deleted]
mhh__ 4y ago
For some programs allocation can be a lot slower than actually accessing the memory unfortunately.
deleted 4y ago
[deleted]

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.
- imron 4y ago
  > Why did the author do things this way? I must be missing something. Likely because it's easier to test against different allocators with a small replay tool than it is to try and get Doom3 to compile against dlmalloc, jemalloc, mimalloc, rpmalloc and tlsf.
  - mcronce 4y ago
    I would also bet that getting the game to perform the exact same series of allocations would be an intractable problem to solve. I don't think Doom 3 has a benchmark mode; the author just recorded themselves loading the game, loading a level, doing a bit of gameplay, etc.
    - sitkack 4y ago
      Carmack is a great empiricist, meaning he pays a lot of attention to how things work in a running system. All of his engines provide rich facilities for record and replay as well as running benchmarks. timedemo <demo file> uscache The DOOM3 source is here https://github.com/id-Software/DOOM-3 https://github.com/id-Software/DOOM-3 There are lots of facilities for recording and playing back demos. The author could record their own gameplay and play it back in realtime vs running timedemo (which plays back as fast as possible). https://github.com/id-Software/DOOM-3/blob/master/neo/framework/Session.cpp https://github.com/id-Software/DOOM-3/blob/master/neo/framew... 2865: cmdSystem->AddCommand( "recordDemo", "records a demo" ); 2866: cmdSystem->AddCommand( "stopRecording", "stops demo recording" ); 2867: cmdSystem->AddCommand( "playDemo", "plays back a demo", 2868: cmdSystem->AddCommand( "timeDemo", "times a demo", 2869: cmdSystem->AddCommand( "timeDemoQuit", "times a demo and quits", https://www.youtube.com/watch?v=CLA42q3myCg https://www.youtube.com/watch?v=CLA42q3myCg https://www.youtube.com/watch?v=9KIhRmdz2cI https://www.youtube.com/watch?v=9KIhRmdz2cI
    - nym375 4y ago
      > I don't think Doom 3 has a benchmark mode id Tech games have "timedemo" mode, where they replay a pre-recorded demo as fast as possible, and report how many FPS it was able to process. These were very popular benchmarks long ago.
abainbridge 4y ago
> I would have measured the time directly inside of the Doom allocator Yeah, that'd be much better. It'd still only tell us how the allocator performed when having to share cache, memory B/W etc with Doom 3 though. Performance of similar allocations in a different application could be different. Even changing the screen resolution of Doom 3 might be enough to change the performance of the allocator. To get anywhere we need to understand what all the hardware components that alter performance are, the limits of their various resources and the penalties for running out of those resources. I normally find it is easier to remove the allocs from my program's main loop than to do this kind of analysis. In fact, I think this analysis is impossible. What happens when some background process like a virus checker decides to run? Doing less work in your program is almost always better. Moving the allocations out of the main loop normally makes the ownership easier to understand too, so helps to minimise code complexity.
moomin 4y ago
I suspect you’d find Carmack’s code was “good enough that there was something more important to work on” rather than necessarily “optimal”. So it’s entirely possible there’s still some fruit to find, just no low-hanging ones.

deleted 4y ago

[deleted]

mhh__ 4y ago

For some programs allocation can be a lot slower than actually accessing the memory unfortunately.

deleted 4y ago

[deleted]