4 ms·

This article is about the ugliest — but arguably the most important — piece of open-source software I’ve written this year. The write-up ended up long and dense

This article is about the ugliest — but arguably the most important — piece of open-source software I’ve written this year. The write-up ended up long and dense, so here’s a short TL;DR: I grouped all Unicode 17 case-folding rules and built ~3K lines of AVX-512 kernels around them to enable fully standards-compliant, case-insensitive substring search across the entire 1M+ Unicode range, operating directly on UTF-8 bytes. In practice, this is often ~50× faster than ICU, and also less wrong than most tools people rely on today—from grep-style utilities to products like Google Docs, Microsoft Excel, and VS Code. StringZilla v4.5 is available for C99, C++11, Python 3, Rust, Swift, Go, and JavaScript. The article covers the algorithmic tradeoffs, benchmarks across 20+ Wikipedia dumps in different languages, and quick starts for each binding. Thanks to everyone for feature requests and bug reports. I'll do my best to port this to Arm as well — but first, I'm trying to ship one more thing before year's end.

fatty_patty89 10mo ago
Thank you do the go bindings require cgo?
- ashvardanian 10mo ago
  The GoLang bindings – yes, they are based on cGo. I realize it's suboptimal, but seems like the only practical option at this point.
  - fatty_patty89 10mo ago
    In a normal world the Go C FFI wouldn't have insane overhead but what can we do, the language is perfect and it will stay that way until morale improves. Thanks for the work you do
    - kardianos 10mo ago
      In a real (not "normal") world, trade-offs exist and Go choose a specific set of design points that are consequential.
    - kbolino 10mo ago
      There are undoubtedly still some optimizations lying around, but the biggest source of Go's FFI overhead is goroutines. There's only two "easy" solutions I can see: switch to N:N threading model or make the C code goroutine-aware. The former would speed up C calls at the expense of slowing down lots of ordinary Go code. Personally, I can still see some scenarios where that's beneficial, but it's pretty niche. The latter would greatly complicate the use of cgo, and defeat one of its core purposes, namely having access to large hard-to-translate C codebases without requiring extensive modifications of them. A lot of people compare Go's FFI overhead to that of other natively compiled languages, like Zig or Rust, or to managed runtime languages like Java (JVM) or C# (.NET), but those alternatives don't use green threads (the general concept behind goroutines) as extensively. If you really want to compare apples-to-apples, you should compare against Erlang (BEAM). As far as I can tell, Erlang NIFs [1] are broadly similar to purego [2] calls, and their runtime performance [3] has more or less the same issues as CGo [4]. [1]: https://www.erlang.org/doc/system/nif.html https://www.erlang.org/doc/system/nif.html [2]: https://pkg.go.dev/github.com/ebitengine/purego https://pkg.go.dev/github.com/ebitengine/purego [3]: https://erlang.org/documentation/doc-10.1/doc/efficiency_guide/myths.html#myth--a-nif-always-speeds-up-your-program https://erlang.org/documentation/doc-10.1/doc/efficiency_gui... [4]: https://www.reddit.com/r/golang/comments/12nt2le/when_dealing_with_c_when_is_go_slow/ https://www.reddit.com/r/golang/comments/12nt2le/when_dealin...
      - fatty_patty89 10mo ago
        Java has green threads and c#/.net has logical threads
        kbolino 10mo ago
        Yes, I have cleaned up the wording a bit. Also, the common implementation of Rust's async is comparable to green threads, and I think Zig is adopting something like it too. However, the "normal" execution model on all of them is using heavyweight native threads, not green threads. As far as I can tell, FFI is either unsupported entirely or has the same kind of overhead as Go and Erlang do, when used from those languages' green threads.
