Reverse FST storage so it can be read forward [LUCENE-8653]

[asfimport]

Discussion of keeping FST off-heap led to the idea of ensuring that FST's can be read forward in order to be more cache-friendly and align better with standard I/O practice. Today FSTs are read in reverse and this leads to some awkwardness, and you can't use standard readers so the code can be confusing to work with.

---

Migrated from LUCENE-8653 by Michael Sokolov (@msokolov), updated Jan 23 2019
Attachments: fst-reverse.patch

[asfimport]

Dawid Weiss (@dweiss) (migrated from JIRA)

The FSTs are by design really cache un-friendly. It's a graph that is traversed in a very irregular way. I don't think making it linear instead of reverse order will help much, but it's worth a shot. Also: Mike's "reverse" reader does have a reason (but I can't remember what it was off the top of my head).

[asfimport]

Michael Sokolov (@msokolov) (migrated from JIRA)

Yeah, some initial measurements using luceneutil are showing pretty neutral impact. I am also thinking of looking at memory-starved conditions and see what happens there, and there is an idea that this could end up helping the off-heap use case in #9681

 

[asfimport]

Michael Sokolov (@msokolov) (migrated from JIRA)

The reverse reading is required because the FST serializes itself from an Object-heavy DAG of Nodes and Arcs into an array of bytes by traversing the DAG backwards, but writing forwards into the byte storage. And it optimizes straight-line sections of the DAG by eliminating the explicit pointers and just implicitly pointing to the (logically) next Node in the byte array, so "next" here means at the next lower byte address. We can eliminate this reversal by reversing the byte array after serialization and fixing-up the explicit pointers when we read them. We can't really fix them up in place without more major surgery because they are VInts.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Impressive how simple this was!  I think it's simpler to think about, reading the byte[] in forward order, and it ought to be a bit more cache friendly.  I agree jumping between FST nodes is very random access, but e.g. at a given node as we scan the arcs looking for a match that would become sequential byte reads with this change.  Curious the impact is neutral, but maybe if we combine this with #9681 we can measure an impact?

[asfimport]

Lucene/Solr QA (migrated from JIRA)

❌ -1 overall

Vote	Subsystem	Runtime	Comment
			Prechecks
+1	test4tests	0m 0s	The patch appears to include 1 new or modified test files.
			master Compile Tests
+1	compile	0m 39s	master passed
			Patch Compile Tests
+1	compile	0m 39s	the patch passed
+1	javac	0m 39s	the patch passed
+1	Release audit (RAT)	0m 37s	the patch passed
+1	Check forbidden APIs	0m 32s	the patch passed
-1	Validate source patterns	0m 32s	Validate source patterns validate-source-patterns failed
			Other Tests
+1	unit	14m 43s	core in the patch passed.
+1	unit	2m 21s	test-framework in the patch passed.
		20m 44s

Subsystem	Report/Notes
JIRA Issue	LUCENE-8653
JIRA Patch URL	https://issues.apache.org/jira/secure/attachment/12955831/fst-reverse.patch
Optional Tests	compile javac unit ratsources checkforbiddenapis validatesourcepatterns
uname	Linux lucene1-us-west 4.4.0-137-generic #163~14.04.1-Ubuntu SMP Mon Sep 24 17:14:57 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
Build tool	ant
Personality	/home/jenkins/jenkins-slave/workspace/PreCommit-LUCENE-Build/sourcedir/dev-tools/test-patch/lucene-solr-yetus-personality.sh
git revision	master / 72a99e9
ant	version: Apache Ant(TM) version 1.9.3 compiled on July 24 2018
Default Java	1.8.0_191
Validate source patterns	https://builds.apache.org/job/PreCommit-LUCENE-Build/154/artifact/out/patch-validate-source-patterns-root.txt
Test Results	https://builds.apache.org/job/PreCommit-LUCENE-Build/154/testReport/
modules	C: lucene/core lucene/test-framework U: lucene
Console output	https://builds.apache.org/job/PreCommit-LUCENE-Build/154/console
Powered by	Apache Yetus 0.7.0 http://yetus.apache.org

This message was automatically generated.