gf2121 commented on PR #15970:
URL: https://github.com/apache/lucene/pull/15970#issuecomment-4294651061
Thanks for opening this PR and looking into this! I apologize for not having
optimized the TrieBuilder for better memory efficiency earlier. As the TODO in
the JavaDoc points out, we definitely need to make it a much more
memory-efficient structure.
Overall, I am fine with the idea of introducing a SaveFrame to shave off
those 16 bytes (an 8-byte object reference + an 8-byte long fp) from each Node.
However, I am a bit skeptical about whether this will resolve the OOM issues
you are seeing with long fields like URLs. Even with this reduction, the sheer
volume of Node object headers and structural references will still consume a
massive amount of heap memory in those worst-case scenarios.
A couple of relatively straightforward optimization ideas come to mind that
might yield more substantial memory savings:
1. Path Compression (Radix Tree approach): Instead of storing a single int
label for every single character, we could store a byte[] labels per Node. This
would compress long, unbranched chains of single-child nodes into a single
edge, which would drastically reduce the total number of allocated Node
objects—especially for long, repetitive strings like URLs or UUIDs.
2. Similar to how the FSTCompiler worked, we could potentially keep the
structures serialized. When merging, we could append the already-serialized
data term-by-term into a brand new TrieBuilder (or compiler). This would trade
off some CPU overhead during merges for a significant reduction in peak heap
memory usage, as we wouldn't need to keep the entire object graph resident in
memory at once.
FWIW the original code with FST:
```
final ByteSequenceOutputs outputs = ByteSequenceOutputs.getSingleton();
final FSTCompiler<BytesRef> fstCompiler =
new FSTCompiler.Builder<>(FST.INPUT_TYPE.BYTE1, outputs)
.suffixRAMLimitMB(0d)
.bytesPageBits(pageBits)
.build();
final byte[] bytes = scratchBytes.toArrayCopy();
assert bytes.length > 0;
fstCompiler.add(Util.toIntsRef(prefix, scratchIntsRef), new
BytesRef(bytes, 0, bytes.length));
scratchBytes.reset();
for (PendingBlock block : blocks) {
if (block.subIndices != null) {
for (FST<BytesRef> subIndex : block.subIndices) {
append(fstCompiler, subIndex, scratchIntsRef);
}
block.subIndices = null;
}
}
index = fstCompiler.compile();
```
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
