Test an FST bytes store that re-reverses (reads bytes forward) on-the-fly
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
At read-time the FST apis must read bytes in reverse, which is perverse and unnatural for all stacks in modern CPUs / IO devices that do read-ahead optimizations for forward reading.
It's quite complex to change the underlying FST format to become fundamentally forward only. It'd require rewriting node addresses, which may then take different numbers of `vInt` bytes, causing more renumbering, etc.
A simpler first step might be, at FST `freeze()` time (when the FST is done being compiled), reverse all bytes in the underlying storage (on disk or on heap), and at read time, pretend to the caller that they are still reading backwards, yet actually read forwards. We could even do this separately for each store, e.g. start by testing on-heap read-time double reversal, or maybe start with on-disk where the OS's readahead optimizations may matter more.
It should be relatively trivial to implement yet hard to think about, and we could see if it helps performance.
Contributor guide
Research direction
Start by locating the FST freeze() implementation and the read APIs for heap and on-disk stores. Compare the store-specific paths before choosing one to experiment with; done means the FST still reads correctly while the underlying bytes are reversed at freeze time and performance can be evaluated.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend, search
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100