Pavel Verigo (Jul 29 2026 at 02:42): Pavel Verigo (Jul 29 2026 at 02:42):Hi, I am complete beginner, decided to tinker with compiler.
Using a fresh-cache, ReleaseFast compiler built from master, I generated programs with N simple U64 add/xor lines.
Timings I observed for compilation (N number of lines):
N=5,000 -> 4s
N=10,000 -> 18s
N=15,000 -> 43s
This is N^2. From build timings, type checking and specialization take most of the time. Codegen and linking under <100ms.
Though above timings is for whole compilation and for some reason "Type Checking" not shown in timings I see that "Specializing" is close 50% of time and everything else is ms level, so I guess everything else is "Type Checking".
Pavel Verigo (Jul 29 2026 at 02:42):Programs template:
main! = || {
var $value = match U64.from_str(Stdin.line!()) {
Ok(number) => number
Err(_) => {
crash "expected an unsigned 64-bit integer"
}
}
# N / 2 repeated pairs of:
$value = $value.plus_wrap(RANDOM_U64)
$value = $value.bitwise_xor(RANDOM_U64)
# ...
Stdout.line!($value.to_str())
}
My cpu is M5 Pro for reference
Pavel Verigo (Jul 29 2026 at 03:31):My question would be is there any maybe blogpost or past explanation about compiler structure? I know it was rewritten and I read blogpost about rewrite, but nothing about internals. Ofc I will read the source, but if there any discussion/blog about I would like to read it. Thank you.
Richard Feldman (Jul 29 2026 at 03:36):Pavel Verigo said:
My question would be is there any maybe blogpost or past explanation about compiler structure? I know it was rewritten and I read blogpost about rewrite, but nothing about internals. Ofc I will read the source, but if there any discussion/blog about I would like to read it. Thank you.
maybe someday, but definitely not anytime soon...it's a really big topic :sweat_smile:
Richard Feldman (Jul 29 2026 at 03:39):I'm surprised those build times are that high for this example on an M5
Richard Feldman (Jul 29 2026 at 03:41):I'm not super surprised it's quadratic because we do hindley-milner type inference, and type inference of local bindings specifically in HM (e.g. $value =) is quadratic; the bet of HM (which tends to be true in practice of real-world programs) is that N in practice is low enough that this doesn't cause real-world problems, which has generally been true in practice
Richard Feldman (Jul 29 2026 at 03:41):even with that in mind, N=5K taking 4 seconds is surprisingly high to me on an M5
Pavel Verigo (Jul 29 2026 at 03:43):Hmm, I decided to some profiling, most time seems to be in lowerCheckedModulesToLir.
Richard Feldman (Jul 29 2026 at 03:43):specialization involves applying the same type unification algorithm as regular type checking, so I wouldn't be surprised if that turned out to be quadratic too
Richard Feldman (Jul 29 2026 at 03:43):(in this example)
Pavel Verigo (Jul 29 2026 at 03:44):Richard Feldman said:
N in practice is low enough that this doesn't cause real-world problems
I will disagree, any compiler especially for such non convoluted problem should be O(N)
Pavel Verigo (Jul 29 2026 at 03:45):I did some other langs recently, I will say good number it to have <10s for N=1_000_000, and excellent <1s
Richard Feldman (Jul 29 2026 at 03:45):you are disagreeing with the claim that Hindley-Milner type inference (used in Haskell and OCaml in thousands of production code bases) has not caused noticeable compile time performance problems for these real-world code bases in practice when it comes specifically to lots of local bindings? :wink:
Richard Feldman (Jul 29 2026 at 03:46):I agree it's slower than what sounds reasonable to me, but your example happens to be a known pathological case that is intentionally accepted as reasonable to be pathological because there are decades of empirical evidence that this pathology is not a problem in real-world uses of these compilers
Richard Feldman (Jul 29 2026 at 03:47):there are lots of slow build problems in the Haskell community, but they have nothing to do with thousands of local variable bindings in the same function - that's the thing that doesn't come up in practice :smile:
Richard Feldman (Jul 29 2026 at 03:47):anyway, I agree that the wall time here is worth investigating and improving!
Richard Feldman (Jul 29 2026 at 03:49):I'm just noting that quadratic is expected for the specific case of "tons and tons of local bindings" because it is a known downside of Hindley-Milner type inference (which has a variety of upsides to compensate for it), and the reason we accept it as a downside is that it's one that we know doesn't cause problems for real-world code bases, only contrived ones
Richard Feldman (Jul 29 2026 at 03:50):in other words, I think it would be a good idea to try to make this faster, but it definitely sounds like a mistake to try to make it take linear time instead of quadratic
Pavel Verigo (Jul 29 2026 at 03:51):Yes this is artificial program and maybe pathological. I just don't think it need to be n^2 like maybe in general case yes, but what in this program makes it to be n^2?
Richard Feldman (Jul 29 2026 at 03:51):it's all the $value =
Richard Feldman (Jul 29 2026 at 03:52):every time you do a new local binding like that (e.g. v1 =, v2 =, ... v5000 = would have the same problem) it creates quadratic work for the type checker
Pavel Verigo (Jul 29 2026 at 03:54):And this + "Hindley-Milner type inference" will always result in N^2? I do not know a lot about "Hindley-Miller inference" so I will not continue argue on N^2 part
Richard Feldman (Jul 29 2026 at 03:59):well, we use a rank-based system that's supposed to improve on the "HM is theoretically quadratic" part, but I don't honestly know how much of an improvement it's supposed to create in practice
Richard Feldman (Jul 29 2026 at 03:59):hence my not being surprised by the quadratic result there
Pavel Verigo (Jul 29 2026 at 03:59):Thank you for info.
Pavel Verigo (Jul 29 2026 at 04:00):Small q. Why I don't see Type Checking time in build output?
Pavel Verigo (Jul 29 2026 at 04:01):roc build
✓ Resolving Dependencies 5ms
✓ Parsing 0ms
✓ Name Resolution 0ms
✓ Type Inference 0ms
✓ Specializing 8.1s
✓ Code Generation 13ms
0 errors and 0 warnings found in 17.8s while successfully building:
oh, that's Type Inference
Richard Feldman (Jul 29 2026 at 04:01):the missing thing is almost certainly compile-time execution...I thought we added a timings section for that, but maybe I'm misremembering
Pavel Verigo (Jul 29 2026 at 04:03):You also caching Type Checking? It seems to be not running on invoking same build.
Richard Feldman (Jul 29 2026 at 04:03):also I had an LLM running an investigation on that in the background, and it did find a bug that's after type checking (aka type inference) and which does cause unnecessary quadratic behavior
Richard Feldman (Jul 29 2026 at 04:03):type-checking outputs should be cached, yeah - if you run the same build a second time, type inference should be ~0ms
Richard Feldman (Jul 29 2026 at 04:03):but if you run it cold with roc build --no-cache then Type Inference should be nontrivial
Pavel Verigo (Jul 29 2026 at 04:04):Well build above is not cached, so I guess it is output bug
Richard Feldman (Jul 29 2026 at 04:04):we don't cache the entire build yet, just type-checking
Richard Feldman (Jul 29 2026 at 04:04):(or rather, up through type-checking)
Richard Feldman (Jul 29 2026 at 04:04):well, actually some other stuff after that - compile-time evaluation of constants and roc test outcomes
Richard Feldman (Jul 29 2026 at 04:05):it's on my list to cache more of the build, but it's not a priority because re-running roc build with no changes to source inputs along the way is not super common in practice :smile:
Richard Feldman (Jul 29 2026 at 04:05):and caching parts of the build after what we're currently caching gets a lot harder because of specialization
Pavel Verigo (Jul 29 2026 at 04:06):Yes, I understand. Just above output was run on fresh and numbers don't add up +
✓ Type Inference 0ms
yeah the missing numbers are compile-time evaluation of constants
Richard Feldman (Jul 29 2026 at 04:08):I'll add them to timings, looks like I never actually got around to adding that - sorry about that!
Richard Feldman (Jul 29 2026 at 04:08):separately, I wonder what constants are being evaluated in that example :thinking:
Richard Feldman (Jul 29 2026 at 04:09):seems like there should be little to no work to do there
Pavel Verigo (Jul 29 2026 at 04:09):Yeah, I am also confused what constants you are speaking about =)
Richard Feldman (Jul 29 2026 at 04:10):well empirically locally that seems to be where it's doing a lot of the work...but I don't know what work it has actually found to do :joy:
Richard Feldman (Jul 29 2026 at 04:10):I'll look into that too
Richard Feldman (Jul 29 2026 at 04:10):this example has already surfaced multiple missed performance opportunities, so thank you very much for sharing it! :smiley:
Richard Feldman (Jul 29 2026 at 04:14):ah, also there is a separate bug regarding reporting type inference timings
Richard Feldman (Jul 29 2026 at 04:16):separately, according to Gemini at least, the rank optimization we're doing is supposed to improve HM's quadratic inference time to be nearly O(n) in practice even for pathological cases. I've never attempted to measure that before, but I guess we'll see after these other fixes land!
Pavel Verigo (Jul 29 2026 at 04:23):I ran profile and this to seems to be the hottest part
lowerBlockStatements
→ lowerPatternStatement
→ lowerExprAtTypeCellWithDemand
→ lowerDispatchExprAtType
→ lowerResolvedDispatchAtNode
→ methodTargetCalleeAtNode
→ InstGraph.unifyRootsTransitively
→ InstGraph.union_
→ HashMap.put
→ Wyhash.hash
yeah the InstGraph.union_ is the specific thing that is doing more work than it needs to
Pavel Verigo (Jul 29 2026 at 04:26):I also needed to pass -Dstrip=false when building ReleaseFast, as strip set to true in non Debug in build.zig which is bad choice IMHO.
Pavel Verigo (Jul 29 2026 at 04:27):Well, I can may be work on it I don't think diff will be complex, if it yours/agents priority now, I am glad that I helped there.
Richard Feldman (Jul 29 2026 at 04:29):oh yeah the fix looks fairly quick - I'm about to go to bed but will probably have a fix tomorrow :smile:
Richard Feldman (Jul 29 2026 at 04:29):but I really appreciate the repro, this is really useful!
Richard Feldman (Jul 29 2026 at 04:30):and also even after the fix there may still be more room for improvement just on this one example
Richard Feldman (Jul 29 2026 at 04:30):and I'll also fix the timings to include compile-time eval and also fix the type-checking report time too
Pavel Verigo (Jul 29 2026 at 04:32):If this will result in running O(N) time this is good metric of single thread benchmark of compiler pipeline, most work is processing this one big function.
Pavel Verigo (Jul 29 2026 at 04:33):Ofc this is artificial program but yet it shed some light especially in profiling. Which passes/stages of compiler just read through the bytes and do mostly nothing as this program is trivial in Semantic way.
Anton (Jul 29 2026 at 12:33):strip set to true in non Debug in build.zig which is bad choice IMHO.
Can you elaborate on this @Pavel Verigo? I suspect it makes a significant difference in the size of our release.
Pavel Verigo (Jul 29 2026 at 15:56):The saving from strip=true is 17% reduction of binary size, but it removes better experience for debugging, crashes info and profiling, I think this is more valuable for WIP status of compiler. I myself take part in Zig compiler development, there are talks about even compiling using ReleaseSafe for non tagged releases binaries so we catch more bugs.
Pavel Verigo (Jul 29 2026 at 15:57):Speaking about modern computers and disk sizes this 17% increase is nothing and if reduction needed idk for wasm builds it could be passed separately.
Pavel Verigo (Jul 29 2026 at 15:59):It would be also cool to have no llvm build for Roc in build.zig for development it will greatly improve iteration time on compiler.
Pavel Verigo (Jul 29 2026 at 15:59):
Pavel Verigo (Jul 29 2026 at 16:00):I did some tinkering with patches and was able to make it linear and like 100x faster overall, but as you see compiler is not really memory efficient and time degrade due to my 24 GB mac starts to fight for RAM.
Pavel Verigo (Jul 29 2026 at 16:06):I would assume <50s is achievable if memory being used sanely
Anton (Jul 29 2026 at 16:21):I suspect we had a regression in memory usage recently, given this other issue I just hit.
Anton (Jul 29 2026 at 16:23):Pavel Verigo said:
It would be also cool to have no llvm build for Roc in build.zig for development it will greatly improve iteration time on compiler.
We sure love to make gains there, it would surprise me if @Richard Feldman has not already thought about this.
Anton (Jul 29 2026 at 16:26):Pavel Verigo said:
The saving from strip=true is 17% reduction of binary size, but it removes better experience for debugging, crashes info and profiling, I think this is more valuable for WIP status of compiler. I myself take part in Zig compiler development, there are talks about even compiling using ReleaseSafe for non tagged releases binaries so we catch more bugs.
Shall we disable stripping debug info @Richard Feldman?
Richard Feldman (Jul 29 2026 at 18:10):I'm game! :thumbs_up:
Richard Feldman (Jul 29 2026 at 18:10):(for both of those - noLLVM build and also don't bother stripping release builds)
Richard Feldman (Jul 29 2026 at 18:10):we should still strip wasm builds of the compiler though
Anton (Jul 29 2026 at 18:10):I will update stripping right away
Richard Feldman (Jul 29 2026 at 18:14):also, it turns out a significant part of the reason this is quadratic is that we use the same HM inference for vars as we do for constants, but we are only applying the "rank" performance optimization to constants (or rather, we aren't applying it to some var-specific additional work that we do). I'm expecting a big improvement in asymptotic performance once that has been incorporated, and also a big improvement in total compile time due to other unnecessary work that this benchmark revealed
Richard Feldman (Jul 29 2026 at 18:14):hopefully I'll have a PR with all that sometime tonight!
Richard Feldman (Jul 30 2026 at 04:12):@Pavel Verigo if you try it out on https://github.com/roc-lang/roc/pull/10467 you should see some much nicer numbers!
Richard Feldman (Jul 30 2026 at 04:12):(it's still running through CI and I gotta head to bed)
Richard Feldman (Jul 30 2026 at 04:13):also the timings are fixed and also broken down into more categories now, plus they also report memory usage
Richard Feldman (Jul 30 2026 at 04:13):of note, roc build does full optimizations by default, so if you don't want the times to be dominated by LLVM stuff, you can do roc build --opt=dev
Anton (Jul 31 2026 at 12:33):Richard Feldman said:
(for both of those - noLLVM build and also don't bother stripping release builds)
On macOS the no strip increase is small (+18.6%) but on linux it is substantial (+98%) putting the binary at 342 MiB instead of 173 MiB. I know on macOS the size of the binary makes a noticeable difference in the runtime for a clean run and I suspect that to be the case on linux too. So I feel like it's not worth it, especially because we've seemingly had no issues with lack of debug info leading to worse issue reports and only a sliver of our user base wants to do profiling.
Richard Feldman (Jul 31 2026 at 12:46):yeah I agree. Thanks for investigating!
Lukas Juhrich (Jul 31 2026 at 17:22):Anton said:
So I feel like it's not worth it,
Are we currently providing debug symbols with the nightly builds as an explicit download in some known location? I.e., a roc.debug dwarf for unixes and a .pdb for windows.
Then any stacktraces could be interpreted properly (after loading that file in scope or re-merging with the binary). I think that would address the de-facto pain point of @Pavel Verigo?
Anton (Jul 31 2026 at 17:42):Are we currently providing debug symbols with the nightly builds as an explicit download in some known location?
No, but I am happy to add it if people want it.
Anton (Aug 01 2026 at 16:32):The noLLVM build leads to a 3.6 % speedup for a clean build and 6.5 % after an edit in one file. It is built using zig build roc -Dno-llvm. roc build, roc glue and roc test --opt=size/speed are unavailable when roc was built with this flag. I presume the edit benefit will disappear with a future zig version due to the better incremental compilation. I have not wired this through the tests yet, when running all tests you do want just the one binary and for some tests the no-llvm version is enough, that wiring may add some noise to the code. Do you all think it's worth it for the 3.6 % speedup?
Anton (Aug 01 2026 at 16:33):Without the test wiring the change is lean at 68 insertions, 15 deletions
Richard Feldman (Aug 01 2026 at 16:33):Anton said:
Do you all think it's worth it for the 3.6 % speedup?
nah
Last updated: Aug 12 2026 at 12:35 UTC