You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2019/11/14 08:41:11 UTC
[lucene-solr] 06/07: LUCENE-8920: Reduce the memory used by direct
addressing of arcs (#980)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
commit 5dd9c4c04bcab9911b9a9f0b092eadc50262ee2c
Author: Bruno Roustant <33...@users.noreply.github.com>
AuthorDate: Wed Nov 13 22:48:13 2019 +0100
LUCENE-8920: Reduce the memory used by direct addressing of arcs (#980)
---
.../analysis/ja/dict/TokenInfoDictionary$fst.dat | Bin 1698570 -> 1707541 bytes
.../analysis/ko/dict/TokenInfoDictionary$fst.dat | Bin 5640903 -> 6009053 bytes
.../codecs/blocktreeords/OrdsSegmentTermsEnum.java | 2 +-
.../src/java/org/apache/lucene/util/BitUtil.java | 125 ++++
.../java/org/apache/lucene/util/fst/Builder.java | 114 +++-
.../org/apache/lucene/util/fst/BytesStore.java | 21 +
.../src/java/org/apache/lucene/util/fst/FST.java | 715 +++++++++++++++------
.../java/org/apache/lucene/util/fst/FSTEnum.java | 236 ++++---
.../java/org/apache/lucene/util/fst/NodeHash.java | 17 +-
.../src/java/org/apache/lucene/util/fst/Util.java | 29 +-
.../test/org/apache/lucene/util/TestBitUtil.java | 85 +++
.../test/org/apache/lucene/util/fst/TestFSTs.java | 33 +-
.../org/apache/lucene/util/fst/TestFstDirect.java | 106 ---
.../lucene/util/fst/TestFstDirectAddressing.java | 212 ++++++
.../test/org/apache/lucene/util/fst/TestUtil.java | 21 +-
15 files changed, 1266 insertions(+), 450 deletions(-)
diff --git a/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat b/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat
index c06fd4a..9ffdbc9 100644
Binary files a/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat and b/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat differ
diff --git a/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat b/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat
index fa0cb32..bf84bd8 100644
Binary files a/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat and b/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat differ
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java b/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
index d6a182b..d740b3b 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
@@ -1084,7 +1084,7 @@ public final class OrdsSegmentTermsEnum extends BaseTermsEnum {
result.grow(1+upto);
fr.index.readFirstRealTargetArc(arc.target(), arc, fstReader);
- if (arc.bytesPerArc() != 0 && arc.arcIdx() > Integer.MIN_VALUE) {
+ if (arc.bytesPerArc() != 0 && arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
// System.out.println(" array arcs");
int low = 0;
int high = arc.numArcs() -1;
diff --git a/lucene/core/src/java/org/apache/lucene/util/BitUtil.java b/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
index bcc66a1..f9557bc 100644
--- a/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
@@ -178,4 +178,129 @@ public final class BitUtil {
return ((l >>> 1) ^ -(l & 1));
}
+ /**
+ * Returns whether the bit at given zero-based index is set.
+ * <br>Example: bitIndex 66 means the third bit on the right of the second long.
+ *
+ * @param bits The bits stored in an array of long for efficiency.
+ * @param numLongs The number of longs in {@code bits} to consider.
+ * @param bitIndex The bit zero-based index. It must be greater than or equal to 0,
+ * and strictly less than {@code numLongs * Long.SIZE}.
+ */
+ public static boolean isBitSet(long[] bits, int numLongs, int bitIndex) {
+ assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= 0 && bitIndex < numLongs * Long.SIZE
+ : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+ return (bits[bitIndex / Long.SIZE] & (1L << bitIndex)) != 0; // Shifts are mod 64.
+ }
+
+ /**
+ * Counts all bits set in the provided longs.
+ *
+ * @param bits The bits stored in an array of long for efficiency.
+ * @param numLongs The number of longs in {@code bits} to consider.
+ */
+ public static int countBits(long[] bits, int numLongs) {
+ assert numLongs >= 0 && numLongs <= bits.length
+ : "numLongs=" + numLongs + " bits.length=" + bits.length;
+ int bitCount = 0;
+ for (int i = 0; i < numLongs; i++) {
+ bitCount += Long.bitCount(bits[i]);
+ }
+ return bitCount;
+ }
+
+ /**
+ * Counts the bits set up to the given bit zero-based index, exclusive.
+ * <br>In other words, how many 1s there are up to the bit at the given index excluded.
+ * <br>Example: bitIndex 66 means the third bit on the right of the second long.
+ *
+ * @param bits The bits stored in an array of long for efficiency.
+ * @param numLongs The number of longs in {@code bits} to consider.
+ * @param bitIndex The bit zero-based index, exclusive. It must be greater than or equal to 0,
+ * and less than or equal to {@code numLongs * Long.SIZE}.
+ */
+ public static int countBitsUpTo(long[] bits, int numLongs, int bitIndex) {
+ assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= 0 && bitIndex <= numLongs * Long.SIZE
+ : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+ int bitCount = 0;
+ int lastLong = bitIndex / Long.SIZE;
+ for (int i = 0; i < lastLong; i++) {
+ // Count the bits set for all plain longs.
+ bitCount += Long.bitCount(bits[i]);
+ }
+ if (lastLong < numLongs) {
+ // Prepare a mask with 1s on the right up to bitIndex exclusive.
+ long mask = (1L << bitIndex) - 1L; // Shifts are mod 64.
+ // Count the bits set only within the mask part, so up to bitIndex exclusive.
+ bitCount += Long.bitCount(bits[lastLong] & mask);
+ }
+ return bitCount;
+ }
+
+ /**
+ * Returns the index of the next bit set following the given bit zero-based index.
+ * <br>For example with bits 100011:
+ * the next bit set after index=-1 is at index=0;
+ * the next bit set after index=0 is at index=1;
+ * the next bit set after index=1 is at index=5;
+ * there is no next bit set after index=5.
+ *
+ * @param bits The bits stored in an array of long for efficiency.
+ * @param numLongs The number of longs in {@code bits} to consider.
+ * @param bitIndex The bit zero-based index. It must be greater than or equal to -1,
+ * and strictly less than {@code numLongs * Long.SIZE}.
+ * @return The zero-based index of the next bit set after the provided {@code bitIndex};
+ * or -1 if none.
+ */
+ public static int nextBitSet(long[] bits, int numLongs, int bitIndex) {
+ assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= -1 && bitIndex < numLongs * Long.SIZE
+ : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+ int longIndex = bitIndex / Long.SIZE;
+ // Prepare a mask with 1s on the left down to bitIndex exclusive.
+ long mask = -(1L << (bitIndex + 1)); // Shifts are mod 64.
+ long l = mask == -1 && bitIndex != -1 ? 0 : bits[longIndex] & mask;
+ while (l == 0) {
+ if (++longIndex == numLongs) {
+ return -1;
+ }
+ l = bits[longIndex];
+ }
+ return Long.numberOfTrailingZeros(l) + longIndex * 64;
+ }
+
+ /**
+ * Returns the index of the previous bit set preceding the given bit zero-based index.
+ * <br>For example with bits 100011:
+ * there is no previous bit set before index=0.
+ * the previous bit set before index=1 is at index=0;
+ * the previous bit set before index=5 is at index=1;
+ * the previous bit set before index=64 is at index=5;
+ *
+ * @param bits The bits stored in an array of long for efficiency.
+ * @param numLongs The number of longs in {@code bits} to consider.
+ * @param bitIndex The bit zero-based index. It must be greater than or equal to 0,
+ * and less than or equal to {@code numLongs * Long.SIZE}.
+ * @return The zero-based index of the previous bit set before the provided {@code bitIndex};
+ * or -1 if none.
+ */
+ public static int previousBitSet(long[] bits, int numLongs, int bitIndex) {
+ assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= 0 && bitIndex <= numLongs * Long.SIZE
+ : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+ int longIndex = bitIndex / Long.SIZE;
+ long l;
+ if (longIndex == numLongs) {
+ l = 0;
+ } else {
+ // Prepare a mask with 1s on the right up to bitIndex exclusive.
+ long mask = (1L << bitIndex) - 1L; // Shifts are mod 64.
+ l = bits[longIndex] & mask;
+ }
+ while (l == 0) {
+ if (longIndex-- == 0) {
+ return -1;
+ }
+ l = bits[longIndex];
+ }
+ return 63 - Long.numberOfLeadingZeros(l) + longIndex * 64;
+ }
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java b/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java
index c54b144..a35c4d7 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java
@@ -19,6 +19,7 @@ package org.apache.lucene.util.fst;
import java.io.IOException;
+import org.apache.lucene.store.ByteArrayDataOutput;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.IntsRef;
import org.apache.lucene.util.IntsRefBuilder;
@@ -50,6 +51,30 @@ import org.apache.lucene.util.fst.FST.INPUT_TYPE; // javadoc
public class Builder<T> {
+ /**
+ * Default oversizing factor used to decide whether to encode a node with direct addressing or binary search.
+ * Default is 1: ensure no oversizing on average.
+ * <p>
+ * This factor does not determine whether to encode a node with a list of variable length arcs or with
+ * fixed length arcs. It only determines the effective encoding of a node that is already known to be
+ * encoded with fixed length arcs.
+ * See {@code FST.shouldExpandNodeWithFixedLengthArcs()}
+ * and {@code FST.shouldExpandNodeWithDirectAddressing()}.
+ * <p>
+ * For English words we measured 217K nodes, only 3.27% nodes are encoded with fixed length arcs,
+ * and 99.99% of them with direct addressing. Overall FST memory reduced by 1.67%.
+ * <p>
+ * For worst case we measured 168K nodes, 50% of them are encoded with fixed length arcs,
+ * and 14% of them with direct encoding. Overall FST memory reduced by 0.8%.
+ * <p>
+ * Use {@code TestFstDirectAddressing.main()}
+ * and {@code TestFstDirectAddressing.testWorstCaseForDirectAddressing()}
+ * to evaluate a change.
+ *
+ * @see #setDirectAddressingMaxOversizingFactor
+ */
+ static final float DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR = 1.0f;
+
private final NodeHash<T> dedupHash;
final FST<T> fst;
private final T NO_OUTPUT;
@@ -83,12 +108,18 @@ public class Builder<T> {
long lastFrozenNode;
// Reused temporarily while building the FST:
- int[] reusedBytesPerArc = new int[4];
+ int[] numBytesPerArc = new int[4];
+ int[] numLabelBytesPerArc = new int[numBytesPerArc.length];
+ final FixedLengthArcsBuffer fixedLengthArcsBuffer = new FixedLengthArcsBuffer();
long arcCount;
long nodeCount;
+ long binarySearchNodeCount;
+ long directAddressingNodeCount;
- boolean allowArrayArcs;
+ boolean allowFixedLengthArcs;
+ float directAddressingMaxOversizingFactor = DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR;
+ long directAddressingExpansionCredit;
BytesStore bytes;
@@ -138,9 +169,9 @@ public class Builder<T> {
* FSA, use {@link NoOutputs#getSingleton()} and {@link NoOutputs#getNoOutput()} as the
* singleton output object.
*
- * @param allowArrayArcs Pass false to disable the array arc optimization
- * while building the FST; this will make the resulting
- * FST smaller but slower to traverse.
+ * @param allowFixedLengthArcs Pass false to disable the fixed length arc optimization (binary search or
+ * direct addressing) while building the FST; this will make the resulting FST smaller but slower to
+ * traverse.
*
* @param bytesPageBits How many bits wide to make each
* byte[] block in the BytesStore; if you know the FST
@@ -149,12 +180,12 @@ public class Builder<T> {
*/
public Builder(FST.INPUT_TYPE inputType, int minSuffixCount1, int minSuffixCount2, boolean doShareSuffix,
boolean doShareNonSingletonNodes, int shareMaxTailLength, Outputs<T> outputs,
- boolean allowArrayArcs, int bytesPageBits) {
+ boolean allowFixedLengthArcs, int bytesPageBits) {
this.minSuffixCount1 = minSuffixCount1;
this.minSuffixCount2 = minSuffixCount2;
this.doShareNonSingletonNodes = doShareNonSingletonNodes;
this.shareMaxTailLength = shareMaxTailLength;
- this.allowArrayArcs = allowArrayArcs;
+ this.allowFixedLengthArcs = allowFixedLengthArcs;
fst = new FST<>(inputType, outputs, bytesPageBits);
bytes = fst.bytes;
assert bytes != null;
@@ -173,6 +204,27 @@ public class Builder<T> {
}
}
+ /**
+ * Overrides the default the maximum oversizing of fixed array allowed to enable direct addressing
+ * of arcs instead of binary search.
+ * <p>
+ * Setting this factor to a negative value (e.g. -1) effectively disables direct addressing,
+ * only binary search nodes will be created.
+ *
+ * @see #DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR
+ */
+ public Builder<T> setDirectAddressingMaxOversizingFactor(float factor) {
+ directAddressingMaxOversizingFactor = factor;
+ return this;
+ }
+
+ /**
+ * @see #setDirectAddressingMaxOversizingFactor(float)
+ */
+ public float getDirectAddressingMaxOversizingFactor() {
+ return directAddressingMaxOversizingFactor;
+ }
+
public long getTermCount() {
return frontier[0].inputCount;
}
@@ -639,4 +691,52 @@ public class Builder<T> {
}
}
}
+
+ /**
+ * Reusable buffer for building nodes with fixed length arcs (binary search or direct addressing).
+ */
+ static class FixedLengthArcsBuffer {
+
+ // Initial capacity is the max length required for the header of a node with fixed length arcs:
+ // header(byte) + numArcs(vint) + numBytes(vint)
+ private byte[] bytes = new byte[11];
+ private final ByteArrayDataOutput bado = new ByteArrayDataOutput(bytes);
+
+ /** Ensures the capacity of the internal byte array. Enlarges it if needed. */
+ FixedLengthArcsBuffer ensureCapacity(int capacity) {
+ if (bytes.length < capacity) {
+ bytes = new byte[ArrayUtil.oversize(capacity, Byte.BYTES)];
+ bado.reset(bytes);
+ }
+ return this;
+ }
+
+ FixedLengthArcsBuffer resetPosition() {
+ bado.reset(bytes);
+ return this;
+ }
+
+ FixedLengthArcsBuffer writeByte(byte b) {
+ bado.writeByte(b);
+ return this;
+ }
+
+ FixedLengthArcsBuffer writeVInt(int i) {
+ try {
+ bado.writeVInt(i);
+ } catch (IOException e) { // Never thrown.
+ throw new RuntimeException(e);
+ }
+ return this;
+ }
+
+ int getPosition() {
+ return bado.getPosition();
+ }
+
+ /** Gets the internal byte array. */
+ byte[] getBytes() {
+ return bytes;
+ }
+ }
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java b/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java
index 37b2baa..02ff583 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java
@@ -239,6 +239,27 @@ class BytesStore extends DataOutput implements Accountable {
}
}
+ /** Copies bytes from this store to a target byte array. */
+ public void copyBytes(long src, byte[] dest, int offset, int len) {
+ int blockIndex = (int) (src >> blockBits);
+ int upto = (int) (src & blockMask);
+ byte[] block = blocks.get(blockIndex);
+ while (len > 0) {
+ int chunk = blockSize - upto;
+ if (len <= chunk) {
+ System.arraycopy(block, upto, dest, offset, len);
+ break;
+ } else {
+ System.arraycopy(block, upto, dest, offset, chunk);
+ blockIndex++;
+ block = blocks.get(blockIndex);
+ upto = 0;
+ len -= chunk;
+ offset += chunk;
+ }
+ }
+ }
+
/** Writes an int at the absolute position without
* changing the current pointer. */
public void writeInt(long pos, int value) {
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/FST.java b/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
index 3389343..89e4e62 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
@@ -26,7 +26,6 @@ import java.nio.file.Files;
import java.nio.file.Path;
import org.apache.lucene.codecs.CodecUtil;
-import org.apache.lucene.store.ByteArrayDataOutput;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
import org.apache.lucene.store.InputStreamDataInput;
@@ -34,6 +33,7 @@ import org.apache.lucene.store.OutputStreamDataOutput;
import org.apache.lucene.store.RAMOutputStream;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BitUtil;
import org.apache.lucene.util.Constants;
import org.apache.lucene.util.RamUsageEstimator;
@@ -81,33 +81,43 @@ public final class FST<T> implements Accountable {
private static final int BIT_ARC_HAS_FINAL_OUTPUT = 1 << 5;
- // We use this as a marker (because this one flag is
- // illegal by itself ...):
- private static final byte ARCS_AS_ARRAY_PACKED = BIT_ARC_HAS_FINAL_OUTPUT;
+ /** Value of the arc flags to declare a node with fixed length arcs
+ * designed for binary search. */
+ // We use this as a marker because this one flag is illegal by itself.
+ public static final byte ARCS_FOR_BINARY_SEARCH = BIT_ARC_HAS_FINAL_OUTPUT;
- // this means either of these things in different contexts
- // in the midst of a direct array:
- private static final byte BIT_MISSING_ARC = 1 << 6;
+ /** Value of the arc flags to declare a node with fixed length arcs
+ * and bit table designed for direct addressing. */
+ static final byte ARCS_FOR_DIRECT_ADDRESSING = 1 << 6;
/**
- * @see #shouldExpand(Builder, Builder.UnCompiledNode)
+ * @see #shouldExpandNodeWithFixedLengthArcs
*/
- static final int FIXED_ARRAY_SHALLOW_DISTANCE = 3; // 0 => only root node.
+ static final int FIXED_LENGTH_ARC_SHALLOW_DEPTH = 3; // 0 => only root node.
/**
- * @see #shouldExpand(Builder, Builder.UnCompiledNode)
+ * @see #shouldExpandNodeWithFixedLengthArcs
*/
- static final int FIXED_ARRAY_NUM_ARCS_SHALLOW = 5;
+ static final int FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS = 5;
/**
- * @see #shouldExpand(Builder, Builder.UnCompiledNode)
+ * @see #shouldExpandNodeWithFixedLengthArcs
*/
- static final int FIXED_ARRAY_NUM_ARCS_DEEP = 10;
+ static final int FIXED_LENGTH_ARC_DEEP_NUM_ARCS = 10;
+
+ /**
+ * Maximum oversizing factor allowed for direct addressing compared to binary search when expansion
+ * credits allow the oversizing. This factor prevents expansions that are obviously too costly even
+ * if there are sufficient credits.
+ *
+ * @see #shouldExpandNodeWithDirectAddressing
+ */
+ private static final float DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR = 1.66f;
// Increment version to change it
private static final String FILE_FORMAT_NAME = "FST";
private static final int VERSION_START = 6;
- private static final int VERSION_CURRENT = VERSION_START;
+ private static final int VERSION_CURRENT = 7;
// Never serialized; just used to represent the virtual
// final node w/ no arcs:
@@ -145,6 +155,8 @@ public final class FST<T> implements Accountable {
/** Represents a single arc. */
public static final class Arc<T> {
+ //*** Arc fields.
+
private int label;
private T output;
@@ -155,17 +167,25 @@ public final class FST<T> implements Accountable {
private T nextFinalOutput;
- // address (into the byte[]), or ord/address if label == END_LABEL
private long nextArc;
+ private int arcIdx;
+
+ //*** Fields for arcs belonging to a node with fixed length arcs.
+ // So only valid when bytesPerArc != 0.
+
+ private byte nodeFlags;
+
private long posArcsStart;
private int bytesPerArc;
- private int arcIdx;
-
private int numArcs;
+ private BitTable bitTable;
+
+ private int firstLabel;
+
/** Returns this */
public Arc<T> copyFrom(Arc<T> other) {
label = other.label();
@@ -174,11 +194,16 @@ public final class FST<T> implements Accountable {
output = other.output();
nextFinalOutput = other.nextFinalOutput();
nextArc = other.nextArc();
+ nodeFlags = other.nodeFlags();
bytesPerArc = other.bytesPerArc();
if (bytesPerArc() != 0) {
posArcsStart = other.posArcsStart();
arcIdx = other.arcIdx();
numArcs = other.numArcs();
+ if (nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING) {
+ bitTable = other.bitTable() == null ? null : other.bitTable().copy();
+ firstLabel = other.firstLabel();
+ }
}
return this;
}
@@ -195,10 +220,6 @@ public final class FST<T> implements Accountable {
return flag(BIT_FINAL_ARC);
}
- public boolean isPackedArray() {
- return bytesPerArc != 0 && arcIdx > Integer.MIN_VALUE;
- }
-
@Override
public String toString() {
StringBuilder b = new StringBuilder();
@@ -236,7 +257,7 @@ public final class FST<T> implements Accountable {
return output;
}
- /** To node (ord or address) */
+ /** Ord/address to target node. */
public long target() {
return target;
}
@@ -249,38 +270,126 @@ public final class FST<T> implements Accountable {
return nextFinalOutput;
}
- long nextArc() {
+ /** Address (into the byte[]) of the next arc - only for list of variable length arc.
+ * Or ord/address to the next node if label == {@link #END_LABEL}. */
+ long nextArc() {
return nextArc;
}
- /** Where the first arc in the array starts; only valid if
- * bytesPerArc != 0 */
+ /** Where we are in the array; only valid if bytesPerArc != 0. */
+ public int arcIdx() {
+ return arcIdx;
+ }
+
+ /** Node header flags. Only meaningful to check if the value is either
+ * {@link #ARCS_FOR_BINARY_SEARCH} or {@link #ARCS_FOR_DIRECT_ADDRESSING}
+ * (other value when bytesPerArc == 0). */
+ public byte nodeFlags() {
+ return nodeFlags;
+ }
+
+ /** Where the first arc in the array starts; only valid if bytesPerArc != 0 */
public long posArcsStart() {
return posArcsStart;
}
- /** Non-zero if this arc is part of an array, which means all
+ /** Non-zero if this arc is part of a node with fixed length arcs, which means all
* arcs for the node are encoded with a fixed number of bytes so
- * that we can random access by index. We do when there are enough
- * arcs leaving one node. It wastes some bytes but gives faster
- * lookups. */
+ * that we binary search or direct address. We do when there are enough
+ * arcs leaving one node. It wastes some bytes but gives faster lookups. */
public int bytesPerArc() {
return bytesPerArc;
}
- /** Where we are in the array; only valid if bytesPerArc != 0, and the array has no holes.
- * arcIdx = Integer.MIN_VALUE indicates that the arc is part of a direct array, addressed by
- * label.
- */
- public int arcIdx() {
- return arcIdx;
- }
-
- /** How many arc, if bytesPerArc == 0. Otherwise, the size of the arc array. If the array is
- * direct, this may include holes. Otherwise it is also how many arcs are in the array */
+ /** How many arcs; only valid if bytesPerArc != 0 (fixed length arcs).
+ * For a node designed for binary search this is the array size.
+ * For a node designed for direct addressing, this is the label range. */
public int numArcs() {
return numArcs;
}
+
+ /** Table of bits of a direct addressing node.
+ * Only valid if nodeFlags == {@link #ARCS_FOR_DIRECT_ADDRESSING};
+ * may be null otherwise. */
+ BitTable bitTable() {
+ return bitTable;
+ }
+
+ /** The table of bits of a direct addressing node created lazily. */
+ BitTable getOrCreateBitTable() {
+ if (bitTable == null) {
+ bitTable = new BitTable();
+ }
+ return bitTable;
+ }
+
+ /** First label of a direct addressing node.
+ * Only valid if nodeFlags == {@link #ARCS_FOR_DIRECT_ADDRESSING}. */
+ int firstLabel() {
+ return firstLabel;
+ }
+
+ /**
+ * Reusable table of bits using an array of long internally.
+ */
+ static class BitTable {
+
+ private long[] bits;
+ private int numLongs;
+
+ /** Sets the number of longs in the internal long array.
+ * Enlarges it if needed. Always clears the array. */
+ BitTable setNumLongs(int numLongs) {
+ assert numLongs >= 0;
+ this.numLongs = numLongs;
+ if (bits == null || bits.length < numLongs) {
+ bits = new long[ArrayUtil.oversize(numLongs, Long.BYTES)];
+ } else {
+ for (int i = 0; i < numLongs; i++) {
+ bits[i] = 0L;
+ }
+ }
+ return this;
+ }
+
+ /** Creates a new {@link BitTable} by copying this one. */
+ BitTable copy() {
+ BitTable bitTable = new BitTable();
+ bitTable.bits = ArrayUtil.copyOfSubArray(bits, 0, bits.length);
+ bitTable.numLongs = numLongs;
+ return bitTable;
+ }
+
+ boolean assertIsValid() {
+ assert numLongs > 0 && numLongs <= bits.length;
+ return true;
+ }
+
+ /** Forwards to {@link BitUtil#isBitSet(long[], int, int)}. */
+ boolean isBitSet(int bitIndex) {
+ return BitUtil.isBitSet(bits, numLongs, bitIndex);
+ }
+
+ /** Forwards to {@link BitUtil#countBits(long[], int)}. */
+ int countBits() {
+ return BitUtil.countBits(bits, numLongs);
+ }
+
+ /** Forwards to {@link BitUtil#countBitsUpTo(long[], int, int)}. */
+ int countBitsUpTo(int bitIndex) {
+ return BitUtil.countBitsUpTo(bits, numLongs, bitIndex);
+ }
+
+ /** Forwards to {@link BitUtil#nextBitSet(long[], int, int)}. */
+ int nextBitSet(int bitIndex) {
+ return BitUtil.nextBitSet(bits, numLongs, bitIndex);
+ }
+
+ /** Forwards to {@link BitUtil#previousBitSet(long[], int, int)}. */
+ int previousBitSet(int bitIndex) {
+ return BitUtil.previousBitSet(bits, numLongs, bitIndex);
+ }
+ }
}
private static boolean flag(int flags, int bit) {
@@ -436,7 +545,7 @@ public final class FST<T> implements Accountable {
int cacheRAM = (int) ramBytesUsed(arcs);
// Don't cache if there are only a few arcs or if the cache would use > 20% RAM of the FST itself:
- if (count >= FIXED_ARRAY_NUM_ARCS_SHALLOW && cacheRAM < ramBytesUsed()/5) {
+ if (count >= FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS && cacheRAM < ramBytesUsed()/5) {
cachedRootArcs = arcs;
cachedArcsBytesUsed = cacheRAM;
}
@@ -576,11 +685,12 @@ public final class FST<T> implements Accountable {
final long startAddress = builder.bytes.getPosition();
//System.out.println(" startAddr=" + startAddress);
- final boolean doFixedArray = shouldExpand(builder, nodeIn);
- if (doFixedArray) {
- //System.out.println(" fixedArray");
- if (builder.reusedBytesPerArc.length < nodeIn.numArcs) {
- builder.reusedBytesPerArc = new int[ArrayUtil.oversize(nodeIn.numArcs, 1)];
+ final boolean doFixedLengthArcs = shouldExpandNodeWithFixedLengthArcs(builder, nodeIn);
+ if (doFixedLengthArcs) {
+ //System.out.println(" fixed length arcs");
+ if (builder.numBytesPerArc.length < nodeIn.numArcs) {
+ builder.numBytesPerArc = new int[ArrayUtil.oversize(nodeIn.numArcs, Integer.BYTES)];
+ builder.numLabelBytesPerArc = new int[builder.numBytesPerArc.length];
}
}
@@ -590,6 +700,7 @@ public final class FST<T> implements Accountable {
long lastArcStart = builder.bytes.getPosition();
int maxBytesPerArc = 0;
+ int maxBytesPerArcWithoutLabel = 0;
for(int arcIdx=0; arcIdx < nodeIn.numArcs; arcIdx++) {
final Builder.Arc<T> arc = nodeIn.arcs[arcIdx];
final Builder.CompiledNode target = (Builder.CompiledNode) arc.target;
@@ -600,7 +711,7 @@ public final class FST<T> implements Accountable {
flags += BIT_LAST_ARC;
}
- if (builder.lastFrozenNode == target.node && !doFixedArray) {
+ if (builder.lastFrozenNode == target.node && !doFixedLengthArcs) {
// TODO: for better perf (but more RAM used) we
// could avoid this except when arc is "near" the
// last arc:
@@ -627,7 +738,9 @@ public final class FST<T> implements Accountable {
}
builder.bytes.writeByte((byte) flags);
+ long labelStart = builder.bytes.getPosition();
writeLabel(builder.bytes, arc.label);
+ int numLabelBytes = (int) (builder.bytes.getPosition() - labelStart);
// System.out.println(" write arc: label=" + (char) arc.label + " flags=" + flags + " target=" + target.node + " pos=" + bytes.getPosition() + " output=" + outputs.outputToString(arc.output));
@@ -649,15 +762,18 @@ public final class FST<T> implements Accountable {
// just write the arcs "like normal" on first pass, but record how many bytes each one took
// and max byte size:
- if (doFixedArray) {
- builder.reusedBytesPerArc[arcIdx] = (int) (builder.bytes.getPosition() - lastArcStart);
+ if (doFixedLengthArcs) {
+ int numArcBytes = (int) (builder.bytes.getPosition() - lastArcStart);
+ builder.numBytesPerArc[arcIdx] = numArcBytes;
+ builder.numLabelBytesPerArc[arcIdx] = numLabelBytes;
lastArcStart = builder.bytes.getPosition();
- maxBytesPerArc = Math.max(maxBytesPerArc, builder.reusedBytesPerArc[arcIdx]);
- //System.out.println(" bytes=" + builder.reusedBytesPerArc[arcIdx]);
+ maxBytesPerArc = Math.max(maxBytesPerArc, numArcBytes);
+ maxBytesPerArcWithoutLabel = Math.max(maxBytesPerArcWithoutLabel, numArcBytes - numLabelBytes);
+ //System.out.println(" arcBytes=" + numArcBytes + " labelBytes=" + numLabelBytes);
}
}
- // TODO: try to avoid wasteful cases: disable doFixedArray in that case
+ // TODO: try to avoid wasteful cases: disable doFixedLengthArcs in that case
/*
*
* LUCENE-4682: what is a fair heuristic here?
@@ -667,65 +783,245 @@ public final class FST<T> implements Accountable {
* 3. waste: numBytes vs numBytesExpanded
*
* the one below just looks at #3
- if (doFixedArray) {
+ if (doFixedLengthArcs) {
// rough heuristic: make this 1.25 "waste factor" a parameter to the phd ctor????
int numBytes = lastArcStart - startAddress;
int numBytesExpanded = maxBytesPerArc * nodeIn.numArcs;
if (numBytesExpanded > numBytes*1.25) {
- doFixedArray = false;
+ doFixedLengthArcs = false;
}
}
*/
- if (doFixedArray) {
- final int MAX_HEADER_SIZE = 11; // header(byte) + numArcs(vint) + numBytes(vint)
+ if (doFixedLengthArcs) {
assert maxBytesPerArc > 0;
// 2nd pass just "expands" all arcs to take up a fixed byte size
- // create the header
- // TODO: clean this up: or just rewind+reuse and deal with it
- byte[] header = new byte[MAX_HEADER_SIZE];
- ByteArrayDataOutput bad = new ByteArrayDataOutput(header);
- // write a "false" first arc:
- bad.writeByte(ARCS_AS_ARRAY_PACKED);
- bad.writeVInt(nodeIn.numArcs);
- bad.writeVInt(maxBytesPerArc);
- int headerLen = bad.getPosition();
-
- final long fixedArrayStart = startAddress + headerLen;
-
- writeArrayPacked(builder, nodeIn, fixedArrayStart, maxBytesPerArc);
-
- // now write the header
- builder.bytes.writeBytes(startAddress, header, 0, headerLen);
+ int labelRange = nodeIn.arcs[nodeIn.numArcs - 1].label - nodeIn.arcs[0].label + 1;
+ assert labelRange > 0;
+ if (shouldExpandNodeWithDirectAddressing(builder, nodeIn, maxBytesPerArc, maxBytesPerArcWithoutLabel, labelRange)) {
+ writeNodeForDirectAddressing(builder, nodeIn, startAddress, maxBytesPerArcWithoutLabel, labelRange);
+ builder.directAddressingNodeCount++;
+ } else {
+ writeNodeForBinarySearch(builder, nodeIn, startAddress, maxBytesPerArc);
+ builder.binarySearchNodeCount++;
+ }
}
final long thisNodeAddress = builder.bytes.getPosition()-1;
-
builder.bytes.reverse(startAddress, thisNodeAddress);
-
builder.nodeCount++;
return thisNodeAddress;
}
- private void writeArrayPacked(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long fixedArrayStart, int maxBytesPerArc) {
- // expand the arcs in place, backwards
+ /**
+ * Returns whether the given node should be expanded with fixed length arcs.
+ * Nodes will be expanded depending on their depth (distance from the root node) and their number
+ * of arcs.
+ * <p>
+ * Nodes with fixed length arcs use more space, because they encode all arcs with a fixed number
+ * of bytes, but they allow either binary search or direct addressing on the arcs (instead of linear
+ * scan) on lookup by arc label.
+ */
+ private boolean shouldExpandNodeWithFixedLengthArcs(Builder<T> builder, Builder.UnCompiledNode<T> node) {
+ return builder.allowFixedLengthArcs &&
+ ((node.depth <= FIXED_LENGTH_ARC_SHALLOW_DEPTH && node.numArcs >= FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS) ||
+ node.numArcs >= FIXED_LENGTH_ARC_DEEP_NUM_ARCS);
+ }
+
+ /**
+ * Returns whether the given node should be expanded with direct addressing instead of binary search.
+ * <p>
+ * Prefer direct addressing for performance if it does not oversize binary search byte size too much,
+ * so that the arcs can be directly addressed by label.
+ *
+ * @see Builder#getDirectAddressingMaxOversizingFactor()
+ */
+ private boolean shouldExpandNodeWithDirectAddressing(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn,
+ int numBytesPerArc, int maxBytesPerArcWithoutLabel, int labelRange) {
+ // Anticipate precisely the size of the encodings.
+ int sizeForBinarySearch = numBytesPerArc * nodeIn.numArcs;
+ int sizeForDirectAddressing = getNumPresenceBytes(labelRange) + builder.numLabelBytesPerArc[0]
+ + maxBytesPerArcWithoutLabel * nodeIn.numArcs;
+
+ // Determine the allowed oversize compared to binary search.
+ // This is defined by a parameter of FST Builder (default 1: no oversize).
+ int allowedOversize = (int) (sizeForBinarySearch * builder.getDirectAddressingMaxOversizingFactor());
+ int expansionCost = sizeForDirectAddressing - allowedOversize;
+
+ // Select direct addressing if either:
+ // - Direct addressing size is smaller than binary search.
+ // In this case, increment the credit by the reduced size (to use it later).
+ // - Direct addressing size is larger than binary search, but the positive credit allows the oversizing.
+ // In this case, decrement the credit by the oversize.
+ // In addition, do not try to oversize to a clearly too large node size
+ // (this is the DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR parameter).
+ if (expansionCost <= 0 || (builder.directAddressingExpansionCredit >= expansionCost
+ && sizeForDirectAddressing <= allowedOversize * DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR)) {
+ builder.directAddressingExpansionCredit -= expansionCost;
+ return true;
+ }
+ return false;
+ }
+
+ private void writeNodeForBinarySearch(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long startAddress, int maxBytesPerArc) {
+ // Build the header in a buffer.
+ // It is a false/special arc which is in fact a node header with node flags followed by node metadata.
+ builder.fixedLengthArcsBuffer
+ .resetPosition()
+ .writeByte(ARCS_FOR_BINARY_SEARCH)
+ .writeVInt(nodeIn.numArcs)
+ .writeVInt(maxBytesPerArc);
+ int headerLen = builder.fixedLengthArcsBuffer.getPosition();
+
+ // Expand the arcs in place, backwards.
long srcPos = builder.bytes.getPosition();
- long destPos = fixedArrayStart + nodeIn.numArcs * maxBytesPerArc;
+ long destPos = startAddress + headerLen + nodeIn.numArcs * maxBytesPerArc;
assert destPos >= srcPos;
if (destPos > srcPos) {
builder.bytes.skipBytes((int) (destPos - srcPos));
- for(int arcIdx = nodeIn.numArcs - 1; arcIdx >= 0; arcIdx--) {
+ for (int arcIdx = nodeIn.numArcs - 1; arcIdx >= 0; arcIdx--) {
destPos -= maxBytesPerArc;
- srcPos -= builder.reusedBytesPerArc[arcIdx];
- //System.out.println(" repack arcIdx=" + arcIdx + " srcPos=" + srcPos + " destPos=" + destPos);
+ int arcLen = builder.numBytesPerArc[arcIdx];
+ srcPos -= arcLen;
if (srcPos != destPos) {
- //System.out.println(" copy len=" + builder.reusedBytesPerArc[arcIdx]);
- assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " reusedBytesPerArc[arcIdx]=" + builder.reusedBytesPerArc[arcIdx] + " nodeIn.numArcs=" + nodeIn.numArcs;
- builder.bytes.copyBytes(srcPos, destPos, builder.reusedBytesPerArc[arcIdx]);
+ assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " arcLen=" + arcLen + " nodeIn.numArcs=" + nodeIn.numArcs;
+ builder.bytes.copyBytes(srcPos, destPos, arcLen);
}
}
}
+
+ // Write the header.
+ builder.bytes.writeBytes(startAddress, builder.fixedLengthArcsBuffer.getBytes(), 0, headerLen);
+ }
+
+ private void writeNodeForDirectAddressing(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long startAddress, int maxBytesPerArcWithoutLabel, int labelRange) {
+ // Expand the arcs backwards in a buffer because we remove the labels.
+ // So the obtained arcs might occupy less space. This is the reason why this
+ // whole method is more complex.
+ // Drop the label bytes since we can infer the label based on the arc index,
+ // the presence bits, and the first label. Keep the first label.
+ int headerMaxLen = 11;
+ int numPresenceBytes = getNumPresenceBytes(labelRange);
+ long srcPos = builder.bytes.getPosition();
+ int totalArcBytes = builder.numLabelBytesPerArc[0] + nodeIn.numArcs * maxBytesPerArcWithoutLabel;
+ int bufferOffset = headerMaxLen + numPresenceBytes + totalArcBytes;
+ byte[] buffer = builder.fixedLengthArcsBuffer.ensureCapacity(bufferOffset).getBytes();
+ // Copy the arcs to the buffer, dropping all labels except first one.
+ for (int arcIdx = nodeIn.numArcs - 1; arcIdx >= 0; arcIdx--) {
+ bufferOffset -= maxBytesPerArcWithoutLabel;
+ int srcArcLen = builder.numBytesPerArc[arcIdx];
+ srcPos -= srcArcLen;
+ int labelLen = builder.numLabelBytesPerArc[arcIdx];
+ // Copy the flags.
+ builder.bytes.copyBytes(srcPos, buffer, bufferOffset, 1);
+ // Skip the label, copy the remaining.
+ int remainingArcLen = srcArcLen - 1 - labelLen;
+ if (remainingArcLen != 0) {
+ builder.bytes.copyBytes(srcPos + 1 + labelLen, buffer, bufferOffset + 1, remainingArcLen);
+ }
+ if (arcIdx == 0) {
+ // Copy the label of the first arc only.
+ bufferOffset -= labelLen;
+ builder.bytes.copyBytes(srcPos + 1, buffer, bufferOffset, labelLen);
+ }
+ }
+ assert bufferOffset == headerMaxLen + numPresenceBytes;
+
+ // Build the header in the buffer.
+ // It is a false/special arc which is in fact a node header with node flags followed by node metadata.
+ builder.fixedLengthArcsBuffer
+ .resetPosition()
+ .writeByte(ARCS_FOR_DIRECT_ADDRESSING)
+ .writeVInt(labelRange) // labelRange instead of numArcs.
+ .writeVInt(maxBytesPerArcWithoutLabel); // maxBytesPerArcWithoutLabel instead of maxBytesPerArc.
+ int headerLen = builder.fixedLengthArcsBuffer.getPosition();
+
+ // Prepare the builder byte store. Enlarge or truncate if needed.
+ long nodeEnd = startAddress + headerLen + numPresenceBytes + totalArcBytes;
+ long currentPosition = builder.bytes.getPosition();
+ if (nodeEnd >= currentPosition) {
+ builder.bytes.skipBytes((int) (nodeEnd - currentPosition));
+ } else {
+ builder.bytes.truncate(nodeEnd);
+ }
+ assert builder.bytes.getPosition() == nodeEnd;
+
+ // Write the header.
+ long writeOffset = startAddress;
+ builder.bytes.writeBytes(writeOffset, builder.fixedLengthArcsBuffer.getBytes(), 0, headerLen);
+ writeOffset += headerLen;
+
+ // Write the presence bits
+ writePresenceBits(builder, nodeIn, writeOffset, numPresenceBytes);
+ writeOffset += numPresenceBytes;
+
+ // Write the first label and the arcs.
+ builder.bytes.writeBytes(writeOffset, builder.fixedLengthArcsBuffer.getBytes(), bufferOffset, totalArcBytes);
+ }
+
+ private void writePresenceBits(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long dest, int numPresenceBytes) {
+ long bytePos = dest;
+ byte presenceBits = 1; // The first arc is always present.
+ int presenceIndex = 0;
+ int previousLabel = nodeIn.arcs[0].label;
+ for (int arcIdx = 1; arcIdx < nodeIn.numArcs; arcIdx++) {
+ int label = nodeIn.arcs[arcIdx].label;
+ assert label > previousLabel;
+ presenceIndex += label - previousLabel;
+ while (presenceIndex >= Byte.SIZE) {
+ builder.bytes.writeByte(bytePos++, presenceBits);
+ presenceBits = 0;
+ presenceIndex -= Byte.SIZE;
+ }
+ // Set the bit at presenceIndex to flag that the corresponding arc is present.
+ presenceBits |= 1 << presenceIndex;
+ previousLabel = label;
+ }
+ assert presenceIndex == (nodeIn.arcs[nodeIn.numArcs - 1].label - nodeIn.arcs[0].label) % 8;
+ assert presenceBits != 0; // The last byte is not 0.
+ assert (presenceBits & (1 << presenceIndex)) != 0; // The last arc is always present.
+ builder.bytes.writeByte(bytePos++, presenceBits);
+ assert bytePos - dest == numPresenceBytes;
+ }
+
+ /** Gets the number of bytes required to flag the presence of each arc in the given label range, one bit per arc. */
+ private static int getNumPresenceBytes(int labelRange) {
+ return (labelRange + 7) / Byte.SIZE;
+ }
+
+ /**
+ * Reads the presence bits of a direct-addressing node, store them in the provided arc {@link Arc#bitTable()}
+ * and returns the number of presence bytes.
+ */
+ private int readPresenceBytes(Arc<T> arc, BytesReader in) throws IOException {
+ int numPresenceBytes = getNumPresenceBytes(arc.numArcs());
+ Arc.BitTable presenceBits = arc.getOrCreateBitTable().setNumLongs((numPresenceBytes + 7) / Long.BYTES);
+ for (int i = 0; i < numPresenceBytes; i++) {
+ // Read the next unsigned byte, shift it to the left, and appends it to the current long.
+ presenceBits.bits[i / Long.BYTES] |= (in.readByte() & 0xFFL) << (i * Byte.SIZE);
+ }
+ assert assertPresenceBytesAreValid(arc);
+ return numPresenceBytes;
+ }
+
+ private int getNumArcsDirectAddressing(Arc<T> arc) {
+ assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
+ return arc.bitTable().countBits();
+ }
+
+ private boolean assertPresenceBytesAreValid(Arc<T> arc) {
+ assert arc.bitTable() != null;
+ assert arc.bitTable().assertIsValid();
+ // First bit must be set.
+ assert arc.bitTable().isBitSet(0);
+ // Last bit must be set.
+ assert arc.bitTable().isBitSet(arc.numArcs() - 1);
+ // No bit set after the last arc.
+ assert arc.bitTable().nextBitSet(arc.numArcs() - 1) == -1;
+ // Total bit set (real num arcs) must be <= label range (stored in arc.numArcs()).
+ assert getNumArcsDirectAddressing(arc) <= arc.numArcs();
+ return true;
}
/** Fills virtual 'start' arc, ie, an empty incoming arc to the FST's start node */
@@ -765,19 +1061,29 @@ public final class FST<T> implements Accountable {
arc.target = FINAL_END_NODE;
arc.output = follow.nextFinalOutput();
arc.flags = BIT_LAST_ARC;
+ arc.nodeFlags = arc.flags;
return arc;
} else {
in.setPosition(follow.target());
- final byte b = in.readByte();
- if (b == ARCS_AS_ARRAY_PACKED) {
- // array: jump straight to end
+ byte flags = arc.nodeFlags = in.readByte();
+ if (flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING) {
+ // Special arc which is actually a node header for fixed length arcs.
+ // Jump straight to end to find the last arc.
arc.numArcs = in.readVInt();
arc.bytesPerArc = in.readVInt();
//System.out.println(" array numArcs=" + arc.numArcs + " bpa=" + arc.bytesPerArc);
- arc.posArcsStart = in.getPosition();
- arc.arcIdx = arc.numArcs - 2;
+ if (flags == ARCS_FOR_DIRECT_ADDRESSING) {
+ readPresenceBytes(arc, in);
+ arc.firstLabel = readLabel(in);
+ arc.posArcsStart = in.getPosition();
+ readArcByDirectAddressing(arc, in, arc.numArcs() - 1);
+ } else {
+ arc.arcIdx = arc.numArcs() - 2;
+ arc.posArcsStart = in.getPosition();
+ readNextRealArc(arc, in);
+ }
} else {
- arc.flags = b;
+ arc.flags = flags;
// non-array: linear scan
arc.bytesPerArc = 0;
//System.out.println(" scan");
@@ -800,8 +1106,8 @@ public final class FST<T> implements Accountable {
// Undo the byte flags we read:
in.skipBytes(-1);
arc.nextArc = in.getPosition();
+ readNextRealArc(arc, in);
}
- readNextRealArc(arc, in);
assert arc.isLast();
return arc;
}
@@ -833,6 +1139,7 @@ public final class FST<T> implements Accountable {
arc.nextArc = follow.target();
}
arc.target = FINAL_END_NODE;
+ arc.nodeFlags = arc.flags;
//System.out.println(" insert isFinal; nextArc=" + follow.target + " isLast=" + arc.isLast() + " output=" + outputs.outputToString(arc.output));
return arc;
} else {
@@ -844,21 +1151,20 @@ public final class FST<T> implements Accountable {
in.setPosition(nodeAddress);
//System.out.println(" flags=" + arc.flags);
- byte flags = in.readByte();
- if (flags == ARCS_AS_ARRAY_PACKED) {
- //System.out.println(" fixedArray");
- // this is first arc in a fixed-array
+ byte flags = arc.nodeFlags = in.readByte();
+ if (flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING) {
+ //System.out.println(" fixed length arc");
+ // Special arc which is actually a node header for fixed length arcs.
arc.numArcs = in.readVInt();
arc.bytesPerArc = in.readVInt();
- if (flags == ARCS_AS_ARRAY_PACKED) {
- arc.arcIdx = -1;
- } else {
- arc.arcIdx = Integer.MIN_VALUE;
+ arc.arcIdx = -1;
+ if (flags == ARCS_FOR_DIRECT_ADDRESSING) {
+ readPresenceBytes(arc, in);
+ arc.firstLabel = readLabel(in);
}
- arc.nextArc = arc.posArcsStart = in.getPosition();
+ arc.posArcsStart = in.getPosition();
//System.out.println(" bytesPer=" + arc.bytesPerArc + " numArcs=" + arc.numArcs + " arcsStart=" + pos);
} else {
- //arc.flags = b;
arc.nextArc = nodeAddress;
arc.bytesPerArc = 0;
}
@@ -867,10 +1173,7 @@ public final class FST<T> implements Accountable {
}
/**
- * Checks if <code>arc</code>'s target state is in expanded (or vector) format.
- *
- * @return Returns <code>true</code> if <code>arc</code> points to a state in an
- * expanded array format.
+ * Returns whether <code>arc</code>'s target points to a node in expanded format (fixed length arcs).
*/
boolean isExpandedTarget(Arc<T> follow, BytesReader in) throws IOException {
if (!targetHasArcs(follow)) {
@@ -878,7 +1181,7 @@ public final class FST<T> implements Accountable {
} else {
in.setPosition(follow.target());
byte flags = in.readByte();
- return flags == ARCS_AS_ARRAY_PACKED;
+ return flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING;
}
}
@@ -901,68 +1204,73 @@ public final class FST<T> implements Accountable {
assert !arc.isLast();
if (arc.label() == END_LABEL) {
- //System.out.println(" nextArc fake " +
- //arc.nextArc);
-
- long pos = arc.nextArc();
- in.setPosition(pos);
-
- final byte flags = in.readByte();
- if (flags == ARCS_AS_ARRAY_PACKED) {
- //System.out.println(" nextArc fixed array");
- in.readVInt();
+ //System.out.println(" nextArc fake " + arc.nextArc);
+ // Next arc is the first arc of a node.
+ // Position to read the first arc label.
- // Skip bytesPerArc:
- in.readVInt();
- } else {
- in.setPosition(pos);
+ in.setPosition(arc.nextArc());
+ byte flags = in.readByte();
+ if (flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING) {
+ //System.out.println(" nextArc fixed length arc");
+ // Special arc which is actually a node header for fixed length arcs.
+ int numArcs = in.readVInt();
+ in.readVInt(); // Skip bytesPerArc.
+ if (flags == ARCS_FOR_BINARY_SEARCH) {
+ in.readByte(); // Skip arc flags.
+ } else {
+ in.skipBytes(getNumPresenceBytes(numArcs));
+ }
}
- // skip flags
- in.readByte();
} else {
if (arc.bytesPerArc() != 0) {
//System.out.println(" nextArc real array");
- // arcs are in an array
- if (arc.arcIdx() >= 0) {
- in.setPosition(arc.posArcsStart());
- // point at next arc, -1 to skip flags
- in.skipBytes((1 + arc.arcIdx()) * arc.bytesPerArc() + 1);
+ // 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()) * arc.bytesPerArc() - 1);
} else {
- in.setPosition(arc.nextArc());
- byte flags = in.readByte();
- // skip missing arcs
- while (flag(flags, BIT_MISSING_ARC)) {
- in.skipBytes(arc.bytesPerArc() - 1);
- flags = in.readByte();
- }
+ 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 assertPresenceBytesAreValid(arc);
+ assert arc.bitTable().isBitSet(arc.arcIdx());
+ int nextIndex = arc.bitTable().nextBitSet(arc.arcIdx());
+ assert nextIndex != -1;
+ return arc.firstLabel() + nextIndex;
}
} else {
- // arcs are packed
- //System.out.println(" nextArc real packed");
- // -1 to skip flags
+ // Arcs have variable length.
+ //System.out.println(" nextArc real list");
+ // Position to next arc, -1 to skip flags.
in.setPosition(arc.nextArc() - 1);
}
}
return readLabel(in);
}
- public Arc<T> readArcAtPosition(Arc<T> arc, final BytesReader in, long pos) throws IOException {
- in.setPosition(pos);
+ public Arc<T> readArcByIndex(Arc<T> arc, final BytesReader in, int idx) throws IOException {
+ assert idx >= 0 && idx < arc.numArcs();
+ in.setPosition(arc.posArcsStart() - idx * arc.bytesPerArc());
+ arc.arcIdx = idx;
arc.flags = in.readByte();
- arc.nextArc = pos;
- while (flag(arc.flags(), BIT_MISSING_ARC)) {
- // skip empty arcs
- arc.nextArc -= arc.bytesPerArc();
- in.skipBytes(arc.bytesPerArc() - 1);
- arc.flags = in.readByte();
- }
return readArc(arc, in);
}
- public Arc<T> readArcByIndex(Arc<T> arc, final BytesReader in, int idx) throws IOException {
- arc.arcIdx = idx;
- assert arc.arcIdx() < arc.numArcs();
- in.setPosition(arc.posArcsStart() - arc.arcIdx() * arc.bytesPerArc());
+ /** Reads a present direct addressing node arc, with the provided index in the label range.
+ *
+ * @param rangeIndex The index of the arc in the label range. It must be present.
+ * The real arc offset is computed based on the presence bits of
+ * the direct addressing node.
+ */
+ public Arc<T> readArcByDirectAddressing(Arc<T> arc, final BytesReader in, int rangeIndex) throws IOException {
+ assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
+ assert arc.bytesPerArc() > 0;
+ assert assertPresenceBytesAreValid(arc);
+ assert rangeIndex >= 0 && rangeIndex < arc.numArcs();
+ assert arc.bitTable().isBitSet(rangeIndex);
+ int presenceIndex = arc.bitTable().countBitsUpTo(rangeIndex);
+ in.setPosition(arc.posArcsStart() - presenceIndex * arc.bytesPerArc());
+ arc.arcIdx = rangeIndex;
arc.flags = in.readByte();
return readArc(arc, in);
}
@@ -974,35 +1282,43 @@ public final class FST<T> implements Accountable {
// TODO: can't assert this because we call from readFirstArc
// assert !flag(arc.flags, BIT_LAST_ARC);
- // this is a continuing arc in a fixed array
- if (arc.bytesPerArc() != 0) {
- // arcs are in an array
- if (arc.arcIdx() > Integer.MIN_VALUE) {
+ switch (arc.nodeFlags()) {
+
+ case ARCS_FOR_BINARY_SEARCH:
+ assert arc.bytesPerArc() > 0;
arc.arcIdx++;
- assert arc.arcIdx < arc.numArcs;
+ assert arc.arcIdx() >= 0 && arc.arcIdx() < arc.numArcs();
in.setPosition(arc.posArcsStart() - arc.arcIdx() * arc.bytesPerArc());
arc.flags = in.readByte();
- } else {
- assert arc.nextArc() <= arc.posArcsStart() && arc.nextArc() > arc.posArcsStart() - arc.numArcs() * arc.bytesPerArc();
+ break;
+
+ case ARCS_FOR_DIRECT_ADDRESSING:
+ assert arc.bytesPerArc() > 0;
+ assert assertPresenceBytesAreValid(arc);
+ assert arc.arcIdx() == -1 || arc.bitTable().isBitSet(arc.arcIdx());
+ int nextIndex = arc.bitTable().nextBitSet(arc.arcIdx());
+ return readArcByDirectAddressing(arc, in, nextIndex);
+
+ default:
+ // Variable length arcs - linear search.
+ assert arc.bytesPerArc() == 0;
in.setPosition(arc.nextArc());
arc.flags = in.readByte();
- while (flag(arc.flags(), BIT_MISSING_ARC)) {
- // skip empty arcs
- arc.nextArc = arc.nextArc() - arc.bytesPerArc();
- in.skipBytes(arc.bytesPerArc() - 1);
- arc.flags = in.readByte();
- }
- }
- } else {
- // arcs are packed
- in.setPosition(arc.nextArc());
- arc.flags = in.readByte();
}
return readArc(arc, in);
}
+ /**
+ * Reads an arc.
+ * <br>Precondition: The arc flags byte has already been read and set;
+ * the given BytesReader is positioned just after the arc flags byte.
+ */
private Arc<T> readArc(Arc<T> arc, BytesReader in) throws IOException {
- arc.label = readLabel(in);
+ if (arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING) {
+ arc.label = arc.firstLabel() + arc.arcIdx();
+ } else {
+ arc.label = readLabel(in);
+ }
if (arc.flag(BIT_ARC_HAS_OUTPUT)) {
arc.output = outputs.read(in);
@@ -1022,13 +1338,9 @@ public final class FST<T> implements Accountable {
} else {
arc.target = NON_FINAL_END_NODE;
}
- if (arc.bytesPerArc() == 0) {
- arc.nextArc = in.getPosition();
- } else {
- arc.nextArc -= arc.bytesPerArc();
- }
+ arc.nextArc = in.getPosition(); // Only useful for list.
} else if (arc.flag(BIT_TARGET_NEXT)) {
- arc.nextArc = in.getPosition();
+ arc.nextArc = in.getPosition(); // Only useful for list.
// TODO: would be nice to make this lazy -- maybe
// caller doesn't need the target and is scanning arcs...
if (!arc.flag(BIT_LAST_ARC)) {
@@ -1036,21 +1348,14 @@ public final class FST<T> implements Accountable {
// must scan
seekToNextNode(in);
} else {
- in.setPosition(arc.posArcsStart());
- in.skipBytes(arc.bytesPerArc() * arc.numArcs());
+ int numArcs = arc.nodeFlags == ARCS_FOR_DIRECT_ADDRESSING ? getNumArcsDirectAddressing(arc) : arc.numArcs();
+ in.setPosition(arc.posArcsStart() - arc.bytesPerArc() * numArcs);
}
}
arc.target = in.getPosition();
} else {
arc.target = readUnpackedNodeTarget(in);
- if (arc.bytesPerArc() > 0 && arc.arcIdx() == Integer.MIN_VALUE) {
- // nextArc was pointing to *this* arc when we entered; advance to the next
- // if it is a missing arc, we will skip it later
- arc.nextArc = arc.nextArc() - arc.bytesPerArc();
- } else {
- // in list and fixed table encodings, the next arc always follows this one
- arc.nextArc = in.getPosition();
- }
+ arc.nextArc = in.getPosition(); // Only useful for list.
}
return arc;
}
@@ -1090,12 +1395,14 @@ public final class FST<T> implements Accountable {
assert cachedArc.bytesPerArc() == result.bytesPerArc();
assert cachedArc.flags() == result.flags();
assert cachedArc.label() == result.label();
- assert (cachedArc.bytesPerArc() != 0 && cachedArc.arcIdx() != Integer.MIN_VALUE) || cachedArc.nextArc() == result.nextArc();
+ assert cachedArc.bytesPerArc() != 0 || cachedArc.nextArc() == result.nextArc();
assert cachedArc.nextFinalOutput().equals(result.nextFinalOutput());
assert cachedArc.numArcs() == result.numArcs();
assert cachedArc.output().equals(result.output());
assert cachedArc.posArcsStart() == result.posArcsStart();
assert cachedArc.target() == result.target();
+ assert cachedArc.nodeFlags() == result.nodeFlags();
+ assert cachedArc.nodeFlags() != ARCS_FOR_DIRECT_ADDRESSING || cachedArc.firstLabel() == result.firstLabel();
}
return true;
@@ -1125,6 +1432,7 @@ public final class FST<T> implements Accountable {
}
arc.output = follow.nextFinalOutput();
arc.label = END_LABEL;
+ arc.nodeFlags = arc.flags;
return arc;
} else {
return null;
@@ -1155,8 +1463,22 @@ public final class FST<T> implements Accountable {
// System.out.println("fta label=" + (char) labelToMatch);
- byte flags = in.readByte();
- if (flags == ARCS_AS_ARRAY_PACKED) {
+ byte flags = arc.nodeFlags = in.readByte();
+ if (flags == ARCS_FOR_DIRECT_ADDRESSING) {
+ arc.numArcs = in.readVInt(); // This is in fact the label range.
+ arc.bytesPerArc = in.readVInt();
+ readPresenceBytes(arc, in);
+ arc.firstLabel = readLabel(in);
+ arc.posArcsStart = in.getPosition();
+
+ int arcIndex = labelToMatch - arc.firstLabel();
+ if (arcIndex < 0 || arcIndex >= arc.numArcs()) {
+ return null; // Before or after label range.
+ } else if (!arc.bitTable().isBitSet(arcIndex)) {
+ return null; // Arc missing in the range.
+ }
+ return readArcByDirectAddressing(arc, in, arcIndex);
+ } else if (flags == ARCS_FOR_BINARY_SEARCH) {
arc.numArcs = in.readVInt();
arc.bytesPerArc = in.readVInt();
arc.posArcsStart = in.getPosition();
@@ -1230,27 +1552,6 @@ public final class FST<T> implements Accountable {
}
}
- /**
- * Nodes will be expanded if their depth (distance from the root node) is
- * <= this value and their number of arcs is >=
- * {@link #FIXED_ARRAY_NUM_ARCS_SHALLOW}.
- *
- * <p>
- * Fixed array consumes more RAM but enables binary search on the arcs
- * (instead of a linear scan) on lookup by arc label.
- *
- * @return <code>true</code> if <code>node</code> should be stored in an
- * expanded (array) form.
- *
- * @see #FIXED_ARRAY_NUM_ARCS_DEEP
- * @see Builder.UnCompiledNode#depth
- */
- private boolean shouldExpand(Builder<T> builder, Builder.UnCompiledNode<T> node) {
- return builder.allowArrayArcs &&
- ((node.depth <= FIXED_ARRAY_SHALLOW_DISTANCE && node.numArcs >= FIXED_ARRAY_NUM_ARCS_SHALLOW) ||
- node.numArcs >= FIXED_ARRAY_NUM_ARCS_DEEP);
- }
-
/** Returns a {@link BytesReader} for this FST, positioned at
* position 0. */
public BytesReader getBytesReader() {
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java b/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
index 36d8ddd..fb82194 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
@@ -138,12 +138,13 @@ abstract class FSTEnum<T> {
while(arc != null) {
int targetLabel = getTargetLabel();
//System.out.println(" cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") vs targetLabel=" + targetLabel);
- if (arc.bytesPerArc() != 0 && arc.label() != -1) {
+ if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
// Arcs are in an array
final FST.BytesReader in = fst.getBytesReader();
- if (arc.arcIdx() == Integer.MIN_VALUE) {
- arc = doSeekCeilArrayWithGaps(arc, targetLabel, in);
+ if (arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+ arc = doSeekCeilArrayDirectAddressing(arc, targetLabel, in);
} else {
+ assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH;
arc = doSeekCeilArrayPacked(arc, targetLabel, in);
}
} else {
@@ -152,17 +153,12 @@ abstract class FSTEnum<T> {
}
}
- private FST.Arc<T> doSeekCeilArrayWithGaps(final FST.Arc<T> arc, final int targetLabel, final FST.BytesReader in) throws IOException {
- // The array is addressed directly by label and may contain holes.
+ private FST.Arc<T> doSeekCeilArrayDirectAddressing(final FST.Arc<T> arc, final int targetLabel, final FST.BytesReader in) throws IOException {
+ // The array is addressed directly by label, with presence bits to compute the actual arc offset.
- in.setPosition(arc.posArcsStart());
- in.skipBytes(1);
- int firstLabel = fst.readLabel(in);
- int arcOffset = targetLabel - firstLabel;
- if (arcOffset >= arc.numArcs()) {
- // target is beyond the last arc
- fst.readArcAtPosition(arc, in, arc.posArcsStart() - (arc.numArcs() - 1) * arc.bytesPerArc());
- assert arc.isLast();
+ int targetIndex = targetLabel - arc.firstLabel();
+ if (targetIndex >= arc.numArcs()) {
+ // Target is beyond the last arc, out of label range.
// Dead end (target is after the last arc);
// rollback to last fork then push
upto--;
@@ -180,17 +176,13 @@ abstract class FSTEnum<T> {
upto--;
}
} else {
- // TODO: if firstLabel == targetLabel
- long pos;
- if (arcOffset >= 0) {
- pos = arc.posArcsStart() - (arc.bytesPerArc() * arcOffset);
- } else {
- pos = arc.posArcsStart();
- }
- fst.readArcAtPosition(arc, in, pos);
- if (arc.label() == targetLabel) {
+ if (targetIndex < 0) {
+ targetIndex = -1;
+ } else if (arc.bitTable().isBitSet(targetIndex)) {
+ fst.readArcByDirectAddressing(arc, in, targetIndex);
+ assert arc.label() == targetLabel;
// found -- copy pasta from below
- output[upto] = fst.outputs.add(output[upto-1], arc.output());
+ output[upto] = fst.outputs.add(output[upto - 1], arc.output());
if (targetLabel == FST.END_LABEL) {
return null;
}
@@ -198,7 +190,10 @@ abstract class FSTEnum<T> {
incr();
return fst.readFirstTargetArc(arc, getArc(upto), fstReader);
}
- // not found, return the next highest
+ // Not found, return the next arc (ceil).
+ int ceilIndex = arc.bitTable().nextBitSet(targetIndex);
+ assert ceilIndex != -1;
+ fst.readArcByDirectAddressing(arc, in, ceilIndex);
assert arc.label() > targetLabel;
pushFirst();
return null;
@@ -319,9 +314,10 @@ abstract class FSTEnum<T> {
if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
// Arcs are in an array
final FST.BytesReader in = fst.getBytesReader();
- if (arc.arcIdx() == Integer.MIN_VALUE) {
- arc = doSeekFloorArrayWithGaps(arc, targetLabel, in);
+ if (arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+ arc = doSeekFloorArrayDirectAddressing(arc, targetLabel, in);
} else {
+ assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH;
arc = doSeekFloorArrayPacked(arc, targetLabel, in);
}
} else {
@@ -330,46 +326,25 @@ abstract class FSTEnum<T> {
}
}
- private FST.Arc<T> doSeekFloorArrayWithGaps(FST.Arc<T> arc, int targetLabel, final FST.BytesReader in) throws IOException {
- // The array is addressed directly by label and may contain holes.
- in.setPosition(arc.posArcsStart());
- in.skipBytes(1);
- int firstLabel = fst.readLabel(in);
- int targetOffset = targetLabel - firstLabel;
- if (targetOffset < 0) {
- //System.out.println(" before first"); Very first arc is after our target TODO: if each
- // arc could somehow read the arc just before, we can save this re-scan. The ceil case
- // doesn't need this because it reads the next arc instead:
- while(true) {
- // First, walk backwards until we find a first arc
- // that's before our target label:
- fst.readFirstTargetArc(getArc(upto-1), arc, fstReader);
- if (arc.label() < targetLabel) {
- // Then, scan forwards to the arc just before
- // the targetLabel:
- while(!arc.isLast() && fst.readNextArcLabel(arc, in) < targetLabel) {
- fst.readNextArc(arc, fstReader);
- }
- pushLast();
- return null;
- }
- upto--;
- if (upto == 0) {
- return null;
- }
- targetLabel = getTargetLabel();
- arc = getArc(upto);
- }
+ private FST.Arc<T> doSeekFloorArrayDirectAddressing(FST.Arc<T> arc, int targetLabel, FST.BytesReader in) throws IOException {
+ // The array is addressed directly by label, with presence bits to compute the actual arc offset.
+
+ int targetIndex = targetLabel - arc.firstLabel();
+ if (targetIndex < 0) {
+ // Before first arc.
+ return backtrackToFloorArc(arc, targetLabel, in);
+ } else if (targetIndex >= arc.numArcs()) {
+ // After last arc.
+ fst.readArcByDirectAddressing(arc, in, arc.numArcs() - 1);
+ assert arc.label() < targetLabel;
+ assert arc.isLast();
+ pushLast();
+ return null;
} else {
- if (targetOffset >= arc.numArcs()) {
- fst.readArcAtPosition(arc, in, arc.posArcsStart() - arc.bytesPerArc() * (arc.numArcs() - 1));
- assert arc.isLast();
- assert arc.label() < targetLabel: "arc.label=" + arc.label() + " vs targetLabel=" + targetLabel;
- pushLast();
- return null;
- }
- fst.readArcAtPosition(arc, in, arc.posArcsStart() - arc.bytesPerArc() * targetOffset);
- if (arc.label() == targetLabel) {
+ // Within label range.
+ if (arc.bitTable().isBitSet(targetIndex)) {
+ fst.readArcByDirectAddressing(arc, in, targetIndex);
+ assert arc.label() == targetLabel;
// found -- copy pasta from below
output[upto] = fst.outputs.add(output[upto-1], arc.output());
if (targetLabel == FST.END_LABEL) {
@@ -379,18 +354,99 @@ abstract class FSTEnum<T> {
incr();
return fst.readFirstTargetArc(arc, getArc(upto), fstReader);
}
- // Scan backwards to find a floor arc that is not missing
- for (long arcOffset = arc.posArcsStart() - targetOffset * arc.bytesPerArc(); arcOffset <= arc.posArcsStart(); arcOffset += arc.bytesPerArc()) {
- // TODO: we can do better here by skipping missing arcs
- fst.readArcAtPosition(arc, in, arcOffset);
- if (arc.label() < targetLabel) {
- assert arc.isLast() || fst.readNextArcLabel(arc, in) > targetLabel;
- pushLast();
- return null;
+ // Scan backwards to find a floor arc.
+ int floorIndex = arc.bitTable().previousBitSet(targetIndex);
+ assert floorIndex != -1;
+ fst.readArcByDirectAddressing(arc, in, floorIndex);
+ assert arc.label() < targetLabel;
+ assert arc.isLast() || fst.readNextArcLabel(arc, in) > targetLabel;
+ pushLast();
+ return null;
+ }
+ }
+
+ /**
+ * Backtracks until it finds a node which first arc is before our target label.`
+ * Then on the node, finds the arc just before the targetLabel.
+ *
+ * @return null to continue the seek floor recursion loop.
+ */
+ private FST.Arc<T> backtrackToFloorArc(FST.Arc<T> arc, int targetLabel, final FST.BytesReader in) throws IOException {
+ while (true) {
+ // First, walk backwards until we find a node which first arc is before our target label.
+ fst.readFirstTargetArc(getArc(upto-1), arc, fstReader);
+ if (arc.label() < targetLabel) {
+ // Then on this node, find the arc just before the targetLabel.
+ if (!arc.isLast()) {
+ if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
+ if (arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
+ findNextFloorArcBinarySearch(arc, targetLabel, in);
+ } else {
+ assert arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
+ findNextFloorArcDirectAddressing(arc, targetLabel, in);
+ }
+ } else {
+ while (!arc.isLast() && fst.readNextArcLabel(arc, in) < targetLabel) {
+ fst.readNextArc(arc, fstReader);
+ }
+ }
+ }
+ assert arc.label() < targetLabel;
+ assert arc.isLast() || fst.readNextArcLabel(arc, in) >= targetLabel;
+ pushLast();
+ return null;
+ }
+ upto--;
+ if (upto == 0) {
+ return null;
+ }
+ targetLabel = getTargetLabel();
+ arc = getArc(upto);
+ }
+ }
+
+ /**
+ * Finds and reads an arc on the current node which label is strictly less than the given label.
+ * Skips the first arc, finds next floor arc; or none if the floor arc is the first
+ * arc itself (in this case it has already been read).
+ * <p>
+ * Precondition: the given arc is the first arc of the node.
+ */
+ private void findNextFloorArcDirectAddressing(FST.Arc<T> arc, int targetLabel, final FST.BytesReader in) throws IOException {
+ assert arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
+ assert arc.label() != FST.END_LABEL;
+ assert arc.label() == arc.firstLabel();
+ if (arc.numArcs() > 1) {
+ int targetIndex = targetLabel - arc.firstLabel();
+ assert targetIndex >= 0;
+ if (targetIndex >= arc.numArcs()) {
+ // Beyond last arc. Take last arc.
+ fst.readArcByDirectAddressing(arc, in, arc.numArcs() - 1);
+ } else {
+ // Take the preceding arc, even if the target is present.
+ int floorIndex = arc.bitTable().previousBitSet(targetIndex);
+ if (floorIndex > 0) {
+ fst.readArcByDirectAddressing(arc, in, floorIndex);
}
}
- assert false: "arc.label=" + arc.label() + " vs targetLabel=" + targetLabel;
- return arc; // unreachable
+ }
+ }
+
+ /**
+ * Same as {@link #findNextFloorArcDirectAddressing} for binary search node.
+ */
+ private void findNextFloorArcBinarySearch(FST.Arc<T> arc, int targetLabel, FST.BytesReader in) throws IOException {
+ assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH;
+ assert arc.label() != FST.END_LABEL;
+ assert arc.arcIdx() == 0;
+ if (arc.numArcs() > 1) {
+ int idx = Util.binarySearch(fst, arc, targetLabel);
+ assert idx != -1;
+ if (idx > 1) {
+ fst.readArcByIndex(arc, in, idx - 1);
+ } else if (idx < -2) {
+ fst.readArcByIndex(arc, in, -2 - idx);
+ }
}
}
@@ -412,34 +468,10 @@ abstract class FSTEnum<T> {
incr();
return fst.readFirstTargetArc(arc, getArc(upto), fstReader);
} else if (idx == -1) {
- //System.out.println(" before first");
- // Very first arc is after our target
- // TODO: if each arc could somehow read the arc just
- // before, we can save this re-scan. The ceil case
- // doesn't need this because it reads the next arc
- // instead:
- while(true) {
- // First, walk backwards until we find a first arc
- // that's before our target label:
- fst.readFirstTargetArc(getArc(upto-1), arc, fstReader);
- if (arc.label() < targetLabel) {
- // Then, scan forwards to the arc just before
- // the targetLabel:
- while(!arc.isLast() && fst.readNextArcLabel(arc, in) < targetLabel) {
- fst.readNextArc(arc, fstReader);
- }
- pushLast();
- return null;
- }
- upto--;
- if (upto == 0) {
- return null;
- }
- targetLabel = getTargetLabel();
- arc = getArc(upto);
- }
+ // Before first arc.
+ return backtrackToFloorArc(arc, targetLabel, in);
} else {
- // There is a floor arc; idx will be {@code -1 - (floor + 1)}.
+ // There is a floor arc; idx will be (-1 - (floor + 1)).
fst.readArcByIndex(arc, in, -2 - idx);
assert arc.isLast() || fst.readNextArcLabel(arc, in) > targetLabel;
assert arc.label() < targetLabel: "arc.label=" + arc.label() + " vs targetLabel=" + targetLabel;
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java b/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
index 8530ccb..af152fe 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
@@ -41,9 +41,22 @@ final class NodeHash<T> {
private boolean nodesEqual(Builder.UnCompiledNode<T> node, long address) throws IOException {
fst.readFirstRealTargetArc(address, scratchArc, in);
- if (scratchArc.isPackedArray() && node.numArcs != scratchArc.numArcs()) {
- return false;
+
+ // 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 != scratchArc.bitTable().countBits()) {
+ return false;
+ }
+ }
}
+
for(int arcUpto=0; arcUpto < node.numArcs; arcUpto++) {
final Builder.Arc<T> arc = node.arcs[arcUpto];
if (arc.label != scratchArc.label() ||
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
index ddecade..5f822c4 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
@@ -151,7 +151,7 @@ public final class Util {
fst.readFirstRealTargetArc(arc.target(), arc, in);
- if (arc.bytesPerArc() != 0 && arc.arcIdx() > Integer.MIN_VALUE) {
+ if (arc.bytesPerArc() != 0 && arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
int low = 0;
int high = arc.numArcs() -1;
@@ -940,18 +940,27 @@ public final class Util {
}
fst.readFirstTargetArc(follow, arc, in);
if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
- if (arc.arcIdx() == Integer.MIN_VALUE) {
- // Arcs are in an array-with-gaps
- int offset = label - arc.label();
- if (offset >= arc.numArcs()) {
+ if (arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+ // Fixed length arcs in a direct addressing node.
+ int targetIndex = label - arc.label();
+ if (targetIndex >= arc.numArcs()) {
return null;
- } else if (offset < 0) {
+ } else if (targetIndex < 0) {
return arc;
} else {
- return fst.readArcAtPosition(arc, in, arc.posArcsStart() - offset * arc.bytesPerArc());
+ if (arc.bitTable().isBitSet(targetIndex)) {
+ fst.readArcByDirectAddressing(arc, in, targetIndex);
+ assert arc.label() == label;
+ } else {
+ int ceilIndex = arc.bitTable().nextBitSet(targetIndex);
+ assert ceilIndex != -1;
+ fst.readArcByDirectAddressing(arc, in, ceilIndex);
+ assert arc.label() > label;
+ }
+ return arc;
}
}
- // Arcs are packed array -- use binary search to find the target.
+ // Fixed length arcs in a binary search node.
int idx = binarySearch(fst, arc, label);
if (idx >= 0) {
return fst.readArcByIndex(arc, in, idx);
@@ -964,7 +973,8 @@ public final class Util {
return fst.readArcByIndex(arc, in , idx);
}
- // Linear scan
+ // Variable length arcs in a linear scan list,
+ // or special arc with label == FST.END_LABEL.
fst.readFirstRealTargetArc(follow.target(), arc, in);
while (true) {
@@ -995,6 +1005,7 @@ public final class Util {
* @throws IOException when the FST reader does
*/
static <T> int binarySearch(FST<T> fst, FST.Arc<T> arc, int targetLabel) throws IOException {
+ assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH : "Arc is not encoded as packed array for binary search (nodeFlags=" + arc.nodeFlags() + ")";
BytesReader in = fst.getBytesReader();
int low = arc.arcIdx();
int mid = 0;
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java b/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java
new file mode 100644
index 0000000..84a7b75
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+public class TestBitUtil extends LuceneTestCase {
+
+ public void testNextBitSet() {
+ for (int i = 0; i < 10000; i++) {
+ long[] bits = buildRandomBits();
+ int numLong = bits.length - 1;
+
+ // Verify nextBitSet with countBitsUpTo for all bit indexes.
+ for (int bitIndex = -1; bitIndex < 64 * numLong; bitIndex++) {
+ int nextIndex = BitUtil.nextBitSet(bits, numLong, bitIndex);
+ if (nextIndex == -1) {
+ assertEquals("No next bit set, so expected no bit count diff"
+ + " (i=" + i + " bitIndex=" + bitIndex + ")",
+ BitUtil.countBitsUpTo(bits, numLong, bitIndex + 1), BitUtil.countBits(bits, numLong));
+ } else {
+ assertTrue("Expected next bit set at nextIndex=" + nextIndex
+ + " (i=" + i + " bitIndex=" + bitIndex + ")",
+ BitUtil.isBitSet(bits, numLong, nextIndex));
+ assertEquals("Next bit set at nextIndex=" + nextIndex
+ + " so expected bit count diff of 1"
+ + " (i=" + i + " bitIndex=" + bitIndex + ")",
+ BitUtil.countBitsUpTo(bits, numLong, bitIndex + 1) + 1,
+ BitUtil.countBitsUpTo(bits, numLong, nextIndex + 1));
+ }
+ }
+ }
+ }
+
+ public void testPreviousBitSet() {
+ for (int i = 0; i < 10000; i++) {
+ long[] bits = buildRandomBits();
+ int numLong = bits.length - 1;
+
+ // Verify previousBitSet with countBitsUpTo for all bit indexes.
+ for (int bitIndex = 0; bitIndex <= 64 * numLong; bitIndex++) {
+ int previousIndex = BitUtil.previousBitSet(bits, numLong, bitIndex);
+ if (previousIndex == -1) {
+ assertEquals("No previous bit set, so expected bit count 0"
+ + " (i=" + i + " bitIndex=" + bitIndex + ")",
+ 0, BitUtil.countBitsUpTo(bits, numLong, bitIndex));
+ } else {
+ assertTrue("Expected previous bit set at previousIndex=" + previousIndex
+ + " (i=" + i + " bitIndex=" + bitIndex + ")",
+ BitUtil.isBitSet(bits, numLong, previousIndex));
+ int bitCount = BitUtil.countBitsUpTo(bits, numLong, Math.min(bitIndex + 1, numLong * Long.SIZE));
+ int expectedPreviousBitCount = bitIndex < numLong * Long.SIZE && BitUtil.isBitSet(bits, numLong, bitIndex) ?
+ bitCount - 1 : bitCount;
+ assertEquals("Previous bit set at previousIndex=" + previousIndex
+ + " with current bitCount=" + bitCount
+ + " so expected previousBitCount=" + expectedPreviousBitCount
+ + " (i=" + i + " bitIndex=" + bitIndex + ")",
+ expectedPreviousBitCount, BitUtil.countBitsUpTo(bits, numLong, previousIndex + 1));
+ }
+ }
+ }
+ }
+
+ private long[] buildRandomBits() {
+ long[] bits = new long[random().nextInt(3) + 2];
+ for (int j = 0; j < bits.length; j++) {
+ // Bias towards zeros which require special logic.
+ bits[j] = random().nextInt(4) == 0 ? 0L : random().nextLong();
+ }
+ return bits;
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
index 8f598f6..316cbdf 100644
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
@@ -303,7 +303,7 @@ public class TestFSTs extends LuceneTestCase {
public void testBigSet() throws IOException {
testRandomWords(TestUtil.nextInt(random(), 50000, 60000), 1);
}
-
+
// Build FST for all unique terms in the test line docs
// file, up until a doc limit
public void testRealTerms() throws Exception {
@@ -1078,10 +1078,10 @@ public class TestFSTs extends LuceneTestCase {
int children = verifyStateAndBelow(fst, new FST.Arc<>().copyFrom(arc), depth + 1);
assertEquals(
- expanded,
- (depth <= FST.FIXED_ARRAY_SHALLOW_DISTANCE &&
- children >= FST.FIXED_ARRAY_NUM_ARCS_SHALLOW) ||
- children >= FST.FIXED_ARRAY_NUM_ARCS_DEEP);
+ (depth <= FST.FIXED_LENGTH_ARC_SHALLOW_DEPTH &&
+ children >= FST.FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS) ||
+ children >= FST.FIXED_LENGTH_ARC_DEEP_NUM_ARCS,
+ expanded);
if (arc.isLast()) break;
}
@@ -1092,8 +1092,8 @@ public class TestFSTs extends LuceneTestCase {
}
// Sanity check.
- assertTrue(FST.FIXED_ARRAY_NUM_ARCS_SHALLOW < FST.FIXED_ARRAY_NUM_ARCS_DEEP);
- assertTrue(FST.FIXED_ARRAY_SHALLOW_DISTANCE >= 0);
+ assertTrue(FST.FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS < FST.FIXED_LENGTH_ARC_DEEP_NUM_ARCS);
+ assertTrue(FST.FIXED_LENGTH_ARC_SHALLOW_DEPTH >= 0);
SyntheticData s = new SyntheticData();
@@ -1635,4 +1635,23 @@ public class TestFSTs extends LuceneTestCase {
// expected
}
}
+
+ public void testSimpleDepth() throws Exception {
+ PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
+ Builder<Long> builder = new Builder<>(FST.INPUT_TYPE.BYTE1, outputs);
+
+ BytesRef ab = new BytesRef("ab");
+ BytesRef ac = new BytesRef("ac");
+ BytesRef bd = new BytesRef("bd");
+
+ builder.add(Util.toIntsRef(ab, new IntsRefBuilder()), 3L);
+ builder.add(Util.toIntsRef(ac, new IntsRefBuilder()), 5L);
+ builder.add(Util.toIntsRef(bd, new IntsRefBuilder()), 7L);
+
+ FST<Long> fst = builder.finish();
+
+ assertEquals(3, (long) Util.get(fst, ab));
+ assertEquals(5, (long) Util.get(fst, ac));
+ assertEquals(7, (long) Util.get(fst, bd));
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirect.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirect.java
deleted file mode 100644
index af9f933..0000000
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirect.java
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.util.fst;
-
-import java.nio.file.Files;
-import java.nio.file.Paths;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-import java.util.Locale;
-
-import org.apache.lucene.store.ByteArrayDataInput;
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.IntsRefBuilder;
-import org.apache.lucene.util.LuceneTestCase;
-
-
-public class TestFstDirect extends LuceneTestCase {
-
- public void testDenseWithGap() throws Exception {
- List<String> words = Arrays.asList("ah", "bi", "cj", "dk", "fl", "gm");
- List<BytesRef> entries = new ArrayList<>();
- for (String word : words) {
- entries.add(new BytesRef(word.getBytes("ascii")));
- }
- final BytesRefFSTEnum<Object> fstEnum = new BytesRefFSTEnum<>(buildFST(entries));
- for (BytesRef entry : entries) {
- assertNotNull(entry.utf8ToString() + " not found", fstEnum.seekExact(entry));
- }
- }
-
- public void testDeDupTails() throws Exception {
- List<BytesRef> entries = new ArrayList<>();
- for (int i = 0; i < 1000000; i += 4) {
- byte[] b = new byte[3];
- int val = i;
- for (int j = b.length - 1; j >= 0; --j) {
- b[j] = (byte) (val & 0xff);
- val >>= 8;
- }
- entries.add(new BytesRef(b));
- }
- long size = buildFST(entries).ramBytesUsed();
- // Size is 1664 when we use only list-encoding. We were previously failing to ever de-dup
- // arrays-with-gaps, which led this case to blow up.
- assertTrue(size < 3000);
- //printf("fst size = %d bytes", size);
- }
-
- private FST<Object> buildFST(List<BytesRef> entries) throws Exception {
- final Outputs<Object> outputs = NoOutputs.getSingleton();
- final Builder<Object> b = new Builder<>(FST.INPUT_TYPE.BYTE1, 0, 0, true, true, Integer.MAX_VALUE, outputs, true, 15);
- BytesRef last = null;
- for (BytesRef entry : entries) {
- if (entry.equals(last) == false) {
- b.add(Util.toIntsRef(entry, new IntsRefBuilder()), outputs.getNoOutput());
- }
- last = entry;
- }
- FST<Object> fst = b.finish();
- return fst;
- }
-
- private static void printf(String format, Object ... values) {
- System.out.println(String.format(Locale.ROOT, format, values));
- }
-
- private static long nsToMs(long ns) {
- return ns / 1_000_000;
- }
-
- public static void main(String... args) throws Exception {
- byte[] buf = Files.readAllBytes(Paths.get(args[0]));
- DataInput in = new ByteArrayDataInput(buf);
- FST<BytesRef> fst = new FST<>(in, ByteSequenceOutputs.getSingleton());
- BytesRefFSTEnum<BytesRef> fstEnum = new BytesRefFSTEnum<>(fst);
- int sparseArrayArcCount = 0, directArrayArcCount = 0, listArcCount = 0;
- while(fstEnum.next() != null) {
- if (fstEnum.arcs[fstEnum.upto].bytesPerArc() == 0) {
- listArcCount ++;
- } else if (fstEnum.arcs[fstEnum.upto].arcIdx() == Integer.MIN_VALUE) {
- directArrayArcCount ++;
- } else {
- sparseArrayArcCount ++;
- }
- }
- System.out.println("direct arcs = " + directArrayArcCount + ", sparse arcs = " + sparseArrayArcCount +
- " list arcs = " + listArcCount);
- }
-
-}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirectAddressing.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirectAddressing.java
new file mode 100644
index 0000000..f69f813
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirectAddressing.java
@@ -0,0 +1,212 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util.fst;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Locale;
+import java.util.Set;
+
+import org.apache.lucene.store.ByteArrayDataInput;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IntsRefBuilder;
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestFstDirectAddressing extends LuceneTestCase {
+
+ public void testDenseWithGap() throws Exception {
+ List<String> words = Arrays.asList("ah", "bi", "cj", "dk", "fl", "gm");
+ List<BytesRef> entries = new ArrayList<>();
+ for (String word : words) {
+ entries.add(new BytesRef(word.getBytes(StandardCharsets.US_ASCII)));
+ }
+ final BytesRefFSTEnum<Object> fstEnum = new BytesRefFSTEnum<>(buildFST(entries));
+ for (BytesRef entry : entries) {
+ assertNotNull(entry.utf8ToString() + " not found", fstEnum.seekExact(entry));
+ }
+ }
+
+ public void testDeDupTails() throws Exception {
+ List<BytesRef> entries = new ArrayList<>();
+ for (int i = 0; i < 1000000; i += 4) {
+ byte[] b = new byte[3];
+ int val = i;
+ for (int j = b.length - 1; j >= 0; --j) {
+ b[j] = (byte) (val & 0xff);
+ val >>= 8;
+ }
+ entries.add(new BytesRef(b));
+ }
+ long size = buildFST(entries).ramBytesUsed();
+ // Size is 1648 when we use only list-encoding. We were previously failing to ever de-dup
+ // direct addressing, which led this case to blow up.
+ assertTrue(size <= 1080);
+ //printf("fst size = %d bytes", size);
+ }
+
+ public void testWorstCaseForDirectAddressing() throws Exception {
+ // This test will fail if there is more than 1% memory increase with direct addressing in this worst case.
+ final double MEMORY_INCREASE_LIMIT_PERCENT = 1d;
+ final int NUM_WORDS = 1000000;
+
+ // Generate words with specially crafted bytes.
+ Set<BytesRef> wordSet = new HashSet<>();
+ for (int i = 0; i < NUM_WORDS; ++i) {
+ byte[] b = new byte[5];
+ random().nextBytes(b);
+ for (int j = 0; j < b.length; ++j) {
+ b[j] &= 0xfc; // Make this byte a multiple of 4.
+ }
+ wordSet.add(new BytesRef(b));
+ }
+ List<BytesRef> wordList = new ArrayList<>(wordSet);
+ Collections.sort(wordList);
+
+ // Disable direct addressing and measure the FST size.
+ Builder<Object> builder = createBuilder(-1f);
+ FST<Object> fst = buildFST(wordList, builder);
+ long ramBytesUsedNoDirectAddressing = fst.ramBytesUsed();
+
+ // Enable direct addressing and measure the FST size.
+ builder = createBuilder(Builder.DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR);
+ fst = buildFST(wordList, builder);
+ long ramBytesUsed = fst.ramBytesUsed();
+
+ // Compute the size increase in percents.
+ double directAddressingMemoryIncreasePercent = ((double) ramBytesUsed / ramBytesUsedNoDirectAddressing - 1) * 100;
+
+// printStats(builder, ramBytesUsed, directAddressingMemoryIncreasePercent);
+
+ // Verify the FST size does not exceed the limit.
+ assertTrue("FST size exceeds limit, size = " + ramBytesUsed
+ + ", increase = " + directAddressingMemoryIncreasePercent + " %"
+ + ", limit = " + MEMORY_INCREASE_LIMIT_PERCENT + " %",
+ directAddressingMemoryIncreasePercent < MEMORY_INCREASE_LIMIT_PERCENT);
+ }
+
+ private static void printStats(Builder<Object> builder, long ramBytesUsed, double directAddressingMemoryIncreasePercent) {
+ System.out.println("directAddressingMaxOversizingFactor = " + builder.getDirectAddressingMaxOversizingFactor());
+ System.out.println("ramBytesUsed = "
+ + String.format(Locale.ENGLISH, "%.2f MB", ramBytesUsed / 1024d / 1024d)
+ + String.format(Locale.ENGLISH, " (%.2f %% increase with direct addressing)", directAddressingMemoryIncreasePercent));
+ System.out.println("num nodes = " + builder.nodeCount);
+ long fixedLengthArcNodeCount = builder.directAddressingNodeCount + builder.binarySearchNodeCount;
+ System.out.println("num fixed-length-arc nodes = " + fixedLengthArcNodeCount
+ + String.format(Locale.ENGLISH, " (%.2f %% of all nodes)",
+ ((double) fixedLengthArcNodeCount / builder.nodeCount * 100)));
+ System.out.println("num binary-search nodes = " + (builder.binarySearchNodeCount)
+ + String.format(Locale.ENGLISH, " (%.2f %% of fixed-length-arc nodes)",
+ ((double) (builder.binarySearchNodeCount) / fixedLengthArcNodeCount * 100)));
+ System.out.println("num direct-addressing nodes = " + (builder.directAddressingNodeCount)
+ + String.format(Locale.ENGLISH, " (%.2f %% of fixed-length-arc nodes)",
+ ((double) (builder.directAddressingNodeCount) / fixedLengthArcNodeCount * 100)));
+ }
+
+ private static Builder<Object> createBuilder(float directAddressingMaxOversizingFactor) {
+ return new Builder<>(FST.INPUT_TYPE.BYTE1, 0, 0, true, true, Integer.MAX_VALUE, NoOutputs.getSingleton(), true, 15)
+ .setDirectAddressingMaxOversizingFactor(directAddressingMaxOversizingFactor);
+ }
+
+ private FST<Object> buildFST(List<BytesRef> entries) throws Exception {
+ return buildFST(entries, createBuilder(Builder.DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR));
+ }
+
+ private static FST<Object> buildFST(List<BytesRef> entries, Builder<Object> builder) throws Exception {
+ BytesRef last = null;
+ for (BytesRef entry : entries) {
+ if (entry.equals(last) == false) {
+ builder.add(Util.toIntsRef(entry, new IntsRefBuilder()), NoOutputs.getSingleton().getNoOutput());
+ }
+ last = entry;
+ }
+ return builder.finish();
+ }
+
+ public static void main(String... args) throws Exception {
+ if (args.length < 2) {
+ throw new IllegalArgumentException("Missing argument");
+ }
+ if (args[0].equals("-countFSTArcs")) {
+ countFSTArcs(args[1]);
+ } else if (args[0].equals("-measureFSTOversizing")) {
+ measureFSTOversizing(args[1]);
+ } else {
+ throw new IllegalArgumentException("Invalid argument " + args[0]);
+ }
+ }
+
+ private static void countFSTArcs(String FSTFilePath) throws IOException {
+ byte[] buf = Files.readAllBytes(Paths.get(FSTFilePath));
+ DataInput in = new ByteArrayDataInput(buf);
+ FST<BytesRef> fst = new FST<>(in, ByteSequenceOutputs.getSingleton());
+ BytesRefFSTEnum<BytesRef> fstEnum = new BytesRefFSTEnum<>(fst);
+ int binarySearchArcCount = 0, directAddressingArcCount = 0, listArcCount = 0;
+ while(fstEnum.next() != null) {
+ if (fstEnum.arcs[fstEnum.upto].bytesPerArc() == 0) {
+ listArcCount ++;
+ } else if (fstEnum.arcs[fstEnum.upto].nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+ directAddressingArcCount ++;
+ } else {
+ binarySearchArcCount ++;
+ }
+ }
+ System.out.println("direct addressing arcs = " + directAddressingArcCount
+ + ", binary search arcs = " + binarySearchArcCount
+ + " list arcs = " + listArcCount);
+ }
+
+ private static void measureFSTOversizing(String wordsFilePath) throws Exception {
+ final int MAX_NUM_WORDS = 1000000;
+
+ // Read real english words.
+ List<BytesRef> wordList = new ArrayList<>();
+ try (BufferedReader reader = Files.newBufferedReader(Paths.get(wordsFilePath))) {
+ while (wordList.size() < MAX_NUM_WORDS) {
+ String word = reader.readLine();
+ if (word == null) {
+ break;
+ }
+ wordList.add(new BytesRef(word));
+ }
+ }
+ Collections.sort(wordList);
+
+ // Disable direct addressing and measure the FST size.
+ Builder<Object> builder = createBuilder(-1f);
+ FST<Object> fst = buildFST(wordList, builder);
+ long ramBytesUsedNoDirectAddressing = fst.ramBytesUsed();
+
+ // Enable direct addressing and measure the FST size.
+ builder = createBuilder(Builder.DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR);
+ fst = buildFST(wordList, builder);
+ long ramBytesUsed = fst.ramBytesUsed();
+
+ // Compute the size increase in percents.
+ double directAddressingMemoryIncreasePercent = ((double) ramBytesUsed / ramBytesUsedNoDirectAddressing - 1) * 100;
+
+ printStats(builder, ramBytesUsed, directAddressingMemoryIncreasePercent);
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java
index 5ec163e..2793e7e 100644
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java
@@ -27,10 +27,10 @@ import org.apache.lucene.util.LuceneTestCase;
public class TestUtil extends LuceneTestCase {
public void testBinarySearch() throws Exception {
- // Creates a node with 8 arcs spanning (z-A) = 57 chars that will be encoded as a sparse array (no gaps)
- // requiring binary search
+ // Create a node with 8 arcs spanning (z-A) and ensure it is encoded as a packed array
+ // requiring binary search.
List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T", "z");
- FST<Object> fst = buildFST(letters, true);
+ FST<Object> fst = buildFST(letters, true, false);
FST.Arc<Object> arc = fst.getFirstArc(new FST.Arc<>());
arc = fst.readFirstTargetArc(arc, arc, fst.getBytesReader());
for (int i = 0; i < letters.size(); i++) {
@@ -47,21 +47,21 @@ public class TestUtil extends LuceneTestCase {
public void testReadCeilArcPackedArray() throws Exception {
List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T", "z");
- verifyReadCeilArc(letters, true);
+ verifyReadCeilArc(letters, true, false);
}
public void testReadCeilArcArrayWithGaps() throws Exception {
List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T");
- verifyReadCeilArc(letters, true);
+ verifyReadCeilArc(letters, true, true);
}
public void testReadCeilArcList() throws Exception {
List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T", "z");
- verifyReadCeilArc(letters, false);
+ verifyReadCeilArc(letters, false, false);
}
- private void verifyReadCeilArc(List<String> letters, boolean allowArrayArcs) throws Exception {
- FST<Object> fst = buildFST(letters, allowArrayArcs);
+ private void verifyReadCeilArc(List<String> letters, boolean allowArrayArcs, boolean allowDirectAddressing) throws Exception {
+ FST<Object> fst = buildFST(letters, allowArrayArcs, allowDirectAddressing);
FST.Arc<Object> first = fst.getFirstArc(new FST.Arc<>());
FST.Arc<Object> arc = new FST.Arc<>();
FST.BytesReader in = fst.getBytesReader();
@@ -81,9 +81,12 @@ public class TestUtil extends LuceneTestCase {
assertNull(Util.readCeilArc('Z', fst, arc, arc, in));
}
- private FST<Object> buildFST(List<String> words, boolean allowArrayArcs) throws Exception {
+ private FST<Object> buildFST(List<String> words, boolean allowArrayArcs, boolean allowDirectAddressing) throws Exception {
final Outputs<Object> outputs = NoOutputs.getSingleton();
final Builder<Object> b = new Builder<>(FST.INPUT_TYPE.BYTE1, 0, 0, true, true, Integer.MAX_VALUE, outputs, allowArrayArcs, 15);
+ if (!allowDirectAddressing) {
+ b.setDirectAddressingMaxOversizingFactor(-1f);
+ }
for (String word : words) {
b.add(Util.toIntsRef(new BytesRef(word), new IntsRefBuilder()), outputs.getNoOutput());