12 ms·

&& operator chains (and ||, possibly) generates unoptimizable LLVM IR

228 points by est31 6y ago

api 6y ago
Rust is already very close to C and C++ performance, and getting to equivalence or possibly better will mean a long slog through these kinds of edge cases. This was already done in C and C++ compiler toolchains, which is why these languages are so fast, and it's a bit of a feedback loop because their popularity and centrality to systems development is what led to the work being done in the first place. Rust + LLVM will already handily beat a naive bare bones C or C++ compiler that isn't loaded with sophisticated optimization tricks. If the work is done I expect Rust to be faster than C and C++ for the same reason that C++ can sometimes be faster than C: a more advanced type system can allow better optimization in many cases. In C++ for example you can do algorithms with templates, while in C you generally end up with function pointers all over the place. See qsort() vs. std::sort<> for one common case. With Rust you can do all this generic stuff plus leverage better safety to do more strict aliasing optimizations, less unnecessary memory fencing, and so on.
- killercup 6y ago
  > If the work is done I expect Rust to be faster than C and C++ for the same reason that C++ can sometimes be faster than C: a more advanced type system can allow better optimization in many cases. Every now and then I check in on whether LLVM can deal with rustc spamming "noalias" on all references. You can find the latest change in [1]. While in theory this unlocks _a ton_ of optimizations, noalias is used very rarely in C/C++ code so these compiler passes are not exercised a lot by existing LLVM tests and/or not realized in full. [1] https://github.com/rust-lang/rust/pull/82834 https://github.com/rust-lang/rust/pull/82834
  - api 6y ago
    This is why I think Rust could eventually be faster than C and C++ for a lot of things. The work has to be done though. You're right that noalias enabled optimizations are neglected because you can rarely use them in C code. On the Rust side I think the language needs some way to annotate if's as likely/unlikely. This doesn't matter in most cases but can occasionally matter a lot in tight high performance code. It can allow the compiler to emit code that is structured so as to cause the branch predictor to usually be right, which can have a large impact.
    - steveklabnik 6y ago
      That's tracked by https://github.com/rust-lang/rust/issues/26179 https://github.com/rust-lang/rust/issues/26179 by the way.
    - drran 6y ago
      Why not just use PGO (Profile Guided Optimizations)? Sadly, PGO does not work with cross-language LTO, because of conflict of LLVM module name ('Profile').
  - deleted 6y ago
    [deleted]
  - amelius 6y ago
    A more advanced type system may also drive you into a corner where you make bad decisions wrt performance.
    - titzer 6y ago
      Can you give an example?
      - Arnavion 6y ago
        Not amelius, but one case that happened to me is that Rust requires wrapping a `T` in a `RefCell` if two closures use it as `&mut T`. This happens even if you the caller know that the closures are invoked from a single thread and do not invoke each other, and thus only one `&mut T` will be in effect at any time. This is because closures are effectively structs with the captures as fields, so both struct values (and thus both `&mut` borrows) exist at the same time even though their respective fields are not used at the same time. Not only do you have to use `RefCell`, but you now also have panicking code when the `RefCell` borrow "fails", even though you know it can't. rustc is also not smart enough to notice the exclusivity at compile-time and elid away the RefCell borrow flag test and the panic branch. fn foo(mut cb1: impl FnMut(), mut cb2: impl FnMut()) { for _ in 0..10 { cb1(); cb2(); } } let mut x = String::new(); foo(|| x.push_str("cb1,"), || x.push_str("cb2,")); https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=9b3aaad390070ffa3dcd0420203a0833 https://play.rust-lang.org/?version=stable&mode=debug&editio... Fixed using `RefCell`: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=b1d8781fc5d5962a40c485b3b148ff2d https://play.rust-lang.org/?version=stable&mode=release&edit... . Inspect the ASM and trace the use of the string constant "already borrowed"; you'll see it being used for the borrow flag test because it wasn't elided. The equivalent non-Rust program could use String pointers for the two closures. I'm not sure whether they could be noalias or not, but at the very least they wouldn't need to generate any panicking code.
        Diggsey 6y ago
        The "used from a single thread" aspect is a red herring: RefCell can only be used from a single thread anyway, and the compiler enforces this statically. The "state" value in a RefCell is overhead, although it's fairly minor given that it doesn't need any synchronization to access. The extra panic branches are probably the largest overhead. That said, these overheads stem from Rust's safety guarantees rather than its strong type system: you can have a language with a strong type system that does not do these checks. Furthermore, there are of course ways to avoid this overhead within safe Rust: if you can use the type system to prove that the cell cannot be borrowed at the same time, then you don't need to do the checks, and in that sense a strong type system can actually help avoid overheads that were introduced by being a safe language.
