You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2019/10/30 15:01:19 UTC
[lucene-solr] 01/03: Elias fano.
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch simd
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
commit e24b6e677c970b5015909bd5cef84330e77f7e1e
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Mon Oct 28 16:47:16 2019 +0100
Elias fano.
---
.../lucene/codecs/lucene84/EliasFanoSequence.java | 113 +++++++++++
.../lucene/codecs/lucene84/EliasFanoUtil.java | 85 +++++++++
.../org/apache/lucene/codecs/lucene84/ForUtil.java | 51 +----
.../codecs/lucene84/Lucene84PostingsReader.java | 206 +++++++++++++--------
.../codecs/lucene84/Lucene84PostingsWriter.java | 27 +--
.../apache/lucene/codecs/lucene84/PForUtil.java | 126 +++++++++++++
.../apache/lucene/codecs/lucene84/gen_ForUtil.py | 47 +----
.../{TestForUtil.java => TestEliasFanoUtil.java} | 39 ++--
.../apache/lucene/codecs/lucene84/TestForUtil.java | 31 ++--
.../{TestForUtil.java => TestPForUtil.java} | 37 ++--
10 files changed, 529 insertions(+), 233 deletions(-)
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/EliasFanoSequence.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/EliasFanoSequence.java
new file mode 100644
index 0000000..ec1de09
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/EliasFanoSequence.java
@@ -0,0 +1,113 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene84;
+
+final class EliasFanoSequence {
+
+ final long[] upperBits = new long[ForUtil.BLOCK_SIZE >>> 5];
+ final long[] lowerBits = new long[ForUtil.BLOCK_SIZE];
+ int lowBitsPerValue;
+ int upperIndex;
+ int i;
+
+ // Like FixedBitSet#nextSetBit
+ private int nextUpperSetBit(int index) {
+ int i = index >>> 6;
+ long word = upperBits[i] >>> index;
+ if (word != 0) {
+ return index + Long.numberOfTrailingZeros(word);
+ } else {
+ while (++i < upperBits.length) {
+ word = upperBits[i];
+ if (word != 0) {
+ return (i << 6) + Long.numberOfTrailingZeros(word);
+ }
+ }
+ }
+ return ForUtil.BLOCK_SIZE << 1;
+ }
+
+ long next() {
+ ++i;
+ upperIndex = nextUpperSetBit(upperIndex+1);
+ long highBits = upperIndex - i;
+ long lowBits = lowerBits[i];
+ return (highBits << lowBitsPerValue) | lowBits;
+ }
+
+ /*private void advanceToHighTarget(long highTarget) {
+ int upperLongIndex = (upperIndex + 1) >>> 6;
+ long word = upperBits[upperLongIndex] >>> upperIndex;
+
+ if (word != 0) {
+ int popCount = Long.bitCount(word);
+ long maxHighBits = (1 << (upperLongIndex + 1)) - 1 - i - popCount;
+ if (maxHighBits >= highTarget) {
+ // The looked up high target might be within the current long, stop here
+ // TODO: rank selection
+ ++i;
+ upperIndex += 1 + Long.numberOfTrailingZeros(word);
+ return;
+ }
+ i += popCount;
+ }
+
+ while (++upperLongIndex < upperBits.length) {
+ word = upperBits[upperLongIndex];
+ if (word != 0) {
+ int popCount = Long.bitCount(word);
+ long maxHighBits = (1 << (upperLongIndex + 1)) - 1 - i - popCount;
+ if (maxHighBits >= highTarget) {
+ // TODO: rank selection
+ ++i;
+ upperIndex = (upperLongIndex << 6) + Long.numberOfTrailingZeros(word);
+ }
+ i += popCount;
+ }
+ }
+ }
+
+ long advance(long target) {
+ final long highTarget = target >>> lowBitsPerValue;
+ advanceToHighTarget(highTarget);
+ long highBits = upperIndex - i;
+ while (highBits < highTarget) {
+ ++i;
+ upperIndex = nextUpperSetBit(upperIndex+1);
+ highBits = upperIndex - i;
+ }
+ long lowBits = lowerBits[i];
+ return (highBits << lowBitsPerValue) | lowBits;
+ }*/
+
+ long maybeAdvance(long target) {
+ final long highTarget = target >>> lowBitsPerValue;
+ final int minUpperIndex = (int) (highTarget + i);
+ final int nextUpperIndex = upperIndex + 1;
+ final int nextWordIndex = nextUpperIndex >>> 6;
+ final int targetWordIndex = Math.min(minUpperIndex >>> 6, 4);
+ if (targetWordIndex > nextWordIndex) {
+ i += Long.bitCount(upperBits[nextUpperIndex] >>> nextUpperIndex);
+ for (int j = nextWordIndex + 1; j < targetWordIndex; ++j) {
+ i += Long.bitCount(upperBits[j]);
+ }
+ upperIndex = (targetWordIndex << 6) - 1;
+ }
+ return next();
+ }
+
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/EliasFanoUtil.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/EliasFanoUtil.java
new file mode 100644
index 0000000..51bf841
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/EliasFanoUtil.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene84;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.packed.PackedInts;
+
+public class EliasFanoUtil {
+
+ private final ForUtil forUtil;
+
+ EliasFanoUtil(ForUtil forUtil) {
+ this.forUtil = forUtil;
+ }
+
+ /**
+ * Encode 128 8-bits integers from {@code data} into {@code out}.
+ */
+ void encode(long[] longs, DataOutput out) throws IOException {
+ final int highBitsPerValue = 7;
+ final int lowBitsPerValue = Math.max(PackedInts.bitsRequired(longs[ForUtil.BLOCK_SIZE - 1]) - highBitsPerValue, 0);
+ out.writeByte((byte) lowBitsPerValue);
+ encodeHighBits(longs, lowBitsPerValue, out);
+ if (lowBitsPerValue > 0) {
+ for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ longs[i] &= (1L << lowBitsPerValue) - 1;
+ }
+ forUtil.encode(longs, lowBitsPerValue, out);
+ }
+ }
+
+ void decode(DataInput in, EliasFanoSequence efSequence) throws IOException {
+ efSequence.upperIndex = -1;
+ efSequence.i = -1;
+ final int lowBitsPerValue = in.readByte();
+ efSequence.lowBitsPerValue = lowBitsPerValue;
+ for (int i = 0; i < ForUtil.BLOCK_SIZE >>> 5; ++i) {
+ efSequence.upperBits[i] = in.readLong();
+ }
+ if (lowBitsPerValue == 0) {
+ Arrays.fill(efSequence.lowerBits, 0L);
+ } else {
+ forUtil.decode(lowBitsPerValue, in, efSequence.lowerBits);
+ }
+ }
+
+ void skip(DataInput in) throws IOException {
+ final int lowBitsPerValue = in.readByte();
+ in.skipBytes((ForUtil.BLOCK_SIZE >>> 2) + forUtil.numBytes(lowBitsPerValue));
+ }
+
+ private void encodeHighBits(long[] longs, int lowBitsPerValue, DataOutput out) throws IOException {
+ final long[] encoded = new long[ForUtil.BLOCK_SIZE >>> 5];
+ long previousHighBits = 0;
+ int index = -1;
+ for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ long highBits = longs[i] >>> lowBitsPerValue;
+ index += 1 + (highBits - previousHighBits);
+ encoded[index >>> 6] |= 1L << index;
+ previousHighBits = highBits;
+ }
+ for (long l : encoded) {
+ out.writeLong(l);
+ }
+ }
+
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/ForUtil.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/ForUtil.java
index 2e78ddd..a35c64b 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/ForUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/ForUtil.java
@@ -25,7 +25,6 @@ import java.util.function.IntToLongFunction;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
-import org.apache.lucene.util.packed.PackedInts;
// Inspired from https://fulmicoton.com/posts/bitpacking/
// Encodes multiple integers in a long to get SIMD-like speedups.
@@ -37,23 +36,6 @@ final class ForUtil {
static final int BLOCK_SIZE = 128;
private static final int BLOCK_SIZE_LOG2 = 7;
- private static int numBitsPerValue(long[] longs) {
- long or = 0;
- for (long l : longs) {
- or |= l;
- }
- return PackedInts.bitsRequired(or);
- }
-
- private static boolean allEqual(long[] longs) {
- for (long l : longs) {
- if (l != longs[0]) {
- return false;
- }
- }
- return true;
- }
-
private static long expandMask32(long mask32) {
return mask32 | (mask32 << 32);
}
@@ -138,16 +120,7 @@ final class ForUtil {
/**
* Encode 128 8-bits integers from {@code data} into {@code out}.
*/
- void encode(long[] longs, DataOutput out) throws IOException {
- if (allEqual(longs)) {
- out.writeByte((byte) 0);
- out.writeVLong(longs[0]);
- return;
- }
-
- final int bitsPerValue = numBitsPerValue(longs);
- out.writeByte((byte) bitsPerValue);
-
+ void encode(long[] longs, int bitsPerValue, DataOutput out) throws IOException {
final int nextPrimitive;
final int numLongs;
final IntToLongFunction maskFunction;
@@ -205,16 +178,10 @@ final class ForUtil {
}
/**
- * Skip 128 integers.
+ * Number of bytes required to encode 128 integers of {@code bitsPerValue}.
*/
- void skip(DataInput in) throws IOException {
- final int bitsPerValue = in.readByte();
- if (bitsPerValue == 0) {
- in.readVLong();
- } else {
- final int numBytes = bitsPerValue << (BLOCK_SIZE_LOG2 - 3);
- in.skipBytes(numBytes);
- }
+ int numBytes(int bitsPerValue) throws IOException {
+ return bitsPerValue << (BLOCK_SIZE_LOG2 - 3);
}
private static void decodeSlow(int bitsPerValue, DataInput in, ByteOrder byteOrder, long[] tmp, long[] longs) throws IOException {
@@ -250,10 +217,6 @@ final class ForUtil {
expand32(longs);
}
- private static void decode0(DataInput in, long[] longs) throws IOException {
- Arrays.fill(longs, 0, BLOCK_SIZE, in.readVLong());
- }
-
/**
* The pattern that this shiftLongs method applies is recognized by the C2
* compiler, which generates SIMD instructions for it in order to shift
@@ -314,12 +277,8 @@ final class ForUtil {
/**
* Decode 128 integers into {@code ints}.
*/
- void decode(DataInput in, long[] longs) throws IOException {
- final int bitsPerValue = in.readByte();
+ void decode(int bitsPerValue, DataInput in, long[] longs) throws IOException {
switch (bitsPerValue) {
- case 0:
- decode0(in, longs);
- break;
case 1:
decode1(in, byteOrder, tmp, longs);
break;
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsReader.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsReader.java
index e722bbd..b43a3e5 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsReader.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsReader.java
@@ -28,6 +28,7 @@ import static org.apache.lucene.codecs.lucene84.Lucene84PostingsFormat.VERSION_S
import java.io.IOException;
import java.nio.ByteOrder;
+import java.util.Arrays;
import org.apache.lucene.codecs.BlockTermState;
import org.apache.lucene.codecs.CodecUtil;
@@ -128,24 +129,42 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
}
+ static void setSingletonDocID(int singletonDocID, EliasFanoSequence docBuffer) {
+ docBuffer.lowBitsPerValue = 31;
+ docBuffer.i = -1;
+ docBuffer.upperIndex = -1;
+ Arrays.fill(docBuffer.upperBits, ~0L);
+ docBuffer.lowerBits[0] = 1L + singletonDocID;
+ }
+
/**
* Read values that have been written using variable-length encoding instead of bit-packing.
*/
- static void readVIntBlock(IndexInput docIn, long[] docBuffer,
+ static void readVIntBlock(IndexInput docIn, EliasFanoSequence docBuffer,
long[] freqBuffer, int num, boolean indexHasFreq) throws IOException {
+ docBuffer.lowBitsPerValue = 31;
+ docBuffer.i = -1;
+ docBuffer.upperIndex = -1;
+ Arrays.fill(docBuffer.upperBits, ~0L);
if (indexHasFreq) {
for(int i=0;i<num;i++) {
final int code = docIn.readVInt();
- docBuffer[i] = code >>> 1;
+ docBuffer.lowerBits[i] = code >>> 1;
if ((code & 1) != 0) {
freqBuffer[i] = 1;
} else {
freqBuffer[i] = docIn.readVInt();
}
+ if (i > 0) {
+ docBuffer.lowerBits[i] += docBuffer.lowerBits[i-1];
+ }
}
} else {
for(int i=0;i<num;i++) {
- docBuffer[i] = docIn.readVInt();
+ docBuffer.lowerBits[i] = docIn.readVInt();
+ if (i > 0) {
+ docBuffer.lowerBits[i] += docBuffer.lowerBits[i-1];
+ }
}
}
}
@@ -253,9 +272,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
final class BlockDocsEnum extends PostingsEnum {
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final PForUtil pforUtil;
+ final EliasFanoUtil efUtil;
+ final EliasFanoSequence docIDSequence = new EliasFanoSequence();
- private final long[] docDeltaBuffer = new long[BLOCK_SIZE];
private final long[] freqBuffer = new long[BLOCK_SIZE];
private int docBufferUpto;
@@ -302,6 +322,9 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
indexHasPos = fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS) >= 0;
indexHasOffsets = fieldInfo.getIndexOptions().compareTo(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS) >= 0;
indexHasPayloads = fieldInfo.hasPayloads();
+ final ForUtil forUtil = new ForUtil(byteOrder);
+ pforUtil = new PForUtil(forUtil);
+ efUtil = new EliasFanoUtil(forUtil);
}
public boolean canReuse(IndexInput docIn, FieldInfo fieldInfo) {
@@ -333,7 +356,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
freqBuffer[i] = 1;
}
}
- accum = 0;
+ accum = -1;
docUpto = 0;
nextSkipDoc = BLOCK_SIZE - 1; // we won't skip if target is found in first block
docBufferUpto = BLOCK_SIZE;
@@ -344,7 +367,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
@Override
public int freq() throws IOException {
if (isFreqsRead == false) {
- forUtil.decode(docIn, freqBuffer); // read freqBuffer for this block
+ pforUtil.decode(docIn, freqBuffer); // read freqBuffer for this block
isFreqsRead = true;
}
return (int) freqBuffer[docBufferUpto-1];
@@ -378,7 +401,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
private void refillDocs() throws IOException {
// Check if we skipped reading the previous block of freqBuffer, and if yes, position docIn after it
if (isFreqsRead == false) {
- forUtil.skip(docIn);
+ pforUtil.skip(docIn);
isFreqsRead = true;
}
@@ -386,21 +409,21 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
assert left > 0;
if (left >= BLOCK_SIZE) {
- forUtil.decode(docIn, docDeltaBuffer);
+ efUtil.decode(docIn, docIDSequence);
if (indexHasFreq) {
if (needsFreq) {
isFreqsRead = false;
} else {
- forUtil.skip(docIn); // skip over freqBuffer if we don't need them at all
+ pforUtil.skip(docIn); // skip over freqBuffer if we don't need them at all
}
}
} else if (docFreq == 1) {
- docDeltaBuffer[0] = singletonDocID;
+ setSingletonDocID(singletonDocID, docIDSequence);
freqBuffer[0] = totalTermFreq;
} else {
// Read vInts:
- readVIntBlock(docIn, docDeltaBuffer, freqBuffer, left, indexHasFreq);
+ readVIntBlock(docIn, docIDSequence, freqBuffer, left, indexHasFreq);
}
docBufferUpto = 0;
}
@@ -411,13 +434,13 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
return doc = NO_MORE_DOCS;
}
if (docBufferUpto == BLOCK_SIZE) {
+ accum = doc;
refillDocs(); // we don't need to load freqBuffer for now (will be loaded later if necessary)
}
- accum += docDeltaBuffer[docBufferUpto];
docUpto++;
- doc = (int) accum;
+ doc = (int) (accum + docIDSequence.next());
docBufferUpto++;
return doc;
}
@@ -456,7 +479,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
// Force to read next block
docBufferUpto = BLOCK_SIZE;
- accum = skipper.getDoc(); // actually, this is just lastSkipEntry
+ doc = skipper.getDoc(); // actually, this is just lastSkipEntry
docIn.seek(skipper.getDocPointer()); // now point to the block we want to search
// even if freqBuffer were not read from the previous block, we will mark them as read,
// as we don't need to skip the previous block freqBuffer in refillDocs,
@@ -471,16 +494,18 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
return doc = NO_MORE_DOCS;
}
if (docBufferUpto == BLOCK_SIZE) {
+ accum = doc;
refillDocs();
}
// Now scan... this is an inlined/pared down version
// of nextDoc():
+
while (true) {
- accum += docDeltaBuffer[docBufferUpto];
+ doc = (int) (accum + docIDSequence.next());
docUpto++;
- if (accum >= target) {
+ if (doc >= target) {
break;
}
docBufferUpto++;
@@ -490,7 +515,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
docBufferUpto++;
- return doc = (int) accum;
+ return doc;
}
@Override
@@ -502,9 +527,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
// Also handles payloads + offsets
final class EverythingEnum extends PostingsEnum {
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final PForUtil pforUtil;
+ final EliasFanoUtil efUtil;
+ final EliasFanoSequence docIDSequence = new EliasFanoSequence();
- private final long[] docDeltaBuffer = new long[BLOCK_SIZE];
private final long[] freqBuffer = new long[BLOCK_SIZE];
private final long[] posDeltaBuffer = new long[BLOCK_SIZE];
@@ -540,7 +566,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
private long totalTermFreq; // number of positions in this posting list
private int docUpto; // how many docs we've read
private int doc; // doc we last read
- private int accum; // accumulator for doc deltas
+ private long accum; // accumulator for doc deltas
private int freq; // freq we last read
private int position; // current position
@@ -613,6 +639,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
payloadBytes = null;
payload = null;
}
+
+ final ForUtil forUtil = new ForUtil(byteOrder);
+ pforUtil = new PForUtil(forUtil);
+ efUtil = new EliasFanoUtil(forUtil);
}
public boolean canReuse(IndexInput docIn, FieldInfo fieldInfo) {
@@ -651,7 +681,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
this.needsPayloads = PostingsEnum.featureRequested(flags, PostingsEnum.PAYLOADS);
doc = -1;
- accum = 0;
+ accum = -1;
docUpto = 0;
if (docFreq > BLOCK_SIZE) {
nextSkipDoc = BLOCK_SIZE - 1; // we won't skip if target is found in first block
@@ -678,13 +708,13 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
assert left > 0;
if (left >= BLOCK_SIZE) {
- forUtil.decode(docIn, docDeltaBuffer);
- forUtil.decode(docIn, freqBuffer);
+ efUtil.decode(docIn, docIDSequence);
+ pforUtil.decode(docIn, freqBuffer);
} else if (docFreq == 1) {
- docDeltaBuffer[0] = singletonDocID;
+ setSingletonDocID(singletonDocID, docIDSequence);
freqBuffer[0] = totalTermFreq;
} else {
- readVIntBlock(docIn, docDeltaBuffer, freqBuffer, left, true);
+ readVIntBlock(docIn, docIDSequence, freqBuffer, left, true);
}
docBufferUpto = 0;
}
@@ -725,11 +755,11 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
payloadByteUpto = 0;
} else {
- forUtil.decode(posIn, posDeltaBuffer);
+ pforUtil.decode(posIn, posDeltaBuffer);
if (indexHasPayloads) {
if (needsPayloads) {
- forUtil.decode(payIn, payloadLengthBuffer);
+ pforUtil.decode(payIn, payloadLengthBuffer);
int numBytes = payIn.readVInt();
if (numBytes > payloadBytes.length) {
@@ -738,7 +768,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
payIn.readBytes(payloadBytes, 0, numBytes);
} else {
// this works, because when writing a vint block we always force the first length to be written
- forUtil.skip(payIn); // skip over lengths
+ pforUtil.skip(payIn); // skip over lengths
int numBytes = payIn.readVInt(); // read length of payloadBytes
payIn.seek(payIn.getFilePointer() + numBytes); // skip over payloadBytes
}
@@ -747,12 +777,12 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
if (indexHasOffsets) {
if (needsOffsets) {
- forUtil.decode(payIn, offsetStartDeltaBuffer);
- forUtil.decode(payIn, offsetLengthBuffer);
+ pforUtil.decode(payIn, offsetStartDeltaBuffer);
+ pforUtil.decode(payIn, offsetLengthBuffer);
} else {
// this works, because when writing a vint block we always force the first length to be written
- forUtil.skip(payIn); // skip over starts
- forUtil.skip(payIn); // skip over lengths
+ pforUtil.skip(payIn); // skip over starts
+ pforUtil.skip(payIn); // skip over lengths
}
}
}
@@ -764,16 +794,16 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
return doc = NO_MORE_DOCS;
}
if (docBufferUpto == BLOCK_SIZE) {
+ accum = doc;
refillDocs();
}
- accum += docDeltaBuffer[docBufferUpto];
freq = (int) freqBuffer[docBufferUpto];
posPendingCount += freq;
docBufferUpto++;
docUpto++;
- doc = accum;
+ doc = (int) (accum + docIDSequence.next());
position = 0;
lastStartOffset = 0;
return doc;
@@ -810,7 +840,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
// Force to read next block
docBufferUpto = BLOCK_SIZE;
- accum = skipper.getDoc();
+ doc = skipper.getDoc();
docIn.seek(skipper.getDocPointer());
posPendingFP = skipper.getPosPointer();
payPendingFP = skipper.getPayPointer();
@@ -824,18 +854,19 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
return doc = NO_MORE_DOCS;
}
if (docBufferUpto == BLOCK_SIZE) {
+ accum = doc;
refillDocs();
}
// Now scan:
while (true) {
- accum += docDeltaBuffer[docBufferUpto];
+ doc = (int) (accum + docIDSequence.next());
freq = (int) freqBuffer[docBufferUpto];
posPendingCount += freq;
docBufferUpto++;
docUpto++;
- if (accum >= target) {
+ if (doc >= target) {
break;
}
if (docUpto == docFreq) {
@@ -845,7 +876,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
position = 0;
lastStartOffset = 0;
- return doc = accum;
+ return doc;
}
// TODO: in theory we could avoid loading frq block
@@ -872,11 +903,11 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
toSkip -= leftInBlock;
while(toSkip >= BLOCK_SIZE) {
assert posIn.getFilePointer() != lastPosBlockFP;
- forUtil.skip(posIn);
+ pforUtil.skip(posIn);
if (indexHasPayloads) {
// Skip payloadLength block:
- forUtil.skip(payIn);
+ pforUtil.skip(payIn);
// Skip payloadBytes block:
int numBytes = payIn.readVInt();
@@ -884,8 +915,8 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
if (indexHasOffsets) {
- forUtil.skip(payIn);
- forUtil.skip(payIn);
+ pforUtil.skip(payIn);
+ pforUtil.skip(payIn);
}
toSkip -= BLOCK_SIZE;
}
@@ -978,9 +1009,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
final class BlockImpactsPostingsEnum extends ImpactsEnum {
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final PForUtil pforUtil;
+ final EliasFanoUtil efUtil;
+ final EliasFanoSequence docIDSequence = new EliasFanoSequence();
- private final long[] docDeltaBuffer = new long[BLOCK_SIZE];
private final long[] freqBuffer = new long[BLOCK_SIZE];
private final long[] posDeltaBuffer = new long[BLOCK_SIZE];
@@ -1055,7 +1087,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
doc = -1;
- accum = 0;
+ accum = -1;
docUpto = 0;
docBufferUpto = BLOCK_SIZE;
@@ -1065,6 +1097,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
indexHasOffsets,
indexHasPayloads);
skipper.init(docTermStartFP+termState.skipOffset, docTermStartFP, posTermStartFP, payTermStartFP, docFreq);
+
+ final ForUtil forUtil = new ForUtil(byteOrder);
+ pforUtil = new PForUtil(forUtil);
+ efUtil = new EliasFanoUtil(forUtil);
}
@Override
@@ -1082,10 +1118,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
assert left > 0;
if (left >= BLOCK_SIZE) {
- forUtil.decode(docIn, docDeltaBuffer);
- forUtil.decode(docIn, freqBuffer);
+ efUtil.decode(docIn, docIDSequence);
+ pforUtil.decode(docIn, freqBuffer);
} else {
- readVIntBlock(docIn, docDeltaBuffer, freqBuffer, left, true);
+ readVIntBlock(docIn, docIDSequence, freqBuffer, left, true);
}
docBufferUpto = 0;
}
@@ -1115,7 +1151,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
}
} else {
- forUtil.decode(posIn, posDeltaBuffer);
+ pforUtil.decode(posIn, posDeltaBuffer);
}
}
@@ -1158,6 +1194,9 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
@Override
public int advance(int target) throws IOException {
+ if (docBufferUpto == BLOCK_SIZE) {
+ accum = Math.max(accum, doc);
+ }
if (target > nextSkipDoc) {
advanceShallow(target);
}
@@ -1173,25 +1212,26 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
// Now scan:
- long freq;
+ long doc, freq;
while (true) {
- accum += docDeltaBuffer[docBufferUpto];
+ doc = accum + docIDSequence.next();
freq = freqBuffer[docBufferUpto];
posPendingCount += freq;
docBufferUpto++;
docUpto++;
- if (accum >= target) {
+ if (doc >= target) {
break;
}
if (docUpto == docFreq) {
- return doc = NO_MORE_DOCS;
+ return this.doc = NO_MORE_DOCS;
}
}
+ this.doc = (int) doc;
this.freq = (int) freq;
position = 0;
- return doc = (int) accum;
+ return this.doc;
}
// TODO: in theory we could avoid loading frq block
@@ -1209,7 +1249,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
toSkip -= leftInBlock;
while(toSkip >= BLOCK_SIZE) {
assert posIn.getFilePointer() != lastPosBlockFP;
- forUtil.skip(posIn);
+ pforUtil.skip(posIn);
toSkip -= BLOCK_SIZE;
}
refillPositions();
@@ -1270,9 +1310,10 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
final class BlockImpactsEverythingEnum extends ImpactsEnum {
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final PForUtil pforUtil;
+ final EliasFanoUtil efUtil;
+ final EliasFanoSequence docIDSequence = new EliasFanoSequence();
- private final long[] docDeltaBuffer = new long[BLOCK_SIZE];
private final long[] freqBuffer = new long[BLOCK_SIZE];
private final long[] posDeltaBuffer = new long[BLOCK_SIZE];
@@ -1410,7 +1451,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
doc = -1;
- accum = 0;
+ accum = -1;
docUpto = 0;
posDocUpTo = 0;
isFreqsRead = true;
@@ -1428,12 +1469,16 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
freqBuffer[i] = 1;
}
}
+
+ final ForUtil forUtil = new ForUtil(byteOrder);
+ pforUtil = new PForUtil(forUtil);
+ efUtil = new EliasFanoUtil(forUtil);
}
@Override
public int freq() throws IOException {
if (indexHasFreq && (isFreqsRead == false)) {
- forUtil.decode(docIn, freqBuffer); // read freqBuffer for this block
+ pforUtil.decode(docIn, freqBuffer); // read freqBuffer for this block
isFreqsRead = true;
}
return (int) freqBuffer[docBufferUpto-1];
@@ -1449,9 +1494,9 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
if (isFreqsRead == false) { // previous freq block was not read
// check if we need to load the previous freq block to catch up on positions or we can skip it
if (indexHasPos && needsPositions && (posDocUpTo < docUpto)) {
- forUtil.decode(docIn, freqBuffer); // load the previous freq block
+ pforUtil.decode(docIn, freqBuffer); // load the previous freq block
} else {
- forUtil.skip(docIn); // skip it
+ pforUtil.skip(docIn); // skip it
}
isFreqsRead = true;
}
@@ -1467,12 +1512,12 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
assert left > 0;
if (left >= BLOCK_SIZE) {
- forUtil.decode(docIn, docDeltaBuffer);
+ efUtil.decode(docIn, docIDSequence);
if (indexHasFreq) {
isFreqsRead = false; // freq block will be loaded lazily when necessary, we don't load it here
}
} else {
- readVIntBlock(docIn, docDeltaBuffer, freqBuffer, left, indexHasFreq);
+ readVIntBlock(docIn, docIDSequence, freqBuffer, left, indexHasFreq);
}
docBufferUpto = 0;
}
@@ -1513,11 +1558,11 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
payloadByteUpto = 0;
} else {
- forUtil.decode(posIn, posDeltaBuffer);
+ pforUtil.decode(posIn, posDeltaBuffer);
if (indexHasPayloads && payIn != null) {
if (needsPayloads) {
- forUtil.decode(payIn, payloadLengthBuffer);
+ pforUtil.decode(payIn, payloadLengthBuffer);
int numBytes = payIn.readVInt();
if (numBytes > payloadBytes.length) {
@@ -1526,7 +1571,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
payIn.readBytes(payloadBytes, 0, numBytes);
} else {
// this works, because when writing a vint block we always force the first length to be written
- forUtil.skip(payIn); // skip over lengths
+ pforUtil.skip(payIn); // skip over lengths
int numBytes = payIn.readVInt(); // read length of payloadBytes
payIn.seek(payIn.getFilePointer() + numBytes); // skip over payloadBytes
}
@@ -1535,12 +1580,12 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
if (indexHasOffsets && payIn != null) {
if (needsOffsets) {
- forUtil.decode(payIn, offsetStartDeltaBuffer);
- forUtil.decode(payIn, offsetLengthBuffer);
+ pforUtil.decode(payIn, offsetStartDeltaBuffer);
+ pforUtil.decode(payIn, offsetLengthBuffer);
} else {
// this works, because when writing a vint block we always force the first length to be written
- forUtil.skip(payIn); // skip over starts
- forUtil.skip(payIn); // skip over lengths
+ pforUtil.skip(payIn); // skip over starts
+ pforUtil.skip(payIn); // skip over lengths
}
}
}
@@ -1589,6 +1634,9 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
@Override
public int advance(int target) throws IOException {
+ if (docBufferUpto == BLOCK_SIZE) {
+ accum = Math.max(accum, doc);
+ }
if (target > nextSkipDoc) {
advanceShallow(target);
}
@@ -1606,11 +1654,11 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
// Now scan:
while (true) {
- accum += docDeltaBuffer[docBufferUpto];
+ doc = (int) (accum + docIDSequence.next());
docBufferUpto++;
docUpto++;
- if (accum >= target) {
+ if (doc >= target) {
break;
}
if (docUpto == docFreq) {
@@ -1620,7 +1668,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
position = 0;
lastStartOffset = 0;
- return doc = accum;
+ return doc;
}
// TODO: in theory we could avoid loading frq block
@@ -1647,11 +1695,11 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
toSkip -= leftInBlock;
while(toSkip >= BLOCK_SIZE) {
assert posIn.getFilePointer() != lastPosBlockFP;
- forUtil.skip(posIn);
+ pforUtil.skip(posIn);
if (indexHasPayloads && payIn != null) {
// Skip payloadLength block:
- forUtil.skip(payIn);
+ pforUtil.skip(payIn);
// Skip payloadBytes block:
int numBytes = payIn.readVInt();
@@ -1659,8 +1707,8 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
if (indexHasOffsets && payIn != null) {
- forUtil.skip(payIn);
- forUtil.skip(payIn);
+ pforUtil.skip(payIn);
+ pforUtil.skip(payIn);
}
toSkip -= BLOCK_SIZE;
}
@@ -1686,7 +1734,7 @@ public final class Lucene84PostingsReader extends PostingsReaderBase {
}
if (isFreqsRead == false) {
- forUtil.decode(docIn, freqBuffer); // read freqBuffer for this docs block
+ pforUtil.decode(docIn, freqBuffer); // read freqBuffer for this docs block
isFreqsRead = true;
}
while (posDocUpTo < docUpto) { // bring posPendingCount upto the current doc
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsWriter.java
index ab878f3..70eca5e 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/Lucene84PostingsWriter.java
@@ -91,7 +91,8 @@ public final class Lucene84PostingsWriter extends PushPostingsWriterBase {
private int lastStartOffset;
private int docCount;
- private final ForUtil forUtil;
+ private final PForUtil pforUtil;
+ private final EliasFanoUtil efUtil;
private final Lucene84SkipWriter skipWriter;
private boolean fieldHasNorms;
@@ -117,7 +118,9 @@ public final class Lucene84PostingsWriter extends PushPostingsWriterBase {
} else {
throw new Error();
}
- forUtil = new ForUtil(byteOrder);
+ final ForUtil forUtil = new ForUtil(byteOrder);
+ pforUtil = new PForUtil(forUtil);
+ efUtil = new EliasFanoUtil(forUtil);
if (state.fieldInfos.hasProx()) {
posDeltaBuffer = new long[BLOCK_SIZE];
String posFileName = IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, Lucene84PostingsFormat.POS_EXTENSION);
@@ -230,9 +233,9 @@ public final class Lucene84PostingsWriter extends PushPostingsWriterBase {
competitiveFreqNormAccumulator.clear();
}
- final int docDelta = docID - lastDocID;
+ final int docDelta = docID - lastBlockDocID;
- if (docID < 0 || (docCount > 0 && docDelta <= 0)) {
+ if (docID < 0 || (docCount > 0 && docID <= lastDocID)) {
throw new CorruptIndexException("docs out of order (" + docID + " <= " + lastDocID + " )", docOut);
}
@@ -245,9 +248,9 @@ public final class Lucene84PostingsWriter extends PushPostingsWriterBase {
docCount++;
if (docBufferUpto == BLOCK_SIZE) {
- forUtil.encode(docDeltaBuffer, docOut);
+ efUtil.encode(docDeltaBuffer, docOut);
if (writeFreqs) {
- forUtil.encode(freqBuffer, docOut);
+ pforUtil.encode(freqBuffer, docOut);
}
// NOTE: don't set docBufferUpto back to 0 here;
// finishDoc will do so (because it needs to see that
@@ -312,17 +315,17 @@ public final class Lucene84PostingsWriter extends PushPostingsWriterBase {
posBufferUpto++;
lastPosition = position;
if (posBufferUpto == BLOCK_SIZE) {
- forUtil.encode(posDeltaBuffer, posOut);
+ pforUtil.encode(posDeltaBuffer, posOut);
if (writePayloads) {
- forUtil.encode(payloadLengthBuffer, payOut);
+ pforUtil.encode(payloadLengthBuffer, payOut);
payOut.writeVInt(payloadByteUpto);
payOut.writeBytes(payloadBytes, 0, payloadByteUpto);
payloadByteUpto = 0;
}
if (writeOffsets) {
- forUtil.encode(offsetStartDeltaBuffer, payOut);
- forUtil.encode(offsetLengthBuffer, payOut);
+ pforUtil.encode(offsetStartDeltaBuffer, payOut);
+ pforUtil.encode(offsetLengthBuffer, payOut);
}
posBufferUpto = 0;
}
@@ -361,12 +364,12 @@ public final class Lucene84PostingsWriter extends PushPostingsWriterBase {
final int singletonDocID;
if (state.docFreq == 1) {
// pulse the singleton docid into the term dictionary, freq is implicitly totalTermFreq
- singletonDocID = (int) docDeltaBuffer[0];
+ singletonDocID = (int) (docDeltaBuffer[0] - 1);
} else {
singletonDocID = -1;
// vInt encode the remaining doc deltas and freqs:
for(int i=0;i<docBufferUpto;i++) {
- final int docDelta = (int) docDeltaBuffer[i];
+ final int docDelta = (int) (docDeltaBuffer[i] - (i == 0 ? 0 : docDeltaBuffer[i-1]));
final int freq = (int) freqBuffer[i];
if (!writeFreqs) {
docOut.writeVInt(docDelta);
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/PForUtil.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/PForUtil.java
new file mode 100644
index 0000000..e9c962a
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/PForUtil.java
@@ -0,0 +1,126 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene84;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.util.packed.PackedInts;
+
+final class PForUtil {
+
+ private static boolean allEqual(long[] l) {
+ for (int i = 1; i < ForUtil.BLOCK_SIZE; ++i) {
+ if (l[i] != l[0]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private final ForUtil forUtil;
+
+ PForUtil(ForUtil forUtil) {
+ this.forUtil = forUtil;
+ }
+
+ /**
+ * Encode 128 8-bits integers from {@code data} into {@code out}.
+ */
+ void encode(long[] longs, DataOutput out) throws IOException {
+ // At most 3 exceptions
+ final long[] top4 = new long[4];
+ Arrays.fill(top4, -1L);
+ for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ if (longs[i] > top4[0]) {
+ top4[0] = longs[i];
+ Arrays.sort(top4);
+ }
+ }
+
+ final int maxBitsRequired = PackedInts.bitsRequired(top4[3]);
+ // We store the patch on a byte, so we can't decrease the number of bits required by more than 8
+ final int patchedBitsRequired = Math.max(PackedInts.bitsRequired(top4[0]), maxBitsRequired - 8);
+ int numExceptions = 0;
+ for (int i = 1; i < 4; ++i) {
+ if (top4[i] > (1L << patchedBitsRequired) - 1) {
+ numExceptions++;
+ }
+ }
+ final byte[] exceptions = new byte[numExceptions*2];
+ if (numExceptions > 0) {
+ int exceptionCount = 0;
+ for (int i = 0; i < ForUtil.BLOCK_SIZE; ++i) {
+ if (longs[i] > (1L << patchedBitsRequired) - 1) {
+ exceptions[exceptionCount*2] = (byte) i;
+ exceptions[exceptionCount*2+1] = (byte) (longs[i] >>> patchedBitsRequired);
+ longs[i] &= (1L << patchedBitsRequired) - 1;
+ exceptionCount++;
+ }
+ }
+ assert exceptionCount == numExceptions : exceptionCount + " " + numExceptions;
+ }
+
+ if (allEqual(longs) && maxBitsRequired <= 8) {
+ for (int i = 0; i < numExceptions; ++i) {
+ exceptions[2*i + 1] = (byte) (Byte.toUnsignedLong(exceptions[2*i + 1]) << patchedBitsRequired);
+ }
+ out.writeByte((byte) (numExceptions << 5));
+ out.writeVLong(longs[0]);
+ } else {
+ final int token = (numExceptions << 5) | patchedBitsRequired;
+ out.writeByte((byte) token);
+ forUtil.encode(longs, patchedBitsRequired, out);
+ }
+ out.writeBytes(exceptions, exceptions.length);
+ }
+
+ /**
+ * Decode 128 integers into {@code ints}.
+ */
+ void decode(DataInput in, long[] longs) throws IOException {
+ final int token = Byte.toUnsignedInt(in.readByte());
+ final int bitsPerValue = token & 0x1f;
+ final int numExceptions = token >>> 5;
+ if (bitsPerValue == 0) {
+ Arrays.fill(longs, 0, ForUtil.BLOCK_SIZE, in.readVLong());
+ } else {
+ forUtil.decode(bitsPerValue, in, longs);
+ }
+ for (int i = 0; i < numExceptions; ++i) {
+ longs[Byte.toUnsignedInt(in.readByte())] |= Byte.toUnsignedLong(in.readByte()) << bitsPerValue;
+ }
+ }
+
+ /**
+ * Skip 128 integers.
+ */
+ void skip(DataInput in) throws IOException {
+ final int token = Byte.toUnsignedInt(in.readByte());
+ final int bitsPerValue = token & 0x1f;
+ final int numExceptions = token >>> 5;
+ if (bitsPerValue == 0) {
+ in.readVLong();
+ in.skipBytes((numExceptions << 1));
+ } else {
+ in.skipBytes(forUtil.numBytes(bitsPerValue) + (numExceptions << 1));
+ }
+ }
+
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/gen_ForUtil.py b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/gen_ForUtil.py
index 91c10c1..ba4e468 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene84/gen_ForUtil.py
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene84/gen_ForUtil.py
@@ -48,7 +48,6 @@ import java.util.function.IntToLongFunction;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
-import org.apache.lucene.util.packed.PackedInts;
// Inspired from https://fulmicoton.com/posts/bitpacking/
// Encodes multiple integers in a long to get SIMD-like speedups.
@@ -60,23 +59,6 @@ final class ForUtil {
static final int BLOCK_SIZE = 128;
private static final int BLOCK_SIZE_LOG2 = 7;
- private static int numBitsPerValue(long[] longs) {
- long or = 0;
- for (long l : longs) {
- or |= l;
- }
- return PackedInts.bitsRequired(or);
- }
-
- private static boolean allEqual(long[] longs) {
- for (long l : longs) {
- if (l != longs[0]) {
- return false;
- }
- }
- return true;
- }
-
private static long expandMask32(long mask32) {
return mask32 | (mask32 << 32);
}
@@ -161,16 +143,7 @@ final class ForUtil {
/**
* Encode 128 8-bits integers from {@code data} into {@code out}.
*/
- void encode(long[] longs, DataOutput out) throws IOException {
- if (allEqual(longs)) {
- out.writeByte((byte) 0);
- out.writeVLong(longs[0]);
- return;
- }
-
- final int bitsPerValue = numBitsPerValue(longs);
- out.writeByte((byte) bitsPerValue);
-
+ void encode(long[] longs, int bitsPerValue, DataOutput out) throws IOException {
final int nextPrimitive;
final int numLongs;
final IntToLongFunction maskFunction;
@@ -228,12 +201,10 @@ final class ForUtil {
}
/**
- * Skip 128 integers.
+ * Number of bytes required to encode 128 integers of {@code bitsPerValue}.
*/
- void skip(DataInput in) throws IOException {
- final int bitsPerValue = in.readByte();
- final int numBytes = bitsPerValue << (BLOCK_SIZE_LOG2 - 3);
- in.skipBytes(numBytes);
+ int numBytes(int bitsPerValue) throws IOException {
+ return bitsPerValue << (BLOCK_SIZE_LOG2 - 3);
}
private static void decodeSlow(int bitsPerValue, DataInput in, ByteOrder byteOrder, long[] tmp, long[] longs) throws IOException {
@@ -269,10 +240,6 @@ final class ForUtil {
expand32(longs);
}
- private static void decode0(DataInput in, long[] longs) throws IOException {
- Arrays.fill(longs, 0, BLOCK_SIZE, in.readVLong());
- }
-
/**
* The pattern that this shiftLongs method applies is recognized by the C2
* compiler, which generates SIMD instructions for it in order to shift
@@ -354,12 +321,8 @@ if __name__ == '__main__':
/**
* Decode 128 integers into {@code ints}.
*/
- void decode(DataInput in, long[] longs) throws IOException {
- final int bitsPerValue = in.readByte();
+ void decode(int bitsPerValue, DataInput in, long[] longs) throws IOException {
switch (bitsPerValue) {
- case 0:
- decode0(in, longs);
- break;
""")
for i in range(1, MAX_SPECIALIZED_BITS_PER_VALUE+1):
f.write(' case %d:\n' %i)
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java b/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestEliasFanoUtil.java
similarity index 76%
copy from lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
copy to lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestEliasFanoUtil.java
index 86eedce..e9e7258 100644
--- a/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestEliasFanoUtil.java
@@ -27,11 +27,12 @@ import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.TestUtil;
import org.apache.lucene.util.packed.PackedInts;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
-public class TestForUtil extends LuceneTestCase {
+public class TestEliasFanoUtil extends LuceneTestCase {
public void testEncodeDecodeLE() throws IOException {
doTestEncodeDecode(ByteOrder.LITTLE_ENDIAN);
@@ -46,18 +47,12 @@ public class TestForUtil extends LuceneTestCase {
final int[] values = new int[iterations * ForUtil.BLOCK_SIZE];
for (int i = 0; i < iterations; ++i) {
- final int bpv = random().nextInt(32);
- if (bpv == 0) {
- final int value = RandomNumbers.randomIntBetween(random(), 0, Integer.MAX_VALUE);
- for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- values[i * ForUtil.BLOCK_SIZE + j] = value;
- }
- } else {
- for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- values[i * ForUtil.BLOCK_SIZE + j] = RandomNumbers.randomIntBetween(random(),
- 0, (int) PackedInts.maxValue(bpv));
- }
+ final int bpv = TestUtil.nextInt(random(), 0, 31);
+ for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
+ values[i * ForUtil.BLOCK_SIZE + j] = RandomNumbers.randomIntBetween(random(),
+ 0, (int) PackedInts.maxValue(bpv));
}
+ Arrays.sort(values, i * ForUtil.BLOCK_SIZE, (i + 1) * ForUtil.BLOCK_SIZE);
}
final Directory d = new ByteBuffersDirectory();
@@ -66,14 +61,14 @@ public class TestForUtil extends LuceneTestCase {
{
// encode
IndexOutput out = d.createOutput("test.bin", IOContext.DEFAULT);
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final EliasFanoUtil efUtil = new EliasFanoUtil(new ForUtil(byteOrder));
for (int i = 0; i < iterations; ++i) {
long[] source = new long[ForUtil.BLOCK_SIZE];
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
source[j] = values[i*ForUtil.BLOCK_SIZE+j];
}
- forUtil.encode(source, out);
+ efUtil.encode(source, out);
}
endPointer = out.getFilePointer();
out.close();
@@ -82,17 +77,17 @@ public class TestForUtil extends LuceneTestCase {
{
// decode
IndexInput in = d.openInput("test.bin", IOContext.READONCE);
- final ForUtil forUtil = new ForUtil(byteOrder);
+ EliasFanoSequence sequence = new EliasFanoSequence();
+ final EliasFanoUtil efUtil = new EliasFanoUtil(new ForUtil(byteOrder));
for (int i = 0; i < iterations; ++i) {
- if (random().nextBoolean()) {
- forUtil.skip(in);
+ if (random().nextInt(5) == 0) {
+ efUtil.skip(in);
continue;
}
- final long[] restored = new long[ForUtil.BLOCK_SIZE];
- forUtil.decode(in, restored);
+ efUtil.decode(in, sequence);
int[] ints = new int[ForUtil.BLOCK_SIZE];
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- ints[j] = Math.toIntExact(restored[j]);
+ ints[j] = Math.toIntExact(sequence.next());
}
assertArrayEquals(Arrays.toString(ints),
ArrayUtil.copyOfSubArray(values, i*ForUtil.BLOCK_SIZE, (i+1)*ForUtil.BLOCK_SIZE),
@@ -104,4 +99,8 @@ public class TestForUtil extends LuceneTestCase {
d.close();
}
+
+ public void testAdvance() {
+
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java b/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
index 86eedce..2538102 100644
--- a/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
@@ -27,6 +27,7 @@ import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.TestUtil;
import org.apache.lucene.util.packed.PackedInts;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
@@ -46,17 +47,10 @@ public class TestForUtil extends LuceneTestCase {
final int[] values = new int[iterations * ForUtil.BLOCK_SIZE];
for (int i = 0; i < iterations; ++i) {
- final int bpv = random().nextInt(32);
- if (bpv == 0) {
- final int value = RandomNumbers.randomIntBetween(random(), 0, Integer.MAX_VALUE);
- for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- values[i * ForUtil.BLOCK_SIZE + j] = value;
- }
- } else {
- for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- values[i * ForUtil.BLOCK_SIZE + j] = RandomNumbers.randomIntBetween(random(),
- 0, (int) PackedInts.maxValue(bpv));
- }
+ final int bpv = TestUtil.nextInt(random(), 1, 31);
+ for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
+ values[i * ForUtil.BLOCK_SIZE + j] = RandomNumbers.randomIntBetween(random(),
+ 0, (int) PackedInts.maxValue(bpv));
}
}
@@ -70,10 +64,14 @@ public class TestForUtil extends LuceneTestCase {
for (int i = 0; i < iterations; ++i) {
long[] source = new long[ForUtil.BLOCK_SIZE];
+ long or = 0;
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
source[j] = values[i*ForUtil.BLOCK_SIZE+j];
+ or |= source[j];
}
- forUtil.encode(source, out);
+ final int bpv = PackedInts.bitsRequired(or);
+ out.writeByte((byte) bpv);
+ forUtil.encode(source, bpv, out);
}
endPointer = out.getFilePointer();
out.close();
@@ -84,12 +82,10 @@ public class TestForUtil extends LuceneTestCase {
IndexInput in = d.openInput("test.bin", IOContext.READONCE);
final ForUtil forUtil = new ForUtil(byteOrder);
for (int i = 0; i < iterations; ++i) {
- if (random().nextBoolean()) {
- forUtil.skip(in);
- continue;
- }
+ final int bitsPerValue = in.readByte();
+ final long currentFilePointer = in.getFilePointer();
final long[] restored = new long[ForUtil.BLOCK_SIZE];
- forUtil.decode(in, restored);
+ forUtil.decode(bitsPerValue, in, restored);
int[] ints = new int[ForUtil.BLOCK_SIZE];
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
ints[j] = Math.toIntExact(restored[j]);
@@ -97,6 +93,7 @@ public class TestForUtil extends LuceneTestCase {
assertArrayEquals(Arrays.toString(ints),
ArrayUtil.copyOfSubArray(values, i*ForUtil.BLOCK_SIZE, (i+1)*ForUtil.BLOCK_SIZE),
ints);
+ assertEquals(forUtil.numBytes(bitsPerValue), in.getFilePointer() - currentFilePointer);
}
assertEquals(endPointer, in.getFilePointer());
in.close();
diff --git a/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java b/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestPForUtil.java
similarity index 74%
copy from lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
copy to lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestPForUtil.java
index 86eedce..8ba7e62 100644
--- a/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestForUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/codecs/lucene84/TestPForUtil.java
@@ -27,11 +27,12 @@ import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.TestUtil;
import org.apache.lucene.util.packed.PackedInts;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
-public class TestForUtil extends LuceneTestCase {
+public class TestPForUtil extends LuceneTestCase {
public void testEncodeDecodeLE() throws IOException {
doTestEncodeDecode(ByteOrder.LITTLE_ENDIAN);
@@ -46,16 +47,18 @@ public class TestForUtil extends LuceneTestCase {
final int[] values = new int[iterations * ForUtil.BLOCK_SIZE];
for (int i = 0; i < iterations; ++i) {
- final int bpv = random().nextInt(32);
- if (bpv == 0) {
- final int value = RandomNumbers.randomIntBetween(random(), 0, Integer.MAX_VALUE);
- for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- values[i * ForUtil.BLOCK_SIZE + j] = value;
- }
- } else {
- for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
- values[i * ForUtil.BLOCK_SIZE + j] = RandomNumbers.randomIntBetween(random(),
- 0, (int) PackedInts.maxValue(bpv));
+ final int bpv = TestUtil.nextInt(random(), 0, 31);
+ for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
+ values[i * ForUtil.BLOCK_SIZE + j] = RandomNumbers.randomIntBetween(random(),
+ 0, (int) PackedInts.maxValue(bpv));
+ if (random().nextInt(100) == 0) {
+ final int exceptionBpv;
+ if (random().nextInt(10) == 0) {
+ exceptionBpv = Math.min(bpv + TestUtil.nextInt(random(), 9, 16), 31);
+ } else {
+ exceptionBpv = Math.min(bpv + TestUtil.nextInt(random(), 1, 8), 31);
+ }
+ values[i * ForUtil.BLOCK_SIZE + j] |= random().nextInt(1 << (exceptionBpv - bpv)) << bpv;
}
}
}
@@ -66,14 +69,14 @@ public class TestForUtil extends LuceneTestCase {
{
// encode
IndexOutput out = d.createOutput("test.bin", IOContext.DEFAULT);
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final PForUtil pforUtil = new PForUtil(new ForUtil(byteOrder));
for (int i = 0; i < iterations; ++i) {
long[] source = new long[ForUtil.BLOCK_SIZE];
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
source[j] = values[i*ForUtil.BLOCK_SIZE+j];
}
- forUtil.encode(source, out);
+ pforUtil.encode(source, out);
}
endPointer = out.getFilePointer();
out.close();
@@ -82,14 +85,14 @@ public class TestForUtil extends LuceneTestCase {
{
// decode
IndexInput in = d.openInput("test.bin", IOContext.READONCE);
- final ForUtil forUtil = new ForUtil(byteOrder);
+ final PForUtil pforUtil = new PForUtil(new ForUtil(byteOrder));
for (int i = 0; i < iterations; ++i) {
- if (random().nextBoolean()) {
- forUtil.skip(in);
+ if (random().nextInt(5) == 0) {
+ pforUtil.skip(in);
continue;
}
final long[] restored = new long[ForUtil.BLOCK_SIZE];
- forUtil.decode(in, restored);
+ pforUtil.decode(in, restored);
int[] ints = new int[ForUtil.BLOCK_SIZE];
for (int j = 0; j < ForUtil.BLOCK_SIZE; ++j) {
ints[j] = Math.toIntExact(restored[j]);