7 ms·

IdTech 4, 15% frame rate increase through semiautomatic paralellization

64 points by willvarfar 14y ago

egypturnash 14y ago
For those of us who haven't played Doom 3, is it normal to have those rapid flashes of numbers when you're smacked by one of those red guys in the demo they're showing it off with? Or is this a weird bug introduced somewhere along the line?
- kevingadd 14y ago
  Those are absolutely a bug. They probably screwed up and didn't put mutexes around every piece of shared state.
  - fons 14y ago
    It is not a bug. That effect was already present in the pristine unoptimized code. Quoting Vector Fabrics new blog post [1]: "Some people wondered if the HUD textures are messed up in the optimized version, because the demo shows that as soon as you get hit by a monster the health and score numbers seem to blow up in your face. The answer is that this is part of the game play and already present in the original unoptimized version." [1] http://www.vectorfabrics.com/blog/item/accelerating_the_idtech_4_engine_with_pareon_a_follow_up http://www.vectorfabrics.com/blog/item/accelerating_the_idte...
kevingadd 14y ago
A 15% framerate increase from 3 weeks of work isn't particularly impressive. It would be more meaningful if the measurement was in terms of frametime (i.e. elapsed time per frame) since framerate is not linear. From looking at the patch (nice of them to provide it), it seems like most of the changes are putting mutexes around things to guard against simultaneous access and then parallelizing some loops. It seems to me like anyone with basic knowledge of the game's codebase could have made these changes without any support from a tool like the one they're trying to sell, and probably done it in far less than 3 weeks. If your goal is to run a piece of code in parallel, you don't need a program to walk through that code and identify all the shared state it manipulates (and then go through and make sure that state has a mutex guard). If the software they're trying to sell did that for you, now that would be nice. It seems unlikely that you could automatically modify C++ source code without a lot of constraints, though. Software to aid authoring parallel C++, or detect places where you can safely parallelize existing code, would certainly be valuable but this is a pretty poor demonstration of any actual advantages offered by their software. EDIT: From watching the included demo video, the game is running well below 60fps which suggests that they're running it on a low end graphics card (or generally low-clocked machine) to improve the gains from their optimizations. I don't think their results are necessarily real-world as a result of this - someone playing Doom 3 on an actual gaming rig would probably not see a 15% framerate increase because their framerate would already be well above 60fps (framerate is nonlinear, as I mentioned above).
- jspthrowaway 14y ago
  Came for the dismissive hand-waving that I fully expected to be the top comment and I wasn't disappointed. What's the improvement factor where you'd be impressed? 50%? 60%? It's remarkable in my opinion how little work it took to improve upon an already very-optimized engine, in the constraints that they set for the developer, by a developer who's never worked with game engines in his career. Edit: No longer the top comment; it was when I commented.
  - kevingadd 14y ago
    Framerate isn't a comparative measurement. You have to measure elapsed time. Instead of spending 3 weeks wrapping data structures in mutexes for a 15% framerate increase, you could probably get an equivalent speedup by reducing shader detail, texture size, or any number of other options. This kind of measurement is not meaningful without additional information: Is this improved performance for low-spec GPUs? High-spec CPUs? universal performance improvement for all users? Low end machines typically do not have lots of cores; will they actually benefit tremendously from parallelism? As I said before, a high-spec machine already runs Doom 3 fine, so I question whether the gains here would actually be significant at all. EDIT: Also, gains of this size can easily be produced by changes as simple as turning on Profile-Guided Optimization in your compiler. We'd also need to know what settings they used to compile the game to know whether the results are actually realistic.
    - jspthrowaway 14y ago
      > Instead of spending 3 weeks wrapping data structures in mutexes for a 15% framerate increase, you could probably get an equivalent speedup by reducing shader detail, texture size, or any number of other options. I see why we differ in opinion here: you feel that regressing backwards and sacrificing visual quality is a better approach than parallelizing the same exact engine with the same quality. I don't think we're going to see eye-to-eye on this one.
      - kevingadd 14y ago
