[GitHub] [lucene-solr] jpountz commented on a change in pull request #980: LUCENE-8920: Reduce the memory used by direct addressing of arcs

[GitBox <gi...@apache.org>]

jpountz commented on a change in pull request #980: LUCENE-8920: Reduce the memory used by direct addressing of arcs
URL: https://github.com/apache/lucene-solr/pull/980#discussion_r339956145
 
 

 ##########
 File path: lucene/core/src/java/org/apache/lucene/util/fst/FST.java
 ##########
 @@ -864,6 +1012,68 @@ private long readUnpackedNodeTarget(BytesReader in) throws IOException {
     return readNextRealArc(arc, in);
   }
 
+  /**
+   * 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());
+    long[] presenceBits = new long[numPresenceBytes + 7 >>> 3];
+    int longIndex = 0;
+    int byteIndex = 0;
+    for (int i = 0; i < numPresenceBytes; i++) {
+      presenceBits[longIndex] |= (long) (in.readByte() & 0xFF) << (i << 3);
+      if (++byteIndex == 8) {
+        byteIndex = 0;
+        longIndex++;
+      }
+    }
+    arc.bitTable = presenceBits;
+    assert checkPresenceBytesAreValid(arc);
+    return numPresenceBytes;
+  }
+
+  static boolean checkPresenceBytesAreValid(Arc arc) {
+    assert (arc.bitTable()[0] & 1L) != 0; // First bit must be set.
+    assert (arc.bitTable()[arc.bitTable().length - 1] & (1L << (arc.numArcs() - 1))) != 0; // Last bit must be set.
+    assert countBits(arc.bitTable()) <= arc.numArcs(); // Total bit set must be <= label range.
+    return true;
+  }
+
+  /**
+   * Counts all bits set in the provided longs.
+   */
+  static int countBits(long[] bits) {
+    int bitCount = 0;
+    for (long l : bits) {
+      bitCount += Long.bitCount(l);
+    }
+    return bitCount;
+  }
+
+  /**
+   * Returns whether the bit at given index is set.
+   */
+  static boolean isBitSet(long[] bits, int bitIndex) {
+    return (bits[bitIndex >> 6] & (1L << (bitIndex & 63))) != 0;
+  }
+
+  /**
+   * Counts the bits set up to the given bit index, exclusive.
+   */
+  static int countBitsUpTo(long[] bits, int bitIndex) {
+    int bitCount = 0;
+    int lastLong = bitIndex >>> 6; // index / 64
+    for (int i = 0; i < lastLong; i++) {
+      bitCount += Long.bitCount(bits[i]);
+    }
+    int indexInLastLong = bitIndex & 63; // index % 64
+    if (indexInLastLong != 0) {
+      long mask = 0xFFFFFFFFFFFFFFFFL >>> (Long.SIZE - indexInLastLong);
+      bitCount += Long.bitCount(bits[lastLong] & mask);
+    }
 
 Review comment:
   we should be able to remove the conditional? e.g. something like this:
   
   ```
   long mask = (1L << bitIndex) - 1L; // shifts are mode 64
   bitCount += Long.bitCount(bits[lastLong] & mask);
   ```

----------------------------------------------------------------
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.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org