Hacker News Reader

Comment by throwaway894345 | Hacker News Reader

This seems like the “sufficiently smart compiler” argument. A sufficiently complex compiler could certainly optimize this away, but building and maintaining such a compiler while also keeping compilation times low is an enormous challenge. Rust does an impressive job here, but Rust was built from the ground up to handle these problems and it also trades compile times to achieve those optimizations.

View on HN

Not really on this case, a common optimization pass on functional programming languages since the 70's is to flatten such kind of calls.

Rust long compile times are mainly caused by LLVM, and the amount of IR that is given to it.

Can you point me to a paper from the 70s that explains how to flatten such calls? The best that I know is "stream fusion, to completeness" which was published in something like 2019!

You can get the book

"Lisp on Small Pieces" from 1994

https://www.amazon.com/exec/obidos/ASIN/0521562473/acmorg-20

It is not 70's, but 26 years should be enough to get hold of such knowledge.

Or "Modern Compiler Implementation" from 1998, a little more young.

https://www.cs.princeton.edu/~appel/modern/

Or rather "The Implementation of Functional Programming Languages", from 1986, now getting closer to 70's.

https://www.microsoft.com/en-us/research/publication/the-imp...

I can still have a look into my SIGPLAN paper collection to dust off some ML papers.

It's easy in functional languages where execution order and side effects aren't an issue. In JS with prototype monkey-patching you can't even know that the call to `.map()`, or anything that it touches, won't suddenly replace the implementation of the `.filter()` method that follows it.

The large amount of IR given to LLVM is closely related to the amount of abstractions that Rust uses. It's especially relevant for iterators where a "simple" `for` loop expands to `into_iter()`, `iter.next()`, `match`, `drop`, and arithmetic expands to calls to overloadable operator methods, all moves are `memcpy` to clean up, and so on.

https://rust.godbolt.org/z/71aEnf9Ta

I remember the days when functional languages wasn't a synonym for like Haskell does it.

Speaking of which just use OCaml bytecode backend or Haskell interpreter to see how slow complex languages are.

This is what is missing to Rust and cranelift might help to deliver, alongside not having to keep compiling the whole world from scratch.

I don't know about JS's particular challenges here and I believe you but a lot of languages with a lot of other features also do this optimization. It's not just the hardcore functional ones though admittedly maybe mostly in the ones most influenced by them.

This is one of the idioms that leads to large amounts of IR!

Avoiding that means doing the flattening earlier, in a higher level IR.

If F#, Haskell, Scheme, Lisp and OCaml are able to do it and still remain fast compilers (there is more than one backend to choose from), I am sure Rust will manage it eventually.

I am not familiar with the compilers for all of these, but I can make a couple of interesting comparisons:

* GHC does exactly what I suggested rustc needs to do- it does the flattening on an earlier, higher-level IR than LLVM's. (It is also not exactly a fast compiler, though!)

* I'm not sure if this applies to F#, but in C#, LINQ compiles faster by not doing as much (if any) flattening in the first place.

Reply on news.ycombinator.com