- MaxBarraclough 6y ago
  I think Ada/GNAT performs roughly on par with C and C++, so we have reason to be optimistic. It's not just the dominant languages that end up with mature optimizing compilers.
  - pjmlp 6y ago
    Having been there when C compilers used to generate lousy code and we had legends like Mike Abrash teaching an whole industry how to write high performance Assembly, it always feels ironic that there is this myth about C and C++ being blazing fast since they were created.
    - mids_hn 6y ago
      C was fast. On a PDP-11.
    - anthk 6y ago
      C++ was always taken as big, bloated and unusable compared to C.
      - pjmlp 6y ago
        Only by C developers that still believe C generates faster code than C++, while their beloved C compiler has been rewritten in C++.
        anthk 6y ago
        gcc is not my daily compiler.
        pjmlp 6y ago
        I found another tinyc user.
        bcrl 6y ago
        That's not what I believe. C generates the code I expect, rather than the insanely bloated crap that comes out of C++. C++ obfuscates what is actually going on. Oh, and then there are all the problems with the C++ standard library. It's unusable in high performance embedded style code due to many aspects of the standard library being unconstrained - things like memory allocations and unspecified complexity. In some cases we were able to use boost, but in many cases we had to reimplement many algorithms where the implementation performed allocations at init time, and no allocs at runtime. But oh how does an event driven, multithreaded and hot running messaging system go fast...
