Adding UTF-8 byte array support to SafeRE

After publishing my first SafeRE blog post a month ago, I got an interesting feature request: add support for UTF-8-encoded byte arrays, in addition to Java Strings.

The person who requested it works on Trino, a widely used distributed SQL engine. For the Googlers in the audience, it’s similar to Dremel but with support for multiple at-rest storage formats. We used Trino at GitHub, so I was familiar with it.

The reason you might want the ability to run regexes over UTF-8-encoded byte arrays is that in systems like Trino, underlying string data is often stored as UTF-8 bytes, and if you can avoid going back and forth to Java Strings, you can substantially improve performance. A safe, linear-time regular expression library is important for these applications because users can supply regex patterns in their queries. A query engine might apply one of those patterns to millions or billions of values across many workers. Catastrophic backtracking in a single match can therefore turn into enormous CPU consumption across the cluster, while linear-time matching bounds the work in terms of the input size.

Making SafeRE independent of encoding

First, a bit of background on Unicode and string representations. Unicode is a standard for representing text. It assigns numeric values, called code points, to characters.¹ For example, the code point U+1F469 represents the woman emoji (👩). These code points are shared across all Unicode encodings.

What’s a Unicode encoding? It specifies how Unicode code points are represented as code units, which can then be stored or transmitted as bytes. Code units are the smallest units used by an encoding. In UTF-8, code units are 8 bits each. Because there are more than $2^8$ code points, some code points must be represented by multiple UTF-8 code units. For example, U+1F469 (woman emoji) is represented in UTF-8 by these four bytes: F0 9F 91 A9. UTF-8 is a variable-length encoding; some code points are represented by 1 code unit, and others by 2, 3, or 4 code units.

Java’s String API represents text in UTF-16, and its indices refer to 16-bit char code units. Modern JVMs can store some strings more compactly, but that is an implementation detail and does not change the API’s UTF-16 behavior. UTF-16 is also a variable-length encoding: some code points are represented by 2 code units, called a surrogate pair.

SafeRE’s engines operate on code points, not code units. I didn’t think deeply about this decision at the start of the project. RE2 operates on Unicode code points, so that’s what I did for SafeRE. But that decision turned out to be really important if I wanted to support a different encoding like UTF-8.

Instead of rewriting the engines, I could simply add a level of indirection between the input representation and the engine. Basically, you need to be able to step forward² one code point at a time, and you need position information that understands the underlying encoding. This level of indirection might harm performance, but HotSpot’s JIT is pretty good at optimizing virtual dispatch, so it could be performance-neutral. Plus, it means that a UTF-8 implementation would inherit all the correctness and performance work that has gone into SafeRE’s engines.

This is the approach SafeRE uses.

The resulting API looks like this:

byte[] bytes = "id=42; name=café".getBytes(UTF_8);
Utf8Input input = Utf8Input.validated(bytes);

Pattern pattern = Pattern.compile("name=(\\p{L}+)");
Utf8Matcher matcher = pattern.matcher(input);
if (matcher.find()) {
    int nameStart = matcher.start(1);
    int nameEnd = matcher.end(1);
}

Utf8Input is a borrowed view over a whole byte array or a window within one, so SafeRE doesn’t copy the input. Patterns are still compiled from Java Strings, but match and capture positions are UTF-8 byte offsets relative to the input view. Callers can use those bounds to slice their existing storage without allocating a String. The API also supports repeated find() calls and byte-native replacement.

Discovery and implementation

SafeRE contributor @cushon created a prototype of UTF-8 byte array support.³ I picked up the task from this amazing starting point.

The person who filed the feature request had mentioned that they were using RE2/J in Trino for exactly this, so initially my plan was to match the byte[] interface that RE2/J provides. But then, as I (or really, my agent) dug into Trino’s code, we learned that it was more complicated than this. Trino had actually forked RE2/J before RE2/J added byte[] support and built its own byte-native interface around Airlift’s Slice type. Airlift is a collection of Java libraries used by Trino, and Slice provides an efficient view over byte-oriented storage.

