SmackerNews

How close can pure functional programming get to C?

rtfeldman.com/fp-vs-c

275 points · 99 comments · 1 day ago · stmonty

rtfeldman.com/fp-vs-c

jandrewrogers1 day ago
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.
VorpalWay1 day ago
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/
WalterBright1 day ago
D has a nice feature where a function can be annotated with `pure`, and the compiler will check that the function is pure.
It's fun trying to reorganize your code to make it pass the `pure` checking.
giovannibonetti1 day ago
I wonder if Roc will eventually have high-level abstraction to handle SIMD support. Perhaps by bringing some ideas from Futhark [1], a functional language focused on data parallelism. IIRC, the author has already been interviewed on Richard's podcast.
[1] https://futhark-lang.org/
gobdovan1 day ago
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?
andai1 day ago
Roc is not a mature language (it's still weeks away from its first numbered release, 0.1.0)
It then links to a video where a consultant mentions using in production (for several years already?), which confused me.
How can you justify using immature technologies for client work? Or is it an extra benefit when it breaks and you have to fix it?
I'm genuinely curious, maybe it's not as bad as I think. But I've used immature hosting platforms, and that certainly didn't go well for me!
michaelteter1 day ago
I never saw Roc before, but at first glance I love it: functional compiled language with good performance and Ruby ergonomics.
uecker9 hours ago
If you let the agents mess with the code, there seems to be no fundamental reason to use a pure functional language in the first place. The point here is that it is proven correctly. This could be done for C or even assembly. Going to Rust makes no sense either, as this just adds restrictions which are unnecessary if you have a correctness proof.
johnny221 day ago
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.
amelius1 day ago
We should probably all be programming in a FP language, with behind the scenes an AI translating it to something faster using correctness preserving transforms.
I suspect this will be the best way to delegate things to AI while still staying in driver's seat.
NohatCoder1 day ago
Uh, so the program is almost as fast as libdeflate at compressing at a given level. But the post makes absolutely no attempt at establishing that a given level compresses as well as the corresponding level in libdeflate. In the linked post there is a graph detailing that libdeflate does indeed compress quite a lot better than the original lean-zip at the same level.
Without data on compression levels it is hard to make any useful conclusions.
pmkary1 day ago
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.
jeffbee1 day ago
This seems to raise the question: is libdeflate fast? My overall impression of libdeflate is that it produces a similar output size to zstd but takes 40 times longer to do it. I realize these are different algorithms of course, but they aren't that different, both being in the Huffman line of the LZ family. So why is libdeflate considered a performance benchmark?
eigenblake1 day ago
I'm very simple. I see Richard Feldman post. I like it. I'll leave it to the experts as to whether this is a case of opportunistic mutation.
cubefox1 day ago
Problem specifically in Haskell is that you have to worry about implementing tail recursion to get efficient stack usage. That's not necessary for loops, which Haskell doesn't support. Though other functional languages do support them.
deadbabe1 day ago
In the age of powerful LLMs, is there really any reason to program in any higher abstraction than C? Seems like most other languages can be put out to pasture. They were just compromises and shortcuts to make things easier for humans.
jdw641 day ago
What are some well known programs made with Roc? And I'm curious about the difficulty level of its syntax

news.ycombinator.com/item?id=50218195

SmackerNews

A placeholder title for loading skeleton

example.com/path/to/article

000 points · username · 0 hours ago

example.com

SmackerNews

How close can pure functional programming get to C?

rtfeldman.com/fp-vs-c

275 points · 99 comments · 1 day ago · stmonty

rtfeldman.com/fp-vs-c

jandrewrogers1 day ago
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.
VorpalWay1 day ago
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/
WalterBright1 day ago
D has a nice feature where a function can be annotated with `pure`, and the compiler will check that the function is pure.
It's fun trying to reorganize your code to make it pass the `pure` checking.
giovannibonetti1 day ago
I wonder if Roc will eventually have high-level abstraction to handle SIMD support. Perhaps by bringing some ideas from Futhark [1], a functional language focused on data parallelism. IIRC, the author has already been interviewed on Richard's podcast.
[1] https://futhark-lang.org/
gobdovan1 day ago
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?
andai1 day ago
Roc is not a mature language (it's still weeks away from its first numbered release, 0.1.0)
It then links to a video where a consultant mentions using in production (for several years already?), which confused me.
How can you justify using immature technologies for client work? Or is it an extra benefit when it breaks and you have to fix it?
I'm genuinely curious, maybe it's not as bad as I think. But I've used immature hosting platforms, and that certainly didn't go well for me!
michaelteter1 day ago
I never saw Roc before, but at first glance I love it: functional compiled language with good performance and Ruby ergonomics.
uecker9 hours ago
If you let the agents mess with the code, there seems to be no fundamental reason to use a pure functional language in the first place. The point here is that it is proven correctly. This could be done for C or even assembly. Going to Rust makes no sense either, as this just adds restrictions which are unnecessary if you have a correctness proof.
johnny221 day ago
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.
amelius1 day ago
We should probably all be programming in a FP language, with behind the scenes an AI translating it to something faster using correctness preserving transforms.
I suspect this will be the best way to delegate things to AI while still staying in driver's seat.
NohatCoder1 day ago
Uh, so the program is almost as fast as libdeflate at compressing at a given level. But the post makes absolutely no attempt at establishing that a given level compresses as well as the corresponding level in libdeflate. In the linked post there is a graph detailing that libdeflate does indeed compress quite a lot better than the original lean-zip at the same level.
Without data on compression levels it is hard to make any useful conclusions.
pmkary1 day ago
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.
jeffbee1 day ago
This seems to raise the question: is libdeflate fast? My overall impression of libdeflate is that it produces a similar output size to zstd but takes 40 times longer to do it. I realize these are different algorithms of course, but they aren't that different, both being in the Huffman line of the LZ family. So why is libdeflate considered a performance benchmark?
eigenblake1 day ago
I'm very simple. I see Richard Feldman post. I like it. I'll leave it to the experts as to whether this is a case of opportunistic mutation.
cubefox1 day ago
Problem specifically in Haskell is that you have to worry about implementing tail recursion to get efficient stack usage. That's not necessary for loops, which Haskell doesn't support. Though other functional languages do support them.
deadbabe1 day ago
In the age of powerful LLMs, is there really any reason to program in any higher abstraction than C? Seems like most other languages can be put out to pasture. They were just compromises and shortcuts to make things easier for humans.
jdw641 day ago
What are some well known programs made with Roc? And I'm curious about the difficulty level of its syntax

news.ycombinator.com/item?id=50218195