Hacker News Reader

Comment by dgzxzgzx | Hacker News Reader

The level of optimization they are not doing must be staggering.

Not really. The two main reasons LLVM and gcc do a better optimization job is they have a better function inliner and loop unroller. Neither are particularly computation intensive.

DMD does all the usual data flow analysis optimizations - strength reduction, copy propagation, loop unrolling, dead store elimination, live range analysis, etc.

https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...

The optimizer / code generator is the same one that Digital Mars C++ uses, which was developed in the 1980's (!). Up until 2000 or so, the code generated was about the same as gcc, though DMC++ ran several times faster.

Since 2000, all my attention has been on the D front end, and so the optimizer wasn't getting the devoted attention it had earlier.

Just recently I finished converting the DMD optimizer from C to D, and am doing the code generator. This should make the code much more tractable.

Respectfully—and I truly mean this!—this is nowhere near enough to attain parity with GCC and LLVM. I don't see any SSA form, to name just one of many issues.

GCC 4.0, which introduced the SSA-based GIMPLE, was released in 2004, which is roughly around the same time you mentioned that the optimization quality started to diverge. This is not an accident. At the time, lots of compilers thought that they could continue to compete with GCC without doing SSA-based optimizations. GCC crushed them all one by one.

I forgot to add SROA to the list. DMD does a limited form of SROA I wrote as a proof of concept, it should be generalized.

https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...

I've also written a loop unroller, but it can be improved:

https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...

My evaluation was based on comparing the code gen output of the various compilers, not looking at how they were achieved.

As for SSA, DMD's optimizer is based on an intermediate representation that is a binary tree. A binary tree is a form of SSA - each operator node is a value assigned once and never modified.

> Respectfully

No worries. I'm used to people telling me I can't do things :-)

Is the intermediate representation documented/described somewhere?

"Use the Source, Luke!"

https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...

Well, I did look at it, but it was difficult to figure out how control-flow is structured. Is every “basic block” a single “el”, or is the CFG structured inside the binary tree? How are variables handled? Are there load expressions? Do you use something similar to phi-nodes to merge values from different branches? How do you do analysis? Do you walk over the expression tree and store the results (e.g. in constant propagation) on the nodes themselves? Do you use a separate cache/hashmap?

Basic blocks form a linked list (block*), and each basic block has a tree of elem's. Control flow is done with the basic block "predecessor" and "successor" lists.

We're doing tons of optimizations, trust me. :) Working on compile times is a constant, high-priority request from users. rustc is also a Rust project, and so we want Rust programs to compile faster too. It's just non-trivial. If you've got a suggestion to make rustc compile quickly with little effort, we're all ears!

D, on the other hand, was always designed for fast compilation (If I recall correctly), and so it compiles quickly. It's important to us, but not as important as other things. You can't be the best at every task, so you have to prioritize. For example, take two implementations of D: DMD and LDC. As I understand it, DMD uses its own codegen, so it compiles quickly, but produces slower binaries. LDC, based on LLVM, compiles more slowly, but produces faster binaries, for the exact same code. My understanding is that LDC is still faster to compile than rustc, but these are the kinds of tradeoffs you have to make.

As I replied in another comment, even C++ still compiles faster in non-template heavy code.

I can iterate faster in UWP, C++/CX projects than what it takes to compile my dummy Gtk-rs project from scratch.

The factors that affect it I guess are the incremental compiler and linker, binary libraries (which cargo doesn't support) and whatever the Pango bindings are doing during their compilation.

I think cargo supporting binaries and sharing build dependencies between projects (cf maven's .m2 directory) will mitigate a /lot/ of Rust's build time issues.

That only helps on the first build, really.

It brings the cost of trying an idea out down considerably. I've had a few times where I think "i know, I'll just try this idea out" and then I make a new project, add a few deps in Cargo.toml, hack some code, and then build. Oops, the first build takes half an hour. Then I think I should try new ideas out in Go or python. Alas.

That’s fair!

Also CI builds...

> even C++ still compiles faster in non-template heavy code.

But Rust is a template heavy language, and when it comes to compile time of template heave code, Rust is an order of magnitude faster than Clang in my experience (having worked a lot in and with Boost).

I have worked in many C++ codebases and compile-time was a problem _everywhere_, very probably the #1 problem. If you want to replace C++ you need to fix the most important problem. No it's not "safety".

I love how the ambiguity has caused BOTH compiler teams to comment on what they're optimizing.

Amusing anecdote - back in 1982, I took a 2 week compiler course from Hennessy and Ullman at Stanford. I decided to implement the data flow analysis techniques in my C compiler. It appeared as Datalight Optimum C.

The benchmarks used by the computer magazines were all dead code, and so the flow analysis deleted them. The journalists sadly concluded and wrote that DC was an utterly broken compiler :-(

This problem persisted until a year or two later when Borland and Microsoft caught up. They had much better marketing teams (!). The benchmarks got changed.

Well, at least today you'd be able to start a Twitter war and with a few strategically placed Reddit and HN posts you'd shame them into fixing their benchmarks :)

In those days, what could you do? Write a strongly worded letter to the editor? Have the magazine print a retraction two months later for their feature article? Not going to happen.

Reply on news.ycombinator.com