Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

IdTech 4, 15% frame rate increase through semiautomatic paralellization

vectorfabrics.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#31

Post by BlackAura »

KaeseEs wrote: post #23
jspthrowaway wrote: post #13

Earlier quoted context omitted.

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.h...

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.

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.

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#32

Post by confluence »

jblow wrote: post #30
FrankBooth wrote: post #28

Earlier quoted context omitted.

When were you in the AAA world, Jonathan?

I did a lot of consulting / contract work at AAA companies between 2000-2005. "Parachute in and make the E3 demo work / implement some tough feature / etc". Sometimes it was less well-defined than that.

Woah you're the guy that did Braid - glad to see you on HN :D

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.

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#33

Post by BlackAura »

jblow wrote: post #24
kevingadd wrote: post #3

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 m…

This is not just middlebrow dismissal, it's outright wrong. In the AAA world we would love to spend only 3 weeks of an engineer's time to get a 15% speedup. Seriously, that is a great deal, it's like, where do I sign up? 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 implementatio…

Worse, they didn't actually get a 15% speedup. They reduced the frame time from 16.7ms (around 60FPS) to 15.3ms (around 65 FPS), which is only a speedup of something like 7%.

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).

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#34

Post by pascal_cuoq »

randallu wrote: post #29
randallu wrote: post #5

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 th…

Oh, so I just noticed the "Whitepaper" link, and that has lots more good info in (I wish the blog post was the whitepaper!). 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…

> 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.

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

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#35

Post by groby_b »

confluence wrote: post #32
jblow wrote: post #30

Earlier quoted context omitted.

I did a lot of consulting / contract work at AAA companies between 2000-2005. "Parachute in and make the E3 demo work / implement some tough feature / etc". Sometimes it was less well-defined than that.

Woah you're the guy that did Braid - glad to see you on HN :D 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 same way it gets done elsewhere - you find a person who's an expert at that kind of stuff and tell them to get it done :)

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.)

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#36

Post by to3m »

BlackAura wrote: post #33
jblow wrote: post #24

Earlier quoted context omitted.

This is not just middlebrow dismissal, it's outright wrong. In the AAA world we would love to spend only 3 weeks of an engineer's time to get a 15% speedup. Seriously, that is a great deal, it's like, where do I sign up? 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 implementatio…

Worse, they didn't actually get a 15% speedup. They reduced the frame time from 16.7ms (around 60FPS) to 15.3ms (around 65 FPS), which is only a speedup of something like 7%. 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, especiall…

p21 in the white paper suggests the speedup is ~2x, for the parts that were actually parallelized. That's more interesting (well, to me) than the rather limited increase in overall frame rate.

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.)

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#37

Post by [deleted] »

kevingadd wrote: post #11
jspthrowaway wrote: post #10

Earlier quoted context omitted.

All of what you say is wise, but the engineer doesn't work for the studio and isn't on Doom 3's release timeline. He made the game's frame rate 15% faster of his own volition simply because he could . So it's wrapped in a sales pitch, oh well. "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 of…

This article is clearly trying to sell licenses for a commercial product based on unsupported, possibly deceptive claims. I don't laud that. If the goal here is to prove the value of this analysis software, they should be proving it in terms of the value it will produce for an actual company developing software - if they're proving value for a game studio, it should probably be in the context I provided above. For ot…

[deleted]

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#38

Post by BlackAura »

to3m wrote: post #36
BlackAura wrote: post #33

Earlier quoted context omitted.

Worse, they didn't actually get a 15% speedup. They reduced the frame time from 16.7ms (around 60FPS) to 15.3ms (around 65 FPS), which is only a speedup of something like 7%. 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, especiall…

p21 in the white paper suggests the speedup is ~2x, for the parts that were actually parallelized. That's more interesting (well, to me) than the rather limited increase in overall frame rate. 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 t…

Good point. Their tool is obviously useful, even though something like this might not be the best use case for it.

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.

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#39

Post by chipsy »

jspthrowaway wrote: post #15
ww520 wrote: post #14

Earlier quoted context omitted.

Wow. You really invoked some hates. All your long and thoughtful comments have been voted down. I would say you have hit a nerve.

I, like pg and hopefully other Hacker News readers, am pretty sick of every story about something cool being immediately derailed by a know-it-all in an industry dismissing the innovation as "not cool enough". pg calls it middlebrow dismissal[1]. Rather than being treated as an imperfect launching-off point for further innovation, everything has to be world-changing perfect to have a reasonably sane comments section.…

When I see dismissals I look for a particular kind of fallacy, which this is an example of: Reasoning backwards to support the opinion. "This tool is unknown to me and their claimed improvements are dramatic" - "I would not trust an unknown tool and I do not trust their marketing efforts" - "Here's some mix of facts and expert's assumptions that supports the idea that you can't trust it."

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.)

Re: IdTech 4, 15% frame rate increase through semiautomatic paralellization

#40

Post by wladimir »

pascal_cuoq wrote: post #34
randallu wrote: post #29

Earlier quoted context omitted.

Oh, so I just noticed the "Whitepaper" link, and that has lots more good info in (I wish the blog post was the whitepaper!). 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…

> 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. 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 big part of the problem is trying to do this with C in the first place.

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.

Post reply on HN