How close can pure functional programming get to C?rtfeldman.com
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.
That's a nice explanation, thanks.
Are there any common resources for this kind of access methods and patterns that specifically aim to bridge the soft-/hardware gap? The best one I can come up with is Performance Analysis and Tuning on Modern CPUs[0] by Denis Bakhvalov.
I recently came across https://www.kernel.org/pub/linux/kernel/people/paulmck/perfb... , it draws from author's experience about applying optimizations in linux codebase .
I also like this very readable paper https://xnning.github.io/papers/perceus.pdf, about reducing the costs of reference counting in context of functional languages.
Clojure creator Rich Hickey describes traditional imperative programming as "PLace Oriented Programming (PLOP)" when talking about how Clojure's approach is better for certain kinds of problems.
I agree with his point, and Clojure is my favorite programming language, but the computer itself is place-oriented. It runs on reading from and writing to locations in memory, and extracting maximum efficiency from it requires direct control over that memory.
Modern computers are exquisitely sensitive to spatial and temporal locality because many of the hardware features that speed your code up (for free!) take advantage of data or instructions that are “next to each other.” This can be a challenge in a functional program, because not only do you often have little control about where things go, the abstractions that make cool things possible (eg, closures, or lazy evaluation) naturally introduce indirection that hurts locality.
─ 1 more ─
You can have great abstractions on the upper levels that lower to fast primitives. See the articles [1] Push your "ifs" up and "fors' down and [2] Vectorized interpreters for more details.
[1] https://debasishg.github.io/blog/push-ifs-up-fors-down/ [2] https://venge.net/graydon/talks/VectorizedInterpretersTalk-2...
>but the computer itself is place-oriented
You could similarly argue that the computer is in fact fundamentally functional, since the core instruction cycle (Fetch Decode Execute) does not modify any memory.
The key insight into that system is that we've embedded a functional system within a mechanism that makes it imperative. The functional cycle can output commands to fetch it more data, that it can then use in the next cycle. It becomes imperative by the addition of time, which it needs because it's limited in the amount of input and output.
─ 4 more ─
If a function is computed in the woods, does it return a result?
─ 2 more ─
Only if it has a place to put the result.
three pounds of stacks!
The execute stage very much modifies state; in fact it always modifies state. Any non-memory instructions modify registers, and any memory instructions either write to registers or to memory. Even a noop will increment the instruction pointer, so you're always modifying a register regardless.
it seems like in this case SIMD is one of the biggest reasons libdeflate beats miniz-oxide. at that point you are either using assembly or a library of functions that maps in names and functionality to the assembly. I think C isn't really better than other languages in that regard. Its not like its using auto-vectorization to get that SIMD support.
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?
It’s probably just because a zstd implementation in Lean would be more difficult. The whole project depends on being able to have a correctness proof for the implementation, and implementing that for the DEFLATE algorithm is simpler.
─ 1 more ─
The pure Lean implementation of zstd in that project is only decompression, not compression. It kind of proves my point.
What are some well known programs made with Roc? And I'm curious about the difficulty level of its syntax
Well, it has not even reached 0.1.0, so the language is still in early development phase. But it has interesting properties, so I would recommend experimenting with it.
There are no well known programs made with Roc. It's been usable for writing real software since July or so for those of us willing to deal with compiler crashes and regular syntax/feature changes. To my knowledge there are six people producing substantial amounts of software in Roc. I'm using it for a speech recognition/transcription app and the desktop environment and apps on my eink tablet, both on my own UI framework.
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.
And it's something they've been working on for the past 8 years!
What are you talking about? It comes across as trolling, or the unloading of some unrelated personal grievance.
Probably a recent typescript ai rewrite in rust that was on HN a few days ago [1]. Agreed, I'd much rather read about engineering.
─ 1 more ─
I don't mind the OP. I'm objecting to the other commenter's rhetoric:
>gizzilion times slower than a tortoise… [people who disagree with me about a tech issue, who are] flat-earthers getting freaked out
>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/
So, lean-zip "outperforming an equivalent Rust package that crates.io says has been downloaded over a billion times". Yes, zlib-rs has only been downloaded 200 million times... But it is way faster!
downloads is such a weird metric to focus on
─ 5 more ─
If something has a lot of downloads it shows a revealed preference that this kind of performance is acceptable.
─ 4 more ─
I think its pretty safe to say most (bit not all) users of deflate don't have it in their hot path and arent zipping super large files.
Yes, but it also has many conditionals, for example:
- The faster package may have been available for a shorter amount of time and so downloads have not had the time to catch up yet.
- Many people may not be aware of the faster package, but they would switch if they knew.
- Maybe people are aware of the faster package, but there are switching costs that prevent them from adopting it right now that are greater than the costs incurred from the slower package.
Recent downloads per day show the opposite trend, with 2500k vs 1600k per day (with zlib-rs leading). The issue is zlib-rs is far younger so looking at total downloads is nonsense. And there is inertia to switch over as well.
How does it help? You could just as well compare to some slow popular Python version if all you need is "revealed preference"
Zlib-rs is several years newer, of course it has fewer downloads. Looking at recent downloads per day zlib-rs easily leads (2,500,000 vs 1,600,000)
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?
IIRC in weird corner cases, JS code can outperform wasm/C/C++ because JIT optimizes with escape analysis/inlining.
>where it doesn't optimise to SIMD even when beyond obvious
What was that code?
Yes, it does beat -O3 C sometimes. I took code from diverse 'language speed' benchmarks from the internet and had to rearrange them to get -O3 to beat equivalent-looking JS (Node 25.8.1 w\ V8 14.1 and clang 21 on MBP3).
>What was that code?
literally:
``` function numericKernel(a, b, out, n) {
for (let i = 0; i < n; i += 4) {
out[i] = a[i] * b[i] + 0.25;
out[i + 1] = a[i + 1] * b[i + 1] + 0.25;
out[i + 2] = a[i + 2] * b[i + 2] + 0.25;
out[i + 3] = a[i + 3] * b[i + 3] + 0.25;
}
}
```─ 1 more ─
i've tried various options, Firefox prefers ` for (let i = n; i--;) out[i] = a[i] * b[i] + 0.25;` Its already at peak optimization so no form is significantly better.
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.
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.
Haskell most definitely supports loops:
ghci> :{
ghci| for_ [1 .. 10] $ \i ->
ghci| print i
ghci| :}
1
2
3
4
5
6
7
8
9
10
It doesn't require loops to be implemented at the language level, however. The language is rich enough to support user-defined loop constructs.Loop constructs like whileM_ require extra IORef effort to the point where people actually recommend recursion (with tail recursion) instead, which is still harder to implement than conventional while loops.
Digging through the current Haskell standard library - for_ calls traverse_, which calls foldr, which calls foldMap, which calls… foldr. Found the recursion! The person you’re replying to is correct - you can mimic the style of a for loop, but under the hood all of this stuff is going to be implemented with recursion (and tail recursion, if you don’t want to hate your life).
I also may have gotten some detail slightly wrong, the code in Data.Foldable is kinda weird and I haven’t Haskell’d in a while
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.
Because LLMs make mistakes, and you want to prevent that? No wonder Rust is becoming the default language for high-performance LLM-written code. I hope Roc becomes a viable option soon, as it reaches stability.
>No wonder Rust is becoming the default language for high-performance LLM-written code.
What's the evidence for this claim?
oh wow, so mistakes can be prevented by merely picking Rust. wow.
─ 1 more ─
For some categories of mistake, yes.
Yes, nobody wants to have to spot a memory bug in C code.
Indeed nobody wants to review LLM generated slop.
So being able to know that this code cannot contain memory bugs, race conditions, etc is extremely valuable.
I might go a far as to claim: I'd be okay with the AI using an obscure language, if I can know the code is free from memory issue, race conditions and has no side effects, etc.
The argument that with LLMs pure functional language that I didn't bother to write before is now viable.
Memory bugs are also just bugs. If you want to remove also others bugs, you need to formally verify, which soon AI and tools will also just do for you.
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.
The snarky answer to that is that you just described a compiler with extra undefined behavior sprinkled in for extra excitement.
Compiled ones already translate to the theoretically fastest imperative language (machine code) using correctness preserving transforms. And plenty of them already occupy the top tier of performance for garbage collected languages. But being able to match the performance people can achieve with C, C++, etc. requires manual memory management, and that is a difficult nut for functional languages to crack because it interacts poorly with closures.
But the undefined behavior would only apply to the performance, not to the correctness.
─ 7 more ─
If we’re talking AI-assisted translation, and by AI you mean LLM, it would apply to everything.
─ 6 more ─
You missed "correctness preserving transformations" in my first comment :)
─ 5 more ─
If you want to be 100% sure of transformations being correctness preserving, then they need to be deterministic and formally proven to be correct.
We have had a good technology for doing that since the late 1950s, and, like I pointed out in my first reply, it already works very well.
Replacing it with a probabilistic model would not improve things. In this case, it would do the opposite of what you want because you would be replacing something that is provably and reliably able to produce correctness preserving translations with something that is fundamentally and inherently loosey-goosey.
─ 4 more ─
Suppose at some point a classic algorithm can choose between doing 2 transforms. Both are correct, but one will lead to a better optimization than the other. You ask the LLM. No matter which one it chooses, you will get a correct output.
─ 2 more ─
You're still describing a compiler. You want that decision to be deterministic. An LLM is a really bad solution for such a problem.
No, you use a profile-guided optimizer. Because you want that decision to be based on real empirical performance data, not a language model’s output based on conditional token probabilities.
>it already works very well.
Peephole optimization that can't be made global due to combinatorial explosion?
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.
>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!
I don't know about roc specifically, but the best projects often come out of something someone built for a particular need. The open source / public version will often need work to strip out stuff specific to the original project, as well as refinement to make it more suitable for generic public consumption, such as adding support for edge cases, features that the original project didn't need but others likely will, support for multiple platforms for deployment, etc.
>How can you justify using immature technologies for client work?
Ask everyone that's using generative AI?
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.
I appreciate that about D. I've always wondered though, if the convention isn't backwards, like how Lua forces you to specify local instead of global, TS isn't strict by default, most languages have default mutable rather than default immutable, etc.
I always thought having a working program should be opt-out, not opt-in.
(For example, my ideal language supports dynamic typing, with the compiler directive #jammode, or alternatively #explodeinprod)
It's a great question. The answer is `pure` came along after D was already established with a lot of existing code. Making it the default would break pretty much all of it.
Part of the problem is `pure` is transitive, i.e. a pure function calling an impure one is not allowed. This makes it hard to incrementally make the code pure.
But when one succeeds at it, it is very satisfying.
There is an escape hatch, however. Prefixing a statement with `debug` allows the dependent statement to be impure. This is very handy when one needs to insert some print statements to debug a program. (Calls to printf are impure!)
─ 4 more ─
That `debug` trick is clever! We gave Roc a dedicated `dbg` language keyword which does this - it's allowed to be used in pure functions even though, as you said, logging debug output is a side effect.
By the way, hi again! We chatted briefly in person after Handmade Seattle 2021, and I remember being really impressed to learn that you're one of the few people (maybe the only one?) who has ever implemented a working C++ compiler solo.
Anyway, hope all is well, and let me know if you're ever interested in recording a podcast episode sometime - oss@rtfeldman.com
─ 3 more ─
AFAIK I am still the only person who has implemented a complete C++ compiler, compliant with C++98, including preprocessor, optimizer, and code generator.
Anyhow, I'll be speaking at NWCPP soon:
THURSDAY, Nov 19, 2026 at 6:30 PM to 8:00 PM
Elegant D - There’s More to Programming than Getting Code to Work Bellevue City Hall, Room 1E-121 450 110th Ave NE Bellevue, WA 98004
nwcpp.org
Please come! All are welcome!
─ 2 more ─
will this be recorded? it sounds interesting!
─ 1 more ─
Yes, all the nwcpp.org presentations are recorded and posted online.
For all its quirks (lazy IO) and ills (partial functions in base, proliferation of language extensions) - Haskell really does well on this axis.
So glad to have been writing production Haskell for almost a decade
does this mean if you want to add some print statements for local debugging inside a pure function that you will have to remove pure from the whole callgraph? or is there a way to treat it as just a warning?
You would have to, which is why D allows code to be prefixed with `debug`, as in:
debug printf("I made it this far before crashing\n");
which turns off the purity checks for the dependent statement.Early Rust had a ‘pure’ function annotation, too, but it was removed as unnecessary as the borrow checker evolved and became central to Rust’s safety story.
I never saw Roc before, but at first glance I love it: functional compiled language with good performance and Ruby ergonomics.
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.
roc-deflate produces identical outputs to libdeflate - I mentioned it briefly, although in retrospect the wording could have been clearer:
>I didn't expect to beat libdeflate's performance across the board, but I wanted to see how close it could get on the non-streaming APIs (as roc-deflate hasn't implemented streaming yet), using the classic Silesia corpus for benchmarking and verifying that it produced identical outputs.
So it is a port of libdeflate, that is indeed not very clear.
Looking at it again, do you actually have any working correctness check? If you simply ask the AI to test the code for correctness and speed against the benchmark suite, it could easily hyperoptimise for the suite in both regards.
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.
How do you get the correctness proof?
You let the AI generate it. Apparently it becomes quite good at proving things. Here is a some effort: https://www.anthropic.com/research/formal-verification (but this is on generated RISC-V code)
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.