dungba88 commented on code in PR #12738:
URL: https://github.com/apache/lucene/pull/12738#discussion_r1378848941
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -107,28 +121,43 @@ public long add(FSTCompiler.UnCompiledNode<T> nodeIn)
throws IOException {
long node = primaryTable.get(pos);
if (node == 0) {
// node is not in primary table; is it in fallback table?
- node = getFallback(nodeIn, hash);
- if (node != 0) {
+ NodeAddressAndLength addressAndLength = getFallback(nodeIn, hash);
+ if (addressAndLength != null) {
+ node = addressAndLength.address;
// it was already in fallback -- promote to primary
- primaryTable.set(pos, node);
+ // TODO: Copy directly between 2 ByteBlockPool to avoid double-copy
+ primaryTable.set(pos, node, fallbackTable.getBytes(node,
addressAndLength.length));
} else {
// not in fallback either -- freeze & add the incoming node
+ long startAddress = fstCompiler.bytes.getPosition();
// freeze & add
node = fstCompiler.addNode(nodeIn);
// we use 0 as empty marker in hash table, so it better be
impossible to get a frozen node
// at 0:
- assert node != 0;
+ assert node != FST.FINAL_END_NODE && node != FST.NON_FINAL_END_NODE;
+ byte[] buf = new byte[Math.toIntExact(node - startAddress + 1)];
Review Comment:
I have a TODO in `set()` itself, which covers the case of writing from
BytesStore. But I could move to here instead.
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -186,132 +214,99 @@ private long hash(FSTCompiler.UnCompiledNode<T> node) {
return h;
}
- // hash code for a frozen node. this must precisely match the hash
computation of an unfrozen
- // node!
- private long hash(long node) throws IOException {
- final int PRIME = 31;
-
- long h = 0;
- fstCompiler.fst.readFirstRealTargetArc(node, scratchArc, in);
- while (true) {
- h = PRIME * h + scratchArc.label();
- h = PRIME * h + (int) (scratchArc.target() ^ (scratchArc.target() >>
32));
- h = PRIME * h + scratchArc.output().hashCode();
- h = PRIME * h + scratchArc.nextFinalOutput().hashCode();
- if (scratchArc.isFinal()) {
- h += 17;
- }
- if (scratchArc.isLast()) {
- break;
- }
- fstCompiler.fst.readNextRealArc(scratchArc, in);
- }
-
- return h;
- }
-
- /**
- * Compares an unfrozen node (UnCompiledNode) with a frozen node at byte
location address (long),
- * returning true if they are equal.
- */
- private boolean nodesEqual(FSTCompiler.UnCompiledNode<T> node, long address)
throws IOException {
- fstCompiler.fst.readFirstRealTargetArc(address, scratchArc, in);
-
- // fail fast for a node with fixed length arcs
- if (scratchArc.bytesPerArc() != 0) {
- assert node.numArcs > 0;
- // the frozen node uses fixed-with arc encoding (same number of bytes
per arc), but may be
- // sparse or dense
- switch (scratchArc.nodeFlags()) {
- case FST.ARCS_FOR_BINARY_SEARCH:
- // sparse
- if (node.numArcs != scratchArc.numArcs()) {
- return false;
- }
- break;
- case FST.ARCS_FOR_DIRECT_ADDRESSING:
- // dense -- compare both the number of labels allocated in the array
(some of which may
- // not actually be arcs), and the number of arcs
- if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) !=
scratchArc.numArcs()
- || node.numArcs != FST.Arc.BitTable.countBits(scratchArc, in)) {
- return false;
- }
- break;
- default:
- throw new AssertionError("unhandled scratchArc.nodeFlag() " +
scratchArc.nodeFlags());
- }
- }
-
- // compare arc by arc to see if there is a difference
- for (int arcUpto = 0; arcUpto < node.numArcs; arcUpto++) {
- final FSTCompiler.Arc<T> arc = node.arcs[arcUpto];
- if (arc.label != scratchArc.label()
- || arc.output.equals(scratchArc.output()) == false
- || ((FSTCompiler.CompiledNode) arc.target).node !=
scratchArc.target()
- || arc.nextFinalOutput.equals(scratchArc.nextFinalOutput()) == false
- || arc.isFinal != scratchArc.isFinal()) {
- return false;
- }
-
- if (scratchArc.isLast()) {
- if (arcUpto == node.numArcs - 1) {
- return true;
- } else {
- return false;
- }
- }
-
- fstCompiler.fst.readNextRealArc(scratchArc, in);
- }
-
- // unfrozen node has fewer arcs than frozen node
-
- return false;
- }
-
/** Inner class because it needs access to hash function and FST bytes. */
private class PagedGrowableHash {
- private PagedGrowableWriter entries;
+ public long copiedBytes;
+ // storing the FST node address where the position is the masked hash of
the node arcs
+ private PagedGrowableWriter fstHashAddress;
+ // storing the local copiedNodes address
+ private PagedGrowableWriter copiedNodeAddress;
+ // storing the global FST nodes address in the same position as
copiedNodeAddress
+ private PagedGrowableWriter fstNodeAddress;
private long count;
private long mask;
+ private final ByteBlockPool copiedNodes;
// 256K blocks, but note that the final block is sized only as needed so
it won't use the full
// block size when just a few elements were written to it
private static final int BLOCK_SIZE_BYTES = 1 << 18;
public PagedGrowableHash() {
- entries = new PagedGrowableWriter(16, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
+ fstHashAddress = new PagedGrowableWriter(16, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
+ fstNodeAddress = new PagedGrowableWriter(16, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
+ copiedNodeAddress = new PagedGrowableWriter(16, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
mask = 15;
+ copiedNodes = new ByteBlockPool(new ByteBlockPool.DirectAllocator());
}
public PagedGrowableHash(long lastNodeAddress, long size) {
- entries =
+ fstHashAddress =
new PagedGrowableWriter(
size, BLOCK_SIZE_BYTES,
PackedInts.bitsRequired(lastNodeAddress), PackedInts.COMPACT);
+ fstNodeAddress =
+ new PagedGrowableWriter(
+ size, BLOCK_SIZE_BYTES,
PackedInts.bitsRequired(lastNodeAddress), PackedInts.COMPACT);
+ copiedNodeAddress = new PagedGrowableWriter(size, BLOCK_SIZE_BYTES, 8,
PackedInts.COMPACT);
mask = size - 1;
assert (mask & size) == 0 : "size must be a power-of-2; got size=" +
size + " mask=" + mask;
+ copiedNodes = new ByteBlockPool(new ByteBlockPool.DirectAllocator());
+ }
+
+ public long getCopiedNodeAddress(long node) {
+ long pos = Long.hashCode(node) & mask;
+ while (true) {
+ long address = fstNodeAddress.get(pos);
+ assert address != 0;
+ if (address == node) {
+ return copiedNodeAddress.get(pos);
+ }
+ pos = (pos + 1) & mask;
+ }
+ }
+
+ public byte[] getBytes(long node, int length) {
+ long copiedNodeAddress = getCopiedNodeAddress(node);
+ byte[] buf = new byte[length];
+ copiedNodes.readBytes(copiedNodeAddress - length + 1, buf, 0, length);
+ return buf;
}
public long get(long index) {
- return entries.get(index);
+ return fstHashAddress.get(index);
}
- public void set(long index, long pointer) throws IOException {
- entries.set(index, pointer);
+ public void set(long index, long pointer, byte[] bytes) {
+ fstHashAddress.set(index, pointer);
count++;
+ setOffset(pointer, bytes);
+ }
+
+ private void setOffset(long pointer, byte[] bytes) {
+ // TODO: Write the bytes directly from BytesStore
+ copiedNodes.append(new BytesRef(bytes));
+ copiedBytes += bytes.length;
+ long pos = Long.hashCode(pointer) & mask;
+ // find an empty slot
+ while (fstNodeAddress.get(pos) != 0) {
+ pos = (pos + 1) & mask;
Review Comment:
Is it this PR (https://github.com/apache/lucene/pull/12716)? That's
interesting. I also got the linear probing from that PR. Lemme change it to
quadratic.
##########
lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java:
##########
@@ -328,7 +323,128 @@ private void rehash(long lastNodeAddress) throws
IOException {
}
mask = newMask;
- entries = newEntries;
+ fstHashAddress = newEntries;
+
+ PagedGrowableWriter newCopiedOffsets =
+ new PagedGrowableWriter(
+ newSize, BLOCK_SIZE_BYTES, PackedInts.bitsRequired(copiedBytes),
PackedInts.COMPACT);
+ PagedGrowableWriter newFSTOffsets =
+ new PagedGrowableWriter(
+ newSize,
+ BLOCK_SIZE_BYTES,
+ PackedInts.bitsRequired(lastNodeAddress),
+ PackedInts.COMPACT);
+ for (long idx = 0; idx < fstNodeAddress.size(); idx++) {
+ long address = fstNodeAddress.get(idx);
+ if (address != 0) {
+ long pos = Long.hashCode(address) & newMask;
+ while (true) {
+ if (newFSTOffsets.get(pos) == 0) {
+ newFSTOffsets.set(pos, address);
+ newCopiedOffsets.set(pos, copiedNodeAddress.get(idx));
+ break;
+ }
+
+ pos = (pos + 1) & newMask;
+ }
+ }
+ }
+
+ fstNodeAddress = newFSTOffsets;
+ copiedNodeAddress = newCopiedOffsets;
+ }
+
+ // hash code for a frozen node. this must precisely match the hash
computation of an unfrozen
+ // node!
+ private long hash(long node) throws IOException {
+ FST.BytesReader in = getBytesReader(node);
+
+ final int PRIME = 31;
+
+ long h = 0;
+ fstCompiler.fst.readFirstRealTargetArc(node, scratchArc, in);
+ while (true) {
+ h = PRIME * h + scratchArc.label();
+ h = PRIME * h + (int) (scratchArc.target() ^ (scratchArc.target() >>
32));
+ h = PRIME * h + scratchArc.output().hashCode();
+ h = PRIME * h + scratchArc.nextFinalOutput().hashCode();
+ if (scratchArc.isFinal()) {
+ h += 17;
+ }
+ if (scratchArc.isLast()) {
+ break;
+ }
+ fstCompiler.fst.readNextRealArc(scratchArc, in);
+ }
+
+ return h;
+ }
+
+ /**
+ * Compares an unfrozen node (UnCompiledNode) with a frozen node at byte
location address
+ * (long), returning the local copiedNodes start address if the two nodes
are matched, or -1
+ * otherwise
+ */
+ private int getMatchedNodeLength(FSTCompiler.UnCompiledNode<T> node, long
address)
Review Comment:
This is actually renamed from `nodesEqual` (it was removed), so there is no
duplication.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