randallu 14y ago
So looking at the patch: 1. The allocator was a bottleneck; wonder if tcmalloc would have done better? 2. Computing what to draw? (idInteraction) was reduced to a for-loop and parallelized 3. ... lots more pre-rendering stuff ... Unfortunately they didn't annotate the patch with the size of the win for any given change, or write up an analysis on what the changes were (I'm unfamiliar with idTech, too). If they got the biggest win from improving the allocator, well, that's not very interesting. If they got the biggest win from the other stuff, and the tool told them what was safe to parallelize then that's much more interesting. Actually, the whole thing would be better if the write up explained how they used the tool and what it did and how much improvement they got at each step...
- jspthrowaway 14y ago
  glibc's malloc() is known to be lackluster under parallel workloads. Alternatives do perform better in certain circumstances, but profile before making the switch -- your situation might not be one of them. It's possible to inject tcmalloc into an executable using Linux's preloader, too, without recompiling[1]. [1]: http://gperftools.googlecode.com/svn/trunk/doc/heapprofile.html http://gperftools.googlecode.com/svn/trunk/doc/heapprofile.h...
  - KaeseEs 14y ago
    I'm quite surprised that idTech4 was using _any_ malloc implementation aside from the initial allocation of the memory pool that it would use for its actual runtime allocator.
    - BlackAura 14y ago
      It actually does use it's own heap allocator, with some additional allocators built on top of it. I don't know if it also uses the system / libc allocator for anything, but I'd be surprised if it did. Aside from glQuake (which used a custom allocator for most of the game, but used malloc quite often in the GL renderer), all of id's other engines used custom allocators for everything. Edit: just skimmed the white paper. They were talking about the custom allocator which was, of course, not thread safe, because it was designed for a single threaded game engine. Replacing that with an allocator designed for parallel usage (tcmalloc for example) would have helped, but so would having separate allocation pools for different threads (which you might do for a game engine designed for multithreading). Instead, they made the allocator thread safe, using their tool to analyze it, and then sprinkling it with mutexes. That would probably be why it was a bottleneck.
fons 14y ago
There is a new blog post from Vector Fabrics on this topic. It includes some clarifications and tries to respond the questions raised until now: http://www.vectorfabrics.com/blog/item/accelerating_the_idtech_4_engine_with_pareon_a_follow_up http://www.vectorfabrics.com/blog/item/accelerating_the_idte...

64 points by willvarfar 14y ago

For those of us who haven't played Doom 3, is it normal to have those rapid flashes of numbers when you're smacked by one of those red guys in the demo they're showing it off with? Or is this a weird bug introduced somewhere along the line?

kevingadd 14y ago
Those are absolutely a bug. They probably screwed up and didn't put mutexes around every piece of shared state.
- fons 14y ago
  It is not a bug. That effect was already present in the pristine unoptimized code. Quoting Vector Fabrics new blog post [1]: "Some people wondered if the HUD textures are messed up in the optimized version, because the demo shows that as soon as you get hit by a monster the health and score numbers seem to blow up in your face. The answer is that this is part of the game play and already present in the original unoptimized version." [1] http://www.vectorfabrics.com/blog/item/accelerating_the_idtech_4_engine_with_pareon_a_follow_up http://www.vectorfabrics.com/blog/item/accelerating_the_idte...

kevingadd 14y ago

A 15% framerate increase from 3 weeks of work isn't particularly impressive. It would be more meaningful if the measurement was in terms of frametime (i.e. elapsed time per frame) since framerate is not linear. From looking at the patch (nice of them to provide it), it seems like most of the changes are putting mutexes around things to guard against simultaneous access and then parallelizing some loops. It seems to me like anyone with basic knowledge of the game's codebase could have made these changes without any support from a tool like the one they're trying to sell, and probably done it in far less than 3 weeks. If your goal is to run a piece of code in parallel, you don't need a program to walk through that code and identify all the shared state it manipulates (and then go through and make sure that state has a mutex guard). If the software they're trying to sell did that for you, now that would be nice. It seems unlikely that you could automatically modify C++ source code without a lot of constraints, though. Software to aid authoring parallel C++, or detect places where you can safely parallelize existing code, would certainly be valuable but this is a pretty poor demonstration of any actual advantages offered by their software. EDIT: From watching the included demo video, the game is running well below 60fps which suggests that they're running it on a low end graphics card (or generally low-clocked machine) to improve the gains from their optimizations. I don't think their results are necessarily real-world as a result of this - someone playing Doom 3 on an actual gaming rig would probably not see a 15% framerate increase because their framerate would already be well above 60fps (framerate is nonlinear, as I mentioned above).