- gnulinux 6y ago
  I write compilers for fun (hobby) and I just transpile my IR data structure to C++ (I'm also experimenting with other targets like Haskell (similar to agda compiler) and Rust (work in progress)). My friends usually treat this approach "too amateur" and a "real language" should compile all the way to assembly. The reason I don't do that is if you transpile to a well-known language and then manage that compiler to go all the way to machine code, you get insane amount of optimizations for free. Like C++ compilers are so good, you rarely need think about low-level optimizations, as long as your program is asymptotically sound (i.e. you don't keep random inserting into an array) it gives pretty good performance regardless.
  - Flow 6y ago
    But then you miss all the fun with doing a nanopass compiler. Maybe that's not entirely true though, you can still generate C/C++ in the end I guess.
  - zokier 6y ago
    Nim compiler also generates C, so I'd say you are in pretty good company there.
    - Blikkentrekker 6y ago
      The Idris 2 compiler compiles to Chez Scheme; the Idris 1 compiler compiled to C, and the former actually produces significantly faster executables than the latter. I sometimes see programmers have very strange, irrational purity misgivings a particular case was someone who did not wish to fork off `grep` for some task, but actually wrote his own implementation which broke input into lines and used and manually searched for substrings; — he was initially convinced that this would be faster, or was at least “cleaner” than simply forking off `grep`, and piping to it. The reality is that modern `grep` implementations are so optimized that writing something that was as efficient would probably exceed the complexity of his entire project. I have never understood why many programmers seem to have an irrational dislike against forking off POSIX utilities when they target such platforms, and piping through them, which are often far more optimized than anything they've ever written.
- mhh__ 6y ago
  I'm a little suspect of the "Language x is faster than language y" talk - it seems too prone to programmer culture to test scientifically, beyond being able to prove that you can or can't end up with the same machine code from multiple languages.
  - Sohcahtoa82 6y ago
    And you can almost always write a program that executes faster in a "slower" language than a "faster" one.
- nwallin 6y ago
  > Rust + LLVM will already handily beat a naive bare bones C or C++ compiler that isn't loaded with sophisticated optimization tricks. Well - sure. LLVM is loaded with sophisticated optimization tricks. If one compiler does sophisticated optimization tricks and the other compiler doesn't do sophisticated optimization tricks, the compiler with the sophisticated optimization tricks will be faster. Tangent: Ten years ago or so, LLVM/Clang was touted as being head and shoulders better than GCC, the big new thing, the bees knees. Some of how it was better was obvious to everyone- readable error messages are pretty awesome. (GCC stole that idea pretty quickly) But the big thing that the LLVM/Clang people talked about was how blazingly fast compilation was compared to GCC. It was normal to take 1/10th as long to compile something. The code didn't run as fast as the code generated by GCC, maybe 50% of the performance, but that was a problem that they would eventually fix with more sophisticated optimizers. But compilation was fast! Here we are ten years later, and LLVM/Clang generates code that runs almost as quickly as GCC. What did it cost, besides ten years of incrementally making the optimizer more and more sophisticated, a little bit better one little bit at a time? Well, it takes just as long to compile something with LLVM's sophisticated optimizer as it does to compile something with GCC's sophisticated optimizer. The point is, there's a lot of yak shaving that will have to go into making Rust+LLVM work together better. And LLVM is already well acquainted with the barber. The low hanging fruit you're looking for has already been plucked.
  - throwaway894345 6y ago
    It’s been a a bit since I was a C++ developer, but didn’t LLVM spur GCC on to improve significantly? Maybe LLVM and GCC are pretty comparable today with respect to build time and performance, but I think the more interesting question is how LLVM compares to GCC ten years ago (or more precisely, where GCC would be today were it not for competition from LLVM). Personally I’m glad there are multiple options, and people seem to prefer using LLVM for a language backend more than GCC for whatever reason, so it seems like a significant contribution to our digital society.
    - nwallin 6y ago
      Hard to say. In some places it's clear: LLVM's error messages were head and shoulders better than GCC's, and it was immediately obvious to everyone that GCC had to improve. And they're much better now. But I don't believe GCC has made substantial improvements to its compilation speed since LLVM was introduced. In fact I believe it to be the opposite; as a Gentoo user I generally notice that compilation performance gets worse with every major GCC update. It's only due to hardware upgrades that compilation gets shorter. LLVM is inherently much more modular than GCC is, which makes it a very attractive target for a language backend. It's a very large amount of work to shoehorn a language into GCC. The modular nature of LLVM is quite useful for lots of purposes, it is the back end for the syntax highlighting and error highlighting module I use in emacs. clang-format is a godsend for me, and unlike most other autoformatters, it formats based on semantics instead of syntax, which is a huge boon. The static analyzer and llvm-mca are also closely tied to the modularity of LLVM. It's not immediately obvious how one might implement these features based on GCC. So yes, I 100% agree that LLVM is a hugely beneficial contribution to our digital society, even though it's not my first choice for a compiler.
wyldfire 6y ago
Interesting investigation. But it sounds like the discssion revealed that this may be "just" a regression.
- losvedir 6y ago
  A regression when the LLVM backend updated from 8 to 9. So arguably a regression in LLVM! Reminds me of a Zig stream I watched recently where Andy was updating the compiler backend to use an LLVM 12 release candidate. He ended up filling a couple bug reports with LLVM, using Zig compiler issues to generate reduced case LLVM IR examples that compiled differently with LLVM 11. He mentioned that he had to try this upgrade with the release candidate because right now they're LLVM regressions, but once 12 ships they become Zig regressions!
  - jedisct1 6y ago
    Zig does a really good job at finding bugs in LLVM every time the LLVM version is updated. And Zig developers also do a very good job at reporting and fixing them. Which is why contributing to Zig also means contributing to LLVM.
    - rob74 6y ago
      Language developers finding bugs in LLVM is ok, but if there are already several instances of regressions in LLVM found by developers of (maybe "exotic") languages, then the reaction should be less "hey, well done, you found a bug" and more "how can we avoid such regressions in the future?"...
      - MaxBarraclough 6y ago
        I imagine Clang and GCC have growing test-suites to defend against regressions. I wonder if they share them.
        wyldfire 6y ago
        They both do, yes. LLVM's [1] includes (some of?) gcc's, the reverse may also be true. LLVM also has extensive unit tests that can exercise codegen and backend functionality. [1] https://github.com/llvm/llvm-test-suite https://github.com/llvm/llvm-test-suite
kazinator 6y ago
This stuff is fun. In the TXR Lisp compiler was running into pattern matching code refusing to optimize nicely. My test case was this Ackermann: (defun ack (:match) ((0 @n) (+ n 1)) ((@m 0) (ack (- m 1) 1)) ((@m @n) (ack (- m 1) (ack m (- n 1))))) I then added an "early peephole" pass which works on the input code before it has been divided into basic blocks: http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/optimize.tl?h=txr-255#n588 http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/optimi... (function at line 588) There, I added recognition for a certain four-instruction kernel occurring out of pattern matching code, and rewrote it to three instructions. Poof; I was left rubbing my eyes as out popped an instruction sequence identical to the one for this non-pattern-matching Ackermann, modulo some register names: (defun ack (m n) (cond ((eq m 0) (+ n 1)) ((eq n 0) (ack (- m 1) 1)) (t (ack (- m 1) (ack m (- n 1)))))) That early reduction kind of removed a logjam, allowing other optimizations to proceed. The pattern matching code generates a flag which is set true upon matching, so that subsequent cases are skipped. This flag completely disappears. The recognized instruction pattern spans (what would be) two basic blocks because it includes a jmp instruction. The rewritten instruction sequence eliminates one conditional branch, which gets rid of a basic block division, which is part of why it works. Anyway, a big picture lesson here is that a big reason for the existence of pattern matching is so that so you have a tool that can be applied to optimize pattern matching.
- kazinator 6y ago
  This is more related to the story than meets the eye. early-peephole matches a pattern that will span two basic blocks if it is not replaced. The rewrite removes a conditional which tests a temporary flag; that test ends up in a basic block by itself: (defun early-peephole (code) (rewrite-case insns code (((mov (t @t1) (d @d1)) (jmp @lab2) @(symbolp @lab1) (mov (t @t1) (t 0)) A label is matched (backreferencing the earlier (jmp @lab2), so we know this item must be a label) followed by an ifq: @lab2 (ifq (t @t1) (t 0) @lab3) and so the above label and ifq form a basic block which does nothing more than tests a register to go somewhere else: the following code or some lab3 elsewhere. This is very reminiscent to the numerous temporary-testing basic blocks shown the messy "unoptimizable" flow graph in the submission. . @rest) ^((mov (t ,t1) (d ,d1)) (jmp ,lab3) ,lab1 (mov (t ,t1) (t 0)) ,lab2 ,*rest)) In the rewritten pattern, that ifq is gone. If we look at the diagram in the submission: some things are striking. For instance, have a basic block 14: bb14: fill temp5 with false And another one: bb13: fill temp5 with true Both of these jumps unconditionally to bb16: check temp5 The situation tested by my pattern above is exactly this sort of thing. E.g. if we look at the pattern matching ack without optimization, we can find them: 2> (disassemble (let ((*opt-level* 0)) (compile 'ack))) data: 0: ack 1: 0 2: 1 3: t Note 3: t means that in this VM description, register d3 holds t, the canonical Boolean true symbol: [ snip ] 31: 2C060403 movsr t6 d3 32: 34000022 jmp 34 33: 2C060000 movsr t6 nil 34: 10000006 end t6 35: 3C000036 ifq t6 nil 54 Here is an instance of the pattern. Except for the "end t6" has to do with closing a "frame ..." instruction earlier. We don't see this "end t6" in the pattern, and so it would cause a mismatch; but this instruction is removed by frame elimination, which is earlier in the compiler and happens at a lower optimization level. So then, what do we have here? basic block A: "fill temp6 with true, jump to C" 31: 2C060403 movsr t6 d3 32: 34000022 jmp 34 basic block B: "fill temp6 with false, fall to C" 33: 2C060000 movsr t6 nil basic block C: "check temp6" 34: 10000006 end t6 35: 3C000036 ifq t6 nil 54 That very similar that aforementioned situation in that basic block diagram! In my case, what breaks the logjam is that we get rid of the check, because the pattern knows that the check is only being reached from those two sources. And then, register t6 succumbs to dead register removal. A subsequent data flow analysis, done after flow control optimizations (jump threading) discovers that these definitions of the t6 value have no next use. I think that thanks to work done since then, that early-peephole thing could be moved into jump threading. There could be jump threading patterns which infer that the target of a jump is a conditional instruction which depends on the value of a register which is set to a true/false value prior to the jump, and then adjust the original jump. It's more general, but more annoying to code because of pattern matching across multiple discontinuous basic blocks.
quiescant_dodo 6y ago
This is a phenomenal bug report.
- mhh__ 6y ago
  I reserve a different term for bugs where the backend is actually wrong (e.g. emitting the wrong SIMD instruction was a fun one)!
adwn 6y ago
Whenever someone repeats the tired meme of "the compiler generates better assembly code than a human", I think of cases like this one (or the many occasions where I inspected compiler-generated assembly and it was atrocious). The rule of thumb should be "the compiler generates better assembly code than a human could within the time it takes to write high-level code and press 'Build project'", but that's not as catchy.
- theamk 6y ago
  Your rule is much weaker to the point of being useless -- you are claiming that if it took me 1 hour to write high-level code, the compiler will generate better assembly code than what I can write in 1 hour. This is obviously true in most cases -- if it takes me an hour to write task X in high-level language, it will probably take me a day or more to write it in assembly. After spending only one hour on assembly version the program will be nowhere close to completion, and likely completely non-functional. So whatever compiler produces will be much better -- it will at least work. I can believe that at some moment hand-rolled assembly will "beat" generated code (I am pretty sure that if someone spends a month optimizing assembly listing it will beat the best Rust program written in a hour), but I am not sure what the ratio is. I am sure it is not 1:1, and I suspect the ratio gets worse as program grows and there are more parts that one needs to keep track of.
  - adwn 6y ago
    > Your rule is much weaker to the point of being useless Yes, it's much weaker, but it's not useless. The vast majority of code in a program does not need to be as fast as it could possibly be [1], so there's no point in manually implementing everything in assembly. That doesn't mean that it never makes sense to manually implement something in assembly for performance reasons. [1] And for many programs, all the code does not need to be as fast as it could possibly be.
    - theamk 6y ago
      Right, but I called the rules "useless" because it does not tell you any actionable info -- and this is normally expected of rules. Here is a fixed version (note I added "times 20" at the end): "the compiler generates better assembly code than a human could within the time it takes to write high-level code times 20" See -- now I can make predictions. Let's say you have a function that you want to make fast, and you want to optimize it in assembly. The function took 30 minutes to write and debug. Do you have 10 hours to spare? Try assembly. No time? Leave as-is. Much more useful this way, no?
unwind 6y ago
Meta: odd typo in the title, "-|" should just be "||".
- est31 6y ago
  I copy pasted the title from Github. I think the mismatch is caused by hn's headline mangling? I can't edit it any more, but an admin like dang could maybe correct it.
ashton314 6y ago
Wow! What a write-up! I appreciate the liberal use of the summary/details tags. Really helps things stay readable. Curious: is there a Markdown exporter that supports some syntax for this?
- est31 6y ago
  The details tag is just html that you can fall back to in markdown: https://developer.mozilla.org/de/docs/Web/HTML/Element/details https://developer.mozilla.org/de/docs/Web/HTML/Element/detai... The main contribution by Github's markdown renderer is that it doesn't remove that tag.
  - franga2000 6y ago
    But how do they put code tags in there? Last time I checked, Markdown doesn't allow Markdown inside HTML tags. Or do they just wrap it in <code><pre> and the syntax highlighter picks it up later in the chain?
    - arthur2e5 6y ago
      Markdown inside HTML tags is fine as long as there's a paragraph break (two newlines) between the Markdown and the HTML tag. So it usually goes like: <detail> <summary>...</summary> Some `markdown` </detail> I would imagine this sort of behavior is in commonmark, but I am too lazy to check.
barbazoo 6y ago
That is one well written Github issue!
lilyball 6y ago
I’m really impressed by the diagrams (and they’re vertical so they’re mobile-friendly too!), how were they generated?
- monowii 6y ago
  I think they used Graphviz: https://graphviz.org/ https://graphviz.org/

228 points by est31 6y ago

api 6y ago

Rust is already very close to C and C++ performance, and getting to equivalence or possibly better will mean a long slog through these kinds of edge cases. This was already done in C and C++ compiler toolchains, which is why these languages are so fast, and it's a bit of a feedback loop because their popularity and centrality to systems development is what led to the work being done in the first place. Rust + LLVM will already handily beat a naive bare bones C or C++ compiler that isn't loaded with sophisticated optimization tricks. If the work is done I expect Rust to be faster than C and C++ for the same reason that C++ can sometimes be faster than C: a more advanced type system can allow better optimization in many cases. In C++ for example you can do algorithms with templates, while in C you generally end up with function pointers all over the place. See qsort() vs. std::sort<> for one common case. With Rust you can do all this generic stuff plus leverage better safety to do more strict aliasing optimizations, less unnecessary memory fencing, and so on.

killercup 6y ago
> If the work is done I expect Rust to be faster than C and C++ for the same reason that C++ can sometimes be faster than C: a more advanced type system can allow better optimization in many cases. Every now and then I check in on whether LLVM can deal with rustc spamming "noalias" on all references. You can find the latest change in [1]. While in theory this unlocks _a ton_ of optimizations, noalias is used very rarely in C/C++ code so these compiler passes are not exercised a lot by existing LLVM tests and/or not realized in full. [1] https://github.com/rust-lang/rust/pull/82834 https://github.com/rust-lang/rust/pull/82834
- api 6y ago
  This is why I think Rust could eventually be faster than C and C++ for a lot of things. The work has to be done though. You're right that noalias enabled optimizations are neglected because you can rarely use them in C code. On the Rust side I think the language needs some way to annotate if's as likely/unlikely. This doesn't matter in most cases but can occasionally matter a lot in tight high performance code. It can allow the compiler to emit code that is structured so as to cause the branch predictor to usually be right, which can have a large impact.
  - steveklabnik 6y ago
    That's tracked by https://github.com/rust-lang/rust/issues/26179 https://github.com/rust-lang/rust/issues/26179 by the way.
  - drran 6y ago
    Why not just use PGO (Profile Guided Optimizations)? Sadly, PGO does not work with cross-language LTO, because of conflict of LLVM module name ('Profile').
- deleted 6y ago
  [deleted]
- amelius 6y ago
  A more advanced type system may also drive you into a corner where you make bad decisions wrt performance.
  - titzer 6y ago
    Can you give an example?
    - Arnavion 6y ago
      Not amelius, but one case that happened to me is that Rust requires wrapping a `T` in a `RefCell` if two closures use it as `&mut T`. This happens even if you the caller know that the closures are invoked from a single thread and do not invoke each other, and thus only one `&mut T` will be in effect at any time. This is because closures are effectively structs with the captures as fields, so both struct values (and thus both `&mut` borrows) exist at the same time even though their respective fields are not used at the same time. Not only do you have to use `RefCell`, but you now also have panicking code when the `RefCell` borrow "fails", even though you know it can't. rustc is also not smart enough to notice the exclusivity at compile-time and elid away the RefCell borrow flag test and the panic branch. fn foo(mut cb1: impl FnMut(), mut cb2: impl FnMut()) { for _ in 0..10 { cb1(); cb2(); } } let mut x = String::new(); foo(|| x.push_str("cb1,"), || x.push_str("cb2,")); https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=9b3aaad390070ffa3dcd0420203a0833 https://play.rust-lang.org/?version=stable&mode=debug&editio... Fixed using `RefCell`: https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=b1d8781fc5d5962a40c485b3b148ff2d https://play.rust-lang.org/?version=stable&mode=release&edit... . Inspect the ASM and trace the use of the string constant "already borrowed"; you'll see it being used for the borrow flag test because it wasn't elided. The equivalent non-Rust program could use String pointers for the two closures. I'm not sure whether they could be noalias or not, but at the very least they wouldn't need to generate any panicking code.
      - Diggsey 6y ago
        The "used from a single thread" aspect is a red herring: RefCell can only be used from a single thread anyway, and the compiler enforces this statically. The "state" value in a RefCell is overhead, although it's fairly minor given that it doesn't need any synchronization to access. The extra panic branches are probably the largest overhead. That said, these overheads stem from Rust's safety guarantees rather than its strong type system: you can have a language with a strong type system that does not do these checks. Furthermore, there are of course ways to avoid this overhead within safe Rust: if you can use the type system to prove that the cell cannot be borrowed at the same time, then you don't need to do the checks, and in that sense a strong type system can actually help avoid overheads that were introduced by being a safe language.
MaxBarraclough 6y ago
I think Ada/GNAT performs roughly on par with C and C++, so we have reason to be optimistic. It's not just the dominant languages that end up with mature optimizing compilers.
- pjmlp 6y ago
  Having been there when C compilers used to generate lousy code and we had legends like Mike Abrash teaching an whole industry how to write high performance Assembly, it always feels ironic that there is this myth about C and C++ being blazing fast since they were created.
  - mids_hn 6y ago
    C was fast. On a PDP-11.
  - anthk 6y ago
    C++ was always taken as big, bloated and unusable compared to C.
    - pjmlp 6y ago
      Only by C developers that still believe C generates faster code than C++, while their beloved C compiler has been rewritten in C++.
      - anthk 6y ago
        gcc is not my daily compiler.
        pjmlp 6y ago
        I found another tinyc user.
      - bcrl 6y ago
        That's not what I believe. C generates the code I expect, rather than the insanely bloated crap that comes out of C++. C++ obfuscates what is actually going on. Oh, and then there are all the problems with the C++ standard library. It's unusable in high performance embedded style code due to many aspects of the standard library being unconstrained - things like memory allocations and unspecified complexity. In some cases we were able to use boost, but in many cases we had to reimplement many algorithms where the implementation performed allocations at init time, and no allocs at runtime. But oh how does an event driven, multithreaded and hot running messaging system go fast...
gnulinux 6y ago
I write compilers for fun (hobby) and I just transpile my IR data structure to C++ (I'm also experimenting with other targets like Haskell (similar to agda compiler) and Rust (work in progress)). My friends usually treat this approach "too amateur" and a "real language" should compile all the way to assembly. The reason I don't do that is if you transpile to a well-known language and then manage that compiler to go all the way to machine code, you get insane amount of optimizations for free. Like C++ compilers are so good, you rarely need think about low-level optimizations, as long as your program is asymptotically sound (i.e. you don't keep random inserting into an array) it gives pretty good performance regardless.
- Flow 6y ago
  But then you miss all the fun with doing a nanopass compiler. Maybe that's not entirely true though, you can still generate C/C++ in the end I guess.
- zokier 6y ago
  Nim compiler also generates C, so I'd say you are in pretty good company there.
  - Blikkentrekker 6y ago
    The Idris 2 compiler compiles to Chez Scheme; the Idris 1 compiler compiled to C, and the former actually produces significantly faster executables than the latter. I sometimes see programmers have very strange, irrational purity misgivings a particular case was someone who did not wish to fork off `grep` for some task, but actually wrote his own implementation which broke input into lines and used and manually searched for substrings; — he was initially convinced that this would be faster, or was at least “cleaner” than simply forking off `grep`, and piping to it. The reality is that modern `grep` implementations are so optimized that writing something that was as efficient would probably exceed the complexity of his entire project. I have never understood why many programmers seem to have an irrational dislike against forking off POSIX utilities when they target such platforms, and piping through them, which are often far more optimized than anything they've ever written.
mhh__ 6y ago
I'm a little suspect of the "Language x is faster than language y" talk - it seems too prone to programmer culture to test scientifically, beyond being able to prove that you can or can't end up with the same machine code from multiple languages.
- Sohcahtoa82 6y ago
  And you can almost always write a program that executes faster in a "slower" language than a "faster" one.
nwallin 6y ago
> Rust + LLVM will already handily beat a naive bare bones C or C++ compiler that isn't loaded with sophisticated optimization tricks. Well - sure. LLVM is loaded with sophisticated optimization tricks. If one compiler does sophisticated optimization tricks and the other compiler doesn't do sophisticated optimization tricks, the compiler with the sophisticated optimization tricks will be faster. Tangent: Ten years ago or so, LLVM/Clang was touted as being head and shoulders better than GCC, the big new thing, the bees knees. Some of how it was better was obvious to everyone- readable error messages are pretty awesome. (GCC stole that idea pretty quickly) But the big thing that the LLVM/Clang people talked about was how blazingly fast compilation was compared to GCC. It was normal to take 1/10th as long to compile something. The code didn't run as fast as the code generated by GCC, maybe 50% of the performance, but that was a problem that they would eventually fix with more sophisticated optimizers. But compilation was fast! Here we are ten years later, and LLVM/Clang generates code that runs almost as quickly as GCC. What did it cost, besides ten years of incrementally making the optimizer more and more sophisticated, a little bit better one little bit at a time? Well, it takes just as long to compile something with LLVM's sophisticated optimizer as it does to compile something with GCC's sophisticated optimizer. The point is, there's a lot of yak shaving that will have to go into making Rust+LLVM work together better. And LLVM is already well acquainted with the barber. The low hanging fruit you're looking for has already been plucked.
- throwaway894345 6y ago
  It’s been a a bit since I was a C++ developer, but didn’t LLVM spur GCC on to improve significantly? Maybe LLVM and GCC are pretty comparable today with respect to build time and performance, but I think the more interesting question is how LLVM compares to GCC ten years ago (or more precisely, where GCC would be today were it not for competition from LLVM). Personally I’m glad there are multiple options, and people seem to prefer using LLVM for a language backend more than GCC for whatever reason, so it seems like a significant contribution to our digital society.
  - nwallin 6y ago
    Hard to say. In some places it's clear: LLVM's error messages were head and shoulders better than GCC's, and it was immediately obvious to everyone that GCC had to improve. And they're much better now. But I don't believe GCC has made substantial improvements to its compilation speed since LLVM was introduced. In fact I believe it to be the opposite; as a Gentoo user I generally notice that compilation performance gets worse with every major GCC update. It's only due to hardware upgrades that compilation gets shorter. LLVM is inherently much more modular than GCC is, which makes it a very attractive target for a language backend. It's a very large amount of work to shoehorn a language into GCC. The modular nature of LLVM is quite useful for lots of purposes, it is the back end for the syntax highlighting and error highlighting module I use in emacs. clang-format is a godsend for me, and unlike most other autoformatters, it formats based on semantics instead of syntax, which is a huge boon. The static analyzer and llvm-mca are also closely tied to the modularity of LLVM. It's not immediately obvious how one might implement these features based on GCC. So yes, I 100% agree that LLVM is a hugely beneficial contribution to our digital society, even though it's not my first choice for a compiler.

wyldfire 6y ago

Interesting investigation. But it sounds like the discssion revealed that this may be "just" a regression.

losvedir 6y ago
A regression when the LLVM backend updated from 8 to 9. So arguably a regression in LLVM! Reminds me of a Zig stream I watched recently where Andy was updating the compiler backend to use an LLVM 12 release candidate. He ended up filling a couple bug reports with LLVM, using Zig compiler issues to generate reduced case LLVM IR examples that compiled differently with LLVM 11. He mentioned that he had to try this upgrade with the release candidate because right now they're LLVM regressions, but once 12 ships they become Zig regressions!
- jedisct1 6y ago
  Zig does a really good job at finding bugs in LLVM every time the LLVM version is updated. And Zig developers also do a very good job at reporting and fixing them. Which is why contributing to Zig also means contributing to LLVM.
  - rob74 6y ago
    Language developers finding bugs in LLVM is ok, but if there are already several instances of regressions in LLVM found by developers of (maybe "exotic") languages, then the reaction should be less "hey, well done, you found a bug" and more "how can we avoid such regressions in the future?"...
    - MaxBarraclough 6y ago
      I imagine Clang and GCC have growing test-suites to defend against regressions. I wonder if they share them.
      - wyldfire 6y ago
        They both do, yes. LLVM's [1] includes (some of?) gcc's, the reverse may also be true. LLVM also has extensive unit tests that can exercise codegen and backend functionality. [1] https://github.com/llvm/llvm-test-suite https://github.com/llvm/llvm-test-suite

kazinator 6y ago

This stuff is fun. In the TXR Lisp compiler was running into pattern matching code refusing to optimize nicely. My test case was this Ackermann: (defun ack (:match) ((0 @n) (+ n 1)) ((@m 0) (ack (- m 1) 1)) ((@m @n) (ack (- m 1) (ack m (- n 1))))) I then added an "early peephole" pass which works on the input code before it has been divided into basic blocks: http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/optimize.tl?h=txr-255#n588 http://www.kylheku.com/cgit/txr/tree/share/txr/stdlib/optimi... (function at line 588) There, I added recognition for a certain four-instruction kernel occurring out of pattern matching code, and rewrote it to three instructions. Poof; I was left rubbing my eyes as out popped an instruction sequence identical to the one for this non-pattern-matching Ackermann, modulo some register names: (defun ack (m n) (cond ((eq m 0) (+ n 1)) ((eq n 0) (ack (- m 1) 1)) (t (ack (- m 1) (ack m (- n 1)))))) That early reduction kind of removed a logjam, allowing other optimizations to proceed. The pattern matching code generates a flag which is set true upon matching, so that subsequent cases are skipped. This flag completely disappears. The recognized instruction pattern spans (what would be) two basic blocks because it includes a jmp instruction. The rewritten instruction sequence eliminates one conditional branch, which gets rid of a basic block division, which is part of why it works. Anyway, a big picture lesson here is that a big reason for the existence of pattern matching is so that so you have a tool that can be applied to optimize pattern matching.

kazinator 6y ago
This is more related to the story than meets the eye. early-peephole matches a pattern that will span two basic blocks if it is not replaced. The rewrite removes a conditional which tests a temporary flag; that test ends up in a basic block by itself: (defun early-peephole (code) (rewrite-case insns code (((mov (t @t1) (d @d1)) (jmp @lab2) @(symbolp @lab1) (mov (t @t1) (t 0)) A label is matched (backreferencing the earlier (jmp @lab2), so we know this item must be a label) followed by an ifq: @lab2 (ifq (t @t1) (t 0) @lab3) and so the above label and ifq form a basic block which does nothing more than tests a register to go somewhere else: the following code or some lab3 elsewhere. This is very reminiscent to the numerous temporary-testing basic blocks shown the messy "unoptimizable" flow graph in the submission. . @rest) ^((mov (t ,t1) (d ,d1)) (jmp ,lab3) ,lab1 (mov (t ,t1) (t 0)) ,lab2 ,*rest)) In the rewritten pattern, that ifq is gone. If we look at the diagram in the submission: some things are striking. For instance, have a basic block 14: bb14: fill temp5 with false And another one: bb13: fill temp5 with true Both of these jumps unconditionally to bb16: check temp5 The situation tested by my pattern above is exactly this sort of thing. E.g. if we look at the pattern matching ack without optimization, we can find them: 2> (disassemble (let ((*opt-level* 0)) (compile 'ack))) data: 0: ack 1: 0 2: 1 3: t Note 3: t means that in this VM description, register d3 holds t, the canonical Boolean true symbol: [ snip ] 31: 2C060403 movsr t6 d3 32: 34000022 jmp 34 33: 2C060000 movsr t6 nil 34: 10000006 end t6 35: 3C000036 ifq t6 nil 54 Here is an instance of the pattern. Except for the "end t6" has to do with closing a "frame ..." instruction earlier. We don't see this "end t6" in the pattern, and so it would cause a mismatch; but this instruction is removed by frame elimination, which is earlier in the compiler and happens at a lower optimization level. So then, what do we have here? basic block A: "fill temp6 with true, jump to C" 31: 2C060403 movsr t6 d3 32: 34000022 jmp 34 basic block B: "fill temp6 with false, fall to C" 33: 2C060000 movsr t6 nil basic block C: "check temp6" 34: 10000006 end t6 35: 3C000036 ifq t6 nil 54 That very similar that aforementioned situation in that basic block diagram! In my case, what breaks the logjam is that we get rid of the check, because the pattern knows that the check is only being reached from those two sources. And then, register t6 succumbs to dead register removal. A subsequent data flow analysis, done after flow control optimizations (jump threading) discovers that these definitions of the t6 value have no next use. I think that thanks to work done since then, that early-peephole thing could be moved into jump threading. There could be jump threading patterns which infer that the target of a jump is a conditional instruction which depends on the value of a register which is set to a true/false value prior to the jump, and then adjust the original jump. It's more general, but more annoying to code because of pattern matching across multiple discontinuous basic blocks.

quiescant_dodo 6y ago

This is a phenomenal bug report.

mhh__ 6y ago
I reserve a different term for bugs where the backend is actually wrong (e.g. emitting the wrong SIMD instruction was a fun one)!

adwn 6y ago

Whenever someone repeats the tired meme of "the compiler generates better assembly code than a human", I think of cases like this one (or the many occasions where I inspected compiler-generated assembly and it was atrocious). The rule of thumb should be "the compiler generates better assembly code than a human could within the time it takes to write high-level code and press 'Build project'", but that's not as catchy.

theamk 6y ago
Your rule is much weaker to the point of being useless -- you are claiming that if it took me 1 hour to write high-level code, the compiler will generate better assembly code than what I can write in 1 hour. This is obviously true in most cases -- if it takes me an hour to write task X in high-level language, it will probably take me a day or more to write it in assembly. After spending only one hour on assembly version the program will be nowhere close to completion, and likely completely non-functional. So whatever compiler produces will be much better -- it will at least work. I can believe that at some moment hand-rolled assembly will "beat" generated code (I am pretty sure that if someone spends a month optimizing assembly listing it will beat the best Rust program written in a hour), but I am not sure what the ratio is. I am sure it is not 1:1, and I suspect the ratio gets worse as program grows and there are more parts that one needs to keep track of.
- adwn 6y ago
  > Your rule is much weaker to the point of being useless Yes, it's much weaker, but it's not useless. The vast majority of code in a program does not need to be as fast as it could possibly be [1], so there's no point in manually implementing everything in assembly. That doesn't mean that it never makes sense to manually implement something in assembly for performance reasons. [1] And for many programs, all the code does not need to be as fast as it could possibly be.
  - theamk 6y ago
    Right, but I called the rules "useless" because it does not tell you any actionable info -- and this is normally expected of rules. Here is a fixed version (note I added "times 20" at the end): "the compiler generates better assembly code than a human could within the time it takes to write high-level code times 20" See -- now I can make predictions. Let's say you have a function that you want to make fast, and you want to optimize it in assembly. The function took 30 minutes to write and debug. Do you have 10 hours to spare? Try assembly. No time? Leave as-is. Much more useful this way, no?

unwind 6y ago

Meta: odd typo in the title, "-|" should just be "||".

est31 6y ago
I copy pasted the title from Github. I think the mismatch is caused by hn's headline mangling? I can't edit it any more, but an admin like dang could maybe correct it.

ashton314 6y ago

Wow! What a write-up! I appreciate the liberal use of the summary/details tags. Really helps things stay readable. Curious: is there a Markdown exporter that supports some syntax for this?

est31 6y ago
The details tag is just html that you can fall back to in markdown: https://developer.mozilla.org/de/docs/Web/HTML/Element/details https://developer.mozilla.org/de/docs/Web/HTML/Element/detai... The main contribution by Github's markdown renderer is that it doesn't remove that tag.
- franga2000 6y ago
  But how do they put code tags in there? Last time I checked, Markdown doesn't allow Markdown inside HTML tags. Or do they just wrap it in <code><pre> and the syntax highlighter picks it up later in the chain?
  - arthur2e5 6y ago
    Markdown inside HTML tags is fine as long as there's a paragraph break (two newlines) between the Markdown and the HTML tag. So it usually goes like: <detail> <summary>...</summary> Some `markdown` </detail> I would imagine this sort of behavior is in commonmark, but I am too lazy to check.

barbazoo 6y ago

That is one well written Github issue!

lilyball 6y ago

I’m really impressed by the diagrams (and they’re vertical so they’re mobile-friendly too!), how were they generated?

monowii 6y ago
I think they used Graphviz: https://graphviz.org/ https://graphviz.org/