Roc's DEFLATE library comes within 2.6% of C's libdeflate on an M1 Mac
How close can pure functional programming get to C?
Richard Feldman set out to see how close a pure functional language could get to C by optimizing roc-deflate, a DEFLATE package written in Roc, and benchmarking it against libdeflate on the Silesia corpus. Across 144 benchmarks, Roc ran a median 2.6% slower on an M1 MacBook Pro and 8.9% slower on a Ryzen 3900X — with identical output and no streaming support yet. Roc hasn't even hit version 0.1.0.
libdeflate unsurprisingly blows it out of the water (unsurprisingly because this is a very carefully tuned implementation using architecture-specific SIMD, that we can't touch in Lean).
- jandrewrogers
Much of the difference in optimizability is that C/C++ allows you to do fairly extreme copy elision. This is important because memory bandwidth tends to be a major performance bottleneck.
C/C++ code can trivially reach into some remote bit of state and mutate it directly. The compiler rarely objects, no matter how ugly the access method or pattern. It is up to the programmer to make sure the invariants hold and the compiler can’t always see through it. These elided copies add up, though it usually has a maintainability and safety cost.
It is related to why functional languages tend to be mediocre for supercomputing in practice despite having nice properties for massive parallelism in theory.
- VorpalWay
> lean-zip beats every single compression level miniz_oxide
Miniz_oxide is an intentionally simple implementation. It would be more fair to compare it to the newer zlib-rs[1], which even beats zlib-ng (fastest implementation in C)[2].
[1]: https://lib.rs/crates/zlib-rs
[2]: https://trifectatech.org/blog/zlib-rs-is-faster-than-c/
- gobdovan
Have you considered exposing these optimisations through a library so programmers can request optimisation passes and have the compiler check the preconditions?
Asking cuz I'm preparing an article on how fast JS can get and found the same thing, you can get in 10% of optimised C-code with basically any code if you torture V8 enough (excepting SIMD where there seems to be a bug in V8 where it doesn't optimise to SIMD even when beyond obvious). Figured out I could extract it in a lib and do it more streamlined but not sure how well manual transforms generalise.
Also, when working on the roc-deflate, did you find recurring transformations that could fit that model or were most improvements specific to compression?
- johnny22
saying it "beats a crate that has been downloaded X times" is not saying anything other than that is popular. It'd be nice to see slightly more detail there.
- pmkary
This is kind of hacker news post and comments I like; extreme languages on extreme performance with extreme features, not types being added to a language ten gizzilion times slower than a tortoise and the post making anti-type flat-earthers getting freaked out if they have to vaccinate next.