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 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 where I give some examples using bananas, bandanas, and cabanas 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

It uses Java Microbenchmark Harness (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/

# 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

Benchmark: Build time per item

Benchmark: Retained Memory

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