Increasing the D Compiler Speed by Over 75%

<i>Time 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.</i><p>It&#x27;s been a long time since I&#x27;ve used gprof. I switched to Valgrind and OProfile about 10 years ago, and more recently to &#x27;perf&#x27; and &#x27;likwid&#x27;. 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.<p>Are there benefits to gprof that I&#x27;ve forgotten?<p>Are there newer and better profiling tools I don&#x27;t know about?

This article chronicles some fun I had boosting DMD&#x27;s speed by doing some simple changes.

Have 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&#x27;ve had success for small collections using arrays and performing linear search. This technique is used in Redis (see <a href="http://redis.io/topics/memory-optimization" rel="nofollow">http:&#x2F;&#x2F;redis.io&#x2F;topics&#x2F;memory-optimization</a>)

A 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!

I wondered why you don&#x27;t store the reciprocal w&#x2F; the hash table object. Obviously it wastes some space, but it wouldn&#x27;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&#x27;d use your code).

Changing the modulus to use known constants is an awesome trick! Great read

Walter, could you explain why lexing was a bottleneck? That&#x27;s very surprising to me. You don&#x27;t re-lex template instantiations do you?

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

Does your compiler perform any transformations at all? I imagine it can run out of memory pretty quickly if you&#x27;re performing multiple transformations in succession on large code base, unless you recycle some of those used memory.<p>Granted...since you explicitly stated that your compiler focused on compile speed, I guess optimized code generation isn&#x27;t your main concern, since the two are more or less mutually exclusive.