4 ms·

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

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.
- nitrogen 14y ago
  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().
randallu 14y ago
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)?
- pascal_cuoq 14y ago
  > 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 http://frama-c.com/try_out.html
  - wladimir 14y ago
    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.

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.
nitrogen 14y ago
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().

randallu 14y ago

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

pascal_cuoq 14y ago
> 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 http://frama-c.com/try_out.html
- wladimir 14y ago
  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.