6 ms·
Increasing the D Compiler Speed by Over 75%
- WalterBright 13y agoThis article chronicles some fun I had boosting DMD's speed by doing some simple changes.
- kevingadd 13y agoThe idea of never free()ing and then taking advantage of that with a dumb allocator to get better performance is pretty clever. I wish I could do that with my compiler; sadly I can't let it leak since I invoke it from unit/functional tests so the test runner would run out of memory and explode :( For DMD tests do you just eat the cost of a process setup and compiler startup for every test run?
- WalterBright 13y agoThe compiler is a batch tool, so restarting the process for every run is normal usage.
- to3m 13y agoI've taken to not bothering to free anything in batch tools if it's not super-obvious what to do. Objects with a simple life time (including memory owned by a stack-local object such as a std::vector, etc.) get freed; everything else just leaks. You'd think this would cause masses of problems, but it doesn't. It's easy to imagine data that would be too large, but it seems to be rarer in practice than you might think. If the alternative is something like a handle-based or smart pointer system, then you'll reap the benefits in terms of ease of debugging on a daily basis.
- willvarfar 13y agoIn the per test tear down you could reset the pointer to the start to reuse the same memory repeatedly?
- acqq 13y agoI do the related small allocations from the pools, and the pools are destroyed at every compilation end. If the pool element is for example 32K and the average element is e.g. 32 bytes that's 1K times less "real" mallocs. Having separate pools for the members of different "structures" also makes for better CPU cache usage. Edit: as aaronblohowiak writes, this method is commonly known as a http://en.wikipedia.org/wiki/Region-based_memory_management http://en.wikipedia.org/wiki/Region-based_memory_management
- aaronblohowiak 13y agoA simple region allocator could do that and then you just pay for one free() at the end of the unit test.
- gngeal 13y agoThe idea of never free()ing and then taking advantage of that with a dumb allocator to get better performance is pretty clever. Doesn't Erlang do something like this with processes? What about doing scratch heaps for data with limited lifetime? Especially if you have a way of somehow reasonably predicting how much heap you're likely going to need (perhaps a heuristics obtained with a bit of machine learning?). Allocate a bit more to give yourself some headroom, use a dumb allocator, and if you run out of space, allocate an emergency area. Obviously, in most cases you won't have to do that, though. (If you're obsessed about speed, you can allocate just blindly and use a memory fault handler to detect that you've run out of space. :-) CLISP does that and it seems to work. Look at GNU libsigsegv.)
- p9idf 13y ago> The idea of never free()ing and then taking advantage of that with a dumb allocator to get better performance is pretty clever. Ken Thompson's C compiler does this. http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/cc/compat.c http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/cc/comp... http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/cc/lex.c http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/cc/lex.... (near the end) http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/cc/macbody http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/cc/macb... (near the end)
- willvarfar 13y agoYou can have a lookup of one overs as well as the hash table sizes? Would be interesting to know if a simple bitsshift hash table is faster for a compiler usecase anyway?
- pdw 13y agoWhy did you use gprof instead of perf? In my experience gprof gives very distorted information because of the instrumenting code it adds to your program. Perf is much more accurate.
- WalterBright 13y agogprof gives the "fan in" and "fan out". As important as knowing how much time each function takes is who is calling it. One may be able to prune away the need to call it.
- X-Istence 13y agoCall graphs are pretty standard across most performance tools ...
- mrich 13y agoOn what version of Windows did you perform the measurements?
- WalterBright 13y ago7
- martin_ 13y agoChanging the modulus to use known constants is an awesome trick! Great read
- qznc 13y agoI reverted that part in dmd once. Same speed on my Intel i7 processor. Branching vs division is probably a tricky tradeoff.
- WalterBright 13y agoIt's worth checking the generated assembler to see if the optimization actually took place in your build. Note that you may be using an older dmc which did not do the divide optimization.
- jongraehl 13y agoI wondered why you don't store the reciprocal w/ the hash table object. Obviously it wastes some space, but it wouldn't be any slower than your specific checks for 4 and 31, I think. (If most of the tables have size 4 or 31, then I'd use your code).
- WalterBright 13y agoIt's not necessary since the set of possible divisors is known in advance. Also, "multiplying by the reciprocal" is a bit simplistic - there's some other instructions added in based on the specific divisor value. Adding more tests and branches for these likely would not pay off.
- jongraehl 13y agoYeah, I looked up the method and agree that if most of your tables are small, it's worth those simple ifs. I only meant to store it in addition because the alternative, storing an index into the list of divisors (and thus reciprocals) might be slower due to an extra indirection.
- shasta 13y agoWalter, could you explain why lexing was a bottleneck? That's very surprising to me. You don't re-lex template instantiations do you?
- WalterBright 13y agoLexing has been a bottleneck in every compiler I've built. The only answer I have is that ASTs are a lot smaller than source code. Templates are stored as ASTs. They are not re-lexed.
- acqq 13y agoDo you consider lexing only "reading the file, finding out if the sequence of characters is the keyword of the literal or the comment" or something more? I admit I lex the source which is already in memory, and there lexing takes less than all other processing (in CPU use). Also in my case the source is always smaller in memory than any AST.
- WalterBright 13y agoLexing is converting the source text into a token stream. If lexing takes relatively smaller times for you, perhaps you have bottlenecks in the later passes?
- shasta 13y agoI'm just having a hard time understanding how you could be having complaints about the compile times if you have a fast lexer and that lexer is a significant percentage of the total time. Can't your lexer handle a million lines of code in a few seconds? How big are these code bases?
- WalterBright 13y agoIt does handle a million lines in a few seconds - it's just that the rest of the compiler's work goes even faster. The top cycle sucker is Lexer::scan(). Here's the source: https://github.com/D-Programming-Language/dmd/blob/master/src/lexer.c https://github.com/D-Programming-Language/dmd/blob/master/sr... See line 440. It's entirely possible I've missed something glaringly obvious - have a go at it and see if you spot anything. Oh, and "complaints" is a relative term. DMD is incredibly fast at compiling compared to other compilers - it's just that I want it to go even faster. Anything less than instantaneous I regard as "needs improvement." When D gets a design win at a company, I'll often ask what put D out in front of the competition. "Compile speed" is usually mentioned. Compile speed has a huge effect on programmer productivity.
- oh_teh_meows 13y agoDoes your compiler perform any transformations at all? I imagine it can run out of memory pretty quickly if you're performing multiple transformations in succession on large code base, unless you recycle some of those used memory. Granted...since you explicitly stated that your compiler focused on compile speed, I guess optimized code generation isn't your main concern, since the two are more or less mutually exclusive.
- WalterBright 13y agoCompile speed issues are for non-optimized builds. Optimized builds take significantly longer, as those are for maximum generated code speed rather than compile speed.
- oh_teh_meows 13y agoI guess I wasn't being clear. I was just curious how do you handle your memory in the case of doing optimized builds?
- WalterBright 13y agoThe same.
- qznc 13y agoThe rule of thumb is that you get a 10% boost if you use the LLVM or the GCC backend compared to DMD. I googled a little for a go vs gccgo comparison, but found no general numbers. The situation is similar.
- chondl 13y agoHave you considered or tested using either closed hashing or linear array lookups as a replacement for you linked list open hashing implementation. Years ago I significantly improved the speed of a color quantization operation that several other engineers had already optimized by replacing it with a simpler closed hashing algorithm straight out of Knuth. More recently I've had success for small collections using arrays and performing linear search. This technique is used in Redis (see http://redis.io/topics/memory-optimization http://redis.io/topics/memory-optimization)
- acqq 13y agoAs soon as pools are used (see my other comment here) chaining is much faster than storing all elements in the table behind the hash -- you can use simpler hash function and have better performance even when the table is relatively full.
- WalterBright 13y agoI haven't spent much time looking into cache effects in the compiler's internal data structures, that gold hasn't been mined yet.
- acqq 13y agoI just wanted to say that when allocations are very cheap and kept "near" keeping lists of elements linked from the hash array (http://en.wikipedia.org/wiki/Hash_table#Separate_chaining http://en.wikipedia.org/wiki/Hash_table#Separate_chaining) instead of keeping all the elements in the hash array itself (http://en.wikipedia.org/wiki/Hash_table#Open_addressing http://en.wikipedia.org/wiki/Hash_table#Open_addressing) makes the hash table faster when the hash functions are simple and fast as the number of collisions inside of the array sinks. I don't know if that would be applicable for dmd.
- p0nce 13y agoSome ideas (at least on x86): - alignment greater than 16-bytes, eg. 128 bytes for isolated buffers. - the hardware prefetcher like to load cachelines around the memory actually accessed, just in case. So data chunks that will be accessed at the same time better be near each other to save cache usage a bit. - memory access which does not have a simple pattern is slower than one which is contiguous or have a simple stride.
- nkurz 13y agoTime to stop guessing where the speed problems were, and start instrumenting. Time to trot out gprof, the Gnu profiler. I fired it up on the slow example, and waited. And waited, and waited, and waited. I waited overnight. It pole-axed my Ubuntu box, I had to cold boot it. The test case was so big that it plus gprof was too much. gprof slows things down a lot, so I had to cut things way down to get it to work. It's been a long time since I've used gprof. I switched to Valgrind and OProfile about 10 years ago, and more recently to 'perf' and 'likwid'. If the goal is finding hot-spots, these last might be more convenient since they run with minimal overhead --- a couple percent rather than 100x. Are there benefits to gprof that I've forgotten? Are there newer and better profiling tools I don't know about?
- WalterBright 13y agoAs I mentioned elsewhere, I like gprof because it reports on fan-in and fan-out. This gives a picture of how the tree is executing, rather than just the functions.
- nkurz 13y agoMaybe I misunderstand what you need, but generating a call graph and showing what percentage of time is spent in a function by caller is possible with all of these. Example for perf: http://lwn.net/Articles/340010/ http://lwn.net/Articles/340010/
- WalterBright 13y agoI didn't know it could do that. Thanks for the info.
- haberman 13y agoIf your software runs on OS X, try Instruments! It's free (comes with XCode) and has an Apple-quality UI.
- mrich 13y agoVtune and Zoom need to be mentioned, although they are not free. Vtune is even able to do power consumption analysis these days.
- aidenn0 13y agoA lot of people underestimate the performance impact of malloc(). It is dog slow. In addition if you use a poor malloc() implementation heavily with varying sized data, you can easily end up using more memory than had you used a copying GC!
- WalterBright 13y agoI've seen a number of compiler "benchmark" programs that inadvertently measured the performance of malloc, not the generated code.
- wicknicks 13y agoVery interesting. Do you have any URLs or papers that go into more depth regarding your statement?
- marshray 13y agomalloc() hasn't been a subject of interest to academics in many decades. This knowledge pre-dates the web in some cases. Do a web search for the replacement allocator used in Firefox. You'll probably find some good discussion there. Plus, every OS, C runtime, and usage pattern is different. YMMV massively depending on everything.
- scott_s 13y agoConcurrent memory allocation had some interest in the past decade - I did work in it, as did some others.
- haberman 13y agoNot only is it slow, many malloc() implementations (like even in glibc, I think) take a global lock, so they are prone to contention when called concurrently. Other mallocs (like tcmalloc and Hoard) satisfy small allocations from a thread-local pool.
- scott_s 13y ago
- gridspy 13y agoA massive advantage of your new linear allocator is that it keeps your memory access continuous. This means that the processor is more likely to have the most recently used memory locations already in cache. You might see further improvements if you split your allocations between two (or more) allocators. One for memory you expect to remain hot (core to the compiler) and one for stuff you think is one-off. That might improve access locality further.