Hacker News Reader

Comment by asp2insp | Hacker News Reader

The time complexity of comparing variables for equivalence during type unification is reduced from O(n!) to O(n). As a result, some programming patterns compile much, much more quickly.

I love this. Not just my code compiling more quickly, but the underlying implementation is super interesting.

View on HN

Is this something seen frequently in user code, or just an edge case? I'd love to get even faster with my libraries compiling, but honestly the continuous improvements in compile speed over the last half a year have already made me happy :)

Its an edge case for the `n` to get high enough for it make a big impact.

And depending on the multiplying constant, it could mean everything is slower than before _until_ you reach a high enough n.

EDIT: The PR that added the change claims it was done well, though :) https://github.com/rust-lang/rust/pull/32062

Indeed. It's hard to miss just how much better rustc performance has become recently. As I've watched this I been left wondering; is it just the blood and sweat of the compiler developers doing this or is the language somehow inherently efficient to compile? I know there are other, much older languages that seem unable to deal with their compiler performance problems.

It is a combination of both. We took performance into consideration when designing all aspects of the langauge, and so we've laid a lot of groundwork. The gains have come because the compiler had so much technical debt; imagine a hundreds of thousands of LOC codebase where the language changes out from under it on a weekly/daily basis. So every since 1.0, and even before, really, it's been paying off debt, and doing things in better ways. And there's more coming. Incremental recompilation will make after-the-first compiles go even faster. But all of that takes tons of work.

On the other hand, niko has described trait resolution as "basically prolog", so that's something you can push to perform as degenerately bad as you want (the recent addition of specialization only making things worse).

The issue is just how degenerately bad "most" code is -- and I think that hinges a lot on how excited the word "higher" gets you vis-a-vis expressing your programs. If you think C# is a pretty cool type system that doesn't afraid of anything you'll probably be fine. If you think scala or haskell with All The GHC Extensions is where it's at... watch out.

> I think that hinges a lot on how excited the word "higher" gets you vis-a-vis expressing your programs.

You are the best Gankro. <3

What's nice about coherence is that there's little risk in modifying the constraint solving algorithm to optimize for the common use cases (because it can't be backward incompatible). What's nice about crater is that it's comparatively easy to test that optimization.

Reply on news.ycombinator.com