jspthrowaway 14y ago
Came for the dismissive hand-waving that I fully expected to be the top comment and I wasn't disappointed. What's the improvement factor where you'd be impressed? 50%? 60%? It's remarkable in my opinion how little work it took to improve upon an already very-optimized engine, in the constraints that they set for the developer, by a developer who's never worked with game engines in his career. Edit: No longer the top comment; it was when I commented.
- kevingadd 14y ago
  Framerate isn't a comparative measurement. You have to measure elapsed time. Instead of spending 3 weeks wrapping data structures in mutexes for a 15% framerate increase, you could probably get an equivalent speedup by reducing shader detail, texture size, or any number of other options. This kind of measurement is not meaningful without additional information: Is this improved performance for low-spec GPUs? High-spec CPUs? universal performance improvement for all users? Low end machines typically do not have lots of cores; will they actually benefit tremendously from parallelism? As I said before, a high-spec machine already runs Doom 3 fine, so I question whether the gains here would actually be significant at all. EDIT: Also, gains of this size can easily be produced by changes as simple as turning on Profile-Guided Optimization in your compiler. We'd also need to know what settings they used to compile the game to know whether the results are actually realistic.
  - jspthrowaway 14y ago
    > Instead of spending 3 weeks wrapping data structures in mutexes for a 15% framerate increase, you could probably get an equivalent speedup by reducing shader detail, texture size, or any number of other options. I see why we differ in opinion here: you feel that regressing backwards and sacrificing visual quality is a better approach than parallelizing the same exact engine with the same quality. I don't think we're going to see eye-to-eye on this one.
    - kevingadd 14y ago

randallu 14y ago

So looking at the patch: 1. The allocator was a bottleneck; wonder if tcmalloc would have done better? 2. Computing what to draw? (idInteraction) was reduced to a for-loop and parallelized 3. ... lots more pre-rendering stuff ... Unfortunately they didn't annotate the patch with the size of the win for any given change, or write up an analysis on what the changes were (I'm unfamiliar with idTech, too). If they got the biggest win from improving the allocator, well, that's not very interesting. If they got the biggest win from the other stuff, and the tool told them what was safe to parallelize then that's much more interesting. Actually, the whole thing would be better if the write up explained how they used the tool and what it did and how much improvement they got at each step...

jspthrowaway 14y ago
glibc's malloc() is known to be lackluster under parallel workloads. Alternatives do perform better in certain circumstances, but profile before making the switch -- your situation might not be one of them. It's possible to inject tcmalloc into an executable using Linux's preloader, too, without recompiling[1]. [1]: http://gperftools.googlecode.com/svn/trunk/doc/heapprofile.html http://gperftools.googlecode.com/svn/trunk/doc/heapprofile.h...
- KaeseEs 14y ago
  I'm quite surprised that idTech4 was using _any_ malloc implementation aside from the initial allocation of the memory pool that it would use for its actual runtime allocator.
  - BlackAura 14y ago
    It actually does use it's own heap allocator, with some additional allocators built on top of it. I don't know if it also uses the system / libc allocator for anything, but I'd be surprised if it did. Aside from glQuake (which used a custom allocator for most of the game, but used malloc quite often in the GL renderer), all of id's other engines used custom allocators for everything. Edit: just skimmed the white paper. They were talking about the custom allocator which was, of course, not thread safe, because it was designed for a single threaded game engine. Replacing that with an allocator designed for parallel usage (tcmalloc for example) would have helped, but so would having separate allocation pools for different threads (which you might do for a game engine designed for multithreading). Instead, they made the allocator thread safe, using their tool to analyze it, and then sprinkling it with mutexes. That would probably be why it was a bottleneck.

fons 14y ago

There is a new blog post from Vector Fabrics on this topic. It includes some clarifications and tries to respond the questions raised until now: http://www.vectorfabrics.com/blog/item/accelerating_the_idtech_4_engine_with_pareon_a_follow_up http://www.vectorfabrics.com/blog/item/accelerating_the_idte...