adzm 10mo ago
This is a truly amazing accomplishment. Reading these kernels is a joy!
dboon 10mo ago
This is exactly the kind of thankless software which the world operates on. It’s unfortunate that such fundamental code hasn’t already been vectorized or the gills, but thank you for doing so! It’s excellent work
Sesse__ 10mo ago
> I grouped all Unicode 17 case-folding rules But why are you using the case-folding rules and not the collation rules?
- ashvardanian 10mo ago
  Yes, CaseFolding.txt. I'm considering using the collation rules for sorting. Now they only target lexicographic comparisons and seem to be 4x faster than Rust's standard quick-sort implementation, but few people use it: https://github.com/ashvardanian/StringWars?tab=readme-ov-file#sequence-operations https://github.com/ashvardanian/StringWars?tab=readme-ov-fil...
zvr 10mo ago
Thank you for this, and congrats on your achievement!

fatty_patty89 10mo ago

Thank you do the go bindings require cgo?

ashvardanian 10mo ago
The GoLang bindings – yes, they are based on cGo. I realize it's suboptimal, but seems like the only practical option at this point.
- fatty_patty89 10mo ago
  In a normal world the Go C FFI wouldn't have insane overhead but what can we do, the language is perfect and it will stay that way until morale improves. Thanks for the work you do
  - kardianos 10mo ago
    In a real (not "normal") world, trade-offs exist and Go choose a specific set of design points that are consequential.
  - kbolino 10mo ago
    There are undoubtedly still some optimizations lying around, but the biggest source of Go's FFI overhead is goroutines. There's only two "easy" solutions I can see: switch to N:N threading model or make the C code goroutine-aware. The former would speed up C calls at the expense of slowing down lots of ordinary Go code. Personally, I can still see some scenarios where that's beneficial, but it's pretty niche. The latter would greatly complicate the use of cgo, and defeat one of its core purposes, namely having access to large hard-to-translate C codebases without requiring extensive modifications of them. A lot of people compare Go's FFI overhead to that of other natively compiled languages, like Zig or Rust, or to managed runtime languages like Java (JVM) or C# (.NET), but those alternatives don't use green threads (the general concept behind goroutines) as extensively. If you really want to compare apples-to-apples, you should compare against Erlang (BEAM). As far as I can tell, Erlang NIFs [1] are broadly similar to purego [2] calls, and their runtime performance [3] has more or less the same issues as CGo [4]. [1]: https://www.erlang.org/doc/system/nif.html https://www.erlang.org/doc/system/nif.html [2]: https://pkg.go.dev/github.com/ebitengine/purego https://pkg.go.dev/github.com/ebitengine/purego [3]: https://erlang.org/documentation/doc-10.1/doc/efficiency_guide/myths.html#myth--a-nif-always-speeds-up-your-program https://erlang.org/documentation/doc-10.1/doc/efficiency_gui... [4]: https://www.reddit.com/r/golang/comments/12nt2le/when_dealing_with_c_when_is_go_slow/ https://www.reddit.com/r/golang/comments/12nt2le/when_dealin...
    - fatty_patty89 10mo ago
      Java has green threads and c#/.net has logical threads
      - kbolino 10mo ago
        Yes, I have cleaned up the wording a bit. Also, the common implementation of Rust's async is comparable to green threads, and I think Zig is adopting something like it too. However, the "normal" execution model on all of them is using heavyweight native threads, not green threads. As far as I can tell, FFI is either unsupported entirely or has the same kind of overhead as Go and Erlang do, when used from those languages' green threads.

adzm 10mo ago

This is a truly amazing accomplishment. Reading these kernels is a joy!

dboon 10mo ago

This is exactly the kind of thankless software which the world operates on. It’s unfortunate that such fundamental code hasn’t already been vectorized or the gills, but thank you for doing so! It’s excellent work

Sesse__ 10mo ago

> I grouped all Unicode 17 case-folding rules But why are you using the case-folding rules and not the collation rules?

ashvardanian 10mo ago
Yes, CaseFolding.txt. I'm considering using the collation rules for sorting. Now they only target lexicographic comparisons and seem to be 4x faster than Rust's standard quick-sort implementation, but few people use it: https://github.com/ashvardanian/StringWars?tab=readme-ov-file#sequence-operations https://github.com/ashvardanian/StringWars?tab=readme-ov-fil...

zvr 10mo ago

Thank you for this, and congrats on your achievement!