Karl (Sep 03 2026 at 02:24): Karl (Sep 03 2026 at 02:24):Richard Feldman said:
we have SIMD builtins right now - are they not sufficient?
They are sufficient for the narrower 128 bit variant. I'm porting this from the Rust implementation which includes the 256 bit version so the Roc version is going to be slower. The LLM missed the builtins and I didn't catch it because I'd read a thread about missing SIMD float support .
Karl (Sep 03 2026 at 02:26):Initial benchmarks pass has be 100x-5300x slower than Rust. The high end is special case code I don't think I have a path to reach from Roc but even the baseline is excessively slow so I'm working on the reason.
Edit: 75% memory management. Typical reason.
Richard Feldman (Sep 03 2026 at 02:48):ok cool! so I've been working on a (probably?) similar project where I'm trying to get roc-deflate to within 10% of libdeflate's perf
Richard Feldman (Sep 03 2026 at 02:50):when I started out, decompression and compression both had hundreds of percents of slowdown, but eventually I got decompression down to 6-12% slowdown on all libdeflate's benchmarks, and I'm still working on compression - it's now under 100% on average, but not yet down to the 10% range
Karl (Sep 03 2026 at 02:50):I wanted to try the Regex because it's a pure function so in theory the machinery can be folded at compile time and the runtime is just a matcher.
Richard Feldman (Sep 03 2026 at 02:51):yeah I absolutely love it! I think this is a really good case where I'd love to push the boundaries and try really hard to get it within 10% of Rust's perf :smiley:
Richard Feldman (Sep 03 2026 at 02:52):so the approach I've taken with libdeflate has been to iterate a lot with Fable on it, both in terms of getting the Roc implementation closer to libdeflate, and also using that as a way to discover opportunities for improving our own compiler optimizations (while being wary of not overfitting to the benchmark)
Richard Feldman (Sep 03 2026 at 02:52):I'd say it's been mostly changes to the library itself, e.g. at first compression wasn't using our simd builtins at all because the C one wasn't, but it turned out LLVM wasn't autovectorizing ours as well as it was the C ones because we needed to do some bounds checks or something (I forget exactly what the difference was) and switching our implementation to do explicit simd made a difference
Richard Feldman (Sep 03 2026 at 02:54):but I will say that at least on the LLM side, there was a lot of coaxing to get it to the point where the implementation was actually a faithful port - it's so, so prone to doing a "close enough" port, and then trying to go off and optimize something that's fundamentally just doing something much less efficient than the already-optimized C (or in this case Rust) implementation
Richard Feldman (Sep 03 2026 at 02:54):regarding 128-bit vs 256-bit, I get nervous about enabling 256-bit SIMD
Karl (Sep 03 2026 at 02:54):I don't think I can get to within 10% of Rust when it's on the fast paths. The 256 bit wide SIMD is scanning 32 characters versus my 16. Getting to a significant fraction is probably doable on the paths where the matching engine is actually doing work.
Richard Feldman (Sep 03 2026 at 02:55):yeah I'm just nervous about hardware support and increasing the complexity of the targets we support etc.
Richard Feldman (Sep 03 2026 at 02:55):128-bit has very broad support today
Karl (Sep 03 2026 at 02:55):I think the perf will be totally acceptable. It's not like we need 4GB/s scanning to make it work.
Richard Feldman (Sep 03 2026 at 02:55):ok cool
Richard Feldman (Sep 03 2026 at 02:56):in that case I'd say you might consider temporarily changing your local rust impl to use 128-bit too, so you're comparing apples to apples
Richard Feldman (Sep 03 2026 at 02:57):and then if you can get within 10% of that, maybe you zoom out and say ok it's (whatever)% compared to the 256-bit Rust one, and if Roc ever adds 256-bit SIMD (e.g. when hardware support is more widespread, or maybe we just figure out some nice way to offer it in a way that doesn't break when the hardware doesn't support it) then we can presumably close that gap
Karl (Sep 05 2026 at 04:45):| id | pattern | Roc | Rust | Roc ÷ Rust |
|---|---|---|---|---|
| literal_dense | Holmes |
0.055 ms | 0.030 ms | 1.8× |
| literal_sparse | Moriarty |
0.0115 ms | 0.010 ms | 1.2× |
| teddy_alt | Sherlock\|… |
1.01 ms | 0.43 ms | 2.35× |
| class_plus | [A-Za-z]+ |
3.61 ms | 2.22 ms | 1.62× |
| bounded_num | [0-9]{2,4} |
0.153 ms | 0.110 ms | 1.4× |
| word_bound | \bthe\b |
0.335 ms | 0.206 ms | 1.63× |
| two_words | \w+\s+\w+ |
2.44 ms | 1.55 ms | 1.57× |
| caps_email | (\w+)@(\w+) |
0.140 ms | 0.070 ms | 2.0× |
| uni_letters | \p{L}+ |
3.60 ms | 2.10 ms | 1.72× |
| dotstar_lit | .*Holmes |
0.535 ms | 0.645 ms | 0.83× (faster) |
Down to basically codegen and different implementation decisions. This is using my local SIMD patch. The main algorithmic difference is that I generate the DFA based on codepoints instead of bytes which is slightly slower but the main thing I wanted to test when trying this out was doing the pattern compilation at compile time; codepoint approach for patterns with unicode \w results in ~50kB patterns in the binary while byte approach tends to be over a megabyte. These numbers are just the match loop and don't include startup latency.
I plan on doing a code review/cleanup, writing the README, and pushing tomorrow. Then I'll try the RE# approach but I think this is fast enough to be useful.
Richard Feldman (Sep 05 2026 at 15:39):wow, huge improvement compared to the previous numbers! :star_struck:
Richard Feldman (Sep 05 2026 at 15:40):is the SIMD patch to get 256-bit SIMD?
Karl (Sep 05 2026 at 15:41):No, it turns out that Claude was lying to me and they were both running 128 bit
Karl (Sep 05 2026 at 15:42):There's a 256 bit path in the Rust version but my machine is old enough that I can't access it.
Richard Feldman (Sep 05 2026 at 15:42):classic Claude
Richard Feldman (Sep 05 2026 at 15:42):so what's the SIMD patch you needed?
Karl (Sep 05 2026 at 15:43):https://github.com/roc-lang/roc/issues/11117
Is there a way to get unchecked list access or have the checks elided?
Richard Feldman (Sep 05 2026 at 15:43):elided is what we want
Richard Feldman (Sep 05 2026 at 15:44):that's a major part of what I've been doing in the libdeflate work
Richard Feldman (Sep 05 2026 at 15:45):either figuring out how to change the roc code such that bounds checks get elided, or finding ways to make the compiler better able to detect when elision is safe
Richard Feldman (Sep 05 2026 at 15:45):we can never do unchecked in userspace APIs because then roc code would no longer be memory-safe :sweat_smile:
Richard Feldman (Sep 05 2026 at 15:46):so elision improvements (in the package and/or compiler) are the way to go!
Karl (Sep 05 2026 at 15:48):It doesn't show up in these numbers but there's an underlying fallback NFA (PikeVM) that basically interprets the pattern and that gets hit pretty hard by the checked access. The caps_email and teddy_alt are in a similar boat but don't have as many accesses.
Richard Feldman (Sep 05 2026 at 15:53):when does the fallback trigger?
Karl (Sep 05 2026 at 15:55):it was the correctness/starting point so it originally touched everything but at the moment I think it's when the pattern gets too big, part of the capture path and for buried ^/$ like foo|(^bar)
Karl (Sep 05 2026 at 15:59):I'll be doing a bunch of capture stuff in the future. I plan on trying a big matcher as the parser for HTTP requests and seeing how that works.
Last updated: Sep 24 2026 at 15:59 UTC