You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2012/07/19 17:59:32 UTC
svn commit: r1363400 [13/31] - in /lucene/dev/branches/pforcodec_3892: ./
dev-tools/ dev-tools/eclipse/ dev-tools/idea/.idea/
dev-tools/idea/.idea/copyright/ dev-tools/idea/.idea/libraries/
dev-tools/idea/lucene/ dev-tools/maven/ dev-tools/maven/lucene...
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java Thu Jul 19 15:58:54 2012
@@ -1,10 +1,6 @@
-package org.apache.lucene.util.packed;
-
-import java.io.IOException;
-import java.util.Arrays;
+// This file has been automatically generated, DO NOT EDIT
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.RamUsageEstimator;
+package org.apache.lucene.util.packed;
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
@@ -23,32 +19,38 @@ import org.apache.lucene.util.RamUsageEs
* limitations under the License.
*/
-/** 48 bitsPerValue backed by short[] */
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.RamUsageEstimator;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+/**
+ * Packs integers into 3 shorts (48 bits per value).
+ * @lucene.internal
+ */
final class Packed16ThreeBlocks extends PackedInts.MutableImpl {
+ final short[] blocks;
public static final int MAX_SIZE = Integer.MAX_VALUE / 3;
- private final short[] blocks;
-
Packed16ThreeBlocks(int valueCount) {
super(valueCount, 48);
if (valueCount > MAX_SIZE) {
throw new ArrayIndexOutOfBoundsException("MAX_SIZE exceeded");
}
- this.blocks = new short[3 * valueCount];
+ blocks = new short[valueCount * 3];
}
Packed16ThreeBlocks(DataInput in, int valueCount) throws IOException {
this(valueCount);
- for (int i = 0; i < blocks.length; i++) {
+ for (int i = 0; i < 3 * valueCount; ++i) {
blocks[i] = in.readShort();
}
final int mod = blocks.length % 4;
if (mod != 0) {
- final int pad = 4 - mod;
- // round out long
- for (int i = 0; i < pad; i++) {
- in.readShort();
+ for (int i = mod; i < 4; ++i) {
+ in.readShort();
}
}
}
@@ -56,26 +58,55 @@ final class Packed16ThreeBlocks extends
@Override
public long get(int index) {
final int o = index * 3;
- return (blocks[o] & 0xffffL) << 32 | (blocks[o+1] & 0xffffL) << 16 | (blocks[o+2] & 0xffffL);
+ return (blocks[o] & 0xFFFFL) << 32 | (blocks[o+1] & 0xFFFFL) << 16 | (blocks[o+2] & 0xFFFFL);
+ }
+
+ @Override
+ public int get(int index, long[] arr, int off, int len) {
+ assert len > 0 : "len must be > 0 (got " + len + ")";
+ assert index >= 0 && index < valueCount;
+ assert off + len <= arr.length;
+
+ final int gets = Math.min(valueCount - index, len);
+ for (int i = index * 3, end = (index + gets) * 3; i < end; i+=3) {
+ arr[off++] = (blocks[i] & 0xFFFFL) << 32 | (blocks[i+1] & 0xFFFFL) << 16 | (blocks[i+2] & 0xFFFFL);
+ }
+ return gets;
}
@Override
public void set(int index, long value) {
final int o = index * 3;
- blocks[o] = (short) (value >> 32);
- blocks[o+1] = (short) (value >> 16);
+ blocks[o] = (short) (value >>> 32);
+ blocks[o+1] = (short) (value >>> 16);
blocks[o+2] = (short) value;
}
@Override
+ public int set(int index, long[] arr, int off, int len) {
+ assert len > 0 : "len must be > 0 (got " + len + ")";
+ assert index >= 0 && index < valueCount;
+ assert off + len <= arr.length;
+
+ final int sets = Math.min(valueCount - index, len);
+ for (int i = off, o = index * 3, end = off + sets; i < end; ++i) {
+ final long value = arr[i];
+ blocks[o++] = (short) (value >>> 32);
+ blocks[o++] = (short) (value >>> 16);
+ blocks[o++] = (short) value;
+ }
+ return sets;
+ }
+
+ @Override
public void fill(int fromIndex, int toIndex, long val) {
- short block1 = (short) (val >> 32);
- short block2 = (short) (val >> 16);
- short block3 = (short) val;
- for (int i = fromIndex * 3, end = toIndex * 3; i < end; ) {
- blocks[i++] = block1;
- blocks[i++] = block2;
- blocks[i++] = block3;
+ final short block1 = (short) (val >>> 32);
+ final short block2 = (short) (val >>> 16);
+ final short block3 = (short) val;
+ for (int i = fromIndex * 3, end = toIndex * 3; i < end; i += 3) {
+ blocks[i] = block1;
+ blocks[i+1] = block2;
+ blocks[i+2] = block3;
}
}
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java Thu Jul 19 15:58:54 2012
@@ -25,99 +25,40 @@ import java.util.Arrays;
/**
* Space optimized random access capable array of values with a fixed number of
- * bits. For 32 bits/value and less, performance on 32 bit machines is not
- * optimal. Consider using {@link Packed32} for such a setup.
+ * bits/value. Values are packed contiguously.
* </p><p>
- * The implementation strives to avoid conditionals and expensive operations,
- * sacrificing code clarity to achieve better performance.
+ * The implementation strives to perform af fast as possible under the
+ * constraint of contiguous bits, by avoiding expensive operations. This comes
+ * at the cost of code clarity.
+ * </p><p>
+ * Technical details: This implementation is a refinement of a non-branching
+ * version. The non-branching get and set methods meant that 2 or 4 atomics in
+ * the underlying array were always accessed, even for the cases where only
+ * 1 or 2 were needed. Even with caching, this had a detrimental effect on
+ * performance.
+ * Related to this issue, the old implementation used lookup tables for shifts
+ * and masks, which also proved to be a bit slower than calculating the shifts
+ * and masks on the fly.
+ * See https://issues.apache.org/jira/browse/LUCENE-4062 for details.
+ *
*/
-
class Packed64 extends PackedInts.MutableImpl {
static final int BLOCK_SIZE = 64; // 32 = int, 64 = long
static final int BLOCK_BITS = 6; // The #bits representing BLOCK_SIZE
static final int MOD_MASK = BLOCK_SIZE - 1; // x % BLOCK_SIZE
- private static final int ENTRY_SIZE = BLOCK_SIZE + 1;
- static final int FAC_BITPOS = 3;
-
- /*
- * In order to make an efficient value-getter, conditionals should be
- * avoided. A value can be positioned inside of a block, requiring shifting
- * left or right or it can span two blocks, requiring a left-shift on the
- * first block and a right-shift on the right block.
- * </p><p>
- * By always shifting the first block both left and right, we get exactly
- * the right bits. By always shifting the second block right and applying
- * a mask, we get the right bits there. After that, we | the two bitsets.
- */
- static final int[][] SHIFTS =
- new int[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
- static final long[][] MASKS = new long[ENTRY_SIZE][ENTRY_SIZE];
-
- static { // Generate shifts
- for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
- for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
- int[] currentShifts = SHIFTS[elementBits];
- int base = bitPos * FAC_BITPOS;
- currentShifts[base ] = bitPos;
- currentShifts[base + 1] = BLOCK_SIZE - elementBits;
- if (bitPos <= BLOCK_SIZE - elementBits) { // Single block
- currentShifts[base + 2] = 0;
- MASKS[elementBits][bitPos] = 0;
- } else { // Two blocks
- int rBits = elementBits - (BLOCK_SIZE - bitPos);
- currentShifts[base + 2] = BLOCK_SIZE - rBits;
- MASKS[elementBits][bitPos] = ~(~0L << rBits);
- }
- }
- }
- }
-
- /*
- * The setter requires more masking than the getter.
- */
- private static final long[][] WRITE_MASKS =
- new long[ENTRY_SIZE][ENTRY_SIZE * FAC_BITPOS];
- static {
- for (int elementBits = 1 ; elementBits <= BLOCK_SIZE ; elementBits++) {
- long elementPosMask = ~(~0L << elementBits);
- int[] currentShifts = SHIFTS[elementBits];
- long[] currentMasks = WRITE_MASKS[elementBits];
- for (int bitPos = 0 ; bitPos < BLOCK_SIZE ; bitPos++) {
- int base = bitPos * FAC_BITPOS;
- currentMasks[base ] =~((elementPosMask
- << currentShifts[base + 1])
- >>> currentShifts[base]);
- if (bitPos <= BLOCK_SIZE - elementBits) { // Second block not used
- currentMasks[base+1] = ~0; // Keep all bits
- currentMasks[base+2] = 0; // Or with 0
- } else {
- currentMasks[base+1] = ~(elementPosMask
- << currentShifts[base + 2]);
- currentMasks[base+2] = currentShifts[base + 2] == 0 ? 0 : ~0;
- }
- }
- }
- }
-
- private static int pgcd(int a, int b) {
- if (a < b) {
- return pgcd(b, a);
- } else if (b == 0) {
- return a;
- } else {
- return pgcd(b, a % b);
- }
- }
-
- /* The bits */
+ /**
+ * Values are stores contiguously in the blocks array.
+ */
private final long[] blocks;
-
- // Cached calculations
- private int maxPos; // blocks.length * BLOCK_SIZE / elementBits - 1
- private int[] shifts; // The shifts for the current elementBits
- private long[] readMasks;
- private long[] writeMasks;
+ /**
+ * A right-aligned mask of width BitsPerValue used by {@link #get(int)}.
+ */
+ private final long maskRight;
+ /**
+ * Optimization: Saves one lookup in {@link #get(int)}.
+ */
+ private final int bpvMinusBlockSize;
/**
* Creates an array with the internal structures adjusted for the given
@@ -126,18 +67,18 @@ class Packed64 extends PackedInts.Mutabl
* @param bitsPerValue the number of bits available for any given value.
*/
public Packed64(int valueCount, int bitsPerValue) {
- // TODO: Test for edge-cases (2^31 values, 63 bitsPerValue)
- // +2 due to the avoid-conditionals-trick. The last entry is always 0
- this(new long[(int)((long)valueCount * bitsPerValue / BLOCK_SIZE + 2)],
+ // NOTE: block-size was previously calculated as
+ // valueCount * bitsPerValue / BLOCK_SIZE + 1
+ // due to memory layout requirements dictated by non-branching code
+ this(new long[size(valueCount, bitsPerValue)],
valueCount, bitsPerValue);
}
-
/**
* Creates an array backed by the given blocks.
* </p><p>
* Note: The blocks are used directly, so changes to the given block will
- * affect the Packed32-structure.
+ * affect the Packed64-structure.
* @param blocks used as the internal backing array. Not that the last
* element cannot be addressed directly.
* @param valueCount the number of values.
@@ -146,7 +87,8 @@ class Packed64 extends PackedInts.Mutabl
public Packed64(long[] blocks, int valueCount, int bitsPerValue) {
super(valueCount, bitsPerValue);
this.blocks = blocks;
- updateCached();
+ maskRight = ~0L << (BLOCK_SIZE-bitsPerValue) >>> (BLOCK_SIZE-bitsPerValue);
+ bpvMinusBlockSize = bitsPerValue - BLOCK_SIZE;
}
/**
@@ -161,12 +103,12 @@ class Packed64 extends PackedInts.Mutabl
throws IOException {
super(valueCount, bitsPerValue);
int size = size(valueCount, bitsPerValue);
- blocks = new long[size+1]; // +1 due to non-conditional tricks
- // TODO: find a faster way to bulk-read longs...
+ blocks = new long[size]; // Previously +1 due to non-conditional tricks
for(int i=0;i<size;i++) {
blocks[i] = in.readLong();
}
- updateCached();
+ maskRight = ~0L << (BLOCK_SIZE-bitsPerValue) >>> (BLOCK_SIZE-bitsPerValue);
+ bpvMinusBlockSize = bitsPerValue - BLOCK_SIZE;
}
private static int size(int valueCount, int bitsPerValue) {
@@ -174,48 +116,142 @@ class Packed64 extends PackedInts.Mutabl
return (int)(totBitCount/64 + ((totBitCount % 64 == 0 ) ? 0:1));
}
- private void updateCached() {
- readMasks = MASKS[bitsPerValue];
- shifts = SHIFTS[bitsPerValue];
- writeMasks = WRITE_MASKS[bitsPerValue];
- maxPos = (int)((((long)blocks.length) * BLOCK_SIZE / bitsPerValue) - 2);
- }
-
/**
* @param index the position of the value.
* @return the value at the given index.
*/
+ @Override
public long get(final int index) {
- assert index >= 0 && index < size();
+ // The abstract index in a bit stream
final long majorBitPos = (long)index * bitsPerValue;
- final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
- final int bitPos = (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
+ // The index in the backing long-array
+ final int elementPos = (int)(majorBitPos >>> BLOCK_BITS);
+ // The number of value-bits in the second long
+ final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;
+
+ if (endBits <= 0) { // Single block
+ return (blocks[elementPos] >>> -endBits) & maskRight;
+ }
+ // Two blocks
+ return ((blocks[elementPos] << endBits)
+ | (blocks[elementPos+1] >>> (BLOCK_SIZE - endBits)))
+ & maskRight;
+ }
+
+ @Override
+ public int get(int index, long[] arr, int off, int len) {
+ assert len > 0 : "len must be > 0 (got " + len + ")";
+ assert index >= 0 && index < valueCount;
+ len = Math.min(len, valueCount - index);
+ assert off + len <= arr.length;
+
+ final int originalIndex = index;
+ final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);
+
+ // go to the next block where the value does not span across two blocks
+ final int offsetInBlocks = index % op.values();
+ if (offsetInBlocks != 0) {
+ for (int i = offsetInBlocks; i < op.values() && len > 0; ++i) {
+ arr[off++] = get(index++);
+ --len;
+ }
+ if (len == 0) {
+ return index - originalIndex;
+ }
+ }
- final int base = bitPos * FAC_BITPOS;
- assert elementPos < blocks.length : "elementPos: " + elementPos + "; blocks.len: " + blocks.length;
- return ((blocks[elementPos] << shifts[base]) >>> shifts[base+1]) |
- ((blocks[elementPos+1] >>> shifts[base+2]) & readMasks[bitPos]);
+ // bulk get
+ assert index % op.values() == 0;
+ int blockIndex = (int) ((long) index * bitsPerValue) >>> BLOCK_BITS;
+ assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
+ final int iterations = len / op.values();
+ op.get(blocks, blockIndex, arr, off, iterations);
+ final int gotValues = iterations * op.values();
+ index += gotValues;
+ len -= gotValues;
+ assert len >= 0;
+
+ if (index > originalIndex) {
+ // stay at the block boundary
+ return index - originalIndex;
+ } else {
+ // no progress so far => already at a block boundary but no full block to get
+ assert index == originalIndex;
+ return super.get(index, arr, off, len);
+ }
}
+ @Override
public void set(final int index, final long value) {
+ // The abstract index in a contiguous bit stream
final long majorBitPos = (long)index * bitsPerValue;
+ // The index in the backing long-array
final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // / BLOCK_SIZE
- final int bitPos = (int)(majorBitPos & MOD_MASK); // % BLOCK_SIZE);
- final int base = bitPos * FAC_BITPOS;
+ // The number of value-bits in the second long
+ final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;
+
+ if (endBits <= 0) { // Single block
+ blocks[elementPos] = blocks[elementPos] & ~(maskRight << -endBits)
+ | (value << -endBits);
+ return;
+ }
+ // Two blocks
+ blocks[elementPos] = blocks[elementPos] & ~(maskRight >>> endBits)
+ | (value >>> endBits);
+ blocks[elementPos+1] = blocks[elementPos+1] & (~0L >>> endBits)
+ | (value << (BLOCK_SIZE - endBits));
+ }
+
+ @Override
+ public int set(int index, long[] arr, int off, int len) {
+ assert len > 0 : "len must be > 0 (got " + len + ")";
+ assert index >= 0 && index < valueCount;
+ len = Math.min(len, valueCount - index);
+ assert off + len <= arr.length;
+
+ final int originalIndex = index;
+ final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);
+
+ // go to the next block where the value does not span across two blocks
+ final int offsetInBlocks = index % op.values();
+ if (offsetInBlocks != 0) {
+ for (int i = offsetInBlocks; i < op.values() && len > 0; ++i) {
+ set(index++, arr[off++]);
+ --len;
+ }
+ if (len == 0) {
+ return index - originalIndex;
+ }
+ }
- blocks[elementPos ] = (blocks[elementPos ] & writeMasks[base])
- | (value << shifts[base + 1] >>> shifts[base]);
- blocks[elementPos+1] = (blocks[elementPos+1] & writeMasks[base+1])
- | ((value << shifts[base + 2]) & writeMasks[base+2]);
+ // bulk get
+ assert index % op.values() == 0;
+ int blockIndex = (int) ((long) index * bitsPerValue) >>> BLOCK_BITS;
+ assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
+ final int iterations = len / op.values();
+ op.set(blocks, blockIndex, arr, off, iterations);
+ final int setValues = iterations * op.values();
+ index += setValues;
+ len -= setValues;
+ assert len >= 0;
+
+ if (index > originalIndex) {
+ // stay at the block boundary
+ return index - originalIndex;
+ } else {
+ // no progress so far => already at a block boundary but no full block to get
+ assert index == originalIndex;
+ return super.set(index, arr, off, len);
+ }
}
@Override
public String toString() {
return "Packed64(bitsPerValue=" + bitsPerValue + ", size="
- + size() + ", maxPos=" + maxPos
- + ", elements.length=" + blocks.length + ")";
+ + size() + ", elements.length=" + blocks.length + ")";
}
+ @Override
public long ramBytesUsed() {
return RamUsageEstimator.sizeOf(blocks);
}
@@ -226,7 +262,7 @@ class Packed64 extends PackedInts.Mutabl
assert fromIndex <= toIndex;
// minimum number of values that use an exact number of full blocks
- final int nAlignedValues = 64 / pgcd(64, bitsPerValue);
+ final int nAlignedValues = 64 / gcd(64, bitsPerValue);
final int span = toIndex - fromIndex;
if (span <= 3 * nAlignedValues) {
// there needs be at least 2 * nAlignedValues aligned values for the
@@ -270,6 +306,17 @@ class Packed64 extends PackedInts.Mutabl
}
}
+ private static int gcd(int a, int b) {
+ if (a < b) {
+ return gcd(b, a);
+ } else if (b == 0) {
+ return a;
+ } else {
+ return gcd(b, a % b);
+ }
+ }
+
+ @Override
public void clear() {
Arrays.fill(blocks, 0L);
}
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java Thu Jul 19 15:58:54 2012
@@ -1,3 +1,5 @@
+// This file has been automatically generated, DO NOT EDIT
+
package org.apache.lucene.util.packed;
/*
@@ -28,93 +30,36 @@ import org.apache.lucene.util.RamUsageEs
* speed by ensuring that a single block needs to be read/written in order to
* read/write a value.
*/
-final class Packed64SingleBlock extends PackedInts.MutableImpl {
-
- private static final int[] SUPPORTED_BITS_PER_VALUE = new int[] {1, 2, 3, 4,
- 5, 6, 7, 8, 9, 10, 12, 16, 21, 32};
- static final int MAX_SUPPORTED_BITS_PER_VALUE = 32;
- private static final long[][] WRITE_MASKS = new long[MAX_SUPPORTED_BITS_PER_VALUE+1][];
- private static final int[][] SHIFTS = new int[MAX_SUPPORTED_BITS_PER_VALUE+1][];
- static {
- for (int bpv : SUPPORTED_BITS_PER_VALUE) {
- initMasks(bpv);
- }
- }
+abstract class Packed64SingleBlock extends PackedInts.MutableImpl {
- protected static void initMasks(int bpv) {
- int valuesPerBlock = Long.SIZE / bpv;
- long[] writeMasks = new long[valuesPerBlock];
- int[] shifts = new int[valuesPerBlock];
- long bits = (1L << bpv) - 1;
- for (int i = 0; i < valuesPerBlock; ++i) {
- shifts[i] = bpv * i;
- writeMasks[i] = ~(bits << shifts[i]);
- }
- WRITE_MASKS[bpv] = writeMasks;
- SHIFTS[bpv] = shifts;
- }
-
- public static Packed64SingleBlock create(int valueCount, int bitsPerValue) {
- if (isSupported(bitsPerValue)) {
- return new Packed64SingleBlock(valueCount, bitsPerValue);
- }
- throw new IllegalArgumentException("Unsupported bitsPerValue: " + bitsPerValue);
- }
-
- public static Packed64SingleBlock create(DataInput in,
- int valueCount, int bitsPerValue) throws IOException {
- Packed64SingleBlock reader = create(valueCount, bitsPerValue);
- for (int i = 0; i < reader.blocks.length; ++i) {
- reader.blocks[i] = in.readLong();
- }
- return reader;
- }
+ public static final int MAX_SUPPORTED_BITS_PER_VALUE = 32;
+ private static final int[] SUPPORTED_BITS_PER_VALUE = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 21, 32};
public static boolean isSupported(int bitsPerValue) {
return Arrays.binarySearch(SUPPORTED_BITS_PER_VALUE, bitsPerValue) >= 0;
}
- public static float overheadPerValue(int bitsPerValue) {
- int valuesPerBlock = 64 / bitsPerValue;
- int overhead = 64 % bitsPerValue;
- return (float) overhead / valuesPerBlock;
+ private static int requiredCapacity(int valueCount, int valuesPerBlock) {
+ return valueCount / valuesPerBlock
+ + (valueCount % valuesPerBlock == 0 ? 0 : 1);
}
final long[] blocks;
- final int valuesPerBlock;
- final int[] shifts;
- final long[] writeMasks;
- final long readMask;
Packed64SingleBlock(int valueCount, int bitsPerValue) {
super(valueCount, bitsPerValue);
assert isSupported(bitsPerValue);
- valuesPerBlock = Long.SIZE / bitsPerValue;
+ final int valuesPerBlock = 64 / bitsPerValue;
blocks = new long[requiredCapacity(valueCount, valuesPerBlock)];
- shifts = SHIFTS[bitsPerValue];
- writeMasks = WRITE_MASKS[bitsPerValue];
- readMask = ~writeMasks[0];
- }
-
- private static int requiredCapacity(int valueCount, int valuesPerBlock) {
- return valueCount / valuesPerBlock
- + (valueCount % valuesPerBlock == 0 ? 0 : 1);
- }
-
- private int blockOffset(int offset) {
- return offset / valuesPerBlock;
- }
-
- private int offsetInBlock(int offset) {
- return offset % valuesPerBlock;
}
@Override
- public long get(int index) {
- final int o = blockOffset(index);
- final int b = offsetInBlock(index);
+ public void clear() {
+ Arrays.fill(blocks, 0L);
+ }
- return (blocks[o] >>> shifts[b]) & readMask;
+ public long ramBytesUsed() {
+ return RamUsageEstimator.sizeOf(blocks);
}
@Override
@@ -127,7 +72,8 @@ final class Packed64SingleBlock extends
final int originalIndex = index;
// go to the next block boundary
- final int offsetInBlock = offsetInBlock(index);
+ final int valuesPerBlock = 64 / bitsPerValue;
+ final int offsetInBlock = index % valuesPerBlock;
if (offsetInBlock != 0) {
for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
arr[off++] = get(index++);
@@ -139,16 +85,15 @@ final class Packed64SingleBlock extends
}
// bulk get
- assert offsetInBlock(index) == 0;
- final int startBlock = blockOffset(index);
- final int endBlock = blockOffset(index + len);
- final int diff = (endBlock - startBlock) * valuesPerBlock;
+ assert index % valuesPerBlock == 0;
+ final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);
+ assert op.blocks() == 1;
+ assert op.values() == valuesPerBlock;
+ final int blockIndex = index / valuesPerBlock;
+ final int nblocks = (index + len) / valuesPerBlock - blockIndex;
+ op.get(blocks, blockIndex, arr, off, nblocks);
+ final int diff = nblocks * valuesPerBlock;
index += diff; len -= diff;
- for (int block = startBlock; block < endBlock; ++block) {
- for (int i = 0; i < valuesPerBlock; ++i) {
- arr[off++] = (blocks[block] >> shifts[i]) & readMask;
- }
- }
if (index > originalIndex) {
// stay at the block boundary
@@ -162,14 +107,6 @@ final class Packed64SingleBlock extends
}
@Override
- public void set(int index, long value) {
- final int o = blockOffset(index);
- final int b = offsetInBlock(index);
-
- blocks[o] = (blocks[o] & writeMasks[b]) | (value << shifts[b]);
- }
-
- @Override
public int set(int index, long[] arr, int off, int len) {
assert len > 0 : "len must be > 0 (got " + len + ")";
assert index >= 0 && index < valueCount;
@@ -179,7 +116,8 @@ final class Packed64SingleBlock extends
final int originalIndex = index;
// go to the next block boundary
- final int offsetInBlock = offsetInBlock(index);
+ final int valuesPerBlock = 64 / bitsPerValue;
+ final int offsetInBlock = index % valuesPerBlock;
if (offsetInBlock != 0) {
for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
set(index++, arr[off++]);
@@ -191,18 +129,15 @@ final class Packed64SingleBlock extends
}
// bulk set
- assert offsetInBlock(index) == 0;
- final int startBlock = blockOffset(index);
- final int endBlock = blockOffset(index + len);
- final int diff = (endBlock - startBlock) * valuesPerBlock;
+ assert index % valuesPerBlock == 0;
+ final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);
+ assert op.blocks() == 1;
+ assert op.values() == valuesPerBlock;
+ final int blockIndex = index / valuesPerBlock;
+ final int nblocks = (index + len) / valuesPerBlock - blockIndex;
+ op.set(blocks, blockIndex, arr, off, nblocks);
+ final int diff = nblocks * valuesPerBlock;
index += diff; len -= diff;
- for (int block = startBlock; block < endBlock; ++block) {
- long next = 0L;
- for (int i = 0; i < valuesPerBlock; ++i) {
- next |= (arr[off++] << shifts[i]);
- }
- blocks[block] = next;
- }
if (index > originalIndex) {
// stay at the block boundary
@@ -219,8 +154,9 @@ final class Packed64SingleBlock extends
public void fill(int fromIndex, int toIndex, long val) {
assert fromIndex >= 0;
assert fromIndex <= toIndex;
- assert (val & readMask) == val;
+ assert PackedInts.bitsRequired(val) <= bitsPerValue;
+ final int valuesPerBlock = 64 / bitsPerValue;
if (toIndex - fromIndex <= valuesPerBlock << 1) {
// there needs to be at least one full block to set for the block
// approach to be worth trying
@@ -229,22 +165,22 @@ final class Packed64SingleBlock extends
}
// set values naively until the next block start
- int fromOffsetInBlock = offsetInBlock(fromIndex);
+ int fromOffsetInBlock = fromIndex % valuesPerBlock;
if (fromOffsetInBlock != 0) {
for (int i = fromOffsetInBlock; i < valuesPerBlock; ++i) {
set(fromIndex++, val);
}
- assert offsetInBlock(fromIndex) == 0;
+ assert fromIndex % valuesPerBlock == 0;
}
// bulk set of the inner blocks
- final int fromBlock = blockOffset(fromIndex);
- final int toBlock = blockOffset(toIndex);
+ final int fromBlock = fromIndex / valuesPerBlock;
+ final int toBlock = toIndex / valuesPerBlock;
assert fromBlock * valuesPerBlock == fromIndex;
long blockValue = 0L;
for (int i = 0; i < valuesPerBlock; ++i) {
- blockValue = blockValue | (val << shifts[i]);
+ blockValue = blockValue | (val << (i * bitsPerValue));
}
Arrays.fill(blocks, fromBlock, toBlock, blockValue);
@@ -255,17 +191,8 @@ final class Packed64SingleBlock extends
}
@Override
- public void clear() {
- Arrays.fill(blocks, 0L);
- }
-
- public long ramBytesUsed() {
- return RamUsageEstimator.sizeOf(blocks);
- }
-
- @Override
- protected int getFormat() {
- return PackedInts.PACKED_SINGLE_BLOCK;
+ protected PackedInts.Format getFormat() {
+ return PackedInts.Format.PACKED_SINGLE_BLOCK;
}
@Override
@@ -274,4 +201,384 @@ final class Packed64SingleBlock extends
+ ", size=" + size() + ", elements.length=" + blocks.length + ")";
}
+ public static Packed64SingleBlock create(DataInput in,
+ int valueCount, int bitsPerValue) throws IOException {
+ Packed64SingleBlock reader = create(valueCount, bitsPerValue);
+ for (int i = 0; i < reader.blocks.length; ++i) {
+ reader.blocks[i] = in.readLong();
+ }
+ return reader;
+ }
+
+ public static Packed64SingleBlock create(int valueCount, int bitsPerValue) {
+ switch (bitsPerValue) {
+ case 1:
+ return new Packed64SingleBlock1(valueCount);
+ case 2:
+ return new Packed64SingleBlock2(valueCount);
+ case 3:
+ return new Packed64SingleBlock3(valueCount);
+ case 4:
+ return new Packed64SingleBlock4(valueCount);
+ case 5:
+ return new Packed64SingleBlock5(valueCount);
+ case 6:
+ return new Packed64SingleBlock6(valueCount);
+ case 7:
+ return new Packed64SingleBlock7(valueCount);
+ case 8:
+ return new Packed64SingleBlock8(valueCount);
+ case 9:
+ return new Packed64SingleBlock9(valueCount);
+ case 10:
+ return new Packed64SingleBlock10(valueCount);
+ case 12:
+ return new Packed64SingleBlock12(valueCount);
+ case 16:
+ return new Packed64SingleBlock16(valueCount);
+ case 21:
+ return new Packed64SingleBlock21(valueCount);
+ case 32:
+ return new Packed64SingleBlock32(valueCount);
+ default:
+ throw new IllegalArgumentException("Unsupported number of bits per value: " + 32);
+ }
+ }
+
+ static class Packed64SingleBlock1 extends Packed64SingleBlock {
+
+ Packed64SingleBlock1(int valueCount) {
+ super(valueCount, 1);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index >>> 6;
+ final int b = index & 63;
+ final int shift = b << 0;
+ return (blocks[o] >>> shift) & 1L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index >>> 6;
+ final int b = index & 63;
+ final int shift = b << 0;
+ blocks[o] = (blocks[o] & ~(1L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock2 extends Packed64SingleBlock {
+
+ Packed64SingleBlock2(int valueCount) {
+ super(valueCount, 2);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index >>> 5;
+ final int b = index & 31;
+ final int shift = b << 1;
+ return (blocks[o] >>> shift) & 3L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index >>> 5;
+ final int b = index & 31;
+ final int shift = b << 1;
+ blocks[o] = (blocks[o] & ~(3L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock3 extends Packed64SingleBlock {
+
+ Packed64SingleBlock3(int valueCount) {
+ super(valueCount, 3);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 21;
+ final int b = index % 21;
+ final int shift = b * 3;
+ return (blocks[o] >>> shift) & 7L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 21;
+ final int b = index % 21;
+ final int shift = b * 3;
+ blocks[o] = (blocks[o] & ~(7L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock4 extends Packed64SingleBlock {
+
+ Packed64SingleBlock4(int valueCount) {
+ super(valueCount, 4);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index >>> 4;
+ final int b = index & 15;
+ final int shift = b << 2;
+ return (blocks[o] >>> shift) & 15L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index >>> 4;
+ final int b = index & 15;
+ final int shift = b << 2;
+ blocks[o] = (blocks[o] & ~(15L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock5 extends Packed64SingleBlock {
+
+ Packed64SingleBlock5(int valueCount) {
+ super(valueCount, 5);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 12;
+ final int b = index % 12;
+ final int shift = b * 5;
+ return (blocks[o] >>> shift) & 31L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 12;
+ final int b = index % 12;
+ final int shift = b * 5;
+ blocks[o] = (blocks[o] & ~(31L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock6 extends Packed64SingleBlock {
+
+ Packed64SingleBlock6(int valueCount) {
+ super(valueCount, 6);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 10;
+ final int b = index % 10;
+ final int shift = b * 6;
+ return (blocks[o] >>> shift) & 63L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 10;
+ final int b = index % 10;
+ final int shift = b * 6;
+ blocks[o] = (blocks[o] & ~(63L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock7 extends Packed64SingleBlock {
+
+ Packed64SingleBlock7(int valueCount) {
+ super(valueCount, 7);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 9;
+ final int b = index % 9;
+ final int shift = b * 7;
+ return (blocks[o] >>> shift) & 127L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 9;
+ final int b = index % 9;
+ final int shift = b * 7;
+ blocks[o] = (blocks[o] & ~(127L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock8 extends Packed64SingleBlock {
+
+ Packed64SingleBlock8(int valueCount) {
+ super(valueCount, 8);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index >>> 3;
+ final int b = index & 7;
+ final int shift = b << 3;
+ return (blocks[o] >>> shift) & 255L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index >>> 3;
+ final int b = index & 7;
+ final int shift = b << 3;
+ blocks[o] = (blocks[o] & ~(255L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock9 extends Packed64SingleBlock {
+
+ Packed64SingleBlock9(int valueCount) {
+ super(valueCount, 9);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 7;
+ final int b = index % 7;
+ final int shift = b * 9;
+ return (blocks[o] >>> shift) & 511L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 7;
+ final int b = index % 7;
+ final int shift = b * 9;
+ blocks[o] = (blocks[o] & ~(511L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock10 extends Packed64SingleBlock {
+
+ Packed64SingleBlock10(int valueCount) {
+ super(valueCount, 10);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 6;
+ final int b = index % 6;
+ final int shift = b * 10;
+ return (blocks[o] >>> shift) & 1023L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 6;
+ final int b = index % 6;
+ final int shift = b * 10;
+ blocks[o] = (blocks[o] & ~(1023L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock12 extends Packed64SingleBlock {
+
+ Packed64SingleBlock12(int valueCount) {
+ super(valueCount, 12);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 5;
+ final int b = index % 5;
+ final int shift = b * 12;
+ return (blocks[o] >>> shift) & 4095L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 5;
+ final int b = index % 5;
+ final int shift = b * 12;
+ blocks[o] = (blocks[o] & ~(4095L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock16 extends Packed64SingleBlock {
+
+ Packed64SingleBlock16(int valueCount) {
+ super(valueCount, 16);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index >>> 2;
+ final int b = index & 3;
+ final int shift = b << 4;
+ return (blocks[o] >>> shift) & 65535L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index >>> 2;
+ final int b = index & 3;
+ final int shift = b << 4;
+ blocks[o] = (blocks[o] & ~(65535L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock21 extends Packed64SingleBlock {
+
+ Packed64SingleBlock21(int valueCount) {
+ super(valueCount, 21);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index / 3;
+ final int b = index % 3;
+ final int shift = b * 21;
+ return (blocks[o] >>> shift) & 2097151L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index / 3;
+ final int b = index % 3;
+ final int shift = b * 21;
+ blocks[o] = (blocks[o] & ~(2097151L << shift)) | (value << shift);
+ }
+
+ }
+
+ static class Packed64SingleBlock32 extends Packed64SingleBlock {
+
+ Packed64SingleBlock32(int valueCount) {
+ super(valueCount, 32);
+ }
+
+ @Override
+ public long get(int index) {
+ final int o = index >>> 1;
+ final int b = index & 1;
+ final int shift = b << 5;
+ return (blocks[o] >>> shift) & 4294967295L;
+ }
+
+ @Override
+ public void set(int index, long value) {
+ final int o = index >>> 1;
+ final int b = index & 1;
+ final int shift = b << 5;
+ blocks[o] = (blocks[o] & ~(4294967295L << shift)) | (value << shift);
+ }
+
+ }
+
}
\ No newline at end of file
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java Thu Jul 19 15:58:54 2012
@@ -1,10 +1,6 @@
-package org.apache.lucene.util.packed;
-
-import java.io.IOException;
-import java.util.Arrays;
+// This file has been automatically generated, DO NOT EDIT
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.RamUsageEstimator;
+package org.apache.lucene.util.packed;
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
@@ -23,32 +19,38 @@ import org.apache.lucene.util.RamUsageEs
* limitations under the License.
*/
-/** 24 bitsPerValue backed by byte[] */
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.RamUsageEstimator;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+/**
+ * Packs integers into 3 bytes (24 bits per value).
+ * @lucene.internal
+ */
final class Packed8ThreeBlocks extends PackedInts.MutableImpl {
+ final byte[] blocks;
public static final int MAX_SIZE = Integer.MAX_VALUE / 3;
- private final byte[] blocks;
-
Packed8ThreeBlocks(int valueCount) {
super(valueCount, 24);
if (valueCount > MAX_SIZE) {
throw new ArrayIndexOutOfBoundsException("MAX_SIZE exceeded");
}
- this.blocks = new byte[3 * valueCount];
+ blocks = new byte[valueCount * 3];
}
Packed8ThreeBlocks(DataInput in, int valueCount) throws IOException {
this(valueCount);
- for (int i = 0; i < blocks.length; i++) {
+ for (int i = 0; i < 3 * valueCount; ++i) {
blocks[i] = in.readByte();
}
final int mod = blocks.length % 8;
if (mod != 0) {
- final int pad = 8 - mod;
- // round out long
- for (int i = 0; i < pad; i++) {
- in.readByte();
+ for (int i = mod; i < 8; ++i) {
+ in.readByte();
}
}
}
@@ -56,26 +58,55 @@ final class Packed8ThreeBlocks extends P
@Override
public long get(int index) {
final int o = index * 3;
- return (blocks[o] & 0xffL) << 16 | (blocks[o+1] & 0xffL) << 8 | (blocks[o+2] & 0xffL);
+ return (blocks[o] & 0xFFL) << 16 | (blocks[o+1] & 0xFFL) << 8 | (blocks[o+2] & 0xFFL);
+ }
+
+ @Override
+ public int get(int index, long[] arr, int off, int len) {
+ assert len > 0 : "len must be > 0 (got " + len + ")";
+ assert index >= 0 && index < valueCount;
+ assert off + len <= arr.length;
+
+ final int gets = Math.min(valueCount - index, len);
+ for (int i = index * 3, end = (index + gets) * 3; i < end; i+=3) {
+ arr[off++] = (blocks[i] & 0xFFL) << 16 | (blocks[i+1] & 0xFFL) << 8 | (blocks[i+2] & 0xFFL);
+ }
+ return gets;
}
@Override
public void set(int index, long value) {
final int o = index * 3;
+ blocks[o] = (byte) (value >>> 16);
+ blocks[o+1] = (byte) (value >>> 8);
blocks[o+2] = (byte) value;
- blocks[o+1] = (byte) (value >> 8);
- blocks[o] = (byte) (value >> 16);
+ }
+
+ @Override
+ public int set(int index, long[] arr, int off, int len) {
+ assert len > 0 : "len must be > 0 (got " + len + ")";
+ assert index >= 0 && index < valueCount;
+ assert off + len <= arr.length;
+
+ final int sets = Math.min(valueCount - index, len);
+ for (int i = off, o = index * 3, end = off + sets; i < end; ++i) {
+ final long value = arr[i];
+ blocks[o++] = (byte) (value >>> 16);
+ blocks[o++] = (byte) (value >>> 8);
+ blocks[o++] = (byte) value;
+ }
+ return sets;
}
@Override
public void fill(int fromIndex, int toIndex, long val) {
- byte block1 = (byte) (val >> 16);
- byte block2 = (byte) (val >> 8);
- byte block3 = (byte) val;
- for (int i = fromIndex * 3, end = toIndex * 3; i < end; ) {
- blocks[i++] = block1;
- blocks[i++] = block2;
- blocks[i++] = block3;
+ final byte block1 = (byte) (val >>> 16);
+ final byte block2 = (byte) (val >>> 8);
+ final byte block3 = (byte) val;
+ for (int i = fromIndex * 3, end = toIndex * 3; i < end; i += 3) {
+ blocks[i] = block1;
+ blocks[i+1] = block2;
+ blocks[i+2] = block3;
}
}
@@ -93,5 +124,4 @@ final class Packed8ThreeBlocks extends P
return getClass().getSimpleName() + "(bitsPerValue=" + bitsPerValue
+ ", size=" + size() + ", elements.length=" + blocks.length + ")";
}
-
}
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java Thu Jul 19 15:58:54 2012
@@ -19,10 +19,11 @@ package org.apache.lucene.util.packed;
import java.io.Closeable;
+import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
import org.apache.lucene.store.IndexInput;
-import org.apache.lucene.util.CodecUtil;
+import org.apache.lucene.util.LongsRef;
import java.io.IOException;
@@ -34,7 +35,6 @@ import java.io.IOException;
*
* @lucene.internal
*/
-
public class PackedInts {
/**
@@ -62,12 +62,184 @@ public class PackedInts {
*/
public static final int DEFAULT_BUFFER_SIZE = 1024; // 1K
- private final static String CODEC_NAME = "PackedInts";
- private final static int VERSION_START = 0;
- private final static int VERSION_CURRENT = VERSION_START;
+ public final static String CODEC_NAME = "PackedInts";
+ public final static int VERSION_START = 0;
+ public final static int VERSION_CURRENT = VERSION_START;
+
+ /**
+ * A format to write packed ints.
+ *
+ * @lucene.internal
+ */
+ public enum Format {
+ /**
+ * Compact format, all bits are written contiguously.
+ */
+ PACKED(0) {
+
+ @Override
+ public int nblocks(int bitsPerValue, int values) {
+ return (int) Math.ceil((double) values * bitsPerValue / 64);
+ }
+
+ },
+
+ /**
+ * A format that may insert padding bits to improve encoding and decoding
+ * speed. Since this format doesn't support all possible bits per value, you
+ * should never use it directly, but rather use
+ * {@link PackedInts#fastestFormatAndBits(int, int, float)} to find the
+ * format that best suits your needs.
+ */
+ PACKED_SINGLE_BLOCK(1) {
+
+ @Override
+ public int nblocks(int bitsPerValue, int values) {
+ final int valuesPerBlock = 64 / bitsPerValue;
+ return (int) Math.ceil((double) values / valuesPerBlock);
+ }
+
+ @Override
+ public boolean isSupported(int bitsPerValue) {
+ return Packed64SingleBlock.isSupported(bitsPerValue);
+ }
+
+ @Override
+ public float overheadPerValue(int bitsPerValue) {
+ assert isSupported(bitsPerValue);
+ final int valuesPerBlock = 64 / bitsPerValue;
+ final int overhead = 64 % bitsPerValue;
+ return (float) overhead / valuesPerBlock;
+ }
+
+ };
+
+ /**
+ * Get a format according to its ID.
+ */
+ public static Format byId(int id) {
+ for (Format format : Format.values()) {
+ if (format.getId() == id) {
+ return format;
+ }
+ }
+ throw new IllegalArgumentException("Unknown format id: " + id);
+ }
+
+ private Format(int id) {
+ this.id = id;
+ }
+
+ public int id;
+
+ /**
+ * Returns the ID of the format.
+ */
+ public int getId() {
+ return id;
+ }
+
+ /**
+ * Computes how many blocks are needed to store <code>values</code> values
+ * of size <code>bitsPerValue</code>.
+ */
+ public abstract int nblocks(int bitsPerValue, int values);
+
+ /**
+ * Tests whether the provided number of bits per value is supported by the
+ * format.
+ */
+ public boolean isSupported(int bitsPerValue) {
+ return bitsPerValue >= 1 && bitsPerValue <= 64;
+ }
+
+ /**
+ * Returns the overhead per value, in bits.
+ */
+ public float overheadPerValue(int bitsPerValue) {
+ assert isSupported(bitsPerValue);
+ return 0f;
+ }
+
+ /**
+ * Returns the overhead ratio (<code>overhead per value / bits per value</code>).
+ */
+ public final float overheadRatio(int bitsPerValue) {
+ assert isSupported(bitsPerValue);
+ return overheadPerValue(bitsPerValue) / bitsPerValue;
+ }
+ }
+
+ /**
+ * Simple class that holds a format and a number of bits per value.
+ */
+ public static class FormatAndBits {
+ public final Format format;
+ public final int bitsPerValue;
+ public FormatAndBits(Format format, int bitsPerValue) {
+ this.format = format;
+ this.bitsPerValue = bitsPerValue;
+ }
+ }
+
+ /**
+ * Try to find the {@link Format} and number of bits per value that would
+ * restore from disk the fastest reader whose overhead is less than
+ * <code>acceptableOverheadRatio</code>.
+ * </p><p>
+ * The <code>acceptableOverheadRatio</code> parameter makes sense for
+ * random-access {@link Reader}s. In case you only plan to perform
+ * sequential access on this stream later on, you should probably use
+ * {@link PackedInts#COMPACT}.
+ * </p><p>
+ * If you don't know how many values you are going to write, use
+ * <code>valueCount = -1</code>.
+ */
+ public static FormatAndBits fastestFormatAndBits(int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
+ if (valueCount == -1) {
+ valueCount = Integer.MAX_VALUE;
+ }
+
+ acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
+ acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
+ float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits
- static final int PACKED = 0;
- static final int PACKED_SINGLE_BLOCK = 1;
+ int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
+
+ int actualBitsPerValue = -1;
+ Format format = Format.PACKED;
+
+ if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
+ actualBitsPerValue = 8;
+ } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
+ actualBitsPerValue = 16;
+ } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
+ actualBitsPerValue = 32;
+ } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
+ actualBitsPerValue = 64;
+ } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {
+ actualBitsPerValue = 24;
+ } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {
+ actualBitsPerValue = 48;
+ } else {
+ for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {
+ if (Format.PACKED_SINGLE_BLOCK.isSupported(bpv)) {
+ float overhead = Format.PACKED_SINGLE_BLOCK.overheadPerValue(bpv);
+ float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;
+ if (overhead <= acceptableOverhead) {
+ actualBitsPerValue = bpv;
+ format = Format.PACKED_SINGLE_BLOCK;
+ break;
+ }
+ }
+ }
+ if (actualBitsPerValue < 0) {
+ actualBitsPerValue = bitsPerValue;
+ }
+ }
+
+ return new FormatAndBits(format, actualBitsPerValue);
+ }
/**
* A read-only random access array of positive integers.
@@ -132,31 +304,40 @@ public class PackedInts {
public static interface ReaderIterator extends Closeable {
/** Returns next value */
long next() throws IOException;
+ /** Returns at least 1 and at most <code>count</code> next values,
+ * the returned ref MUST NOT be modified */
+ LongsRef next(int count) throws IOException;
/** Returns number of bits per value */
int getBitsPerValue();
/** Returns number of values */
int size();
/** Returns the current position */
int ord();
- /** Skips to the given ordinal and returns its value.
- * @return the value at the given position
- * @throws IOException if reading the value throws an IOException*/
- long advance(int ord) throws IOException;
}
static abstract class ReaderIteratorImpl implements ReaderIterator {
- protected final IndexInput in;
+ protected final DataInput in;
protected final int bitsPerValue;
protected final int valueCount;
- protected ReaderIteratorImpl(int valueCount, int bitsPerValue, IndexInput in) {
+ protected ReaderIteratorImpl(int valueCount, int bitsPerValue, DataInput in) {
this.in = in;
this.bitsPerValue = bitsPerValue;
this.valueCount = valueCount;
}
@Override
+ public long next() throws IOException {
+ LongsRef nextValues = next(1);
+ assert nextValues.length > 0;
+ final long result = nextValues.longs[nextValues.offset];
+ ++nextValues.offset;
+ --nextValues.length;
+ return result;
+ }
+
+ @Override
public int getBitsPerValue() {
return bitsPerValue;
}
@@ -168,7 +349,9 @@ public class PackedInts {
@Override
public void close() throws IOException {
- in.close();
+ if (in instanceof Closeable) {
+ ((Closeable) in).close();
+ }
}
}
@@ -217,7 +400,7 @@ public class PackedInts {
* A simple base for Readers that keeps track of valueCount and bitsPerValue.
* @lucene.internal
*/
- public static abstract class ReaderImpl implements Reader {
+ static abstract class ReaderImpl implements Reader {
protected final int bitsPerValue;
protected final int valueCount;
@@ -257,7 +440,7 @@ public class PackedInts {
}
- public static abstract class MutableImpl extends ReaderImpl implements Mutable {
+ static abstract class MutableImpl extends ReaderImpl implements Mutable {
protected MutableImpl(int valueCount, int bitsPerValue) {
super(valueCount, bitsPerValue);
@@ -283,13 +466,15 @@ public class PackedInts {
}
}
- protected int getFormat() {
- return PACKED;
+ protected Format getFormat() {
+ return Format.PACKED;
}
@Override
public void save(DataOutput out) throws IOException {
- Writer writer = getWriterByFormat(out, valueCount, bitsPerValue, getFormat());
+ Writer writer = getWriterNoHeader(out, getFormat(),
+ valueCount, bitsPerValue, DEFAULT_BUFFER_SIZE);
+ writer.writeHeader();
for (int i = 0; i < valueCount; ++i) {
writer.add(get(i));
}
@@ -302,121 +487,209 @@ public class PackedInts {
*/
public static abstract class Writer {
protected final DataOutput out;
- protected final int bitsPerValue;
protected final int valueCount;
+ protected final int bitsPerValue;
protected Writer(DataOutput out, int valueCount, int bitsPerValue)
throws IOException {
assert bitsPerValue <= 64;
-
+ assert valueCount >= 0 || valueCount == -1;
this.out = out;
this.valueCount = valueCount;
this.bitsPerValue = bitsPerValue;
+ }
+
+ void writeHeader() throws IOException {
+ assert valueCount != -1;
CodecUtil.writeHeader(out, CODEC_NAME, VERSION_CURRENT);
out.writeVInt(bitsPerValue);
out.writeVInt(valueCount);
- out.writeVInt(getFormat());
+ out.writeVInt(getFormat().getId());
}
- protected abstract int getFormat();
+ /** The format used to serialize values. */
+ protected abstract PackedInts.Format getFormat();
+
+ /** Add a value to the stream. */
public abstract void add(long v) throws IOException;
+
+ /** The number of bits per value. */
+ public final int bitsPerValue() {
+ return bitsPerValue;
+ }
+
+ /** Perform end-of-stream operations. */
public abstract void finish() throws IOException;
+
+ /**
+ * Returns the current ord in the stream (number of values that have been
+ * written so far minus one).
+ */
+ public abstract int ord();
}
/**
- * Retrieve PackedInt data from the DataInput and return a packed int
- * structure based on it.
+ * Expert: Restore a {@link Reader} from a stream without reading metadata at
+ * the beginning of the stream. This method is useful to restore data from
+ * streams which have been created using
+ * {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
*
- * @param in positioned at the beginning of a stored packed int structure.
- * @return a read only random access capable array of positive integers.
- * @throws IOException if the structure could not be retrieved.
+ * @param in the stream to read data from, positioned at the beginning of the packed values
+ * @param format the format used to serialize
+ * @param version the version used to serialize the data
+ * @param valueCount how many values the stream holds
+ * @param bitsPerValue the number of bits per value
+ * @return a Reader
+ * @throws IOException
+ * @see PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)
* @lucene.internal
*/
- public static Reader getReader(DataInput in) throws IOException {
- CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
- final int bitsPerValue = in.readVInt();
- assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
- final int valueCount = in.readVInt();
- final int format = in.readVInt();
-
+ public static Reader getReaderNoHeader(DataInput in, Format format, int version,
+ int valueCount, int bitsPerValue) throws IOException {
switch (format) {
+ case PACKED_SINGLE_BLOCK:
+ return Packed64SingleBlock.create(in, valueCount, bitsPerValue);
case PACKED:
switch (bitsPerValue) {
case 8:
return new Direct8(in, valueCount);
case 16:
return new Direct16(in, valueCount);
- case 24:
- return new Packed8ThreeBlocks(in, valueCount);
case 32:
return new Direct32(in, valueCount);
- case 48:
- return new Packed16ThreeBlocks(in, valueCount);
case 64:
return new Direct64(in, valueCount);
- default:
- return new Packed64(in, valueCount, bitsPerValue);
+ case 24:
+ if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
+ return new Packed8ThreeBlocks(in, valueCount);
+ }
+ break;
+ case 48:
+ if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
+ return new Packed16ThreeBlocks(in, valueCount);
+ }
+ break;
}
- case PACKED_SINGLE_BLOCK:
- return Packed64SingleBlock.create(in, valueCount, bitsPerValue);
+ return new Packed64(in, valueCount, bitsPerValue);
default:
throw new AssertionError("Unknwown Writer format: " + format);
}
}
/**
+ * Restore a {@link Reader} from a stream.
+ *
+ * @param in the stream to read data from
+ * @return a Reader
+ * @throws IOException
+ * @lucene.internal
+ */
+ public static Reader getReader(DataInput in) throws IOException {
+ final int version = CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_CURRENT);
+ final int bitsPerValue = in.readVInt();
+ assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
+ final int valueCount = in.readVInt();
+ final Format format = Format.byId(in.readVInt());
+
+ return getReaderNoHeader(in, format, version, valueCount, bitsPerValue);
+ }
+
+ /**
+ * Expert: Restore a {@link ReaderIterator} from a stream without reading
+ * metadata at the beginning of the stream. This method is useful to restore
+ * data from streams which have been created using
+ * {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
+ *
+ * @param in the stream to read data from, positioned at the beginning of the packed values
+ * @param format the format used to serialize
+ * @param version the version used to serialize the data
+ * @param valueCount how many values the stream holds
+ * @param bitsPerValue the number of bits per value
+ * @param mem how much memory the iterator is allowed to use to read-ahead (likely to speed up iteration)
+ * @return a ReaderIterator
+ * @throws IOException
+ * @see PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)
+ * @lucene.internal
+ */
+ public static ReaderIterator getReaderIteratorNoHeader(DataInput in, Format format, int version,
+ int valueCount, int bitsPerValue, int mem) throws IOException {
+ return new PackedReaderIterator(format, valueCount, bitsPerValue, in, mem);
+ }
+
+ /**
* Retrieve PackedInts as a {@link ReaderIterator}
* @param in positioned at the beginning of a stored packed int structure.
+ * @param mem how much memory the iterator is allowed to use to read-ahead (likely to speed up iteration)
* @return an iterator to access the values
* @throws IOException if the structure could not be retrieved.
* @lucene.internal
*/
- public static ReaderIterator getReaderIterator(IndexInput in) throws IOException {
- CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
+ public static ReaderIterator getReaderIterator(DataInput in, int mem) throws IOException {
+ final int version = CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_CURRENT);
final int bitsPerValue = in.readVInt();
assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
final int valueCount = in.readVInt();
- final int format = in.readVInt();
+ final Format format = Format.byId(in.readVInt());
+ return getReaderIteratorNoHeader(in, format, version, valueCount, bitsPerValue, mem);
+ }
+
+ /**
+ * Expert: Construct a direct {@link Reader} from a stream without reading
+ * metadata at the beginning of the stream. This method is useful to restore
+ * data from streams which have been created using
+ * {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
+ * </p><p>
+ * The returned reader will have very little memory overhead, but every call
+ * to {@link Reader#get(int)} is likely to perform a disk seek.
+ *
+ * @param in the stream to read data from
+ * @param format the format used to serialize
+ * @param version the version used to serialize the data
+ * @param valueCount how many values the stream holds
+ * @param bitsPerValue the number of bits per value
+ * @return a direct Reader
+ * @throws IOException
+ * @lucene.internal
+ */
+ public static Reader getDirectReaderNoHeader(IndexInput in, Format format,
+ int version, int valueCount, int bitsPerValue) throws IOException {
switch (format) {
case PACKED:
- return new PackedReaderIterator(valueCount, bitsPerValue, in);
+ return new DirectPackedReader(bitsPerValue, valueCount, in);
case PACKED_SINGLE_BLOCK:
- return new Packed64SingleBlockReaderIterator(valueCount, bitsPerValue, in);
+ return new DirectPacked64SingleBlockReader(bitsPerValue, valueCount, in);
default:
- throw new AssertionError("Unknwown Writer format: " + format);
+ throw new AssertionError("Unknwown format: " + format);
}
}
-
+
/**
- * Retrieve PackedInts.Reader that does not load values
- * into RAM but rather accesses all values via the
- * provided IndexInput.
- * @param in positioned at the beginning of a stored packed int structure.
- * @return an Reader to access the values
- * @throws IOException if the structure could not be retrieved.
+ * Construct a direct {@link Reader} from an {@link IndexInput}. This method
+ * is useful to restore data from streams which have been created using
+ * {@link PackedInts#getWriter(DataOutput, int, int, float)}.
+ * </p><p>
+ * The returned reader will have very little memory overhead, but every call
+ * to {@link Reader#get(int)} is likely to perform a disk seek.
+ *
+ * @param in the stream to read data from
+ * @return a direct Reader
+ * @throws IOException
* @lucene.internal
*/
public static Reader getDirectReader(IndexInput in) throws IOException {
- CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_START);
+ final int version = CodecUtil.checkHeader(in, CODEC_NAME, VERSION_START, VERSION_CURRENT);
final int bitsPerValue = in.readVInt();
assert bitsPerValue > 0 && bitsPerValue <= 64: "bitsPerValue=" + bitsPerValue;
final int valueCount = in.readVInt();
- final int format = in.readVInt();
- switch (format) {
- case PACKED:
- return new DirectPackedReader(bitsPerValue, valueCount, in);
- case PACKED_SINGLE_BLOCK:
- return new DirectPacked64SingleBlockReader(bitsPerValue, valueCount, in);
- default:
- throw new AssertionError("Unknwown Writer format: " + format);
- }
+ final Format format = Format.byId(in.readVInt());
+ return getDirectReaderNoHeader(in, format, version, valueCount, bitsPerValue);
}
/**
* Create a packed integer array with the given amount of values initialized
* to 0. the valueCount and the bitsPerValue cannot be changed after creation.
* All Mutables known by this factory are kept fully in RAM.
- *
+ * </p><p>
* Positive values of <code>acceptableOverheadRatio</code> will trade space
* for speed by selecting a faster but potentially less memory-efficient
* implementation. An <code>acceptableOverheadRatio</code> of
@@ -429,110 +702,134 @@ public class PackedInts {
* @param acceptableOverheadRatio an acceptable overhead
* ratio per value
* @return a mutable packed integer array
- * @throws java.io.IOException if the Mutable could not be created. With the
- * current implementations, this never happens, but the method
- * signature allows for future persistence-backed Mutables.
* @lucene.internal
*/
public static Mutable getMutable(int valueCount,
int bitsPerValue, float acceptableOverheadRatio) {
- acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
- acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
- float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits
-
- int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
+ assert valueCount >= 0;
- if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
- return new Direct8(valueCount);
- } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
- return new Direct16(valueCount);
- } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
- return new Direct32(valueCount);
- } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
- return new Direct64(valueCount);
- } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {
- return new Packed8ThreeBlocks(valueCount);
- } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {
- return new Packed16ThreeBlocks(valueCount);
- } else {
- for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {
- if (Packed64SingleBlock.isSupported(bpv)) {
- float overhead = Packed64SingleBlock.overheadPerValue(bpv);
- float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;
- if (overhead <= acceptableOverhead) {
- return Packed64SingleBlock.create(valueCount, bpv);
- }
+ final FormatAndBits formatAndBits = fastestFormatAndBits(valueCount, bitsPerValue, acceptableOverheadRatio);
+ switch (formatAndBits.format) {
+ case PACKED_SINGLE_BLOCK:
+ return Packed64SingleBlock.create(valueCount, formatAndBits.bitsPerValue);
+ case PACKED:
+ switch (formatAndBits.bitsPerValue) {
+ case 8:
+ return new Direct8(valueCount);
+ case 16:
+ return new Direct16(valueCount);
+ case 32:
+ return new Direct32(valueCount);
+ case 64:
+ return new Direct64(valueCount);
+ case 24:
+ if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
+ return new Packed8ThreeBlocks(valueCount);
+ }
+ break;
+ case 48:
+ if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
+ return new Packed16ThreeBlocks(valueCount);
+ }
+ break;
}
- }
- return new Packed64(valueCount, bitsPerValue);
+ return new Packed64(valueCount, formatAndBits.bitsPerValue);
+ default:
+ throw new AssertionError();
}
}
/**
- * Create a packed integer array writer for the given number of values at the
- * given bits/value. Writers append to the given IndexOutput and has very
- * low memory overhead.
+ * Expert: Create a packed integer array writer for the given output, format,
+ * value count, and number of bits per value.
+ * </p><p>
+ * The resulting stream will be long-aligned. This means that depending on
+ * the format which is used, up to 63 bits will be wasted. An easy way to
+ * make sure that no space is lost is to always use a <code>valueCount</code>
+ * that is a multiple of 64.
+ * </p><p>
+ * This method does not write any metadata to the stream, meaning that it is
+ * your responsibility to store it somewhere else in order to be able to
+ * recover data from the stream later on:
+ * <ul>
+ * <li><code>format</code> (using {@link Format#getId()}),</li>
+ * <li><code>valueCount</code>,</li>
+ * <li><code>bitsPerValue</code>,</li>
+ * <li>{@link #VERSION_CURRENT}.</li>
+ * </ul>
+ * </p><p>
+ * It is possible to start writing values without knowing how many of them you
+ * are actually going to write. To do this, just pass <code>-1</code> as
+ * <code>valueCount</code>. On the other hand, for any positive value of
+ * <code>valueCount</code>, the returned writer will make sure that you don't
+ * write more values than expected and pad the end of stream with zeros in
+ * case you have written less than <code>valueCount</code> when calling
+ * {@link Writer#finish()}.
+ * </p><p>
+ * The <code>mem</code> parameter lets you control how much memory can be used
+ * to buffer changes in memory before flushing to disk. High values of
+ * <code>mem</code> are likely to improve throughput. On the other hand, if
+ * speed is not that important to you, a value of <code>0</code> will use as
+ * little memory as possible and should already offer reasonable throughput.
*
- * Positive values of <code>acceptableOverheadRatio</code> will trade space
+ * @param out the data output
+ * @param format the format to use to serialize the values
+ * @param valueCount the number of values
+ * @param bitsPerValue the number of bits per value
+ * @param mem how much memory (in bytes) can be used to speed up serialization
+ * @return a Writer
+ * @throws IOException
+ * @see PackedInts#getReaderIteratorNoHeader(DataInput, Format, int, int, int, int)
+ * @see PackedInts#getReaderNoHeader(DataInput, Format, int, int, int)
+ * @lucene.internal
+ */
+ public static Writer getWriterNoHeader(
+ DataOutput out, Format format, int valueCount, int bitsPerValue, int mem) throws IOException {
+ return new PackedWriter(format, out, valueCount, bitsPerValue, mem);
+ }
+
+ /**
+ * Create a packed integer array writer for the given output, format, value
+ * count, and number of bits per value.
+ * </p><p>
+ * The resulting stream will be long-aligned. This means that depending on
+ * the format which is used under the hoods, up to 63 bits will be wasted.
+ * An easy way to make sure that no space is lost is to always use a
+ * <code>valueCount</code> that is a multiple of 64.
+ * </p><p>
+ * This method writes metadata to the stream, so that the resulting stream is
+ * sufficient to restore a {@link Reader} from it. You don't need to track
+ * <code>valueCount</code> or <code>bitsPerValue</code> by yourself. In case
+ * this is a problem, you should probably look at
+ * {@link #getWriterNoHeader(DataOutput, Format, int, int, int)}.
+ * </p><p>
+ * The <code>acceptableOverheadRatio</code> parameter controls how
+ * readers that will be restored from this stream trade space
* for speed by selecting a faster but potentially less memory-efficient
* implementation. An <code>acceptableOverheadRatio</code> of
* {@link PackedInts#COMPACT} will make sure that the most memory-efficient
* implementation is selected whereas {@link PackedInts#FASTEST} will make sure
- * that the fastest implementation is selected.
+ * that the fastest implementation is selected. In case you are only interested
+ * in reading this stream sequentially later on, you should probably use
+ * {@link PackedInts#COMPACT}.
*
- * @param out the destination for the produced bits.
- * @param valueCount the number of elements.
- * @param bitsPerValue the number of bits available for any given value.
+ * @param out the data output
+ * @param valueCount the number of values
+ * @param bitsPerValue the number of bits per value
* @param acceptableOverheadRatio an acceptable overhead ratio per value
- * @return a Writer ready for receiving values.
- * @throws IOException if bits could not be written to out.
+ * @return a Writer
+ * @throws IOException
* @lucene.internal
*/
public static Writer getWriter(DataOutput out,
int valueCount, int bitsPerValue, float acceptableOverheadRatio)
throws IOException {
- acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
- acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
- float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits
-
- int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;
-
- if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
- return getWriterByFormat(out, valueCount, 8, PACKED);
- } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
- return getWriterByFormat(out, valueCount, 16, PACKED);
- } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
- return getWriterByFormat(out, valueCount, 32, PACKED);
- } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
- return getWriterByFormat(out, valueCount, 64, PACKED);
- } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {
- return getWriterByFormat(out, valueCount, 24, PACKED);
- } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {
- return getWriterByFormat(out, valueCount, 48, PACKED);
- } else {
- for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {
- if (Packed64SingleBlock.isSupported(bpv)) {
- float overhead = Packed64SingleBlock.overheadPerValue(bpv);
- float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;
- if (overhead <= acceptableOverhead) {
- return getWriterByFormat(out, valueCount, bpv, PACKED_SINGLE_BLOCK);
- }
- }
- }
- return getWriterByFormat(out, valueCount, bitsPerValue, PACKED);
- }
- }
+ assert valueCount >= 0;
- private static Writer getWriterByFormat(DataOutput out,
- int valueCount, int bitsPerValue, int format) throws IOException {
- switch (format) {
- case PACKED:
- return new PackedWriter(out, valueCount, bitsPerValue);
- case PACKED_SINGLE_BLOCK:
- return new Packed64SingleBlockWriter(out, valueCount, bitsPerValue);
- default:
- throw new IllegalArgumentException("Unknown format " + format);
- }
+ final FormatAndBits formatAndBits = fastestFormatAndBits(valueCount, bitsPerValue, acceptableOverheadRatio);
+ final Writer writer = getWriterNoHeader(out, formatAndBits.format, valueCount, formatAndBits.bitsPerValue, DEFAULT_BUFFER_SIZE);
+ writer.writeHeader();
+ return writer;
}
/** Returns how many bits are required to hold values up
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedReaderIterator.java Thu Jul 19 15:58:54 2012
@@ -17,77 +17,71 @@ package org.apache.lucene.util.packed;
* limitations under the License.
*/
-import org.apache.lucene.store.IndexInput;
-
+import java.io.EOFException;
import java.io.IOException;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.LongsRef;
+
final class PackedReaderIterator extends PackedInts.ReaderIteratorImpl {
- private long pending;
- private int pendingBitsLeft;
- private int position = -1;
- // masks[n-1] masks for bottom n bits
- private final long[] masks;
+ final PackedInts.Format format;
+ final BulkOperation bulkOperation;
+ final long[] nextBlocks;
+ final LongsRef nextValues;
+ final int iterations;
+ int position;
- public PackedReaderIterator(int valueCount, int bitsPerValue, IndexInput in)
- throws IOException {
+ PackedReaderIterator(PackedInts.Format format, int valueCount, int bitsPerValue, DataInput in, int mem) {
super(valueCount, bitsPerValue, in);
+ this.format = format;
+ bulkOperation = BulkOperation.of(format, bitsPerValue);
+ iterations = bulkOperation.computeIterations(valueCount, mem);
+ assert iterations > 0;
+ nextBlocks = new long[iterations * bulkOperation.blocks()];
+ nextValues = new LongsRef(new long[iterations * bulkOperation.values()], 0, 0);
+ assert iterations * bulkOperation.values() == nextValues.longs.length;
+ assert iterations * bulkOperation.blocks() == nextBlocks.length;
+ nextValues.offset = nextValues.longs.length;
+ position = -1;
+ }
- masks = new long[bitsPerValue];
+ @Override
+ public LongsRef next(int count) throws IOException {
+ assert nextValues.length >= 0;
+ assert count > 0;
+ assert nextValues.offset + nextValues.length <= nextValues.longs.length;
+
+ nextValues.offset += nextValues.length;
- long v = 1;
- for (int i = 0; i < bitsPerValue; i++) {
- v *= 2;
- masks[i] = v - 1;
+ final int remaining = valueCount - position - 1;
+ if (remaining <= 0) {
+ throw new EOFException();
}
- }
+ count = Math.min(remaining, count);
- public long next() throws IOException {
- if (pendingBitsLeft == 0) {
- pending = in.readLong();
- pendingBitsLeft = 64;
- }
-
- final long result;
- if (pendingBitsLeft >= bitsPerValue) { // not split
- result = (pending >> (pendingBitsLeft - bitsPerValue)) & masks[bitsPerValue-1];
- pendingBitsLeft -= bitsPerValue;
- } else { // split
- final int bits1 = bitsPerValue - pendingBitsLeft;
- final long result1 = (pending & masks[pendingBitsLeft-1]) << bits1;
- pending = in.readLong();
- final long result2 = (pending >> (64 - bits1)) & masks[bits1-1];
- pendingBitsLeft = 64 + pendingBitsLeft - bitsPerValue;
- result = result1 | result2;
+ if (nextValues.offset == nextValues.longs.length) {
+ final int remainingBlocks = format.nblocks(bitsPerValue, remaining);
+ final int blocksToRead = Math.min(remainingBlocks, nextBlocks.length);
+ for (int i = 0; i < blocksToRead; ++i) {
+ nextBlocks[i] = in.readLong();
+ }
+ for (int i = blocksToRead; i < nextBlocks.length; ++i) {
+ nextBlocks[i] = 0L;
+ }
+
+ bulkOperation.get(nextBlocks, 0, nextValues.longs, 0, iterations);
+ nextValues.offset = 0;
}
-
- ++position;
- return result;
+
+ nextValues.length = Math.min(nextValues.longs.length - nextValues.offset, count);
+ position += nextValues.length;
+ return nextValues;
}
+ @Override
public int ord() {
return position;
}
- public long advance(final int ord) throws IOException{
- assert ord < valueCount : "ord must be less than valueCount";
- assert ord > position : "ord must be greater than the current position";
- final long bits = (long) bitsPerValue;
- final int posToSkip = ord - 1 - position;
- final long bitsToSkip = (bits * (long)posToSkip);
- if (bitsToSkip < pendingBitsLeft) { // enough bits left - no seek required
- pendingBitsLeft -= bitsToSkip;
- } else {
- final long skip = bitsToSkip-pendingBitsLeft;
- final long closestByte = (skip >> 6) << 3;
- if (closestByte != 0) { // need to seek
- final long filePointer = in.getFilePointer();
- in.seek(filePointer + closestByte);
- }
- pending = in.readLong();
- pendingBitsLeft = 64 - (int)(skip % 64);
- }
- position = ord-1;
- return next();
- }
}
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/PackedWriter.java Thu Jul 19 15:58:54 2012
@@ -19,101 +19,79 @@ package org.apache.lucene.util.packed;
import org.apache.lucene.store.DataOutput;
+import java.io.EOFException;
import java.io.IOException;
// Packs high order byte first, to match
// IndexOutput.writeInt/Long/Short byte order
-/**
- * Generic writer for space-optimal packed values. The resulting bits can be
- * used directly by Packed32, Packed64 and PackedDirect* and will always be
- * long-aligned.
- */
-
-class PackedWriter extends PackedInts.Writer {
- private long pending;
- private int pendingBitPos;
-
- // masks[n-1] masks for bottom n bits
- private final long[] masks;
- private int written = 0;
+final class PackedWriter extends PackedInts.Writer {
- public PackedWriter(DataOutput out, int valueCount, int bitsPerValue)
- throws IOException {
- super(out, valueCount, bitsPerValue);
-
- pendingBitPos = 64;
- masks = new long[bitsPerValue - 1];
+ boolean finished;
+ final PackedInts.Format format;
+ final BulkOperation bulkOperation;
+ final long[] nextBlocks;
+ final long[] nextValues;
+ final int iterations;
+ int off;
+ int written;
- long v = 1;
- for (int i = 0; i < bitsPerValue - 1; i++) {
- v *= 2;
- masks[i] = v - 1;
- }
+ PackedWriter(PackedInts.Format format, DataOutput out, int valueCount, int bitsPerValue, int mem)
+ throws IOException {
+ super(out, valueCount, bitsPerValue);
+ this.format = format;
+ bulkOperation = BulkOperation.of(format, bitsPerValue);
+ iterations = bulkOperation.computeIterations(valueCount, mem);
+ nextBlocks = new long[iterations * bulkOperation.blocks()];
+ nextValues = new long[iterations * bulkOperation.values()];
+ off = 0;
+ written = 0;
+ finished = false;
}
@Override
- protected int getFormat() {
- return PackedInts.PACKED;
+ protected PackedInts.Format getFormat() {
+ return format;
}
- /**
- * Do not call this after finish
- */
@Override
public void add(long v) throws IOException {
- assert v <= PackedInts.maxValue(bitsPerValue) : "v=" + v
- + " maxValue=" + PackedInts.maxValue(bitsPerValue);
- assert v >= 0;
- //System.out.println(" packedw add v=" + v + " pendingBitPos=" + pendingBitPos);
-
- // TODO
- if (pendingBitPos >= bitsPerValue) {
- // not split
-
- // write-once, so we can |= w/o first masking to 0s
- pending |= v << (pendingBitPos - bitsPerValue);
- if (pendingBitPos == bitsPerValue) {
- // flush
- out.writeLong(pending);
- pending = 0;
- pendingBitPos = 64;
- } else {
- pendingBitPos -= bitsPerValue;
- }
-
- } else {
- // split
-
- // write top pendingBitPos bits of value into bottom bits of pending
- pending |= (v >> (bitsPerValue - pendingBitPos)) & masks[pendingBitPos - 1];
- //System.out.println(" part1 (v >> " + (bitsPerValue - pendingBitPos) + ") & " + masks[pendingBitPos-1]);
-
- // flush
- out.writeLong(pending);
-
- // write bottom (bitsPerValue - pendingBitPos) bits of value into top bits of pending
- pendingBitPos = 64 - bitsPerValue + pendingBitPos;
- //System.out.println(" part2 v << " + pendingBitPos);
- pending = (v << pendingBitPos);
+ assert v >= 0 && v <= PackedInts.maxValue(bitsPerValue);
+ assert !finished;
+ if (valueCount != -1 && written >= valueCount) {
+ throw new EOFException("Writing past end of stream");
+ }
+ nextValues[off++] = v;
+ if (off == nextValues.length) {
+ flush(nextValues.length);
+ off = 0;
}
- written++;
+ ++written;
}
@Override
public void finish() throws IOException {
- while (written < valueCount) {
- add(0L); // Auto flush
+ assert !finished;
+ if (valueCount != -1) {
+ while (written < valueCount) {
+ add(0L);
+ }
}
+ flush(off);
+ finished = true;
+ }
- if (pendingBitPos != 64) {
- out.writeLong(pending);
+ private void flush(int nvalues) throws IOException {
+ bulkOperation.set(nextBlocks, 0, nextValues, 0, iterations);
+ final int blocks = format.nblocks(bitsPerValue, nvalues);
+ for (int i = 0; i < blocks; ++i) {
+ out.writeLong(nextBlocks[i]);
}
+ off = 0;
}
@Override
- public String toString() {
- return "PackedWriter(written " + written + "/" + valueCount + " with "
- + bitsPerValue + " bits/value)";
+ public int ord() {
+ return written - 1;
}
}
Modified: lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html
URL: http://svn.apache.org/viewvc/lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html?rev=1363400&r1=1363399&r2=1363400&view=diff
==============================================================================
--- lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html (original)
+++ lucene/dev/branches/pforcodec_3892/lucene/core/src/java/org/apache/lucene/util/packed/package.html Thu Jul 19 15:58:54 2012
@@ -19,9 +19,16 @@
<head></head>
<body bgcolor="white">
+<p>Packed integer arrays and streams.</p>
+
<p>
- The packed package provides random access capable arrays of positive longs.
- The implementations provides different trade offs between memory usage and
+ The packed package provides
+ <ul>
+ <li>sequential and random access capable arrays of positive longs,</li>
+ <li>routines for efficient serialization and deserialization of streams of packed integers.</li>
+ </ul>
+
+ The implementations provide different trade-offs between memory usage and
access speed. The standard usage scenario is replacing large int or long
arrays in order to reduce the memory footprint.
</p><p>