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