hey it's me back again with a bigass wall of text about a thing. enjoy!
tl;dr: JEI search has to index a surprisingly large amount of text in big modpacks. I made two new small Java libraries for immutable substring search, then built a JMH benchmark to test a new JEI search-index approach against the current one. The early result: on a synthetic 100k-item JEI-like workload, the most promising new index retained about 259 MiB instead of about 426 MiB, roughly 40% less memory, while also making short searches much faster in the benchmark.
# The optimization problem
JEI search feels simple from the player's side: type a few letters, the item list filters down to show what you're looking for.
Internally, that search box has to deal with a lot of text though. Item names are the obvious part, but JEI also searches things like tooltip lines, mod names, and tags. In a large pack, that can become hundreds of thousands of searchable strings. But I can't just remove those to save RAM! Searching
copper, a mod name, a tag-like string, or some tooltip text is one of the things that makes JEI feel good to use.Every nice search feature has a cost. The index has to be built, it has to be kept in memory, and then it has to be fast enough to query repeatedly as the player types.
Since ram is becoming infinitely expensive, I started poking at a very specific question: Can JEI keep the same search features, but use less memory?
# The two new projects
I made two small Java libraries for this:
[baked-substring-index](https://github.com/mezz/baked-substring-index)
baked-suffix-array-index
Both are designed around the same basic idea:
1. Add key/value pairs to a builder.
2. Build an immutable index.
3. Share that built index for read-only lookup.
4. If the source data changes, build a new index.
That maps pretty well to JEI's use case. The searchable data is built after loading/reloading, then queried many times while the player types. The existing library used in JEI is my adaptation of a generalized-suffix-tree, which is mutable. I wanted to look at immutable alternatives since they might be more optimized for the bulk of items, and I can keep the old mutable tree around for when mods add more items at runtime.
The libraries are intentionally not trying to solve every search problem that's out there in the wider computer science world. They do exact Java
String substring matching. It's not pre-AI Google Search, there's no fuzzy search, no ranking, no locale-aware matching, no stemming, no edit distance. If callers want case folding or normalization, they can normalize before indexing and searching.>References:
>
>Esko Ukkonen, "On-line construction of suffix trees," Algorithmica 14, 249-260, 1995. DOI: https://doi.org/10.1007/BF01206331
>
>Udi Manber and Gene Myers. "Suffix Arrays: A New Method for On-Line String Searches." SIAM Journal on Computing, 22(5), 935-948, 1993. DOI: https://doi.org/10.1137/0222058.
>
>Fei Shi. "Suffix Arrays for Multiple Strings: A Method for On-Line Multiple String Searches." ASIAN 1996, Lecture Notes in Computer Science 1179, 11-22, 1996. Bibliographic record: https://dblp.org/rec/conf/asian/Shi96.
>
>Gonzalo Navarro and Ricardo Baeza-Yates, "A Practical q-Gram Index for Text Retrieval Allowing Errors", CLEI Electronic Journal 1(2), 1998. DOI: https://doi.org/10.19153/cleiej.1.2.3.
(I'm lagging, it turns out everything was already figured out by 1998...)
# Baked substring index
The baked substring index uses a q-gram-style approach.
In plain terms: it indexes the unique 1-, 2-, and 3-character fragments in each key.
For short searches like
c, co, or cop, it can look up the matching posting list