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

suffix range.

Longer searches take longer for the Baked substring index, but keep in mind a frame rate of 120 FPS equals approximately 8.33 milliseconds per frame, so 0.073 milliseconds is not even 1% of a fast frame. It's still really fast.

The baked suffix array is more of an exploration of the suffix-array path. It retains less memory than Minecraft's suffix array here, and it does well on longer selective searches, but it is not great for very short broad searches.

# What this means for JEI

This is not me saying "JEI now uses 40% less memory." because JEI uses memory for other stuff too (like recipes) that I haven't bothered testing because I've been writing about computer science, and making little benchmark graphs about banana cabanas and whatever.

What I do think it shows is:

* JEI search memory can be optimized!
* Immutable baked indexes are a good fit for this
* A q-gram substring index looks like a strong candidate for JEI's new default search behavior

The next step was to integrate the new library into JEI [(committed here)](https://github.com/mezz/JustEnoughItems/commit/31b52164944e8f5824c091845016fb538e67bbf5). It's already released in JEI 30.13.0 for Minecraft 26.2, Jei 29.19.0 for Minecraft 26.1, and I'll continue backporting it to older versions. After that we can try measuring the retained memory in some real packs that people really actually use on real versions of Minecraft released a real long time ago.

# Why post about this?

JEI is 10+ years old and squeezing performance out of it is getting harder, there aren't as many low-hanging fruit as there used to be in the beginning! A lot of performance work is not obvious, and it's rarely one giant fix. It is usually a long trial of staring into the void, followed by a bunch of small tools, benchmarks, failed ideas, and hopefully eventually a useful improvement.

I made the libraries separately so they can be tested, documented, reused, and compared outside JEI. If they turn out to be useful for other mods or tools that need exact substring search over mostly-constant data, cool! Everything is released under the MIT license so people can copy and edit it.

# What you can do

If you are interested in this kind of thing:

1. Check out the benchmark report: [https://mezz.github.io/substring-search-benchmarks/](https://mezz.github.io/substring-search-benchmarks/)
2. Look at the two libraries, there's a lot of details in the READMEs for how they work:
* [https://github.com/mezz/baked-substring-index](https://github.com/mezz/baked-substring-index)
* [https://github.com/mezz/baked-suffix-array-index](https://github.com/mezz/baked-suffix-array-index)
3. If you have search-heavy Java code with data that is built once and queried many times, try them and see if the tradeoffs fit.
4. If you know of some better approaches for this, let me know!

I hope to keep JEI search useful, fast, and leave a little more memory for the game and the mods that really need it. I didn't do the math (and I'm not going to apply logic either) but if every player using JEI saves some ram, I have to reasonably assume that's probably saving billions of dollars, nice!

edit: fixed a graph with a weird y-axis label

https://redd.it/1v5vtib
@MinecraftModded

and it feels even worse because source is 100000x easier to get a william of
https://redd.it/1v5z9qv
@MinecraftModded

Ew, actual virus. Had to dig through its wiki to find how it was making it in my game, despite not installing it.
https://redd.it/1v65sfz
@MinecraftModded

Why are my blocks rotation locked?

https://redd.it/1v647u5
@MinecraftModded

In Rick and Morty, it is canon that Rick enjoys Minecraft. Would he enjoy tech packs like GTNH?

https://redd.it/1v6lhi9
@MinecraftModded

Introducing Shared Instances on Modrinth
https://modrinth.com/news/article/shared-instances/

https://redd.it/1v7ca4g
@MinecraftModded

Extreme hopium overdose
https://redd.it/1v7k2fa
@MinecraftModded

WHO THE FUCK SENDS SINGULARITY IN A CRATE

https://redd.it/1v7zh5r
@MinecraftModded

I made a minecraft mod for communicating without typing in chat

https://redd.it/1v86zon
@MinecraftModded

Introducing Build and Thrive, a modpack that (should) give an use for building

https://redd.it/1vemoh5
@MinecraftModded