Hacker News Reader

Comment by randallu | Hacker News Reader

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

View on HN

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 determine dependencies that way (more of a reality now that we have 64bit desktops and GCC has "whopr" and friends)?

> 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

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.

The new followup post [1] explains that Pareon indeed partly relies on good coverage:

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

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.

Even under single-threaded applications, with a custom allocator that suits your workload, it's possible to get significant speed boosts over the system malloc. One of the assignments I enjoyed back in college was writing a memory allocator. By the time I was done optimizing (including replacing all structs with raw pointer arithmetic using #defines), IIRC I was getting over 10000 single-threaded allocations per second vs. ~3000 from malloc().

Reply on news.ycombinator.com