lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From hoss...@apache.org
Subject [05/50] lucene-solr:jira/SOLR-445: optimize BKD leaf block writing: use incoming sorted points to compute commonn prefix (saves one pass); remove an extra copy bytes
Date Mon, 21 Mar 2016 00:43:27 GMT
optimize BKD leaf block writing: use incoming sorted points to compute commonn prefix (saves
one pass); remove an extra copy bytes


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/41ef29a2
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/41ef29a2
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/41ef29a2

Branch: refs/heads/jira/SOLR-445
Commit: 41ef29a2c39241113cb999d9c4b2fbb3e70a40af
Parents: 576a405
Author: Mike McCandless <mikemccand@apache.org>
Authored: Sun Mar 13 05:31:11 2016 -0400
Committer: Mike McCandless <mikemccand@apache.org>
Committed: Sun Mar 13 05:31:11 2016 -0400

----------------------------------------------------------------------
 .../simpletext/SimpleTextPointsWriter.java      |  5 +-
 .../org/apache/lucene/util/bkd/BKDWriter.java   | 87 ++++++++++----------
 .../apache/lucene/util/bkd/HeapPointReader.java |  1 -
 .../apache/lucene/util/bkd/HeapPointWriter.java | 10 +++
 4 files changed, 57 insertions(+), 46 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/41ef29a2/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsWriter.java
----------------------------------------------------------------------
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsWriter.java
b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsWriter.java
index 13494f5..33af33e 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsWriter.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsWriter.java
@@ -158,11 +158,10 @@ class SimpleTextPointsWriter extends PointsWriter {
         }
 
         @Override
