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/06/02 20:36:28 UTC
svn commit: r1345545 - in /lucene/dev/branches/branch_4x: ./ lucene/
lucene/core/ lucene/core/src/java/org/apache/lucene/index/
lucene/core/src/java/org/apache/lucene/util/packed/
lucene/core/src/test/org/apache/lucene/util/packed/
Author: mikemccand
Date: Sat Jun 2 18:36:27 2012
New Revision: 1345545
URL: http://svn.apache.org/viewvc?rev=1345545&view=rev
Log:
LUCENE-4098: add bulk get/set methods to PackedInts
Modified:
lucene/dev/branches/branch_4x/ (props changed)
lucene/dev/branches/branch_4x/lucene/ (props changed)
lucene/dev/branches/branch_4x/lucene/CHANGES.txt (contents, props changed)
lucene/dev/branches/branch_4x/lucene/core/ (props changed)
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocValues.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct16.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct32.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct64.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct8.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/GrowableWriter.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java
lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java
lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/packed/TestPackedInts.java
Modified: lucene/dev/branches/branch_4x/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/CHANGES.txt?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/CHANGES.txt (original)
+++ lucene/dev/branches/branch_4x/lucene/CHANGES.txt Sat Jun 2 18:36:27 2012
@@ -946,7 +946,10 @@ Optimizations
* LUCENE-2357: Reduce transient RAM usage when merging segments in
IndexWriter. (Adrien Grand via Mike McCandless)
-
+
+* LUCENE-4098: Add bulk get/set methods to PackedInts (Adrien Grand
+ via Mike McCandless)
+
Bug fixes
* LUCENE-2803: The FieldCache can miss values if an entry for a reader
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocValues.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocValues.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocValues.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/DocValues.java Sat Jun 2 18:36:27 2012
@@ -18,6 +18,7 @@ package org.apache.lucene.index;
*/
import java.io.Closeable;
import java.io.IOException;
+import java.util.Arrays;
import java.util.Comparator;
import org.apache.lucene.codecs.DocValuesFormat;
@@ -392,6 +393,13 @@ public abstract class DocValues implemen
public Object getArray() {
return null;
}
+
+ @Override
+ public int get(int index, long[] arr, int off, int len) {
+ len = Math.min(len, size() - index);
+ Arrays.fill(arr, off, off+len, 0);
+ return len;
+ }
};
return new SortedSource(type, BytesRef.getUTF8SortedAsUnicodeComparator()) {
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct16.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct16.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct16.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct16.java Sat Jun 2 18:36:27 2012
@@ -28,9 +28,8 @@ import java.util.Arrays;
* @lucene.internal
*/
-class Direct16 extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
- private short[] values;
+class Direct16 extends PackedInts.MutableImpl {
+ private final short[] values;
private static final int BITS_PER_VALUE = 16;
public Direct16(int valueCount) {
@@ -77,6 +76,12 @@ class Direct16 extends PackedInts.Reader
values[index] = (short)(value & 0xFFFF);
}
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ assert (val & 0xffffL) == val;
+ Arrays.fill(values, fromIndex, toIndex, (short) val);
+ }
+
public long ramBytesUsed() {
return RamUsageEstimator.sizeOf(values);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct32.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct32.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct32.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct32.java Sat Jun 2 18:36:27 2012
@@ -28,9 +28,8 @@ import java.util.Arrays;
* @lucene.internal
*/
-class Direct32 extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
- private int[] values;
+class Direct32 extends PackedInts.MutableImpl {
+ private final int[] values;
private static final int BITS_PER_VALUE = 32;
public Direct32(int valueCount) {
@@ -73,6 +72,12 @@ class Direct32 extends PackedInts.Reader
values[index] = (int)(value & 0xFFFFFFFF);
}
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ assert (val & 0xffffffffL) == val;
+ Arrays.fill(values, fromIndex, toIndex, (int) val);
+ }
+
public long ramBytesUsed() {
return RamUsageEstimator.sizeOf(values);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct64.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct64.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct64.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct64.java Sat Jun 2 18:36:27 2012
@@ -28,9 +28,8 @@ import java.util.Arrays;
* @lucene.internal
*/
-class Direct64 extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
- private long[] values;
+class Direct64 extends PackedInts.MutableImpl {
+ private final long[] values;
private static final int BITS_PER_VALUE = 64;
public Direct64(int valueCount) {
@@ -69,6 +68,11 @@ class Direct64 extends PackedInts.Reader
values[index] = value;
}
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ Arrays.fill(values, fromIndex, toIndex, val);
+ }
+
public long ramBytesUsed() {
return RamUsageEstimator.sizeOf(values);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct8.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct8.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct8.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Direct8.java Sat Jun 2 18:36:27 2012
@@ -28,9 +28,8 @@ import java.util.Arrays;
* @lucene.internal
*/
-class Direct8 extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
- private byte[] values;
+class Direct8 extends PackedInts.MutableImpl {
+ private final byte[] values;
private static final int BITS_PER_VALUE = 8;
public Direct8(int valueCount) {
@@ -78,6 +77,12 @@ class Direct8 extends PackedInts.ReaderI
values[index] = (byte)(value & 0xFF);
}
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ assert (val & 0xffL) == val;
+ Arrays.fill(values, fromIndex, toIndex, (byte) val);
+ }
+
public long ramBytesUsed() {
return RamUsageEstimator.sizeOf(values);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/GrowableWriter.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/GrowableWriter.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/GrowableWriter.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/GrowableWriter.java Sat Jun 2 18:36:27 2012
@@ -62,21 +62,21 @@ public class GrowableWriter implements P
return current.hasArray();
}
- public void set(int index, long value) {
- if (value >= currentMaxValue) {
- int bpv = getBitsPerValue();
- while(currentMaxValue <= value && currentMaxValue != Long.MAX_VALUE) {
- bpv++;
- currentMaxValue *= 2;
- }
- final int valueCount = size();
- PackedInts.Mutable next = PackedInts.getMutable(valueCount, bpv, acceptableOverheadRatio);
- for(int i=0;i<valueCount;i++) {
- next.set(i, current.get(i));
- }
- current = next;
- currentMaxValue = PackedInts.maxValue(current.getBitsPerValue());
+ private void ensureCapacity(long value) {
+ assert value >= 0;
+ if (value <= currentMaxValue) {
+ return;
}
+ final int bitsRequired = PackedInts.bitsRequired(value);
+ final int valueCount = size();
+ PackedInts.Mutable next = PackedInts.getMutable(valueCount, bitsRequired, acceptableOverheadRatio);
+ PackedInts.copy(current, 0, next, 0, valueCount, PackedInts.DEFAULT_BUFFER_SIZE);
+ current = next;
+ currentMaxValue = PackedInts.maxValue(current.getBitsPerValue());
+ }
+
+ public void set(int index, long value) {
+ ensureCapacity(value);
current.set(index, value);
}
@@ -87,10 +87,28 @@ public class GrowableWriter implements P
public GrowableWriter resize(int newSize) {
GrowableWriter next = new GrowableWriter(getBitsPerValue(), newSize, acceptableOverheadRatio);
final int limit = Math.min(size(), newSize);
- for(int i=0;i<limit;i++) {
- next.set(i, get(i));
- }
+ PackedInts.copy(current, 0, next, 0, limit, PackedInts.DEFAULT_BUFFER_SIZE);
return next;
}
+ public int get(int index, long[] arr, int off, int len) {
+ return current.get(index, arr, off, len);
+ }
+
+ @Override
+ public int set(int index, long[] arr, int off, int len) {
+ long max = 0;
+ for (int i = off, end = off + len; i < end; ++i) {
+ max |= arr[i];
+ }
+ ensureCapacity(max);
+ return current.set(index, arr, off, len);
+ }
+
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ ensureCapacity(val);
+ current.fill(fromIndex, toIndex, val);
+ }
+
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed16ThreeBlocks.java Sat Jun 2 18:36:27 2012
@@ -24,8 +24,7 @@ import org.apache.lucene.util.RamUsageEs
*/
/** 48 bitsPerValue backed by short[] */
-final class Packed16ThreeBlocks extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
+final class Packed16ThreeBlocks extends PackedInts.MutableImpl {
public static final int MAX_SIZE = Integer.MAX_VALUE / 3;
@@ -69,6 +68,18 @@ final class Packed16ThreeBlocks extends
}
@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;
+ }
+ }
+
+ @Override
public void clear() {
Arrays.fill(blocks, (short) 0);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64.java Sat Jun 2 18:36:27 2012
@@ -32,7 +32,7 @@ import java.util.Arrays;
* sacrificing code clarity to achieve better performance.
*/
-class Packed64 extends PackedInts.ReaderImpl implements PackedInts.Mutable {
+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
@@ -100,8 +100,18 @@ class Packed64 extends PackedInts.Reader
}
}
+ 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 */
- private long[] blocks;
+ private final long[] blocks;
// Cached calculations
private int maxPos; // blocks.length * BLOCK_SIZE / elementBits - 1
@@ -210,6 +220,56 @@ class Packed64 extends PackedInts.Reader
return RamUsageEstimator.sizeOf(blocks);
}
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ assert PackedInts.bitsRequired(val) <= getBitsPerValue();
+ assert fromIndex <= toIndex;
+
+ // minimum number of values that use an exact number of full blocks
+ final int nAlignedValues = 64 / pgcd(64, bitsPerValue);
+ final int span = toIndex - fromIndex;
+ if (span <= 3 * nAlignedValues) {
+ // there needs be at least 2 * nAlignedValues aligned values for the
+ // block approach to be worth trying
+ super.fill(fromIndex, toIndex, val);
+ return;
+ }
+
+ // fill the first values naively until the next block start
+ final int fromIndexModNAlignedValues = fromIndex % nAlignedValues;
+ if (fromIndexModNAlignedValues != 0) {
+ for (int i = fromIndexModNAlignedValues; i < nAlignedValues; ++i) {
+ set(fromIndex++, val);
+ }
+ }
+ assert fromIndex % nAlignedValues == 0;
+
+ // compute the long[] blocks for nAlignedValues consecutive values and
+ // use them to set as many values as possible without applying any mask
+ // or shift
+ final int nAlignedBlocks = (nAlignedValues * bitsPerValue) >> 6;
+ final long[] nAlignedValuesBlocks;
+ {
+ Packed64 values = new Packed64(nAlignedValues, bitsPerValue);
+ for (int i = 0; i < nAlignedValues; ++i) {
+ values.set(i, val);
+ }
+ nAlignedValuesBlocks = values.blocks;
+ assert nAlignedBlocks <= nAlignedValuesBlocks.length;
+ }
+ final int startBlock = (int) (((long) fromIndex * bitsPerValue) >>> 6);
+ final int endBlock = (int) (((long) toIndex * bitsPerValue) >>> 6);
+ for (int block = startBlock; block < endBlock; ++block) {
+ final long blockValue = nAlignedValuesBlocks[block % nAlignedBlocks];
+ blocks[block] = blockValue;
+ }
+
+ // fill the gap
+ for (int i = (int) (((long) endBlock << 6) / bitsPerValue); i < toIndex; ++i) {
+ set(i, val);
+ }
+ }
+
public void clear() {
Arrays.fill(blocks, 0L);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed64SingleBlock.java Sat Jun 2 18:36:27 2012
@@ -1,11 +1,5 @@
package org.apache.lucene.util.packed;
-import java.io.IOException;
-import java.util.Arrays;
-
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.RamUsageEstimator;
-
/**
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with this
@@ -23,13 +17,18 @@ import org.apache.lucene.util.RamUsageEs
* the License.
*/
+import java.io.IOException;
+import java.util.Arrays;
+
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.RamUsageEstimator;
+
/**
* This class is similar to {@link Packed64} except that it trades space for
* speed by ensuring that a single block needs to be read/written in order to
* read/write a value.
*/
-abstract class Packed64SingleBlock extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
+abstract class Packed64SingleBlock extends PackedInts.MutableImpl {
private static final int[] SUPPORTED_BITS_PER_VALUE = new int[] {1, 2, 3, 4,
5, 6, 7, 9, 10, 12, 21};
@@ -140,6 +139,50 @@ abstract class Packed64SingleBlock exten
}
@Override
+ public int get(int index, long[] arr, int off, int len) {
+ assert len > 0;
+ assert index >= 0 && index < valueCount;
+ len = Math.min(len, valueCount - index);
+ assert off + len <= arr.length;
+
+ final int originalIndex = index;
+
+ // go to the next block boundary
+ final int offsetInBlock = offsetInBlock(index);
+ if (offsetInBlock != 0) {
+ for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
+ arr[off++] = get(index++);
+ --len;
+ }
+ if (len == 0) {
+ return index - originalIndex;
+ }
+ }
+
+ // bulk get
+ assert offsetInBlock(index) == 0;
+ final int startBlock = blockOffset(index);
+ final int endBlock = blockOffset(index + len);
+ final int diff = (endBlock - startBlock) * 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
+ 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(int index, long value) {
final int o = blockOffset(index);
final int b = offsetInBlock(index);
@@ -148,6 +191,91 @@ abstract class Packed64SingleBlock exten
}
@Override
+ public int set(int index, long[] arr, int off, int len) {
+ assert len > 0;
+ assert index >= 0 && index < valueCount;
+ len = Math.min(len, valueCount - index);
+ assert off + len <= arr.length;
+
+ final int originalIndex = index;
+
+ // go to the next block boundary
+ final int offsetInBlock = offsetInBlock(index);
+ if (offsetInBlock != 0) {
+ for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
+ set(index++, arr[off++]);
+ --len;
+ }
+ if (len == 0) {
+ return index - originalIndex;
+ }
+ }
+
+ // bulk set
+ assert offsetInBlock(index) == 0;
+ final int startBlock = blockOffset(index);
+ final int endBlock = blockOffset(index + len);
+ final int diff = (endBlock - startBlock) * 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
+ return index - originalIndex;
+ } else {
+ // no progress so far => already at a block boundary but no full block to
+ // set
+ assert index == originalIndex;
+ return super.set(index, arr, off, len);
+ }
+ }
+
+ @Override
+ public void fill(int fromIndex, int toIndex, long val) {
+ assert fromIndex >= 0;
+ assert fromIndex <= toIndex;
+ assert (val & readMask) == val;
+
+ if (toIndex - fromIndex <= valuesPerBlock << 1) {
+ // there needs to be at least one full block to set for the block
+ // approach to be worth trying
+ super.fill(fromIndex, toIndex, val);
+ return;
+ }
+
+ // set values naively until the next block start
+ int fromOffsetInBlock = offsetInBlock(fromIndex);
+ if (fromOffsetInBlock != 0) {
+ for (int i = fromOffsetInBlock; i < valuesPerBlock; ++i) {
+ set(fromIndex++, val);
+ }
+ assert offsetInBlock(fromIndex) == 0;
+ }
+
+ // bulk set of the inner blocks
+ final int fromBlock = blockOffset(fromIndex);
+ final int toBlock = blockOffset(toIndex);
+ assert fromBlock * valuesPerBlock == fromIndex;
+
+ long blockValue = 0L;
+ for (int i = 0; i < valuesPerBlock; ++i) {
+ blockValue = blockValue | (val << shifts[i]);
+ }
+ Arrays.fill(blocks, fromBlock, toBlock, blockValue);
+
+ // fill the gap
+ for (int i = valuesPerBlock * toBlock; i < toIndex; ++i) {
+ set(i, val);
+ }
+ }
+
+ @Override
public void clear() {
Arrays.fill(blocks, 0L);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/Packed8ThreeBlocks.java Sat Jun 2 18:36:27 2012
@@ -24,8 +24,7 @@ import org.apache.lucene.util.RamUsageEs
*/
/** 24 bitsPerValue backed by byte[] */
-final class Packed8ThreeBlocks extends PackedInts.ReaderImpl
- implements PackedInts.Mutable {
+final class Packed8ThreeBlocks extends PackedInts.MutableImpl {
public static final int MAX_SIZE = Integer.MAX_VALUE / 3;
@@ -69,6 +68,18 @@ final class Packed8ThreeBlocks extends P
}
@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;
+ }
+ }
+
+ @Override
public void clear() {
Arrays.fill(blocks, (byte) 0);
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/util/packed/PackedInts.java Sat Jun 2 18:36:27 2012
@@ -57,6 +57,11 @@ public class PackedInts {
*/
public static final float COMPACT = 0f;
+ /**
+ * Default amount of memory to use for bulk operations.
+ */
+ 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;
@@ -76,6 +81,13 @@ public class PackedInts {
long get(int index);
/**
+ * Bulk get: read at least one and at most <code>len</code> longs starting
+ * from <code>index</code> into <code>arr[off:off+len]</code> and return
+ * the actual number of values that have been read.
+ */
+ int get(int index, long[] arr, int off, int len);
+
+ /**
* @return the number of bits used to store any given value.
* Note: This does not imply that memory usage is
* {@code bitsPerValue * #values} as implementations are free to
@@ -167,9 +179,24 @@ public class PackedInts {
void set(int index, long value);
/**
+ * Bulk set: set at least one and at most <code>len</code> longs starting
+ * at <code>off</code> in <code>arr</code> into this mutable, starting at
+ * <code>index</code>. Returns the actual number of values that have been
+ * set.
+ */
+ int set(int index, long[] arr, int off, int len);
+
+ /**
+ * Fill the mutable from <code>fromIndex</code> (inclusive) to
+ * <code>toIndex</code> (exclusive) with <code>val</code>.
+ */
+ void fill(int fromIndex, int toIndex, long val);
+
+ /**
* Sets all values to 0.
- */
+ */
void clear();
+
}
/**
@@ -189,7 +216,7 @@ public class PackedInts {
public int getBitsPerValue() {
return bitsPerValue;
}
-
+
public int size() {
return valueCount;
}
@@ -201,6 +228,45 @@ public class PackedInts {
public boolean hasArray() {
return false;
}
+
+ public int get(int index, long[] arr, int off, int len) {
+ assert index >= 0 && index < valueCount;
+ assert off + len <= arr.length;
+
+ final int gets = Math.min(valueCount - index, len);
+ for (int i = index, o = off, end = index + gets; i < end; ++i, ++o) {
+ arr[o] = get(i);
+ }
+ return gets;
+ }
+ }
+
+ public static abstract class MutableImpl extends ReaderImpl implements Mutable {
+
+ protected MutableImpl(int valueCount, int bitsPerValue) {
+ super(valueCount, bitsPerValue);
+ }
+
+ public int set(int index, long[] arr, int off, int len) {
+ assert len > 0;
+ assert index >= 0 && index < valueCount;
+ len = Math.min(len, valueCount - index);
+ assert off + len <= arr.length;
+
+ for (int i = index, o = off, end = index + len; i < end; ++i, ++o) {
+ set(i, arr[o]);
+ }
+ return len;
+ }
+
+ public void fill(int fromIndex, int toIndex, long val) {
+ assert val <= maxValue(bitsPerValue);
+ assert fromIndex <= toIndex;
+ for (int i = fromIndex; i < toIndex; ++i) {
+ set(i, val);
+ }
+ }
+
}
/** A write-once Writer.
@@ -452,4 +518,43 @@ public class PackedInts {
public static long maxValue(int bitsPerValue) {
return bitsPerValue == 64 ? Long.MAX_VALUE : ~(~0L << bitsPerValue);
}
+
+ /**
+ * Copy <code>src[srcPos:srcPos+len]</code> into
+ * <code>dest[destPos:destPos+len]</code> using at most <code>mem</code>
+ * bytes.
+ */
+ public static void copy(Reader src, int srcPos, Mutable dest, int destPos, int len, int mem) {
+ assert srcPos + len <= src.size();
+ assert destPos + len <= dest.size();
+ final int capacity = mem >>> 3;
+ if (capacity == 0) {
+ for (int i = 0; i < len; ++i) {
+ dest.set(destPos++, src.get(srcPos++));
+ }
+ } else {
+ // use bulk operations
+ long[] buf = new long[Math.min(capacity, len)];
+ int remaining = 0;
+ while (len > 0) {
+ final int read = src.get(srcPos, buf, remaining, Math.min(len, buf.length - remaining));
+ assert read > 0;
+ srcPos += read;
+ len -= read;
+ remaining += read;
+ final int written = dest.set(destPos, buf, 0, remaining);
+ assert written > 0;
+ destPos += written;
+ if (written < remaining) {
+ System.arraycopy(buf, written, buf, 0, remaining - written);
+ }
+ remaining -= written;
+ }
+ while (remaining > 0) {
+ final int written = dest.set(destPos, buf, 0, remaining);
+ remaining -= written;
+ }
+ }
+ }
+
}
Modified: lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/packed/TestPackedInts.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/packed/TestPackedInts.java?rev=1345545&r1=1345544&r2=1345545&view=diff
==============================================================================
--- lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/packed/TestPackedInts.java (original)
+++ lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/util/packed/TestPackedInts.java Sat Jun 2 18:36:27 2012
@@ -17,14 +17,15 @@ package org.apache.lucene.util.packed;
* limitations under the License.
*/
-import org.apache.lucene.store.*;
-import org.apache.lucene.util.LuceneTestCase;
-import org.apache.lucene.util.packed.PackedInts.Reader;
-
+import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
-import java.io.IOException;
+
+import org.apache.lucene.store.*;
+import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util._TestUtil;
+import org.apache.lucene.util.packed.PackedInts.Reader;
public class TestPackedInts extends LuceneTestCase {
public void testBitsRequired() throws Exception {
@@ -150,6 +151,71 @@ public class TestPackedInts extends Luce
assertListEquality(packedInts);
}
+ public void testRandomBulkCopy() {
+ final int numIters = atLeast(10);
+ for(int iter=0;iter<numIters;iter++) {
+ if (VERBOSE) {
+ System.out.println("\nTEST: iter=" + iter);
+ }
+ final int valueCount = atLeast(100000);
+ int bits1 = _TestUtil.nextInt(random(), 1, 64);
+ int bits2 = _TestUtil.nextInt(random(), 1, 64);
+ if (bits1 > bits2) {
+ int tmp = bits1;
+ bits1 = bits2;
+ bits2 = tmp;
+ }
+ if (VERBOSE) {
+ System.out.println(" valueCount=" + valueCount + " bits1=" + bits1 + " bits2=" + bits2);
+ }
+
+ final PackedInts.Mutable packed1 = PackedInts.getMutable(valueCount, bits1, PackedInts.COMPACT);
+ final PackedInts.Mutable packed2 = PackedInts.getMutable(valueCount, bits2, PackedInts.COMPACT);
+
+ final long maxValue = PackedInts.maxValue(bits1);
+ for(int i=0;i<valueCount;i++) {
+ final long val = random().nextLong() & maxValue;
+ packed1.set(i, val);
+ packed2.set(i, val);
+ }
+
+ final long[] buffer = new long[valueCount];
+
+ // Copy random slice over, 100 times:
+ for(int iter2=0;iter2<100;iter2++) {
+ int start = random().nextInt(valueCount-1);
+ int len = _TestUtil.nextInt(random(), 1, valueCount-start);
+ int offset;
+ if (VERBOSE) {
+ System.out.println(" copy " + len + " values @ " + start);
+ }
+ if (len == valueCount) {
+ offset = 0;
+ } else {
+ offset = random().nextInt(valueCount - len);
+ }
+ if (random().nextBoolean()) {
+ int got = packed1.get(start, buffer, offset, len);
+ assertTrue(got <= len);
+ int sot = packed2.set(start, buffer, offset, got);
+ assertTrue(sot <= got);
+ } else {
+ PackedInts.copy(packed1, offset, packed2, offset, len, random().nextInt(10 * len));
+ }
+
+ /*
+ for(int i=0;i<valueCount;i++) {
+ assertEquals("value " + i, packed1.get(i), packed2.get(i));
+ }
+ */
+ }
+
+ for(int i=0;i<valueCount;i++) {
+ assertEquals("value " + i, packed1.get(i), packed2.get(i));
+ }
+ }
+ }
+
public void testRandomEquality() {
final int[] VALUE_COUNTS = new int[]{0, 1, 5, 8, 100, 500};
final int MIN_BITS_PER_VALUE = 1;
@@ -354,4 +420,144 @@ public class TestPackedInts extends Luce
}
}
+ public void testFill() {
+ final int valueCount = 1111;
+ final int from = random().nextInt(valueCount + 1);
+ final int to = from + random().nextInt(valueCount + 1 - from);
+ for (int bpv = 1; bpv <= 64; ++bpv) {
+ final long val = random().nextInt((int) Math.min(Integer.MAX_VALUE, PackedInts.maxValue(bpv)));
+ List<PackedInts.Mutable> packedInts = createPackedInts(valueCount, bpv);
+ for (PackedInts.Mutable ints : packedInts) {
+ String msg = ints.getClass().getSimpleName() + " bpv=" + bpv + ", from=" + from + ", to=" + to + ", val=" + val;
+ ints.fill(0, ints.size(), 1);
+ ints.fill(from, to, val);
+ for (int i = 0; i < ints.size(); ++i) {
+ if (i >= from && i < to) {
+ assertEquals(msg + ", i=" + i, val, ints.get(i));
+ } else {
+ assertEquals(msg + ", i=" + i, 1, ints.get(i));
+ }
+ }
+ }
+ }
+ }
+
+ public void testBulkGet() {
+ final int valueCount = 1111;
+ final int index = random().nextInt(valueCount);
+ final int len = random().nextInt(valueCount * 2);
+ final int off = random().nextInt(77);
+
+ for (int bpv = 1; bpv <= 64; ++bpv) {
+ long mask = PackedInts.maxValue(bpv);
+ List<PackedInts.Mutable> packedInts = createPackedInts(valueCount, bpv);
+
+ for (PackedInts.Mutable ints : packedInts) {
+ for (int i = 0; i < ints.size(); ++i) {
+ ints.set(i, (31L * i - 1099) & mask);
+ }
+ long[] arr = new long[off+len];
+
+ String msg = ints.getClass().getSimpleName() + " valueCount=" + valueCount
+ + ", index=" + index + ", len=" + len + ", off=" + off;
+ final int gets = ints.get(index, arr, off, len);
+ assertTrue(msg, gets > 0);
+ assertTrue(msg, gets <= len);
+
+ for (int i = 0; i < arr.length; ++i) {
+ String m = msg + ", i=" + i;
+ if (i >= off && i < off + gets) {
+ assertEquals(m, ints.get(i - off + index), arr[i]);
+ } else {
+ assertEquals(m, 0, arr[i]);
+ }
+ }
+ }
+ }
+ }
+
+ public void testBulkSet() {
+ final int valueCount = 1111;
+ final int index = random().nextInt(valueCount);
+ final int len = random().nextInt(valueCount * 2);
+ final int off = random().nextInt(77);
+ long[] arr = new long[off+len];
+
+ for (int bpv = 1; bpv <= 64; ++bpv) {
+ long mask = PackedInts.maxValue(bpv);
+ List<PackedInts.Mutable> packedInts = createPackedInts(valueCount, bpv);
+ for (int i = 0; i < arr.length; ++i) {
+ arr[i] = (31L * i + 19) & mask;
+ }
+
+ for (PackedInts.Mutable ints : packedInts) {
+ String msg = ints.getClass().getSimpleName() + " valueCount=" + valueCount
+ + ", index=" + index + ", len=" + len + ", off=" + off;
+ final int sets = ints.set(index, arr, off, len);
+ assertTrue(msg, sets > 0);
+ assertTrue(msg, sets <= len);
+
+ for (int i = 0; i < ints.size(); ++i) {
+ String m = msg + ", i=" + i;
+ if (i >= index && i < index + sets) {
+ assertEquals(m, arr[off - index + i], ints.get(i));
+ } else {
+ assertEquals(m, 0, ints.get(i));
+ }
+ }
+ }
+ }
+ }
+
+ public void testCopy() {
+ final int valueCount = 689;
+ final int off1 = random().nextInt(valueCount);
+ final int off2 = random().nextInt(valueCount);
+ final int len = random().nextInt(Math.min(valueCount - off1, valueCount - off2));
+ final int mem = random().nextInt(1024);
+
+ for (int bpv = 1; bpv <= 64; ++bpv) {
+ long mask = PackedInts.maxValue(bpv);
+ for (PackedInts.Mutable r1 : createPackedInts(valueCount, bpv)) {
+ for (int i = 0; i < r1.size(); ++i) {
+ r1.set(i, (31L * i - 1023) & mask);
+ }
+ for (PackedInts.Mutable r2 : createPackedInts(valueCount, bpv)) {
+ String msg = "src=" + r1 + ", dest=" + r2 + ", srcPos=" + off1
+ + ", destPos=" + off2 + ", len=" + len + ", mem=" + mem;
+ PackedInts.copy(r1, off1, r2, off2, len, mem);
+ for (int i = 0; i < r2.size(); ++i) {
+ String m = msg + ", i=" + i;
+ if (i >= off2 && i < off2 + len) {
+ assertEquals(m, r1.get(i - off2 + off1), r2.get(i));
+ } else {
+ assertEquals(m, 0, r2.get(i));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ public void testGrowableWriter() {
+ final int valueCount = 113 + random().nextInt(1111);
+ GrowableWriter wrt = new GrowableWriter(1, valueCount, PackedInts.DEFAULT);
+ wrt.set(4, 2);
+ wrt.set(7, 10);
+ wrt.set(valueCount - 10, 99);
+ wrt.set(99, 999);
+ wrt.set(valueCount - 1, 1 << 10);
+ assertEquals(1 << 10, wrt.get(valueCount - 1));
+ wrt.set(99, (1 << 23) - 1);
+ assertEquals(1 << 10, wrt.get(valueCount - 1));
+ wrt.set(1, Long.MAX_VALUE);
+ assertEquals(1 << 10, wrt.get(valueCount - 1));
+ assertEquals(Long.MAX_VALUE, wrt.get(1));
+ assertEquals(2, wrt.get(4));
+ assertEquals((1 << 23) - 1, wrt.get(99));
+ assertEquals(10, wrt.get(7));
+ assertEquals(99, wrt.get(valueCount - 10));
+ assertEquals(1 << 10, wrt.get(valueCount - 1));
+ }
+
}