8 ms·

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

WalterBright 8y ago
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/dmc/gflow.d 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.
- pcwalton 8y ago
  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.
  - WalterBright 8y ago
    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/dmc/gsroa.d 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/dmc/gloop.d#L3759 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 :-)
    - judofyr 8y ago
      Is the intermediate representation documented/described somewhere?
      - WalterBright 8y ago
        "Use the Source, Luke!" https://github.com/DigitalMars/Compiler/blob/master/dm/src/dmc/el.d https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...
        judofyr 8y ago
        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?
        WalterBright 8y ago
        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.
veebat 8y ago
I love how the ambiguity has caused BOTH compiler teams to comment on what they're optimizing.
- WalterBright 8y ago
  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.
  - oblio 8y ago
    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 :)
    - WalterBright 8y ago
      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.
steveklabnik 8y ago
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.
- deleted 8y ago
  [deleted]
- pjmlp 8y ago
  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.
  - fnord123 8y ago
    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.
    - steveklabnik 8y ago
      That only helps on the first build, really.
      - 8y ago

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/dmc/gflow.d 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.

pcwalton 8y ago
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.
- WalterBright 8y ago
  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/dmc/gsroa.d 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/dmc/gloop.d#L3759 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 :-)
  - judofyr 8y ago
    Is the intermediate representation documented/described somewhere?
    - WalterBright 8y ago
      "Use the Source, Luke!" https://github.com/DigitalMars/Compiler/blob/master/dm/src/dmc/el.d https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...
      - judofyr 8y ago
        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?
        WalterBright 8y ago
        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.

veebat 8y ago

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

WalterBright 8y ago
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.
- oblio 8y ago
  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 :)
  - WalterBright 8y ago
    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.

steveklabnik 8y ago

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.

deleted 8y ago
[deleted]
pjmlp 8y ago
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.
- fnord123 8y ago
  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.
  - steveklabnik 8y ago
    That only helps on the first build, really.
    - 8y ago