directly. For longer searches like `copper`, it looks up the 3-character fragments, intersects the candidate lists, and then verifies the remaining candidates with `String.contains`.

That last verification step is important. If a key contains `cop` and `ppe`, that does not automatically mean it contains `copper`, so the full substring still gets checked before returning results.

This design is especially interesting for JEI because players often type one character, then two, then three. Those early searches are broad, frequent, and easily the most expensive.

# Baked suffix array index

The [baked suffix array index](https://github.com/mezz/baked-suffix-array-index) takes a different route.

A suffix array sorts every suffix of the indexed text. Once that sorted array exists, substring search becomes a binary search for the range of suffixes that start with the query. This implementation concatenates all keys into one encoded text array with separators between keys, so matches cannot cross from one key into the next. It stores the encoded text, suffix array, text-position-to-value mapping, and value references. It does not retain the original key strings after build.

If that sounds like insane nonsense to you, please [check out the README](https://github.com/mezz/baked-suffix-array-index/blob/main/README.md) where I give some examples using `banana`s, `bandana`s, and `cabana`s that even a highly caffeinated monkey could understand.

The suffix-array version is useful because Minecraft already has their own `SuffixArray`, and I wanted to make something comparable.

# The benchmark

To figure out what actually works, I made a separate benchmark project:

[substring-search-benchmarks](https://github.com/mezz/substring-search-benchmarks)

It uses [Java Microbenchmark Harness (JMH)](https://github.com/openjdk/jmh) and a synthetic large-catalog workload. It models:

* item names
* tooltip lines
* mod names
* tags
* the combined default-search of everything together

For the 100,000-item benchmark, the full combined one has about:

* 80,292 item-name strings
* 729,520 tooltip-line strings
* 430 mod-name strings
* 7,424 tag strings

That is 817,666 searchable strings total.

The benchmark compares:

* `baked-substring-index`
* `baked-suffix-array-index`
* Minecraft's built-in `SuffixArray`
* Abahgat's suffix tree
* my optimized fork of that suffix tree that has been in JEI for ages

The benchmark report with graphs is here:

[https://mezz.github.io/substring-search-benchmarks/](https://mezz.github.io/substring-search-benchmarks/)

# Results

Here are some results from the 100k-item default-search benchmark run.

Lower is better for all of these.

|Implementation|Approx retained memory|Build time|1-char search|3-char search|11-char search|
|:-|:-|:-|:-|:-|:-|
|Baked substring index|259 MiB|375 ms|0.656 ms|0.024 ms|0.073 ms|
|Baked suffix array index|352 MiB|2440 ms|34.851 ms|0.901 ms|0.030 ms|
|Minecraft suffix array|432 MiB|3695 ms|26.204 ms|0.974 ms|0.068 ms|
|JEI suffix tree|426 MiB|696 ms|5.629 ms|0.283 ms|0.016 ms|
|Abahgat suffix tree|590 MiB|995 ms|53.572 ms|2.121 ms|0.185 ms|

[Benchmark: Typed Search Time](https://preview.redd.it/gszx694ojafh1.png?width=995&format=png&auto=webp&s=d7f6e74764f0ca32d72f3dbf8ca58e18d7f3c421)

[Benchmark: Build time per item](https://preview.redd.it/fmqcdd5kfafh1.png?width=888&format=png&auto=webp&s=a793cc1d4665b2bce9b1e62b6975b055acfc0b63)

[Benchmark: Retained Memory](https://preview.redd.it/kmkro6xvfafh1.png?width=870&format=png&auto=webp&s=d0a835abd146d325144d40ad549450df005dd54f)

The biggest result for JEI is the memory number.

In this benchmark, the baked substring index retained about 259 MiB, compared to about 426 MiB for the old suffix tree. That is roughly 40% less retained memory for the full default-search test.

The short-search result is also very promising. One-character searches are extremely broad, and JEI runs searches while the player is typing. The baked substring index is built for that case: short queries hit direct fragment posting lists instead of walking a huge