jpountz commented on a change in pull request #1464:
URL: https://github.com/apache/lucene-solr/pull/1464#discussion_r417953430



##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
##########
@@ -420,16 +421,13 @@ private long writeFieldNDims(IndexOutput out, String 
fieldName, MutablePointValu
     // Mark that we already finished:
     finished = true;
 
-    long countPerLeaf = pointCount = values.size();
-    long innerNodeCount = 1;
+    pointCount = values.size();
 
-    while (countPerLeaf > maxPointsInLeafNode) {
-      countPerLeaf = (countPerLeaf+1)/2;
-      innerNodeCount *= 2;
+    int numLeaves = Math.toIntExact(pointCount / maxPointsInLeafNode);
+    if (pointCount % maxPointsInLeafNode != 0) {
+      numLeaves++;

Review comment:
       nit: It's a bit sad that we try to protect against overflows  when 
dividing, but then don't check again for overflows when incrementing numLeaves. 
Can we compute the right value of `numLeaves` entirely _before_ it gets 
converted to an int, e.g.
   
   ```
   final int numLeaves = Math.toIntExact((pointCount + maxPointsInLeafNode - 1) 
/ maxPointsInLeafNode);
   ```

##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
##########
@@ -822,39 +804,27 @@ public long finish(IndexOutput out) throws IOException {
 
     // Write index:
     long indexFP = out.getFilePointer();
-    writeIndex(out, Math.toIntExact(countPerLeaf), leafBlockFPs, 
splitPackedValues);
+    writeIndex(out, maxPointsInLeafNode, leafBlockFPs, splitPackedValues);
     return indexFP;
   }
 
   /** Packs the two arrays, representing a balanced binary tree, into a 
compact byte[] structure. */
   private byte[] packIndex(long[] leafBlockFPs, byte[] splitPackedValues) 
throws IOException {
-
     int numLeaves = leafBlockFPs.length;
-
-    // Possibly rotate the leaf block FPs, if the index not fully balanced 
binary tree (only happens
-    // if it was created by OneDimensionBKDWriter).  In this case the leaf 
nodes may straddle the two bottom
+    // Possibly rotate the leaf block FPs, if the index not fully balanced 
binary tree.
+    // In this case the leaf nodes may straddle the two bottom
     // levels of the binary tree:
-    if (numIndexDims == 1 && numLeaves > 1) {
-      int levelCount = 2;
-      while (true) {
-        if (numLeaves >= levelCount && numLeaves <= 2*levelCount) {
-          int lastLevel = 2*(numLeaves - levelCount);
-          assert lastLevel >= 0;
-          if (lastLevel != 0) {
-            // Last level is partially filled, so we must rotate the leaf FPs 
to match.  We do this here, after loading
-            // at read-time, so that we can still delta code them on disk at 
write:
-            long[] newLeafBlockFPs = new long[numLeaves];
-            System.arraycopy(leafBlockFPs, lastLevel, newLeafBlockFPs, 0, 
leafBlockFPs.length - lastLevel);
-            System.arraycopy(leafBlockFPs, 0, newLeafBlockFPs, 
leafBlockFPs.length - lastLevel, lastLevel);
-            leafBlockFPs = newLeafBlockFPs;
-          }
-          break;
-        }
-
-        levelCount *= 2;
-      }
+    int lastFullLevel = 31 - Integer.numberOfLeadingZeros(numLeaves);
+    int leavesFullLevel = 1 << lastFullLevel;
+    int unbalancedLeafNodes = 2 * (numLeaves - leavesFullLevel);

Review comment:
       In `getNumLeftLeafNodes` above we do `unbalancedLeafNodes = numLeaves - 
leavesFullLevel`, which has a factor 2 difference with the above formula. I 
think I understand the reason but can me make it less confusing and avoid 
naming the same way different quantities?

##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
##########
@@ -665,55 +663,45 @@ assert valuesInOrderAndBounds(leafCount, 0, 
ArrayUtil.copyOfSubArray(leafValues,
     }
   }
 
-  // TODO: there must be a simpler way?
-  private void rotateToTree(int nodeID, int offset, int count, byte[] index, 
List<byte[]> leafBlockStartValues) {
-    //System.out.println("ROTATE: nodeID=" + nodeID + " offset=" + offset + " 
count=" + count + " bpd=" + bytesPerDim + " index.length=" + index.length);
-    if (count == 1) {
+  private void rotateToTree(int nodeID, int offset, int numNodes, byte[] 
index, List<byte[]> leafBlockStartValues) {
+    if (numNodes == 1) {
       // Leaf index node
-      //System.out.println("  leaf index node");
-      //System.out.println("  index[" + nodeID + "] = blockStartValues[" + 
offset + "]");
       System.arraycopy(leafBlockStartValues.get(offset), 0, index, 
nodeID*(1+bytesPerDim)+1, bytesPerDim);
-    } else if (count > 1) {
-      // Internal index node: binary partition of count
-      int countAtLevel = 1;
-      int totalCount = 0;
-      while (true) {
-        int countLeft = count - totalCount;
-        //System.out.println("    cycle countLeft=" + countLeft + " 
coutAtLevel=" + countAtLevel);
-        if (countLeft <= countAtLevel) {
-          // This is the last level, possibly partially filled:
-          int lastLeftCount = Math.min(countAtLevel/2, countLeft);
-          assert lastLeftCount >= 0;
-          int leftHalf = (totalCount-1)/2 + lastLeftCount;
-
-          int rootOffset = offset + leftHalf;
-          /*
-          System.out.println("  last left count " + lastLeftCount);
-          System.out.println("  leftHalf " + leftHalf + " rightHalf=" + 
(count-leftHalf-1));
-          System.out.println("  rootOffset=" + rootOffset);
-          */
-
-          System.arraycopy(leafBlockStartValues.get(rootOffset), 0, index, 
nodeID*(1+bytesPerDim)+1, bytesPerDim);
-          //System.out.println("  index[" + nodeID + "] = blockStartValues[" + 
rootOffset + "]");
-
-          // TODO: we could optimize/specialize, when we know it's simply 
fully balanced binary tree
-          // under here, to save this while loop on each recursion
-
-          // Recurse left
-          rotateToTree(2*nodeID, offset, leftHalf, index, 
leafBlockStartValues);
-
-          // Recurse right
-          rotateToTree(2*nodeID+1, rootOffset+1, count-leftHalf-1, index, 
leafBlockStartValues);
-          return;
-        }
-        totalCount += countAtLevel;
-        countAtLevel *= 2;
-      }
+    } else if (numNodes > 1) {
+      // Internal index node
+      // numNodes + 1 is the number of leaves
+      // -1 because there is one less inner node
+      int leftHalf = getNumLeftLeafNodes(numNodes + 1) - 1;
+      int rootOffset = offset + leftHalf;
+
+      System.arraycopy(leafBlockStartValues.get(rootOffset), 0, index, 
nodeID*(1+bytesPerDim)+1, bytesPerDim);
+
+      // Recurse left
+      rotateToTree(2*nodeID, offset, leftHalf, index, leafBlockStartValues);
+      // Recurse right
+      rotateToTree(2*nodeID+1, rootOffset+1, numNodes-leftHalf-1, index, 
leafBlockStartValues);
     } else {
-      assert count == 0;
+      assert numNodes == 0;
     }
   }
 
+  private int getNumLeftLeafNodes(int numLeaves) {
+    assert numLeaves > 1: "getNumLeftLeaveNodes() called with " + numLeaves;
+    // return the level that can be filled with this number of leaves
+    int lastFullLevel = 31 - Integer.numberOfLeadingZeros(numLeaves);
+    // how many leaf nodes are in the full level
+    int leavesFullLevel = 1 << lastFullLevel;
+    // half of the leaf nodes from the full level goes to the left
+    int numLeftLeafNodes = leavesFullLevel / 2;
+    // leaf nodes that do not fit in the full level
+    int unbalancedLeafNodes = numLeaves - leavesFullLevel;
+    // distribute unbalanced leaf nodes
+    numLeftLeafNodes += Math.min(unbalancedLeafNodes, numLeftLeafNodes);
+    // we should always place unbalanced leaf nodes on the left
+    assert numLeftLeafNodes >= numLeaves - numLeftLeafNodes;

Review comment:
       also assert that `numLeftLeafNodes < 2L * (numLeaves - 
numLeftLeafNodes)`?




----------------------------------------------------------------
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:
[email protected]



---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to