-        protected void writeLeafBlockPackedValue(IndexOutput out, int[] commonPrefixLengths,
byte[] bytes) throws IOException {
+        protected void writeLeafBlockPackedValue(IndexOutput out, int[] commonPrefixLengths,
byte[] bytes, int bytesOffset) throws IOException {
           // NOTE: we don't do prefix coding, so we ignore commonPrefixLengths
-          assert bytes.length == packedBytesLength;
           write(out, BLOCK_VALUE);
-          write(out, new BytesRef(bytes, 0, bytes.length).toString());
+          write(out, new BytesRef(bytes, bytesOffset, packedBytesLength).toString());
           newline(out);
         }          
       }) {

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/41ef29a2/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
index 6d3cf03..765b01c 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
@@ -106,9 +106,9 @@ public class BKDWriter implements Closeable {
   final double maxMBSortInHeap;
 
   final byte[] scratchDiff;
-  final byte[] scratchPackedValue;
   final byte[] scratch1;
   final byte[] scratch2;
+  final BytesRef scratchBytesRef = new BytesRef();
   final int[] commonPrefixLengths;
 
   protected final FixedBitSet docsSeen;
@@ -152,7 +152,7 @@ public class BKDWriter implements Closeable {
     packedBytesLength = numDims * bytesPerDim;
 
     scratchDiff = new byte[bytesPerDim];
-    scratchPackedValue = new byte[packedBytesLength];
+    scratchBytesRef.length = packedBytesLength;
     scratch1 = new byte[packedBytesLength];
     scratch2 = new byte[packedBytesLength];
     commonPrefixLengths = new int[numDims];
@@ -455,7 +455,7 @@ public class BKDWriter implements Closeable {
       }
       System.arraycopy(reader.state.scratchPackedValue, 0, maxPackedValue, 0, packedBytesLength);
 
-      assert numDims > 1 || valueInOrder(valueCount, lastPackedValue, reader.state.scratchPackedValue);
+      assert numDims > 1 || valueInOrder(valueCount, lastPackedValue, reader.state.scratchPackedValue,
0);
       valueCount++;
       if (pointCount > totalPointCount) {
         throw new IllegalStateException("totalPointCount=" + totalPointCount + " was passed
when we were created, but we just hit " + pointCount + " values");
@@ -502,7 +502,7 @@ public class BKDWriter implements Closeable {
 
         // Write the full values:
         for (int i=0;i<leafCount;i++) {
-          writeLeafBlockPackedValue(out, commonPrefixLengths, leafBlockPackedValues[i]);
+          writeLeafBlockPackedValue(out, commonPrefixLengths, leafBlockPackedValues[i], 0);
         }
 
         leafCount = 0;
@@ -920,10 +920,10 @@ public class BKDWriter implements Closeable {
     }
   }
 
-  protected void writeLeafBlockPackedValue(IndexOutput out, int[] commonPrefixLengths, byte[]
bytes) throws IOException {
+  protected void writeLeafBlockPackedValue(IndexOutput out, int[] commonPrefixLengths, byte[]
bytes, int offset) throws IOException {
     for(int dim=0;dim<numDims;dim++) {
       int prefix = commonPrefixLengths[dim];
-      out.writeBytes(bytes, dim*bytesPerDim+prefix, bytesPerDim-prefix);
+      out.writeBytes(bytes, offset+dim*bytesPerDim+prefix, bytesPerDim-prefix);
     }
   }
 
@@ -994,13 +994,13 @@ public class BKDWriter implements Closeable {
   }
 
   /** Called only in assert */
-  private boolean valueInBounds(byte[] packedValue, byte[] minPackedValue, byte[] maxPackedValue)
{
+  private boolean valueInBounds(BytesRef packedValue, byte[] minPackedValue, byte[] maxPackedValue)
{
     for(int dim=0;dim<numDims;dim++) {
       int offset = bytesPerDim*dim;
-      if (StringHelper.compare(bytesPerDim, packedValue, offset, minPackedValue, offset)
< 0) {
+      if (StringHelper.compare(bytesPerDim, packedValue.bytes, packedValue.offset + offset,
minPackedValue, offset) < 0) {
         return false;
       }
-      if (StringHelper.compare(bytesPerDim, packedValue, offset, maxPackedValue, offset)
> 0) {
+      if (StringHelper.compare(bytesPerDim, packedValue.bytes, packedValue.offset + offset,
maxPackedValue, offset) > 0) {
         return false;
       }
     }
@@ -1060,16 +1060,35 @@ public class BKDWriter implements Closeable {
     }
 
     if (nodeID >= leafNodeOffset) {
+
       // Leaf node: write block
+      for (int dim=0;dim<numDims;dim++) {
+        if (slices[dim].writer instanceof HeapPointWriter == false) {
+          // Adversarial cases can cause this, e.g. very lopsided data, all equal points,
such that we started
+          // offline, but then kept splitting only in one dimension, and so never had to
rewrite into heap writer
+          slices[dim] = switchToHeap(slices[dim]);
+        }
 
-      PathSlice source = slices[0];
+        PathSlice source = slices[dim];
+
+        HeapPointWriter heapSource = (HeapPointWriter) source.writer;
 
-      if (source.writer instanceof HeapPointWriter == false) {
-        // Adversarial cases can cause this, e.g. very lopsided data, all equal points, such
that we started
-        // offline, but then kept splitting only in one dimension, and so never had to rewrite
into heap writer
-        source = switchToHeap(source);
+        // Find common prefix by comparing first and last values, already sorted in this
dimension:
+        heapSource.readPackedValue(Math.toIntExact(source.start), scratch1);
+        heapSource.readPackedValue(Math.toIntExact(source.start + source.count - 1), scratch2);
+
+        int offset = dim * bytesPerDim;
+        commonPrefixLengths[dim] = bytesPerDim;
+        for(int j=0;j<bytesPerDim;j++) {
+          if (scratch1[offset+j] != scratch2[offset+j]) {
+            commonPrefixLengths[dim] = j;
+            break;
+          }
+        }
       }
 
+      PathSlice source = slices[0];
+
       // We ensured that maxPointsSortInHeap was >= maxPointsInLeafNode, so we better
be in heap at this point:
       HeapPointWriter heapSource = (HeapPointWriter) source.writer;
 
@@ -1083,37 +1102,21 @@ public class BKDWriter implements Closeable {
       assert count > 0: "nodeID=" + nodeID + " leafNodeOffset=" + leafNodeOffset;
       writeLeafBlockDocs(out, heapSource.docIDs, Math.toIntExact(source.start), count);
 
-      // First pass: find the per-dim common prefix for all values in this block:
-      Arrays.fill(commonPrefixLengths, bytesPerDim);
-      for (int i=0;i<count;i++) {
-        if (i == 0) {
-          heapSource.readPackedValue(Math.toIntExact(source.start + i), scratch1);
-        } else {
-          heapSource.readPackedValue(Math.toIntExact(source.start + i), scratchPackedValue);
-          for(int dim=0;dim<numDims;dim++) {
-            int offset = dim * bytesPerDim;
-            for(int j=0;j<commonPrefixLengths[dim];j++) {
-              if (scratch1[offset+j] != scratchPackedValue[offset+j]) {
-                commonPrefixLengths[dim] = j;
-                break;
-              }
-            }
-          }
-        }
-      }
+      // TODO: minor opto: we don't really have to write the actual common prefixes, because
BKDReader on recursing can regenerate it for us
+      // from the index, much like how terms dict does so from the FST:
 
+      // Write the common prefixes:
       writeCommonPrefixes(out, commonPrefixLengths, scratch1);
 
-      // Second pass: write the full values:
+      // Write the full values:
       byte[] lastPackedValue = new byte[bytesPerDim];
       for (int i=0;i<count;i++) {
-        // TODO: we could do bulk copying here, avoiding the intermediate copy:
-        heapSource.readPackedValue(Math.toIntExact(source.start + i), scratchPackedValue);
-        assert numDims != 1 || valueInOrder(i, lastPackedValue, scratchPackedValue);
+        heapSource.getPackedValueSlice(Math.toIntExact(source.start + i), scratchBytesRef);
+        assert numDims != 1 || valueInOrder(i, lastPackedValue, scratchBytesRef.bytes, scratchBytesRef.offset);
 
         // Make sure this value does in fact fall within this leaf cell:
-        assert valueInBounds(scratchPackedValue, minPackedValue, maxPackedValue);
-        writeLeafBlockPackedValue(out, commonPrefixLengths, scratchPackedValue);
+        assert valueInBounds(scratchBytesRef, minPackedValue, maxPackedValue);
+        writeLeafBlockPackedValue(out, commonPrefixLengths, scratchBytesRef.bytes, scratchBytesRef.offset);
       }
 
     } else {
@@ -1227,11 +1230,11 @@ public class BKDWriter implements Closeable {
   }
 
   // only called from assert
-  private boolean valueInOrder(long ord, byte[] lastPackedValue, byte[] packedValue) {
-    if (ord > 0 && StringHelper.compare(bytesPerDim, lastPackedValue, 0, packedValue,
0) > 0) {
-      throw new AssertionError("values out of order: last value=" + new BytesRef(lastPackedValue)
+ " current value=" + new BytesRef(packedValue) + " ord=" + ord);
+  private boolean valueInOrder(long ord, byte[] lastPackedValue, byte[] packedValue, int
packedValueOffset) {
+    if (ord > 0 && StringHelper.compare(bytesPerDim, lastPackedValue, 0, packedValue,
packedValueOffset) > 0) {
+      throw new AssertionError("values out of order: last value=" + new BytesRef(lastPackedValue)
+ " current value=" + new BytesRef(packedValue, packedValueOffset, packedBytesLength) + "
ord=" + ord);
     }
-    System.arraycopy(packedValue, 0, lastPackedValue, 0, bytesPerDim);
+    System.arraycopy(packedValue, packedValueOffset, lastPackedValue, 0, bytesPerDim);
     return true;
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/41ef29a2/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
index b178f08..63c7869 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
@@ -16,7 +16,6 @@
  */
 package org.apache.lucene.util.bkd;
 
-
 import java.util.List;
 
 import org.apache.lucene.util.PagedBytes;

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/41ef29a2/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
index 3b043d0..45bb591 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
@@ -20,6 +20,7 @@ import java.util.ArrayList;
 import java.util.List;
 
 import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
 
 final class HeapPointWriter implements PointWriter {
   int[] docIDs;
@@ -72,6 +73,15 @@ final class HeapPointWriter implements PointWriter {
     System.arraycopy(blocks.get(block), blockIndex * packedBytesLength, bytes, 0, packedBytesLength);
   }
 
+  /** Returns a reference, in <code>result</code>, to the byte[] slice holding
this value */
+  void getPackedValueSlice(int index, BytesRef result) {
+    int block = index / valuesPerBlock;
+    int blockIndex = index % valuesPerBlock;
+    result.bytes = blocks.get(block);
+    result.offset = blockIndex * packedBytesLength;
+    assert result.length == packedBytesLength;
+  }
+
   void writePackedValue(int index, byte[] bytes) {
     assert bytes.length == packedBytesLength;
     int block = index / valuesPerBlock;


Mime
View raw message