Trino often represents a string as a logical window into a larger backing array. Its regex functions depend on byte-relative match bounds so they can extract captures and split strings without copying. They also use repeated find() calls for extraction and counting, and they write replacements directly to byte-oriented output. Upstream RE2/J’s whole-array byte[] interface and String-oriented group and replacement operations weren’t enough. SafeRE needed to support array windows, relative byte offsets, repeated matching, and byte-native replacement without depending directly on Trino’s Slice type.

Performance was another complication: Trino had implemented a DFA (deterministic finite automaton) engine in their RE2/J fork! Upstream RE2/J has only an NFA (nondeterministic finite automaton), which limits its performance. If I wanted to meet Trino’s needs, I would need to make sure SafeRE could support everything Trino was using from its RE2/J fork.

Once I understood Trino’s needs, I wanted to make sure the feature could also be used in similar applications. So I had my agent review other large open-source Java data systems to see what they do for regex matching and synthesize the requirements for a more general SafeRE UTF-8 API. The result of this investigation is in the UTF-8 byte input design. For example, the review found that Flink’s BinaryStringData can store UTF-8 across multiple memory segments. SafeRE’s first implementation supports only byte[] windows, but putting them behind Utf8Input leaves room for a future segmented adapter without changing the matcher API.

My implementation, starting from @cushon’s PR, took about a day. I then took a benchmarking and optimization pass to restore any lost performance from adding this level of indirection. At this point, SafeRE’s UTF-8 API outperforms both Trino’s RE2/J fork and its native-UTF-8 backtracking engine, Joni, overall, based on a three-engine run of Trino’s regex microbenchmarks documented in SafeRE’s optimization PR. The matrix covered five pattern families at two input sizes for both matching and replacement. Each comparison below is the geometric mean of the per-benchmark speed ratios.

Workload group	SafeRE compared with RE2/J	SafeRE compared with Joni
Matching	2.48× faster	2.93× faster
Replacement	2.34× faster	1.08× slower
Across all benchmark cases	2.41× faster	1.64× faster

I suspect that SafeRE could outperform Joni on replacement workloads too with a bit more optimization work. I filed a follow-up issue to look at the specific benchmarks where Joni outperforms SafeRE and optimize them.

What I learned

SafeRE’s original goal was to be a drop-in replacement for java.util.regex, and that led me to inherit one of its assumptions: regex input is a Java String. But many Java data systems keep text in UTF-8-oriented storage and create a String only when an API requires one. Supporting them meant treating java.util.regex compatibility as one SafeRE interface, rather than as the definition of what a regex engine should be able to match. Fortunately, SafeRE’s engines were already more general than its public API: they operated on code points, not directly on Java Strings. It was fascinating to go down the rabbit hole of Java big data applications, learn about their needs, and discover a use case that the original compatibility goal had hidden from me.

A second lesson was how useful an agent⁴ can be beyond writing code. Building the final implementation from @cushon’s prototype took about a day; the resulting UTF-8 support PR changed 7,164 lines across 41 files. But just as important was the surrounding research and validation. The agent traced how Trino actually used its RE2/J fork, reviewed the string representations and regex APIs in other Java data systems, and helped turn those findings into a more general API. I wouldn’t have had time to do that much investigative work for a side project, and without it I probably would have shipped a narrower solution.

The optimization work was another good fit. Benchmarks provided an objective verifier, so the agent could repeatedly profile, propose a change, and measure the result.

Note: I wrote this post by hand. I used an agent for proofreading and feedback.

Footnotes

1. This isn’t quite true. There are graphemes where multiple code points combine to represent one user-perceived character. For example, 👩‍💻 is composed of three code points: U+1F469 U+200D U+1F4BB, or WOMAN + ZERO WIDTH JOINER + PERSONAL COMPUTER. The joiner code point tells the renderer to combine those three code points into one character on screen. ↩

2. Technically, SafeRE needs to also step backward one code point, because it has a reverse DFA as an optimization. ↩

3. @cushon contributed two versions of this—PR 520 added two new engines specialized for UTF-8, and PR 530 implemented the approach where SafeRE’s existing engines are adapted to be independent of encoding. ↩

4. I used Codex + GPT-5.6 Sol Medium for this. This was my first time using GPT-5.6, and it’s very impressive. ↩