IdTech 4, 15% frame rate increase through semiautomatic paralellization
vectorfabrics.com
vectorfabrics.com
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...
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.h...
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.
So does Pareon depend on running an instrumented build? If so, wouldn't you need a sample data file (map, demo, whatever) that covers 100% of branches and dependencies in order to know for absolutely sure that there are no dependencies between code.
Could you make a huge SSA of the program and determine dependencies that way (more of a reality now that we have 64bit desktops and GCC has "whopr" and friends)?
> that covers 100% of branches and dependencies in order to know
> for absolutely sure that there are no dependencies between code.
I am curious about that too.
Even 100% statement coverage does not guarantee that you have discovered all dependencies. Think “array of pointers”. You may have good enough coverage to execute once the statement that gets a pointer from the array, but it does not mean that different values do not result in other pointers that create dependencies where you haven't seen any.
I think this is why they call it “semiautomatic”. The tool hints at what looks parallelizable. The user takes responsibility for the changes.
> Could you make a huge SSA of the program and determine
> dependencies that way
The difficulty with just C is not so much multiple assignments to the same memory locations, but everything else, including the pervasive reliance on pointers. C++ adds several abstractions on top of that that do not make it easier to statically tell what the program may do.
There are whole-program static analyzers whose results can be used to resolve pointers and get useful dependencies on medium-sized C programs. I work on one: http://frama-c.com/try_out.html
The explicit memory operations create an extreme complexity in reasoning about a program exhaustively, not far from analyzing generic binary code.
C is so permissive to be overkill for a lot of applications. Would this be more tractable with safer programming languages that avoid "wild" pointers, such as Rust?
Or maybe by extending the C syntax so that the programmer can give hints to the compiler what he means, instead of what he has written so that the compiler can detect mismatches?
BTW props on Frama-C, it's incredible what you guys are doing.
"Regarding the way Pareon performs its analysis: it relies on instrumentation and therefore coverage is key. The parts of the code of interest should be sufficiently covered. Partly it is the user's responsibility to make sure the right data sets are used. However Pareon helps the user by showing the achieved coverage of the parts you want to parallelize."
[1] http://www.vectorfabrics.com/blog/item/accelerating_the_idte...
"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_idte...
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).
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.
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.
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.
When considering performance issues for a particular customer, you have to weigh the cost of improvement. 3 weeks of an engineer's time for 15% speedup (even if it were in elapsed frame time, which it's not) is NOT an easy decision. Those 3 weeks could be spent doing far more valuable things, like improving the tools used by the rest of the development team, fixing crash bugs, or working on downloadable content that will bring in more money for the studio. They could also be spent making architectural changes that provide much larger performance wins through design improvements that require actual knowledge about the design of the application and the significance of the choices made.
When you're doing performance optimization in game development, you go for the biggest, cheapest wins first, based on actual measurements and an understanding of what's wrong. Given that the optimized version of the game is not running at 60fps (and the demo video contains obvious rendering glitches) I don't think it's unfair to question whether CPU parallelism was the most obvious bottleneck here.
Lastly, dropping texture size or shader detail when running on a low spec machine is not a regression. If the machine is not capable of running at max rendering detail due to GPU constraints, no degree of CPU parallelism will overcome this.
"I see something I can improve, but I had better not improve it; were I to work at id, my time would probably be more valuably spent on other things."
I wish you'd just back off and laud the improvement rather than fitting it into your model of game development and continuing to double down on a snarky, dismissive comment that basically shits on somebody else's work. I certainly appreciate that you've worked in professional game development, but come on, someone did something cool. I'm sorry that it isn't cool enough for you or doesn't use the measurements you prefer.
Attitudes like yours hurt our industry as a whole.
Hacker News isn't about selling things to managers who make purchasing decisions by lying to them, last time I checked.
They wrote a tool to find things to parallelize. They parallelize them, the code gets faster. I realize that it isn't the faster you would prefer, but they picked an accessible target that everybody could understand. It isn't as cool if they say "we made Excel render graphs 15% faster" or "we made MP3 transcoding 15% faster". They just made a code base faster using their tool, that's all.
If they had made a video editor faster and you'd worked on video editors all your life, I'm sure you'd be here shitting on the achievement as well. They're not a game development shop. They picked a game to screw around with. They made it quicker. It just happens to be your pet area, so you absolutely cannot stand that someone figured out how to do something in your little world that you wouldn't think of.
I'm impressed you've upgraded to outright calling them liars now rather than just admit, maybe, you might be wrong.
This isn't some lone engineer's noble cause. This is a sales product demonstration.
> Attitudes like yours hurt our industry as a whole.
No it doesn't. People SHOULD be critical of demonstrations like these because they are rarely representative of real world behaviour.
I think the lowest opinion on the totem pole is one formed by assumptions (based upon personal experience with an area) used to reflect upon something from the hip. "I'm pretty versed in game development, and what these people are doing is stupid based on my world view."
I'm actually glad this thread got pushed down, so maybe some actually informative discussion can rise up rather than an analysis of how minutely the people behind this screwed up.
Sounds like a guaranteed way to fail.
If the product does not provide a decent ROI then you are right to dismiss it.
Your postulation is unwarranted, by the way, since my posts have been going up and down based upon their depth in the thread. The top comments have been upvoted more than the lower ones, and the lower ones have actually been muted somewhat. I would actually suggest that people are reading the thread and voting appropriately, and probably aren't making it deepest into the thread.
Your sweeping characterization of mindless Hacker News voters acting by whim is disconcerting, to say the least. That we're so fixated on the voting here when karma is absolutely worthless is equally annoying. I am, however, intrigued by the shift from very light gray back to legible that has taken place on his comments since the beginning of this meta discussion (starting with ww520's remark); there might be something to what you're saying, which is that people are acting based upon what others are saying -- that's troubling.
When you're reasoning backwards you're on thin ice because it's easier to let a logical fallacy through as you start assembling your "facts and assumptions" in the rush to make your point known. You can "win the battle" (by being quick) but "lose the war" (by being wrong), and when I catch myself doing it I have to either cancel the post or put extra effort into it to make sure I have a valid argument(and often, after doing enough research, I don't, or I have gone too far outside my domain to know for sure).
Forward reasoning usually results in very straightforward critiques like "I used this but it was not appropriate for these situations..." or "it completely failed in this case..." or "it turned out to be unnecessary for the project I was on." Kevin's posts(both the initial one and follow-ups) get muddled because he has to weave together several minor points; as each successive rebuttal comes forward, so does his target, so that the final opinion remains the same, even though by the end he's reduced to "they're lying."
(A good example of a game developer who has put some serious effort and notetaking into finding ROI on a new tool is John Carmack and his forays into static analysis.)
However, it becomes substantially less impressive when you notice that you're using 2x or 4x the amount of processor hardware (2 or 4 cores) and only getting a 15% speedup. In a by-hand implementation that would be very disappointing.
If it were fully automated that would still be pretty valuable, but it appears that this isn't. So it seems to be of questionable utility.
Love to hear more about your 2000-2005 paratrooper work at the AAA shops - have you discussed that at all anywhere?
I've always been interested in seeing how the really tough stuff gets done at AAA shops.
The parachute-in often happens for teams that don't have a whole staff of low-level engineers around. Either small studios using an off-the-shelf engine (that can still be customized), or studios in a large conglomerate. (EA e.g. used to be quite happy to ship experts around. At least back in my day.)
They didn't seem to mention how much they're actually utilizing the remaining cores either. From the look of it, they've basically parallelized a couple of loops in the renderer. That strikes me as being the wrong way to go about this, especially considering that modern AAA games apparently break everything down into tasks, and run the separate tasks in parallel (idTech5 apparently does this, for example).
You may be right that they are doing the wrong thing, but I think the fact it's doable at all is reasonable evidence that their tool is useful. I'm pretty impressed that somebody who's totally unfamiliar with the code is able to jump in and start parallelizing stuff - particularly if they've never worked on a game before, and so might not have any real idea where would be a good place to start, or how things are likely to work.
Maybe my standards are too low.
(Those screwy HUD textures might be evidence that they managed to get it completely wrong, of course ;) - or maybe it's just something simple.)
The HUD thing - it looks like they screwed up the post-processing effects somehow. As far as I remember, the original game did apply post-processing effects to the HUD. Probably something to do with OpenGL not getting a decent way to do render-to-texture until 2005, so they'd have had to use the previous frame's render buffer. It wasn't that noticeable in the original though.
It is true that the application domain of the code chosen for the blog post might be a bit unfortunate in order to make a realistic case. Game engine programmers are usually very good at low level optimizations. Pareon can be used by non-experts though and additionally assist experts in during the task of finding and applying optimizations and paralellization oportunities.
Quoting the blog update [1]:
"Our Pareon tool is not aimed to replace parallelization experts. We want the tool to be useful for any programmer who is looking for paralellization opportunities in either his own code or in code that he is unfamiliar with. A domain expert (game programmer) can probably save some time because of his in-depth knowledge."
Additionally:
"The three additional cores on my four-core machine are only used during part of a rendering cycle. They are sleeping the rest of the time. If I would parallelize other pieces of code in the cycle as well, it would increase utilization and I would expect the frame rate to improve even more."
[1] http://www.vectorfabrics.com/blog/item/accelerating_the_idte...