You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "mikemccand (via GitHub)" <gi...@apache.org> on 2023/10/08 10:58:05 UTC
[PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
mikemccand opened a new pull request, #12633:
URL: https://github.com/apache/lucene/pull/12633
This is a first attempt (not committable yet! work in progress! many `nocommit`s!) to use a bounded `NodeHash` when finding common suffixes during FST compilation. It uses a simple double-barrel LRU cache to hold the `NodeHash` entries.
I created a simple tool, `IndexToFST`, to iterate all terms from a `luceneutil` benchy index and build an FST from them, and `test_all_sizes.py` to run this tool multiple times with different `NodeHash` sizes and gather the resulting metrics.
Relates #12542
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1361812236
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -17,50 +17,80 @@
package org.apache.lucene.util.fst;
import java.io.IOException;
-import org.apache.lucene.util.packed.PackedInts;
-import org.apache.lucene.util.packed.PagedGrowableWriter;
+import java.util.Arrays;
+import java.util.Locale;
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // primary table
+ private long[] table;
+
+ // how many nodes are stored in the primary table; when this gets full, we discard tableOld and move primary to it
+ private int count;
+ private int promoteCount;
+ private int missCount;
+ private int hitCount;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table, for a simplistic LRU behaviour
+ private long[] fallbackTable;
+
+ private final int mask;
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ public NodeHash(FST<T> fst, int tableSize, FST.BytesReader in) {
+ if (tableSize < 4) {
+ // 2 is a power of 2, but does not work because the rehash logic (at 2/3 capacity) becomes over-quantized, and the hash
+ // table becomes 100% full before moving to fallback, and then looking up an entry in 100% full hash table spins forever
+ throw new IllegalArgumentException("tableSize must at least 4; got: " + tableSize);
+ }
+ mask = tableSize - 1;
+ if ((mask & tableSize) != 0) {
+ throw new IllegalArgumentException("tableSize must be a power of 2; got: " + tableSize);
+ }
+ table = new long[tableSize];
+ fallbackTable = new long[tableSize];
this.fst = fst;
this.in = in;
}
+ /** Compares an unfrozen node (UnCompiledNode) with a frozen node at byte location address (long), returning
+ * true if they are equal. */
private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
fst.readFirstRealTargetArc(address, scratchArc, in);
Review Comment:
I think we should do that (fully decouple `NodeHash` from the FST's `byte[]`) as a follow-on issue? This change is tricky enough :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1360875178
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -17,50 +17,80 @@
package org.apache.lucene.util.fst;
import java.io.IOException;
-import org.apache.lucene.util.packed.PackedInts;
-import org.apache.lucene.util.packed.PagedGrowableWriter;
+import java.util.Arrays;
+import java.util.Locale;
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // primary table
+ private long[] table;
+
+ // how many nodes are stored in the primary table; when this gets full, we discard tableOld and move primary to it
+ private int count;
+ private int promoteCount;
+ private int missCount;
+ private int hitCount;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table, for a simplistic LRU behaviour
+ private long[] fallbackTable;
+
+ private final int mask;
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ public NodeHash(FST<T> fst, int tableSize, FST.BytesReader in) {
+ if (tableSize < 4) {
+ // 2 is a power of 2, but does not work because the rehash logic (at 2/3 capacity) becomes over-quantized, and the hash
+ // table becomes 100% full before moving to fallback, and then looking up an entry in 100% full hash table spins forever
+ throw new IllegalArgumentException("tableSize must at least 4; got: " + tableSize);
+ }
+ mask = tableSize - 1;
+ if ((mask & tableSize) != 0) {
+ throw new IllegalArgumentException("tableSize must be a power of 2; got: " + tableSize);
+ }
+ table = new long[tableSize];
+ fallbackTable = new long[tableSize];
this.fst = fst;
this.in = in;
}
+ /** Compares an unfrozen node (UnCompiledNode) with a frozen node at byte location address (long), returning
+ * true if they are equal. */
private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
fst.readFirstRealTargetArc(address, scratchArc, in);
Review Comment:
So does this means we still need to read from the in-writing FST? I'm wondering would it be possible to only read from the cache, then we can decouple the FST from NodeHash.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1365589420
##########
lucene/core/src/java/org/apache/lucene/util/fst/FST.java:
##########
@@ -827,18 +826,21 @@ int readNextArcLabel(Arc<T> arc, BytesReader in) throws IOException {
if (arc.bytesPerArc() != 0) {
// System.out.println(" nextArc real array");
// Arcs have fixed length.
- if (arc.nodeFlags() == ARCS_FOR_BINARY_SEARCH) {
- // Point to next arc, -1 to skip arc flags.
- in.setPosition(arc.posArcsStart() - (1 + arc.arcIdx()) * (long) arc.bytesPerArc() - 1);
- } else {
- assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
- // Direct addressing node. The label is not stored but rather inferred
- // based on first label and arc index in the range.
- assert BitTable.assertIsValid(arc, in);
- assert BitTable.isBitSet(arc.arcIdx(), arc, in);
- int nextIndex = BitTable.nextBitSet(arc.arcIdx(), arc, in);
- assert nextIndex != -1;
- return arc.firstLabel() + nextIndex;
+ switch (arc.nodeFlags()) {
+ case ARCS_FOR_BINARY_SEARCH:
+ // Point to next arc, -1 to skip arc flags.
+ in.setPosition(arc.posArcsStart() - (1 + arc.arcIdx()) * (long) arc.bytesPerArc() - 1);
+ break;
+ case ARCS_FOR_DIRECT_ADDRESSING:
+ // Direct addressing node. The label is not stored but rather inferred
+ // based on first label and arc index in the range.
+ assert BitTable.assertIsValid(arc, in);
+ assert BitTable.isBitSet(arc.arcIdx(), arc, in);
+ int nextIndex = BitTable.nextBitSet(arc.arcIdx(), arc, in);
+ assert nextIndex != -1;
+ return arc.firstLabel() + nextIndex;
+ default:
Review Comment:
Ahh you mean remove the outer `if` around this switch right? I like it! I'll do that.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1768373972
OK, I switched the accounting to approximate RAM usage of the `NodeHash`, which is more intuitive for users. It behaves monodically / smoothly: as you give more RAM for the suffixes stored in `NodeHash`, the resulting fst is smaller:
If you pass `Double.POSITIVE_INFINITY` (or any sufficiently large number) then we will store all suffixes and the resulting FST is minimal.
I think this is nearly ready -- I'll next clean up the remaining `nocommit`s, and downgrade some to `TODO`s.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1366903022
##########
lucene/core/src/java/org/apache/lucene/util/packed/AbstractPagedMutable.java:
##########
@@ -110,8 +110,10 @@ protected long baseRamBytesUsed() {
public long ramBytesUsed() {
long bytesUsed = RamUsageEstimator.alignObjectSize(baseRamBytesUsed());
bytesUsed += RamUsageEstimator.alignObjectSize(RamUsageEstimator.shallowSizeOf(subMutables));
+ // System.out.println("abstract.ramBytesUsed:");
Review Comment:
I don't think we have a general rule :) I'll remove these ones.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1753705229
Translating/merging the above two tables into a graph:
Some observations:
* The PR is mostly better at using less RAM to make the same size FST, yay!
* It is a more smooth/predictable/monotonic tradeoff: the larger the `NodeHash` size, the smaller the FST. Whereas on `main`, using the god-like parameters, it's more dicy/spiky/unpredictable. It's like you are the co-pilot trying to land a 747 alone using only toothpicks.
* At the "spend all the RAM necessary to get a truly minimal FST" end (the right of the chart) the PR looks like it uses a bit more RAM than `main`. I think I can improve on this by not wastefully using `long[]` but rather one of Lucene's many cool bit-packing dynamic/growable array thingys, like `main` does for its `NodeHash`. Or maybe @msokolov's idea to somehow do a reversed suffix lookup against the growing FST. I'll try that.
* Bang for the buck tapers off like you'd expect: the early MB of RAM you spend has a bigger payoff in reducing the FST size, while later MB of RAM is less and less impact. This is nice 80/20 like behavior...
* With the PR, you unfortunately cannot easily say "give me a minimal FST at all costs", like you can with `main` today. You'd have to keep trying larger and larger NodeHash sizes until the final FST size gets no smaller. I don't really like this regression -- I'll think about how to somehow keep that capability in the PR. E.g. we would want to use this option when compiling FSTs for Kuromoji, or users may want this when compiling synonym maps.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1366913164
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -99,20 +184,18 @@ private long hash(FSTCompiler.UnCompiledNode<T> node) {
h += 17;
}
}
- // System.out.println(" ret " + (h&Integer.MAX_VALUE));
+
Review Comment:
> I'll open a spinoff issue with this idea. Sounds like a low hanging hashing fruit!
I opened https://github.com/apache/lucene/issues/12704. Thanks @bruno-roustant!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1361814551
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -99,31 +87,23 @@ public class FSTCompiler<T> {
* tuning and tweaking, see {@link Builder}.
*/
public FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
Review Comment:
Yeah, that's a good point -- I'm not sure why we have a public ctor on this class. I'll see if I can remove it, maybe as follow-on PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "dweiss (via GitHub)" <gi...@apache.org>.
dweiss commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1752416032
I didn't get into all the details but I think this looks good. Your questions are indeed intriguing - I can't provide any explanation off the top of my head, really.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1365627269
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -20,76 +20,159 @@
import org.apache.lucene.util.packed.PackedInts;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+// TODO: any way to make a reversee suffix lookup (msokolov's idea) instead of more costly hash?
+// hmmm, though, hash is not so wasteful
+// since it does not have to store value of each entry: the value is the node pointer in the FST.
+// actually, there is much to save
+// there -- we would not need any long per entry -- we'd be able to start at the FST end node and
+// work backwards from the transitions
+
+// TODO: couldn't we prune natrually babck until we see a transition with an output? it's highly
+// unlikely (mostly impossible) such suffixes
+// can be shared?
+
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // primary table -- we add nodes into this until it reaches the requested tableSizeLimit/2, then
+ // we move it to fallback
+ private PagedGrowableHash primaryTable;
+
+ // how many nodes are allowed to store in both primary and fallback tables; when primary gets full
+ // (tableSizeLimit/2), we move it to the
+ // fallback table
+ private final long ramLimitBytes;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table,
+ // for a simplistic and lowish-RAM-overhead
+ // (compared to e.g. LinkedHashMap) LRU behaviour. fallbackTable is read-only.
+ private PagedGrowableHash fallbackTable;
+
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ /**
+ * ramLimitMB is the max RAM we can use for recording suffixes. If we hit this limit, the least
+ * recently used suffixes are discarded, and the FST is no longer minimalI. Still, larger
+ * ramLimitMB will make the FST smaller (closer to minimal).
+ */
+ public NodeHash(FST<T> fst, double ramLimitMB, FST.BytesReader in) {
+ if (ramLimitMB <= 0) {
+ throw new IllegalArgumentException("ramLimitMB must be > 0; got: " + ramLimitMB);
+ }
+ double asBytes = ramLimitMB * 1024 * 1024;
+ if (asBytes >= Long.MAX_VALUE) {
+ // quietly truncate to Long.MAX_VALUE in bytes too
+ ramLimitBytes = Long.MAX_VALUE;
+ } else {
+ ramLimitBytes = (long) asBytes;
+ }
+
+ primaryTable = new PagedGrowableHash();
this.fst = fst;
this.in = in;
}
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
- fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // Fail fast for a node with fixed length arcs.
- if (scratchArc.bytesPerArc() != 0) {
- if (scratchArc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- } else {
- assert scratchArc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) != scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
+ private long getFallback(FSTCompiler.UnCompiledNode<T> nodeIn, long hash) throws IOException {
+ if (fallbackTable == null) {
+ // no fallback yet (primary table is not yet large enough to swap)
+ return 0;
+ }
+ long pos = hash & fallbackTable.mask;
+ int c = 0;
+ while (true) {
+ long node = fallbackTable.get(pos);
+ if (node == 0) {
+ // not found
+ return 0;
+ } else if (nodesEqual(nodeIn, node)) {
+ // frozen version of this node is already here
+ return node;
}
+
+ // quadratic probe (but is it, really?)
+ pos = (pos + (++c)) & fallbackTable.mask;
}
+ }
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || !arc.output.equals(scratchArc.output())
- || ((FSTCompiler.CompiledNode) arc.target).node != scratchArc.target()
- || !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput())
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
+ public long add(FSTCompiler<T> fstCompiler, FSTCompiler.UnCompiledNode<T> nodeIn)
+ throws IOException {
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
+ long hash = hash(nodeIn);
+
+ long pos = hash & primaryTable.mask;
+ int c = 0;
+
+ while (true) {
+
+ long node = primaryTable.get(pos);
+ if (node == 0) {
+ // node is not in primary table; is it in fallback table?
+ node = getFallback(nodeIn, hash);
+ if (node != 0) {
+ // it was already in fallback -- promote to primary
+ primaryTable.set(pos, node);
} else {
- return false;
+ // not in fallback either -- freeze & add the incoming node
+
+ // freeze & add
+ node = fstCompiler.addNode(nodeIn);
+
+ // we use 0 as empty marker in hash table, so it better be impossible to get a frozen node
+ // at 0:
+ assert node != 0;
+
+ // confirm frozen hash and unfrozen hash are the same
+ assert hash(node) == hash : "mismatch frozenHash=" + hash(node) + " vs hash=" + hash;
+
+ primaryTable.set(pos, node);
}
+
+ // how many bytes would be used if we had "perfect" hashing:
+ long ramBytesUsed = primaryTable.count * PackedInts.bitsRequired(node) / 8;
+
+ // NOTE: we could instead use the more precise RAM used, but this leads to unpredictable
+ // quantized behavior due to 2X rehashing where for large ranges of the RAM limit, the
+ // size of the FST does not change, and then suddenly when you cross a secret threshold,
+ // it drops. With this approach (measuring "perfect" hash storage and approximating the
+ // overhead), the behaviour is more strictly monotonic: larger RAM limits smoothly result
+ // in smaller FSTs, even if the precise RAM used is not always under the limit.
+
+ // divide limit by 2 because fallback gets half the RAM and primary gets the other half
+ // divide by 2 again to account for approximate hash table overhead halfway between 33.3%
+ // and 66.7% occupancy = 50%
+ if (ramBytesUsed >= ramLimitBytes / (2 * 2)) {
+ // time to fallback -- fallback is now used read-only to promote a node (suffix) to
+ // primary if we encounter it again
+ fallbackTable = primaryTable;
Review Comment:
+1 to add a TODO :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1366900931
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -135,32 +123,28 @@ public class FSTCompiler<T> {
* Instantiates an FST/FSA builder with default settings and pruning options turned off. For more
* tuning and tweaking, see {@link Builder}.
*/
+ // TODO: remove this? Builder API should be the only entry point?
public FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
- this(inputType, 0, 0, true, true, Integer.MAX_VALUE, outputs, true, 15, 1f);
+ this(inputType, 32.0, outputs, true, 15, 1f);
}
private FSTCompiler(
FST.INPUT_TYPE inputType,
- int minSuffixCount1,
- int minSuffixCount2,
- boolean doShareSuffix,
- boolean doShareNonSingletonNodes,
- int shareMaxTailLength,
+ double suffixRAMLimitMB, // pass 0 to disable suffix compression/trie; larger values create
Review Comment:
Thanks @bruno-roustant -- I agree it looks awful :) -- but I think I'll just remove this wimpy comment. These private ctor parameters are better documented on the Builder setters.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1366910269
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -99,20 +184,18 @@ private long hash(FSTCompiler.UnCompiledNode<T> node) {
h += 17;
}
}
- // System.out.println(" ret " + (h&Integer.MAX_VALUE));
+
Review Comment:
> Do we need to mask with Long.MAX_VALUE below, since we mask anyway with the table mask?
You're right, this is pointless -- I'll remove from both hash functions -- then we preserve that top (sign) bit for this following change:
> Instead, we should multiply with the gold constant BitMixer#PHI_C64 (make it public).
Whoa, this sounds awesome! I was wondering if we could improve the simplistic hashing here ... I'll open a spinoff issue with this idea. Sounds like a low hanging hashing fruit!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1772988443
`Test2BFST` passed!
```
The slowest tests (exceeding 500 ms) during this run:
2993.94s Test2BFST.test (:lucene:core)
The slowest suites (exceeding 1s) during this run:
2994.06s Test2BFST (:lucene:core)
BUILD SUCCESSFUL in 49m 58s
246 actionable tasks: 78 executed, 168 up-to-date
```
That last check failed because of formatting -- I re-tidy'd and I think it's ready -- I'll push shortly.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1766041651
> > With the PR, you unfortunately cannot easily say "give me a minimal FST at all costs", like you can with main today. You'd have to keep trying larger and larger NodeHash sizes until the final FST size gets no smaller.
>
> If we replace `long[]` with a growable array that inits from small and grows smoothly to `nodeHashSize`, can we just pass a big nodeHashSize (e.g. 1L << 63) or a constant `NO_LIMIT` to get a minimal FST ?
I love this idea! This way the hash grows to consume only as much RAM as needed, up until the specified limit, at which point it begins pruning to cap the RAM usage at the limit.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1365607237
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -20,76 +20,159 @@
import org.apache.lucene.util.packed.PackedInts;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+// TODO: any way to make a reversee suffix lookup (msokolov's idea) instead of more costly hash?
+// hmmm, though, hash is not so wasteful
+// since it does not have to store value of each entry: the value is the node pointer in the FST.
+// actually, there is much to save
+// there -- we would not need any long per entry -- we'd be able to start at the FST end node and
+// work backwards from the transitions
+
+// TODO: couldn't we prune natrually babck until we see a transition with an output? it's highly
+// unlikely (mostly impossible) such suffixes
+// can be shared?
+
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // primary table -- we add nodes into this until it reaches the requested tableSizeLimit/2, then
+ // we move it to fallback
+ private PagedGrowableHash primaryTable;
+
+ // how many nodes are allowed to store in both primary and fallback tables; when primary gets full
+ // (tableSizeLimit/2), we move it to the
+ // fallback table
+ private final long ramLimitBytes;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table,
+ // for a simplistic and lowish-RAM-overhead
+ // (compared to e.g. LinkedHashMap) LRU behaviour. fallbackTable is read-only.
+ private PagedGrowableHash fallbackTable;
+
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ /**
+ * ramLimitMB is the max RAM we can use for recording suffixes. If we hit this limit, the least
+ * recently used suffixes are discarded, and the FST is no longer minimalI. Still, larger
+ * ramLimitMB will make the FST smaller (closer to minimal).
+ */
+ public NodeHash(FST<T> fst, double ramLimitMB, FST.BytesReader in) {
+ if (ramLimitMB <= 0) {
+ throw new IllegalArgumentException("ramLimitMB must be > 0; got: " + ramLimitMB);
+ }
+ double asBytes = ramLimitMB * 1024 * 1024;
+ if (asBytes >= Long.MAX_VALUE) {
+ // quietly truncate to Long.MAX_VALUE in bytes too
+ ramLimitBytes = Long.MAX_VALUE;
+ } else {
+ ramLimitBytes = (long) asBytes;
+ }
+
+ primaryTable = new PagedGrowableHash();
this.fst = fst;
this.in = in;
}
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
- fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // Fail fast for a node with fixed length arcs.
- if (scratchArc.bytesPerArc() != 0) {
- if (scratchArc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- } else {
- assert scratchArc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) != scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
+ private long getFallback(FSTCompiler.UnCompiledNode<T> nodeIn, long hash) throws IOException {
+ if (fallbackTable == null) {
+ // no fallback yet (primary table is not yet large enough to swap)
+ return 0;
+ }
+ long pos = hash & fallbackTable.mask;
+ int c = 0;
+ while (true) {
+ long node = fallbackTable.get(pos);
+ if (node == 0) {
+ // not found
+ return 0;
+ } else if (nodesEqual(nodeIn, node)) {
+ // frozen version of this node is already here
+ return node;
}
+
+ // quadratic probe (but is it, really?)
+ pos = (pos + (++c)) & fallbackTable.mask;
}
+ }
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || !arc.output.equals(scratchArc.output())
- || ((FSTCompiler.CompiledNode) arc.target).node != scratchArc.target()
- || !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput())
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
+ public long add(FSTCompiler<T> fstCompiler, FSTCompiler.UnCompiledNode<T> nodeIn)
+ throws IOException {
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
+ long hash = hash(nodeIn);
+
+ long pos = hash & primaryTable.mask;
+ int c = 0;
+
+ while (true) {
+
+ long node = primaryTable.get(pos);
+ if (node == 0) {
+ // node is not in primary table; is it in fallback table?
+ node = getFallback(nodeIn, hash);
+ if (node != 0) {
+ // it was already in fallback -- promote to primary
+ primaryTable.set(pos, node);
} else {
- return false;
+ // not in fallback either -- freeze & add the incoming node
+
+ // freeze & add
+ node = fstCompiler.addNode(nodeIn);
+
+ // we use 0 as empty marker in hash table, so it better be impossible to get a frozen node
+ // at 0:
+ assert node != 0;
+
+ // confirm frozen hash and unfrozen hash are the same
+ assert hash(node) == hash : "mismatch frozenHash=" + hash(node) + " vs hash=" + hash;
+
+ primaryTable.set(pos, node);
}
+
+ // how many bytes would be used if we had "perfect" hashing:
+ long ramBytesUsed = primaryTable.count * PackedInts.bitsRequired(node) / 8;
+
+ // NOTE: we could instead use the more precise RAM used, but this leads to unpredictable
+ // quantized behavior due to 2X rehashing where for large ranges of the RAM limit, the
+ // size of the FST does not change, and then suddenly when you cross a secret threshold,
+ // it drops. With this approach (measuring "perfect" hash storage and approximating the
+ // overhead), the behaviour is more strictly monotonic: larger RAM limits smoothly result
+ // in smaller FSTs, even if the precise RAM used is not always under the limit.
+
+ // divide limit by 2 because fallback gets half the RAM and primary gets the other half
+ // divide by 2 again to account for approximate hash table overhead halfway between 33.3%
+ // and 66.7% occupancy = 50%
+ if (ramBytesUsed >= ramLimitBytes / (2 * 2)) {
+ // time to fallback -- fallback is now used read-only to promote a node (suffix) to
+ // primary if we encounter it again
+ fallbackTable = primaryTable;
Review Comment:
We could indeed do that, but `PagedGrowableWriter` does not implement `clear` yet ... let's defer this small optimization? I'd rather get this change in soon to unblock all the other cool changes you've been working on. I'll add a `TODO` :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1363098628
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -17,79 +17,177 @@
package org.apache.lucene.util.fst;
import java.io.IOException;
-import org.apache.lucene.util.packed.PackedInts;
+import java.util.Arrays;
+import java.util.Locale;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+import org.apache.lucene.util.packed.PackedInts;;
+
+// nocommit we could gradually grow the double-barrel hash size based on size of the growing FST? hmm does not work so well since you
+// failed to use the larger hash in the beginning? it's fundamentally needing two passes?
+
+// TODO: any way to make a reversee suffix lookup (msokolov's idea) instead of more costly hash? hmmm, though, hash is not so wasteful
+// since it does not have to store value of each entry: the value is the node pointer in the FST. actually, there is much to save
+// there -- we would not need any long per entry -- we'd be able to start at the FST end node and work backwards from the transitions
+
+// TODO: couldn't we prune natrually babck until we see a transition with an output? it's highly unlikely (mostly impossible) such suffixes
+// can be shared?
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // nocommit
+ private static final boolean DO_PRINT_HASH_RAM = true;
+
+ // primary table -- we add nodes into this until it reaches the requested tableSizeLimit/2, then we move it to fallback
+ private PagedGrowableHash primaryTable;
+
+ // how many nodes are allowed to store in both primary and fallback tables; when primary gets full (tableSizeLimit/2), we move it to the
+ // fallback table
+ private final long ramLimitBytes;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table, for a simplistic and lowish-RAM-overhead
+ // (compared to e.g. LinkedHashMap) LRU behaviour
+ private PagedGrowableHash fallbackTable;
+
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ /** ramLimitMB is the max RAM we can use for recording suffixes. If we hit this limit, the least recently used suffixes are discarded, and
+ * the FST is no longer minimalI. Still, larger ramLimitMB will make the FST smaller (closer to minimal). */
+ public NodeHash(FST<T> fst, double ramLimitMB, FST.BytesReader in) {
+ if (ramLimitMB <= 0) {
+ throw new IllegalArgumentException("ramLimitMB must be > 0; got: " + ramLimitMB);
+ }
+ double asBytes = ramLimitMB * 1024 * 1024;
+ if (asBytes >= Long.MAX_VALUE) {
+ // quietly truncate to Long.MAX_VALUE in bytes too
+ ramLimitBytes = Long.MAX_VALUE;
+ } else {
+ ramLimitBytes = (long) asBytes;
+ }
+
+ primaryTable = new PagedGrowableHash();
this.fst = fst;
this.in = in;
}
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
- fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // Fail fast for a node with fixed length arcs.
- if (scratchArc.bytesPerArc() != 0) {
- if (scratchArc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- } else {
- assert scratchArc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) != scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
+ // nocommit measure how wasteful/conflicty these hash tables are. should we improve hash function?
+
+ private long getFallback(FSTCompiler.UnCompiledNode<T> nodeIn, long hash) throws IOException {
+ if (fallbackTable == null) {
+ // no fallback yet (primary table is not yet large enough to swap)
+ return 0;
+ }
+ long pos = hash & fallbackTable.mask;
+ int c = 0;
+ while (true) {
+ long node = fallbackTable.get(pos);
+ if (node == 0) {
+ // not found
+ return 0;
+ } else if (nodesEqual(nodeIn, node)) {
+ // frozen version of this node is already here
+ return node;
}
+
+ // nocommit -- is this really quadratic probe?
+ // quadratic probe
+ pos = (pos + (++c)) & fallbackTable.mask;
}
+ }
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || !arc.output.equals(scratchArc.output())
- || ((FSTCompiler.CompiledNode) arc.target).node != scratchArc.target()
- || !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput())
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
+ public long add(FSTCompiler<T> fstCompiler, FSTCompiler.UnCompiledNode<T> nodeIn)
+ throws IOException {
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
+ long hash = hash(nodeIn);
+
+ long pos = hash & primaryTable.mask;
+ int c = 0;
+
+ while (true) {
+
+ long node = primaryTable.get(pos);
+ if (node == 0) {
+ // node is not in primary table; is it in fallback table?
+ node = getFallback(nodeIn, hash);
+ if (node != 0) {
+ // it was already in fallback -- promote to primary
+ primaryTable.set(pos, node);
} else {
- return false;
+ // not in fallback either -- freeze & add the incoming node
+
+ // freeze & add
+ node = fst.addNode(fstCompiler, nodeIn);
+
+ // we use 0 as empty marker in hash table, so it better be impossible to get a frozen node at 0:
+ assert node != 0;
+
+ // confirm frozen hash and unfrozen hash are the same
+ assert hash(node) == hash : "mismatch frozenHash=" + hash(node) + " vs hash=" + hash;
Review Comment:
Not necessarily related to this CR
This seems to be only for assertion, but `hash(long)` require reading the FST and thus one obstacle to decouple the NodeHash & FST. I'm wondering if it would make sense to let `fst.addNode` (it should be `fstCompiler.addNode()` now) return the node value instead of node address.
The 2nd and final obstacle is `nodeEquals`. But it seems it would require the cache table to store the node value & address instead of just address. Maybe we can build a LRU cache from nodeAddress to nodeValue? Storing value would mean more heap for small FST though.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1752165322
For comparison, this is how the curve (RAM required during construction vs final FST size) looks on trunk, using the god-like parameters as best I could. I sorted the results in reverse `FST (mb)` order but not that this results in a confusing mix of the first three columns (the god-like parameters).
I'll try to turn these two tables into a single chart comparing RAM used and final FST size and maybe build time:
|Share suffix?|Share non-singleton?|Max tail length|FST (mb)|RAM (mb)|Build time (sec)|
|-------------|--------|--------|----------------|----------------|----------------|
|True|True|1|584.3|0.0|30.5|
|True|False|1|584.3|0.0|30.5|
|True|True|0|577.4|0.0|30.1|
|True|False|0|577.4|0.0|30.2|
|False|True|0|577.4|0.0|29.9|
|False|False|0|577.4|0.0|29.8|
|True|False|2|576.4|0.0|31.4|
|True|True|2|569.9|14.5|32.4|
|True|False|3|523.7|3.6|32.2|
|True|True|3|509.7|29.0|34.1|
|True|False|4|486.2|7.0|32.9|
|True|True|4|468.9|58.0|36.7|
|True|False|5|456.1|14.0|34.1|
|True|True|5|437.6|56.0|37.8|
|True|False|6|435.4|28.0|35.3|
|True|False|7|419.8|58.0|36.6|
|True|True|6|416.1|116.0|41.2|
|True|False|8|408.1|56.0|37.6|
|True|True|7|399.8|116.0|41.7|
|True|False|9|398.8|116.0|39.9|
|True|False|10|392.1|116.0|40.5|
|True|True|8|387.8|112.0|43.3|
|True|False|11|387.2|116.0|40.7|
|True|False|12|383.7|112.0|41.2|
|True|False|13|381.0|112.0|41.8|
|True|False|14|379.1|112.0|42.1|
|True|True|9|378.2|112.0|45.2|
|True|False|15|377.6|232.0|44.4|
|True|False|16|376.5|232.0|44.0|
|True|False|17|375.6|232.0|45.0|
|True|False|18|374.9|232.0|44.5|
|True|False|19|374.3|232.0|45.6|
|True|False|20|373.9|232.0|44.7|
|True|False|2147483647|371.8|224.0|46.2|
|True|True|10|371.3|232.0|49.5|
|True|True|11|366.2|232.0|48.3|
|True|True|12|362.6|232.0|50.0|
|True|True|13|359.8|232.0|49.3|
|True|True|14|357.8|224.0|49.0|
|True|True|15|356.3|224.0|49.2|
|True|True|16|355.1|224.0|50.2|
|True|True|17|354.2|224.0|50.7|
|True|True|18|353.5|224.0|50.8|
|True|True|19|352.9|224.0|51.4|
|True|True|20|352.4|224.0|51.8|
|True|True|2147483647|350.2|464.0|56.9|
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1363823134
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -17,79 +17,177 @@
package org.apache.lucene.util.fst;
import java.io.IOException;
-import org.apache.lucene.util.packed.PackedInts;
+import java.util.Arrays;
+import java.util.Locale;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+import org.apache.lucene.util.packed.PackedInts;;
+
+// nocommit we could gradually grow the double-barrel hash size based on size of the growing FST? hmm does not work so well since you
+// failed to use the larger hash in the beginning? it's fundamentally needing two passes?
+
+// TODO: any way to make a reversee suffix lookup (msokolov's idea) instead of more costly hash? hmmm, though, hash is not so wasteful
+// since it does not have to store value of each entry: the value is the node pointer in the FST. actually, there is much to save
+// there -- we would not need any long per entry -- we'd be able to start at the FST end node and work backwards from the transitions
+
+// TODO: couldn't we prune natrually babck until we see a transition with an output? it's highly unlikely (mostly impossible) such suffixes
+// can be shared?
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // nocommit
+ private static final boolean DO_PRINT_HASH_RAM = true;
+
+ // primary table -- we add nodes into this until it reaches the requested tableSizeLimit/2, then we move it to fallback
+ private PagedGrowableHash primaryTable;
+
+ // how many nodes are allowed to store in both primary and fallback tables; when primary gets full (tableSizeLimit/2), we move it to the
+ // fallback table
+ private final long ramLimitBytes;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table, for a simplistic and lowish-RAM-overhead
+ // (compared to e.g. LinkedHashMap) LRU behaviour
+ private PagedGrowableHash fallbackTable;
+
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ /** ramLimitMB is the max RAM we can use for recording suffixes. If we hit this limit, the least recently used suffixes are discarded, and
+ * the FST is no longer minimalI. Still, larger ramLimitMB will make the FST smaller (closer to minimal). */
+ public NodeHash(FST<T> fst, double ramLimitMB, FST.BytesReader in) {
+ if (ramLimitMB <= 0) {
+ throw new IllegalArgumentException("ramLimitMB must be > 0; got: " + ramLimitMB);
+ }
+ double asBytes = ramLimitMB * 1024 * 1024;
+ if (asBytes >= Long.MAX_VALUE) {
+ // quietly truncate to Long.MAX_VALUE in bytes too
+ ramLimitBytes = Long.MAX_VALUE;
+ } else {
+ ramLimitBytes = (long) asBytes;
+ }
+
+ primaryTable = new PagedGrowableHash();
this.fst = fst;
this.in = in;
}
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
- fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // Fail fast for a node with fixed length arcs.
- if (scratchArc.bytesPerArc() != 0) {
- if (scratchArc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- } else {
- assert scratchArc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) != scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
+ // nocommit measure how wasteful/conflicty these hash tables are. should we improve hash function?
+
+ private long getFallback(FSTCompiler.UnCompiledNode<T> nodeIn, long hash) throws IOException {
+ if (fallbackTable == null) {
+ // no fallback yet (primary table is not yet large enough to swap)
+ return 0;
+ }
+ long pos = hash & fallbackTable.mask;
+ int c = 0;
+ while (true) {
+ long node = fallbackTable.get(pos);
+ if (node == 0) {
+ // not found
+ return 0;
+ } else if (nodesEqual(nodeIn, node)) {
+ // frozen version of this node is already here
+ return node;
}
+
+ // nocommit -- is this really quadratic probe?
+ // quadratic probe
+ pos = (pos + (++c)) & fallbackTable.mask;
}
+ }
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || !arc.output.equals(scratchArc.output())
- || ((FSTCompiler.CompiledNode) arc.target).node != scratchArc.target()
- || !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput())
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
+ public long add(FSTCompiler<T> fstCompiler, FSTCompiler.UnCompiledNode<T> nodeIn)
+ throws IOException {
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
+ long hash = hash(nodeIn);
+
+ long pos = hash & primaryTable.mask;
+ int c = 0;
+
+ while (true) {
+
+ long node = primaryTable.get(pos);
+ if (node == 0) {
+ // node is not in primary table; is it in fallback table?
+ node = getFallback(nodeIn, hash);
+ if (node != 0) {
+ // it was already in fallback -- promote to primary
+ primaryTable.set(pos, node);
} else {
- return false;
+ // not in fallback either -- freeze & add the incoming node
+
+ // freeze & add
+ node = fst.addNode(fstCompiler, nodeIn);
+
+ // we use 0 as empty marker in hash table, so it better be impossible to get a frozen node at 0:
+ assert node != 0;
+
+ // confirm frozen hash and unfrozen hash are the same
+ assert hash(node) == hash : "mismatch frozenHash=" + hash(node) + " vs hash=" + hash;
Review Comment:
> This seems to be only for assertion, but `hash(long)` require reading the FST and thus one obstacle to decouple the NodeHash & FST. I'm wondering if it would make sense to let `fst.addNode` (it should be `fstCompiler.addNode()` now) return the node value instead of node address.
This assertion is quite important for now, because we have two completely different `hash(...)` implementations: one reads from an already frozen node written into the growing FST (a `byte[]`) and the other from an unfrozen node.
> The 2nd and final obstacle is `nodeEquals`. But it seems it would require the cache table to store the node value & address instead of just address. Maybe we can build a LRU cache from nodeAddress to nodeValue? Storing value would mean more heap for small FST though.
Hmm, if the hash table stores the full node value `byte[]` (instead of a reference into the growing FST `byte[]`), I think we would still need a `nodeEquals` method to compare unfrozen and frozen nodes? Or maybe we could just always freeze the pending unfrozen node to do our comparisons, but often that would be wasted work since the same node (suffix) already exists in the `NodeHash`?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1751999625
Here are the results from running `test_all_sizes.py` then `results_to_md.py`:
|NodeHash size|FST (mb)|RAM (mb)|FST build time (sec)|
|-------------|--------|--------|----------------|
|0|577.4|0.0|35.2|
|4|586.5|0.0|43.2|
|8|587.0|0.0|46.4|
|16|585.2|0.0|44.8|
|32|582.0|0.0|45.9|
|64|578.8|0.0|45.4|
|128|573.0|0.0|45.9|
|256|563.6|0.0|46.1|
|512|551.2|0.0|45.4|
|1024|537.5|0.0|45.7|
|2048|523.4|0.0|46.0|
|4096|509.5|0.1|45.6|
|8192|495.8|0.1|45.2|
|16384|481.8|0.2|46.3|
|32768|461.1|0.5|45.2|
|65536|447.2|1.0|45.7|
|131072|432.4|2.0|46.3|
|262144|418.6|4.0|46.3|
|524288|402.4|8.0|46.9|
|1048576|391.0|16.0|50.0|
|2097152|380.8|32.0|55.2|
|4194304|371.4|64.0|58.3|
|8388608|362.5|128.0|59.9|
|16777216|356.1|256.0|59.3|
|33554432|351.4|512.0|57.3|
|67108864|350.2|1024.0|52.6|
|134217728|350.2|2048.0|49.2|
|268435456|350.2|4096.0|48.4|
|536870912|350.2|8192.0|46.9|
|1073741824|350.2|16384.0|44.5|
One WTF (wow that's funny) is why a `NodeHash` size of 0 (no prefix sharing) creates a smaller FST than the tiny `NodeHash` sizes: it should be monotonic since the `NodeHash` should only enable sharing of suffixes. Maybe something about the loss of locality of the FST suffix nodes, causing more bytes to refer to them later? Confusing.
Another observation is that it takes quite a few RAM MB to bring the final FST size close-ish to its optimal / minimal size (350.2 MB).
It's also curious how the FST Build time grows with a larger `NodeHash` -- maybe this is just the added cost of maintaining/cycling the double barrel hash (and promoting entries from the "old" to the "new" barrel)?
I will try soonish to post a similar table from `main` (unbounded `NodeHash`) for comparison to this approach by tuning the god-like knobs for controlling RAM usage during FST compilation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "dungba88 (via GitHub)" <gi...@apache.org>.
dungba88 commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1360866889
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -99,31 +87,23 @@ public class FSTCompiler<T> {
* tuning and tweaking, see {@link Builder}.
*/
public FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
Review Comment:
Unrelated to this PR and just my thought that would it be more maintainable in the long run if we only have a single way to build the FST through the Builder?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "bruno-roustant (via GitHub)" <gi...@apache.org>.
bruno-roustant commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1366758770
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -20,76 +20,161 @@
import org.apache.lucene.util.packed.PackedInts;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+// TODO: any way to make a reverse suffix lookup (msokolov's idea) instead of more costly hash?
+// hmmm, though, hash is not so wasteful
+// since it does not have to store value of each entry: the value is the node pointer in the FST.
+// actually, there is much to save
+// there -- we would not need any long per entry -- we'd be able to start at the FST end node and
+// work backwards from the transitions
+
+// TODO: couldn't we prune natrually babck until we see a transition with an output? it's highly
Review Comment:
"natrually babck"
##########
lucene/core/src/java/org/apache/lucene/util/packed/AbstractPagedMutable.java:
##########
@@ -110,8 +110,10 @@ protected long baseRamBytesUsed() {
public long ramBytesUsed() {
long bytesUsed = RamUsageEstimator.alignObjectSize(baseRamBytesUsed());
bytesUsed += RamUsageEstimator.alignObjectSize(RamUsageEstimator.shallowSizeOf(subMutables));
+ // System.out.println("abstract.ramBytesUsed:");
Review Comment:
Do we keep these commented prints?
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -99,20 +184,18 @@ private long hash(FSTCompiler.UnCompiledNode<T> node) {
h += 17;
}
}
- // System.out.println(" ret " + (h&Integer.MAX_VALUE));
+
Review Comment:
Do we need to mask with Long.MAX_VALUE below, since we mask anyway with the table mask?
Instead, we should multiply with the gold constant BitMixer#PHI_C64 (make it public).
This really makes a difference in the evenness of the value distribution. This is one of the secrets of the HPPC hashing. By applying this, we get multiple advantages:
- lookup should be improved (less hash collision)
- we can try to rehash at 3/4 occupancy because the performance should not be impacted until this point.
- in case of hash collision, we can lookup linearly with a pos = pos + 1 instead of quadratic probe (lines 95 and 327); this may avoid some mem cache miss.
(same for the other hash method)
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -135,32 +123,28 @@ public class FSTCompiler<T> {
* Instantiates an FST/FSA builder with default settings and pruning options turned off. For more
* tuning and tweaking, see {@link Builder}.
*/
+ // TODO: remove this? Builder API should be the only entry point?
public FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
- this(inputType, 0, 0, true, true, Integer.MAX_VALUE, outputs, true, 15, 1f);
+ this(inputType, 32.0, outputs, true, 15, 1f);
}
private FSTCompiler(
FST.INPUT_TYPE inputType,
- int minSuffixCount1,
- int minSuffixCount2,
- boolean doShareSuffix,
- boolean doShareNonSingletonNodes,
- int shareMaxTailLength,
+ double suffixRAMLimitMB, // pass 0 to disable suffix compression/trie; larger values create
Review Comment:
`@param`in method javadoc instead? This is not easy to read with spotless truncation.
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -207,59 +187,26 @@ public Builder(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
}
/**
- * If pruning the input graph during construction, this threshold is used for telling if a node
- * is kept or pruned. If transition_count(node) >= minSuffixCount1, the node is kept.
+ * The approximate maximum amount of RAM (in MB) to use holding the suffix cache, which enables
+ * the FST to share common suffixes. Pass {@link Double#POSITIVE_INFINITY} to keep all suffixes
+ * and create an exactly minimal FST. In this case, the amount of RAM actually used will be
+ * bounded by the number of unique suffixes. If you pass a value smaller than the builder would
+ * use, the least recently used suffixes will be discarded, thus reducing suffix sharing and
+ * creating a non-minimal FST. In this case, the larger the limit, the closer the FST will be to
+ * its true minimal size, with diminishing returns as you increasea the limit. Pass {@code 0} to
Review Comment:
"increasea"
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1772672994
I'll also confirm `Test2BFST` still passes ... soon this test will no longer require a 35 GB heap to run!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1365585941
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -135,32 +123,27 @@ public class FSTCompiler<T> {
* Instantiates an FST/FSA builder with default settings and pruning options turned off. For more
* tuning and tweaking, see {@link Builder}.
*/
+ // TODO: remove this? Builder API should be the only entry point?
public FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
- this(inputType, 0, 0, true, true, Integer.MAX_VALUE, outputs, true, 15, 1f);
+ this(inputType, 32.0, outputs, true, 15, 1f);
}
private FSTCompiler(
FST.INPUT_TYPE inputType,
- int minSuffixCount1,
- int minSuffixCount2,
- boolean doShareSuffix,
- boolean doShareNonSingletonNodes,
- int shareMaxTailLength,
+ double suffixRAMLimitMB, // pass 0 to disable suffix compression/trie; must be power of two
Review Comment:
Ahh no we do not -- good catch! I'll remove.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1771137767
Thanks @gf2121 -- I agree! So much more intuitive to tell the FST compiler how much RAM it can use to make as minimal an FST as it can. This means we can build bigger FSTs with less worry about heap sizes, and once we get "stream to disk" working, then FST building in a fixed amount of RAM is truly possible. Thank you [Tantivy's FST implementation](https://blog.burntsushi.net/transducers) for inspiring these changes!
I'll leave this for another day or so, and then merge at first only to `main` and let it cook for a while before backporting to 9.x.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #12633:
URL: https://github.com/apache/lucene/pull/12633#discussion_r1365326455
##########
lucene/core/src/java/org/apache/lucene/util/fst/FST.java:
##########
@@ -827,18 +826,21 @@ int readNextArcLabel(Arc<T> arc, BytesReader in) throws IOException {
if (arc.bytesPerArc() != 0) {
// System.out.println(" nextArc real array");
// Arcs have fixed length.
- if (arc.nodeFlags() == ARCS_FOR_BINARY_SEARCH) {
- // Point to next arc, -1 to skip arc flags.
- in.setPosition(arc.posArcsStart() - (1 + arc.arcIdx()) * (long) arc.bytesPerArc() - 1);
- } else {
- assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
- // Direct addressing node. The label is not stored but rather inferred
- // based on first label and arc index in the range.
- assert BitTable.assertIsValid(arc, in);
- assert BitTable.isBitSet(arc.arcIdx(), arc, in);
- int nextIndex = BitTable.nextBitSet(arc.arcIdx(), arc, in);
- assert nextIndex != -1;
- return arc.firstLabel() + nextIndex;
+ switch (arc.nodeFlags()) {
+ case ARCS_FOR_BINARY_SEARCH:
+ // Point to next arc, -1 to skip arc flags.
+ in.setPosition(arc.posArcsStart() - (1 + arc.arcIdx()) * (long) arc.bytesPerArc() - 1);
+ break;
+ case ARCS_FOR_DIRECT_ADDRESSING:
+ // Direct addressing node. The label is not stored but rather inferred
+ // based on first label and arc index in the range.
+ assert BitTable.assertIsValid(arc, in);
+ assert BitTable.isBitSet(arc.arcIdx(), arc, in);
+ int nextIndex = BitTable.nextBitSet(arc.arcIdx(), arc, in);
+ assert nextIndex != -1;
+ return arc.firstLabel() + nextIndex;
+ default:
Review Comment:
Can we use the pattern like what we did in `readNextRealArc` for consistency ?
```
switch (arc.nodeFlags()) {
case ARCS_FOR_BINARY_SEARCH:
...
case ARCS_FOR_DIRECT_ADDRESSING:
...
default:
// Variable length arcs - linear search.
assert arc.bytesPerArc() == 0;
...
```
##########
lucene/core/src/java/org/apache/lucene/util/fst/FSTCompiler.java:
##########
@@ -135,32 +123,27 @@ public class FSTCompiler<T> {
* Instantiates an FST/FSA builder with default settings and pruning options turned off. For more
* tuning and tweaking, see {@link Builder}.
*/
+ // TODO: remove this? Builder API should be the only entry point?
public FSTCompiler(FST.INPUT_TYPE inputType, Outputs<T> outputs) {
- this(inputType, 0, 0, true, true, Integer.MAX_VALUE, outputs, true, 15, 1f);
+ this(inputType, 32.0, outputs, true, 15, 1f);
}
private FSTCompiler(
FST.INPUT_TYPE inputType,
- int minSuffixCount1,
- int minSuffixCount2,
- boolean doShareSuffix,
- boolean doShareNonSingletonNodes,
- int shareMaxTailLength,
+ double suffixRAMLimitMB, // pass 0 to disable suffix compression/trie; must be power of two
Review Comment:
Do we still need it to be a power of two ?
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -20,76 +20,159 @@
import org.apache.lucene.util.packed.PackedInts;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+// TODO: any way to make a reversee suffix lookup (msokolov's idea) instead of more costly hash?
Review Comment:
```suggestion
// TODO: any way to make a reverse suffix lookup (msokolov's idea) instead of more costly hash?
```
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -20,76 +20,159 @@
import org.apache.lucene.util.packed.PackedInts;
import org.apache.lucene.util.packed.PagedGrowableWriter;
+// TODO: any way to make a reversee suffix lookup (msokolov's idea) instead of more costly hash?
+// hmmm, though, hash is not so wasteful
+// since it does not have to store value of each entry: the value is the node pointer in the FST.
+// actually, there is much to save
+// there -- we would not need any long per entry -- we'd be able to start at the FST end node and
+// work backwards from the transitions
+
+// TODO: couldn't we prune natrually babck until we see a transition with an output? it's highly
+// unlikely (mostly impossible) such suffixes
+// can be shared?
+
// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {
- private PagedGrowableWriter table;
- private long count;
- private long mask;
+ // primary table -- we add nodes into this until it reaches the requested tableSizeLimit/2, then
+ // we move it to fallback
+ private PagedGrowableHash primaryTable;
+
+ // how many nodes are allowed to store in both primary and fallback tables; when primary gets full
+ // (tableSizeLimit/2), we move it to the
+ // fallback table
+ private final long ramLimitBytes;
+
+ // fallback table. if we fallback and find the frozen node here, we promote it to primary table,
+ // for a simplistic and lowish-RAM-overhead
+ // (compared to e.g. LinkedHashMap) LRU behaviour. fallbackTable is read-only.
+ private PagedGrowableHash fallbackTable;
+
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<>();
private final FST.BytesReader in;
- public NodeHash(FST<T> fst, FST.BytesReader in) {
- table = new PagedGrowableWriter(16, 1 << 27, 8, PackedInts.COMPACT);
- mask = 15;
+ /**
+ * ramLimitMB is the max RAM we can use for recording suffixes. If we hit this limit, the least
+ * recently used suffixes are discarded, and the FST is no longer minimalI. Still, larger
+ * ramLimitMB will make the FST smaller (closer to minimal).
+ */
+ public NodeHash(FST<T> fst, double ramLimitMB, FST.BytesReader in) {
+ if (ramLimitMB <= 0) {
+ throw new IllegalArgumentException("ramLimitMB must be > 0; got: " + ramLimitMB);
+ }
+ double asBytes = ramLimitMB * 1024 * 1024;
+ if (asBytes >= Long.MAX_VALUE) {
+ // quietly truncate to Long.MAX_VALUE in bytes too
+ ramLimitBytes = Long.MAX_VALUE;
+ } else {
+ ramLimitBytes = (long) asBytes;
+ }
+
+ primaryTable = new PagedGrowableHash();
this.fst = fst;
this.in = in;
}
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address) throws IOException {
- fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // Fail fast for a node with fixed length arcs.
- if (scratchArc.bytesPerArc() != 0) {
- if (scratchArc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- } else {
- assert scratchArc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) != scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
+ private long getFallback(FSTCompiler.UnCompiledNode<T> nodeIn, long hash) throws IOException {
+ if (fallbackTable == null) {
+ // no fallback yet (primary table is not yet large enough to swap)
+ return 0;
+ }
+ long pos = hash & fallbackTable.mask;
+ int c = 0;
+ while (true) {
+ long node = fallbackTable.get(pos);
+ if (node == 0) {
+ // not found
+ return 0;
+ } else if (nodesEqual(nodeIn, node)) {
+ // frozen version of this node is already here
+ return node;
}
+
+ // quadratic probe (but is it, really?)
+ pos = (pos + (++c)) & fallbackTable.mask;
}
+ }
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || !arc.output.equals(scratchArc.output())
- || ((FSTCompiler.CompiledNode) arc.target).node != scratchArc.target()
- || !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput())
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
+ public long add(FSTCompiler<T> fstCompiler, FSTCompiler.UnCompiledNode<T> nodeIn)
+ throws IOException {
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
+ long hash = hash(nodeIn);
+
+ long pos = hash & primaryTable.mask;
+ int c = 0;
+
+ while (true) {
+
+ long node = primaryTable.get(pos);
+ if (node == 0) {
+ // node is not in primary table; is it in fallback table?
+ node = getFallback(nodeIn, hash);
+ if (node != 0) {
+ // it was already in fallback -- promote to primary
+ primaryTable.set(pos, node);
} else {
- return false;
+ // not in fallback either -- freeze & add the incoming node
+
+ // freeze & add
+ node = fstCompiler.addNode(nodeIn);
+
+ // we use 0 as empty marker in hash table, so it better be impossible to get a frozen node
+ // at 0:
+ assert node != 0;
+
+ // confirm frozen hash and unfrozen hash are the same
+ assert hash(node) == hash : "mismatch frozenHash=" + hash(node) + " vs hash=" + hash;
+
+ primaryTable.set(pos, node);
}
+
+ // how many bytes would be used if we had "perfect" hashing:
+ long ramBytesUsed = primaryTable.count * PackedInts.bitsRequired(node) / 8;
+
+ // NOTE: we could instead use the more precise RAM used, but this leads to unpredictable
+ // quantized behavior due to 2X rehashing where for large ranges of the RAM limit, the
+ // size of the FST does not change, and then suddenly when you cross a secret threshold,
+ // it drops. With this approach (measuring "perfect" hash storage and approximating the
+ // overhead), the behaviour is more strictly monotonic: larger RAM limits smoothly result
+ // in smaller FSTs, even if the precise RAM used is not always under the limit.
+
+ // divide limit by 2 because fallback gets half the RAM and primary gets the other half
+ // divide by 2 again to account for approximate hash table overhead halfway between 33.3%
+ // and 66.7% occupancy = 50%
+ if (ramBytesUsed >= ramLimitBytes / (2 * 2)) {
+ // time to fallback -- fallback is now used read-only to promote a node (suffix) to
+ // primary if we encounter it again
+ fallbackTable = primaryTable;
Review Comment:
If `fallbackTable` is not null, would it be better if we implement `PagedGrowableHash#clear` and swap `primaryTable` and `fallbackTable` to reduce garbage collection?
Not really sure, just a question :)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1766082689
Thanks for the suggestions @dungba88! I took the approach you suggested, with a few more pushed commits just now. Despite the increase in `nocommit`s I think this is actually close! I like this new approach:
* It uses the same mutable packed blocked growable (in size and bpv) writer thingy (`PagedGrowableWriter`) that `NodeHash` uses on `main`
* But now the FSTCompiler (and its Builder) take an option to set a limit on the size (count of number of suffix entries) of the `NodeHash`. I plan to change this to a `ramMB` limit instead....
* If you set a massive limit (`Long.MAX_VALUE`) then every suffix is stored (as compactly as on `main` today) and you get a minimal FST.
* If you set a lower limit and the `NodeHash` hits it, it will begin pruning the LRU suffixes, and you get a somewhat compressed FST. The larger the limit, the more RAM used, and the closer to minimal your FST is.
I tested again on all terms from `wikimediumall` index:
|NodeHash size|FST (mb)|RAM (mb)|Build time (sec)|
|-------------|--------|--------|----------------|
|4|585.8|0.0|110.0|
|8|587.0|0.0|74.7|
|16|586.3|0.0|60.1|
|32|583.7|0.0|52.5|
|64|580.4|0.0|46.5|
|128|575.9|0.0|44.0|
|256|568.0|0.0|42.6|
|512|556.6|0.0|41.8|
|1024|543.2|0.0|42.4|
|2048|529.3|0.0|40.9|
|4096|515.2|0.0|41.0|
|8192|501.5|0.1|40.8|
|16384|488.2|0.1|40.3|
|32768|474.0|0.2|41.5|
|65536|453.0|0.5|42.0|
|131072|439.0|0.9|41.6|
|262144|424.2|1.8|41.5|
|524288|408.9|3.6|41.7|
|1048576|396.0|7.3|42.3|
|2097152|384.4|14.5|44.1|
|4194304|375.0|29.0|48.0|
|8388608|365.9|58.0|51.5|
|16777216|358.6|116.0|52.4|
|33554432|352.7|232.0|52.7|
|67108864|350.2|448.0|52.9|
|134217728|350.2|464.0|56.5|
|268435456|350.2|464.0|56.6|
|536870912|350.2|464.0|56.1|
|1073741824|350.2|464.0|55.7|
Rendered as a graph vs `main`:
It's less RAM than the previous `long[]` approach thanks to the packing done by `PagedGrowableWriter`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1768776163
OK I think this is ready -- I removed/downgraded all `nocommit`s, added CHANGES entry, rebased to latest `main`. Tests and precommit passed for me (at least once).
I set the default RAM limit to 32 MB, which should be plenty to get close (within 10%? at least for "real" terms) to the true minimal FST.
I think we could backport this to 9.x. There is an API break in `FSTCompiler`, but this class is marked `@lucene.experimental` so we are free to change the API. Also, this API is so uber-expert that likely very few users rely on it, and those that do would likely welcome the "limit by RAM instead of limit by un-understandable parameters". But we should let this bake for a while in `main` before thinking about backporting...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Bound the RAM used by the NodeHash (sharing common suffixes) during FST compilation [lucene]
Posted by "mikemccand (via GitHub)" <gi...@apache.org>.
mikemccand merged PR #12633:
URL: https://github.com/apache/lucene/pull/12633
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] [WIP] first cut at bounding the NodeHash size during FST compilation [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on PR #12633:
URL: https://github.com/apache/lucene/pull/12633#issuecomment-1754735435
> With the PR, you unfortunately cannot easily say "give me a minimal FST at all costs", like you can with main today. You'd have to keep trying larger and larger NodeHash sizes until the final FST size gets no smaller.
If we replace `long[]` with a growable array that inits from small and grows smoothly to `nodeHashSize`, can we just pass a big nodeHashSize (e.g. 1L << 63) or a constant `NO_LIMIT` to get a minimal FST ?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org