You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by rm...@apache.org on 2010/12/15 23:23:23 UTC
svn commit: r1049731 - in
/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene:
index/codecs/pfordelta/ util/pfor/
Author: rmuir
Date: Wed Dec 15 22:23:23 2010
New Revision: 1049731
URL: http://svn.apache.org/viewvc?rev=1049731&view=rev
Log:
LUCENE-2723: split out for/pfor compression and decompression as a start to refactoring... sorry for creating many (temporary) classes
Added:
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForCompress.java (with props)
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForConstants.java (with props)
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java
- copied, changed from r1049682, lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/FrameOfRef.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompressImpl.java
- copied, changed from r1049682, lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForCompress.java (with props)
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForDecompress.java
- copied, changed from r1049682, lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PFor.java
Removed:
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/FrameOfRef.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PFor.java
Modified:
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexInput.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexOutput.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexInput.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexOutput.java
lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/gendecompress.py
Modified: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexInput.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexInput.java?rev=1049731&r1=1049730&r2=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexInput.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexInput.java Wed Dec 15 22:23:23 2010
@@ -19,10 +19,8 @@ package org.apache.lucene.index.codecs.p
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IndexInput;
-import org.apache.lucene.store.MMapDirectory.MMapIndexInput;
-import org.apache.lucene.store.MMapDirectory.MultiMMapIndexInput;
import org.apache.lucene.index.codecs.intblock.FixedIntBlockIndexInput;
-import org.apache.lucene.util.pfor.FrameOfRef;
+import org.apache.lucene.util.pfor.ForDecompress;
import java.io.IOException;
import java.nio.ByteBuffer;
@@ -37,7 +35,7 @@ public class FORIndexInput extends Fixed
private static class BlockReader implements FixedIntBlockIndexInput.BlockReader {
private final IndexInput in;
private final int[] buffer;
- private final FrameOfRef decompressor;
+ private final ForDecompress decompressor;
private final byte[] input;
private final IntBuffer intInput;
@@ -45,7 +43,7 @@ public class FORIndexInput extends Fixed
this.in = in;
this.buffer = buffer;
- decompressor = new FrameOfRef();
+ decompressor = new ForDecompress();
// nocommit -- can't hardwire 1024; it's a function of blockSize
ByteBuffer byteBuffer = ByteBuffer.allocate(1024);
input = byteBuffer.array();
@@ -75,101 +73,7 @@ public class FORIndexInput extends Fixed
}
}
- // nocommit -- hacked up -- maybe move
- // IntIndexInput/Output into store?
- private static class MMapBlockReader implements FixedIntBlockIndexInput.BlockReader {
- private final MMapIndexInput in;
- private final int[] buffer;
- private final FrameOfRef decompressor;
- private final ByteBuffer byteBufferIn;
- private final IntBuffer intBufferIn;
-
- public MMapBlockReader(MMapIndexInput in, int[] buffer) {
- this.in = in;
- this.buffer = buffer;
-
- // nocommit -- we seem to be creating this class
- // alot... how come?
- decompressor = new FrameOfRef();
-
- byteBufferIn = in.getBuffer();
- //System.out.println("pos start=" + byteBufferIn.position());
- // nocommit -- this sets pos relative to current pos
- // of byteBuffer (confusing) -- this is why we -1 in
- // seek (pos is always 4 here)
- intBufferIn = byteBufferIn.asIntBuffer();
-
- decompressor.setCompressedBuffer(intBufferIn);
- decompressor.setUnCompressedData(buffer, 0, buffer.length);
- //System.out.println("mmmap");
- }
-
- public void seek(long pos) throws IOException {
- assert pos%4 == 0;
- //System.out.println("this=" + this + " seek=" + pos);
- intBufferIn.position((int) (pos/4)-1);
- }
-
- public void readBlock() throws IOException {
- // nocommit -- we don't need this numBytes header --
- // it's a waste. we need something like the zip
- // interface -- the decompressor asks for more bytes
- // if it needs it
- //int numBytes = in.readInt();
- int numBytes = intBufferIn.get();
- //System.out.println("NB=" + numBytes);
- // nocommit -- how to avoid this copy? plus, the copy
- // inside BII. if mmapdir how can we directly access
- // underlying ram w/ no copy?
- //in.readBytes(input, 0, numBytes);
- decompressor.decompress();
- }
- }
-
- // nocommit -- hacked up -- maybe move
- // IntIndexInput/Output into store?
- private static class MultiMMapBlockReader implements FixedIntBlockIndexInput.BlockReader {
- private final MultiMMapIndexInput in;
- private final int[] buffer;
- private final FrameOfRef decompressor;
- private final ByteBuffer byteBufferIn;
- private final IntBuffer intBufferIn;
-
- public MultiMMapBlockReader(MultiMMapIndexInput in, int[] buffer) {
- this.in = in;
- this.buffer = buffer;
-
- decompressor = new FrameOfRef();
-
- byteBufferIn = in.getBuffer();
- intBufferIn = byteBufferIn.asIntBuffer();
-
- decompressor.setCompressedBuffer(intBufferIn);
- decompressor.setUnCompressedData(buffer, 0, buffer.length);
- }
-
- public void seek(long pos) throws IOException {
- //
-
- }
-
- public void readBlock() throws IOException {
- int numBytes = in.readInt();
- // nocommit -- how to avoid this copy? plus, the copy
- // inside BII. if mmapdir how can we directly access
- // underlying ram w/ no copy?
- //in.readBytes(input, 0, numBytes);
- //decompressor.decompress();
- }
- }
-
protected FixedIntBlockIndexInput.BlockReader getBlockReader(IndexInput in, int[] buffer) {
- if (in instanceof MMapIndexInput) {
- return new MMapBlockReader((MMapIndexInput) in, buffer);
- } else if (false && in instanceof MultiMMapIndexInput) {
- return new MultiMMapBlockReader((MultiMMapIndexInput) in, buffer);
- } else {
- return new BlockReader(in, buffer);
- }
+ return new BlockReader(in, buffer);
}
}
Modified: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexOutput.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexOutput.java?rev=1049731&r1=1049730&r2=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexOutput.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/FORIndexOutput.java Wed Dec 15 22:23:23 2010
@@ -22,8 +22,8 @@ package org.apache.lucene.index.codecs.p
* testing the pluggability. One should typically use pfor instead. */
import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.pfor.ForCompress;
import org.apache.lucene.index.codecs.intblock.FixedIntBlockIndexOutput;
-import org.apache.lucene.util.pfor.FrameOfRef;
import java.io.IOException;
import java.nio.ByteBuffer;
@@ -35,7 +35,7 @@ public class FORIndexOutput extends Fixe
public final static String CODEC = "P_FOR_DELTA";
public final static int VERSION_START = 0;
public final static int VERSION_CURRENT = VERSION_START;
- private final FrameOfRef compressor;
+ private final ForCompress compressor;
private final byte[] output;
// nocommit
@@ -46,7 +46,7 @@ public class FORIndexOutput extends Fixe
// nocommit
this.fileName = fileName;
- compressor = new FrameOfRef();
+ compressor = new ForCompress();
// nocommit -- can't hardwire 1024; it's a function of blockSize
ByteBuffer byteBuffer = ByteBuffer.allocate(1024);
output = byteBuffer.array();
Modified: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexInput.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexInput.java?rev=1049731&r1=1049730&r2=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexInput.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexInput.java Wed Dec 15 22:23:23 2010
@@ -20,7 +20,7 @@ package org.apache.lucene.index.codecs.p
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IndexInput;
import org.apache.lucene.index.codecs.intblock.FixedIntBlockIndexInput;
-import org.apache.lucene.util.pfor.PFor;
+import org.apache.lucene.util.pfor.PForDecompress;
import java.io.IOException;
import java.nio.ByteBuffer;
@@ -35,7 +35,7 @@ public class PForDeltaIndexInput extends
private static class BlockReader implements FixedIntBlockIndexInput.BlockReader {
private final IndexInput in;
private final int[] buffer;
- private final PFor decompressor;
+ private final PForDecompress decompressor;
private final byte[] input;
private final IntBuffer intInput;
@@ -43,7 +43,7 @@ public class PForDeltaIndexInput extends
this.in = in;
this.buffer = buffer;
- decompressor = new PFor();
+ decompressor = new PForDecompress();
// nocommit -- can't hardwire 1024; it's a function of blockSize
ByteBuffer byteBuffer = ByteBuffer.allocate(1024);
input = byteBuffer.array();
Modified: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexOutput.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexOutput.java?rev=1049731&r1=1049730&r2=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexOutput.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/index/codecs/pfordelta/PForDeltaIndexOutput.java Wed Dec 15 22:23:23 2010
@@ -19,7 +19,7 @@ package org.apache.lucene.index.codecs.p
import org.apache.lucene.store.Directory;
import org.apache.lucene.index.codecs.intblock.FixedIntBlockIndexOutput;
-import org.apache.lucene.util.pfor.PFor;
+import org.apache.lucene.util.pfor.PForCompress;
import java.io.IOException;
import java.nio.ByteBuffer;
@@ -29,13 +29,13 @@ public class PForDeltaIndexOutput extend
public final static String CODEC = "P_FOR_DELTA";
public final static int VERSION_START = 0;
public final static int VERSION_CURRENT = VERSION_START;
- private final PFor compressor;
+ private final PForCompress compressor;
private final byte[] output;
public PForDeltaIndexOutput(Directory dir, String fileName, int blockSize) throws IOException {
super(dir.createOutput(fileName), blockSize);
- compressor = new PFor();
+ compressor = new PForCompress();
// nocommit -- can't hardwire 1024; it's a function of blockSize
ByteBuffer byteBuffer = ByteBuffer.allocate(1024);
output = byteBuffer.array();
Added: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForCompress.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForCompress.java?rev=1049731&view=auto
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForCompress.java (added)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForCompress.java Wed Dec 15 22:23:23 2010
@@ -0,0 +1,208 @@
+package org.apache.lucene.util.pfor;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.nio.IntBuffer;
+
+import org.apache.lucene.util.BitUtil;
+
+//nocommit: make into static methods without state
+public class ForCompress {
+ /** Number of frame bits. 2**numFrameBits - 1 is the maximum compressed value. */
+ protected int numFrameBits;
+
+ /** IntBuffer for compressed data */
+ protected IntBuffer compressedBuffer;
+
+ /** Uncompressed data */
+ protected int[] unCompressedData;
+ /** Offset into unCompressedData */
+ protected int offset;
+ /** Size of unCompressedData, -1 when not available. */
+ protected int unComprSize = -1;
+
+ /** Integer buffer to hold the compressed data.<br>
+ * Compression and decompression do not affect the current buffer position,
+ * and the beginning of the compressed data should be or will be at the current
+ * buffer position.<br>
+ * When the buffer is not large enough, ArrayIndexOutOfBoundExceptions will occur
+ * during compression/decompression.<br>
+ * Without a buffer for compressed data, compress() will only determine the number
+ * of integers needed in the buffer, see compress().<br>
+ * Without a valid buffer, decompress() will throw a NullPointerException.<br>
+ * For optimal speed when the IntBuffer is a view on a ByteBuffer,
+ * the IntBuffer should have a byte offset of a multiple of 4 bytes, possibly 0. <br>
+ * An IntBuffer is used here because 32 bits can efficiently accessed in the buffer
+ * on all current processors, and a positive int is normally large enough
+ * for various purposes in a Lucene index.
+ *
+ * @param compressedBuffer The buffer to hold the compressed integers.
+ *
+ */
+ public void setCompressedBuffer(IntBuffer compressedBuffer) {
+ this.compressedBuffer = compressedBuffer;
+ }
+
+ /** Array with offset holding uncompressed data.
+ * @param unCompressedData The array holding uncompressed integers.
+ * @param offset offset in unCompressedData.
+ * @param unComprSize The number of uncompressed integers, should be at least 1.
+ */
+ public void setUnCompressedData(int[] unCompressedData, int offset, int unComprSize) {
+ assert unCompressedData != null;
+ assert offset >= 0;
+ assert unComprSize >= 1;
+ assert (offset + unComprSize) <= unCompressedData.length;
+ this.unCompressedData = unCompressedData;
+ this.offset = offset;
+ this.unComprSize = unComprSize;
+ }
+
+ /** Compress the uncompressed data into the buffer using the given number of
+ * frame bits, storing only this number of least significant bits of the
+ * uncompressed integers in the compressed buffer.
+ * Should only be used after setUnCompressedData().
+ * <br>
+ * When setCompressBuffer() was not done, no actual compression is done.
+ * Regardless of the use of setCompressBuffer(), bufferByteSize() will return
+ * a valid value after calling compress().
+ * <p>
+ * When a buffer is available, the following is done.
+ * A header is stored as a first integer into the buffer, encoding
+ * the compression method, the number of frame bits and the number of compressed integers.
+ * All uncompressed integers are stored sequentially in compressed form
+ * in the buffer after the header.
+ *
+ * @param numFrameBits The number of frame bits. Should be between 1 and 32.
+ * Note that when this value is 32, no compression occurs.
+ */
+ public void compress(int numFrameBits) {
+ assert numFrameBits >= 1;
+ assert numFrameBits <= 32;
+ this.numFrameBits = numFrameBits;
+ encodeHeader(unComprSize);
+ for (int i = 0; i < unComprSize; i++) {
+ int v = unCompressedData[i + offset];
+ encodeCompressedValue(i, v);
+ }
+ }
+
+ /** As compress(), using the result of frameBitsForCompression() as the number of frame bits. */
+ public void compress() {
+ compress( frameBitsForCompression());
+ }
+
+ /** Determine the number of frame bits to be used for compression.
+ * Use only after setUnCompressedData().
+ * @return The number of bits needed to encode the maximum positive uncompressed value.
+ * Negative uncompressed values have no influence on the result.
+ */
+ public int frameBitsForCompression() {
+ int maxNonNegVal = 0;
+ for (int i = offset; i < (offset + unComprSize); i++) {
+ if (unCompressedData[i] > maxNonNegVal) {
+ maxNonNegVal = unCompressedData[i];
+ }
+ }
+ return BitUtil.logNextHigherPowerOfTwo(maxNonNegVal) + 1;
+ }
+
+ /** The 4 byte header (32 bits) contains:
+ * <ul>
+ * <li>
+ * <ul>
+ * <li>4 bits for the compression method: 0b0001 for FrameOfRef,
+ * <li>4 bits unused,
+ * </ul>
+ * <li>
+ * <ul>
+ * <li>5 bits for (numFrameBits-1),
+ * <li>3 bit unused,
+ * </ul>
+ * <li>8 bits for number of compressed integers - 1,
+ * <li>8 bits unused.
+ * </ul>
+ */
+ private void encodeHeader(int unComprSize) {
+ assert numFrameBits >= 1;
+ assert numFrameBits <= (1 << 5); // 32
+ assert unComprSize >= 1;
+ assert unComprSize <= (1 << 8); // 256
+ if (compressedBuffer != null) {
+ compressedBuffer.put(ForConstants.HEADER_INDEX,
+ ((unComprSize-1) << 16)
+ | ((numFrameBits-1) << 8)
+ | (ForConstants.FOR_COMPRESSION << 4));
+ }
+ }
+
+ /** Encode an integer value by compressing it into the buffer.
+ * @param compressedPos The index of the compressed integer in the compressed buffer.
+ * @param value The non negative value to be stored in compressed form.
+ * This should fit into the number of frame bits.
+ */
+ protected void encodeCompressedValue(int compressedPos, int value) {
+ encodeCompressedValueBase(compressedPos, value, numFrameBits); // FIXME: inline private method.
+ }
+
+ /** Encode a value into the compressed buffer.
+ * Since numFrameBits is always smaller than the number of bits in an int,
+ * at most two ints in the buffer will be affected.
+ * <br>Has no effect when compressedBuffer == null.
+ * <br>This could be specialized for numBits just like decompressFrame().
+ */
+ private void encodeCompressedValueBase(int compressedPos, int value, int numBits) {
+ assert numBits >= 1;
+ assert numBits <= 32;
+ if (compressedBuffer == null) {
+ return;
+ }
+ final int mask = (int) ((1L << numBits) - 1);
+ assert ((value & mask) == value) : ("value " + value + ", mask " + mask + ", numBits " + numBits); // lossless compression
+ final int compressedBitPos = numBits * compressedPos;
+ final int firstBitPosition = compressedBitPos & 31;
+ int intIndex = ForConstants.COMPRESSED_INDEX + (compressedBitPos >> 5);
+ setBufferIntBits(intIndex, firstBitPosition, numBits, value);
+ if ((firstBitPosition + numBits) > 32) { // value does not fit in first int
+ setBufferIntBits(intIndex+1, 0, (firstBitPosition + numBits - 32), (value >>> (32 - firstBitPosition)));
+ }
+ }
+
+ /** Change bits of an integer in the compressed buffer.
+ * <br> A more efficient implementation is possible when the compressed
+ * buffer is known to contain only zero bits, in that case one mask operation can be removed.
+ * @param intIndex The index of the affected integer in the compressed buffer.
+ * @param firstBitPosition The position of the least significant bit to be changed.
+ * @param numBits The number of more significant bits to be changed.
+ * @param value The new value of the bits to be changed, with the least significant bit at position zero.
+ */
+ protected void setBufferIntBits(int intIndex, int firstBitPosition, int numBits, int value) {
+ final int mask = (int) ((1L << numBits) - 1);
+ compressedBuffer.put(intIndex,
+ (compressedBuffer.get(intIndex)
+ & ~ (mask << firstBitPosition)) // masking superfluous on clear buffer
+ | (value << firstBitPosition));
+ }
+
+ /** Return the number of integers used in IntBuffer.
+ * Only valid after compress() or decompress().
+ */
+ public int compressedSize() {
+ return ForConstants.HEADER_SIZE + (unComprSize * numFrameBits + 31) / 32;
+ }
+}
Added: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForConstants.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForConstants.java?rev=1049731&view=auto
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForConstants.java (added)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForConstants.java Wed Dec 15 22:23:23 2010
@@ -0,0 +1,32 @@
+package org.apache.lucene.util.pfor;
+
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// nocommit: remove this whole class after refactoring
+public class ForConstants {
+ /** nocommit: we dont need to write these */
+ public static final int FOR_COMPRESSION = 1; /** encode compression method in header */
+ public static final int PFOR_COMPRESSION = 2; /** to encode compression method in header */
+
+ /** Index of header in int buffer */
+ public static final int HEADER_INDEX = 0;
+ public static final int HEADER_SIZE = 1; // one integer in IntBuffer
+
+ /** Start index in int buffer of array integers each compressed to numFrameBits. */
+ public static final int COMPRESSED_INDEX = HEADER_INDEX + 1;
+}
Copied: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java (from r1049682, lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/FrameOfRef.java)
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java?p2=lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java&p1=lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/FrameOfRef.java&r1=1049682&r2=1049731&rev=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/FrameOfRef.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java Wed Dec 15 22:23:23 2010
@@ -18,8 +18,6 @@ package org.apache.lucene.util.pfor;
import java.nio.IntBuffer;
-import org.apache.lucene.util.BitUtil;
-
/** Frame of Reference lossless integer compression/decompression.
* For positive integers, the compression is done by leaving out
* the most significant bits, and storing all numbers with a fixed number of bits
@@ -48,32 +46,13 @@ import org.apache.lucene.util.BitUtil;
* </ul>
*/
-// nocommit -- make a dedicated decompressor -- much of this
-// is not needed for decompress:
-
-public class FrameOfRef {
+//nocommit: make into static methods without state
+public class ForDecompress {
/** Number of frame bits. 2**numFrameBits - 1 is the maximum compressed value. */
protected int numFrameBits;
- /** Constant header tag to allow other compression methods, use value 0001 for
- * Frame of reference.
- * CHECKME: Move this to another class defining various decompression methods?
- */
- //protected int compressionMethod;
- private final int FOR_COMPRESSION = 1; /** encode compression method in header */
-
/** IntBuffer for compressed data */
protected IntBuffer compressedBuffer;
-
- /** Index of header in int buffer */
- protected final int HEADER_INDEX = 0;
-
- /** Start index in int buffer of array integers each compressed to numFrameBits. */
- protected final int COMPRESSED_INDEX = HEADER_INDEX + 1;
- protected final int HEADER_SIZE = 1; // one integer in IntBuffer
-
- // used by decompress to read the "input" (compressed) ints
- protected int[] scratch = new int[32];
/** Uncompressed data */
protected int[] unCompressedData;
@@ -82,10 +61,6 @@ public class FrameOfRef {
/** Size of unCompressedData, -1 when not available. */
protected int unComprSize = -1;
- /** Create a Frame of Reference integer compressor/decompressor. */
- public FrameOfRef() {
- }
-
/** Integer buffer to hold the compressed data.<br>
* Compression and decompression do not affect the current buffer position,
* and the beginning of the compressed data should be or will be at the current
@@ -124,122 +99,11 @@ public class FrameOfRef {
this.unComprSize = unComprSize;
}
- /** Compress the uncompressed data into the buffer using the given number of
- * frame bits, storing only this number of least significant bits of the
- * uncompressed integers in the compressed buffer.
- * Should only be used after setUnCompressedData().
- * <br>
- * When setCompressBuffer() was not done, no actual compression is done.
- * Regardless of the use of setCompressBuffer(), bufferByteSize() will return
- * a valid value after calling compress().
- * <p>
- * When a buffer is available, the following is done.
- * A header is stored as a first integer into the buffer, encoding
- * the compression method, the number of frame bits and the number of compressed integers.
- * All uncompressed integers are stored sequentially in compressed form
- * in the buffer after the header.
- *
- * @param numFrameBits The number of frame bits. Should be between 1 and 32.
- * Note that when this value is 32, no compression occurs.
- */
- public void compress(int numFrameBits) {
- assert numFrameBits >= 1;
- assert numFrameBits <= 32;
- this.numFrameBits = numFrameBits;
- encodeHeader(unComprSize);
- for (int i = 0; i < unComprSize; i++) {
- int v = unCompressedData[i + offset];
- encodeCompressedValue(i, v);
- }
- }
-
- /** As compress(), using the result of frameBitsForCompression() as the number of frame bits. */
- public void compress() {
- compress( frameBitsForCompression());
- }
-
/** Return the number of integers used in IntBuffer.
* Only valid after compress() or decompress().
*/
public int compressedSize() {
- return HEADER_SIZE + (unComprSize * numFrameBits + 31) / 32;
- }
-
- /** Encode an integer value by compressing it into the buffer.
- * @param compressedPos The index of the compressed integer in the compressed buffer.
- * @param value The non negative value to be stored in compressed form.
- * This should fit into the number of frame bits.
- */
- protected void encodeCompressedValue(int compressedPos, int value) {
- encodeCompressedValueBase(compressedPos, value, numFrameBits); // FIXME: inline private method.
- }
-
- /** Encode a value into the compressed buffer.
- * Since numFrameBits is always smaller than the number of bits in an int,
- * at most two ints in the buffer will be affected.
- * <br>Has no effect when compressedBuffer == null.
- * <br>This could be specialized for numBits just like decompressFrame().
- */
- private void encodeCompressedValueBase(int compressedPos, int value, int numBits) {
- assert numBits >= 1;
- assert numBits <= 32;
- if (compressedBuffer == null) {
- return;
- }
- final int mask = (int) ((1L << numBits) - 1);
- assert ((value & mask) == value) : ("value " + value + ", mask " + mask + ", numBits " + numBits); // lossless compression
- final int compressedBitPos = numBits * compressedPos;
- final int firstBitPosition = compressedBitPos & 31;
- int intIndex = COMPRESSED_INDEX + (compressedBitPos >> 5);
- setBufferIntBits(intIndex, firstBitPosition, numBits, value);
- if ((firstBitPosition + numBits) > 32) { // value does not fit in first int
- setBufferIntBits(intIndex+1, 0, (firstBitPosition + numBits - 32), (value >>> (32 - firstBitPosition)));
- }
- }
-
- /** Change bits of an integer in the compressed buffer.
- * <br> A more efficient implementation is possible when the compressed
- * buffer is known to contain only zero bits, in that case one mask operation can be removed.
- * @param intIndex The index of the affected integer in the compressed buffer.
- * @param firstBitPosition The position of the least significant bit to be changed.
- * @param numBits The number of more significant bits to be changed.
- * @param value The new value of the bits to be changed, with the least significant bit at position zero.
- */
- protected void setBufferIntBits(int intIndex, int firstBitPosition, int numBits, int value) {
- final int mask = (int) ((1L << numBits) - 1);
- compressedBuffer.put(intIndex,
- (compressedBuffer.get(intIndex)
- & ~ (mask << firstBitPosition)) // masking superfluous on clear buffer
- | (value << firstBitPosition));
- }
-
- /** The 4 byte header (32 bits) contains:
- * <ul>
- * <li>
- * <ul>
- * <li>4 bits for the compression method: 0b0001 for FrameOfRef,
- * <li>4 bits unused,
- * </ul>
- * <li>
- * <ul>
- * <li>5 bits for (numFrameBits-1),
- * <li>3 bit unused,
- * </ul>
- * <li>8 bits for number of compressed integers - 1,
- * <li>8 bits unused.
- * </ul>
- */
- private void encodeHeader(int unComprSize) {
- assert numFrameBits >= 1;
- assert numFrameBits <= (1 << 5); // 32
- assert unComprSize >= 1;
- assert unComprSize <= (1 << 8); // 256
- if (compressedBuffer != null) {
- compressedBuffer.put(HEADER_INDEX,
- ((unComprSize-1) << 16)
- | ((numFrameBits-1) << 8)
- | (FOR_COMPRESSION << 4));
- }
+ return ForConstants.HEADER_SIZE + (unComprSize * numFrameBits + 31) / 32;
}
protected void decodeHeader() {
@@ -249,7 +113,7 @@ public class FrameOfRef {
//unComprSize = ((header >>> 16) & 255) + 1;
numFrameBits = ((header >>> 8) & 31) + 1;
// verify compression method:
- assert FOR_COMPRESSION == ((header >>> 4) & 15);
+ assert ForConstants.FOR_COMPRESSION == ((header >>> 4) & 15);
}
/** Decompress from the buffer into output from a given offset. */
@@ -272,37 +136,37 @@ public class FrameOfRef {
// CHECKME: two other implementations might be faster:
// - array of static methods: Method[numFrameBits].invoke(null, [this]),
// - array of non static decompressors: ForDecompressor[numFrameBits].decompressFrame(this) .
- case 1: ForDecompress.decode1(compressedBuffer, unCompressedData); break;
- case 2: ForDecompress.decode2(compressedBuffer, unCompressedData); break;
- case 3: ForDecompress.decode3(compressedBuffer, unCompressedData); break;
- case 4: ForDecompress.decode4(compressedBuffer, unCompressedData); break;
- case 5: ForDecompress.decode5(compressedBuffer, unCompressedData); break;
- case 6: ForDecompress.decode6(compressedBuffer, unCompressedData); break;
- case 7: ForDecompress.decode7(compressedBuffer, unCompressedData); break;
- case 8: ForDecompress.decode8(compressedBuffer, unCompressedData); break;
- case 9: ForDecompress.decode9(compressedBuffer, unCompressedData); break;
- case 10: ForDecompress.decode10(compressedBuffer, unCompressedData); break;
- case 11: ForDecompress.decode11(compressedBuffer, unCompressedData); break;
- case 12: ForDecompress.decode12(compressedBuffer, unCompressedData); break;
- case 13: ForDecompress.decode13(compressedBuffer, unCompressedData); break;
- case 14: ForDecompress.decode14(compressedBuffer, unCompressedData); break;
- case 15: ForDecompress.decode15(compressedBuffer, unCompressedData); break;
- case 16: ForDecompress.decode16(compressedBuffer, unCompressedData); break;
- case 17: ForDecompress.decode17(compressedBuffer, unCompressedData); break;
- case 18: ForDecompress.decode18(compressedBuffer, unCompressedData); break;
- case 19: ForDecompress.decode19(compressedBuffer, unCompressedData); break;
- case 20: ForDecompress.decode20(compressedBuffer, unCompressedData); break;
- case 21: ForDecompress.decode21(compressedBuffer, unCompressedData); break;
- case 22: ForDecompress.decode22(compressedBuffer, unCompressedData); break;
- case 23: ForDecompress.decode23(compressedBuffer, unCompressedData); break;
- case 24: ForDecompress.decode24(compressedBuffer, unCompressedData); break;
- case 25: ForDecompress.decode25(compressedBuffer, unCompressedData); break;
- case 26: ForDecompress.decode26(compressedBuffer, unCompressedData); break;
- case 27: ForDecompress.decode27(compressedBuffer, unCompressedData); break;
- case 28: ForDecompress.decode28(compressedBuffer, unCompressedData); break;
- case 29: ForDecompress.decode29(compressedBuffer, unCompressedData); break;
- case 30: ForDecompress.decode30(compressedBuffer, unCompressedData); break;
- case 31: ForDecompress.decode31(compressedBuffer, unCompressedData); break;
+ case 1: ForDecompressImpl.decode1(compressedBuffer, unCompressedData); break;
+ case 2: ForDecompressImpl.decode2(compressedBuffer, unCompressedData); break;
+ case 3: ForDecompressImpl.decode3(compressedBuffer, unCompressedData); break;
+ case 4: ForDecompressImpl.decode4(compressedBuffer, unCompressedData); break;
+ case 5: ForDecompressImpl.decode5(compressedBuffer, unCompressedData); break;
+ case 6: ForDecompressImpl.decode6(compressedBuffer, unCompressedData); break;
+ case 7: ForDecompressImpl.decode7(compressedBuffer, unCompressedData); break;
+ case 8: ForDecompressImpl.decode8(compressedBuffer, unCompressedData); break;
+ case 9: ForDecompressImpl.decode9(compressedBuffer, unCompressedData); break;
+ case 10: ForDecompressImpl.decode10(compressedBuffer, unCompressedData); break;
+ case 11: ForDecompressImpl.decode11(compressedBuffer, unCompressedData); break;
+ case 12: ForDecompressImpl.decode12(compressedBuffer, unCompressedData); break;
+ case 13: ForDecompressImpl.decode13(compressedBuffer, unCompressedData); break;
+ case 14: ForDecompressImpl.decode14(compressedBuffer, unCompressedData); break;
+ case 15: ForDecompressImpl.decode15(compressedBuffer, unCompressedData); break;
+ case 16: ForDecompressImpl.decode16(compressedBuffer, unCompressedData); break;
+ case 17: ForDecompressImpl.decode17(compressedBuffer, unCompressedData); break;
+ case 18: ForDecompressImpl.decode18(compressedBuffer, unCompressedData); break;
+ case 19: ForDecompressImpl.decode19(compressedBuffer, unCompressedData); break;
+ case 20: ForDecompressImpl.decode20(compressedBuffer, unCompressedData); break;
+ case 21: ForDecompressImpl.decode21(compressedBuffer, unCompressedData); break;
+ case 22: ForDecompressImpl.decode22(compressedBuffer, unCompressedData); break;
+ case 23: ForDecompressImpl.decode23(compressedBuffer, unCompressedData); break;
+ case 24: ForDecompressImpl.decode24(compressedBuffer, unCompressedData); break;
+ case 25: ForDecompressImpl.decode25(compressedBuffer, unCompressedData); break;
+ case 26: ForDecompressImpl.decode26(compressedBuffer, unCompressedData); break;
+ case 27: ForDecompressImpl.decode27(compressedBuffer, unCompressedData); break;
+ case 28: ForDecompressImpl.decode28(compressedBuffer, unCompressedData); break;
+ case 29: ForDecompressImpl.decode29(compressedBuffer, unCompressedData); break;
+ case 30: ForDecompressImpl.decode30(compressedBuffer, unCompressedData); break;
+ case 31: ForDecompressImpl.decode31(compressedBuffer, unCompressedData); break;
default:
throw new IllegalStateException("Unknown number of frame bits " + numFrameBits);
}
@@ -311,19 +175,4 @@ public class FrameOfRef {
public int getNumFrameBits() {
return numFrameBits;
}
-
- /** Determine the number of frame bits to be used for compression.
- * Use only after setUnCompressedData().
- * @return The number of bits needed to encode the maximum positive uncompressed value.
- * Negative uncompressed values have no influence on the result.
- */
- public int frameBitsForCompression() {
- int maxNonNegVal = 0;
- for (int i = offset; i < (offset + unComprSize); i++) {
- if (unCompressedData[i] > maxNonNegVal) {
- maxNonNegVal = unCompressedData[i];
- }
- }
- return BitUtil.logNextHigherPowerOfTwo(maxNonNegVal) + 1;
- }
}
Copied: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompressImpl.java (from r1049682, lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java)
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompressImpl.java?p2=lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompressImpl.java&p1=lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java&r1=1049682&r2=1049731&rev=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompress.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/ForDecompressImpl.java Wed Dec 15 22:23:23 2010
@@ -19,7 +19,7 @@ package org.apache.lucene.util.pfor;
import java.nio.IntBuffer;
-final class ForDecompress {
+final class ForDecompressImpl {
// nocommit: assess perf of this to see if specializing is really needed
/*
Added: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForCompress.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForCompress.java?rev=1049731&view=auto
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForCompress.java (added)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForCompress.java Wed Dec 15 22:23:23 2010
@@ -0,0 +1,325 @@
+package org.apache.lucene.util.pfor;
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// nocommit need low level unit tests for this
+// nocommit break out decompress seperately?
+
+import java.util.Arrays;
+
+/** Patched Frame of Reference PFOR compression/decompression.
+ * <p>
+ * As defined in:<br>
+ * Super-Scalar RAM-CPU Cache Compression<br>
+ * Marcin Zukowski, Sándor Héman, Niels Nes, Peter Boncz, 2006.<br>
+ * with extensions from:<br>
+ * Performance of Compressed Inverted List Caching in Search Engines<br>
+ * Jiangong Zhang, Xiaohui Long, Torsten Suel, 2008.<br>
+ * <p>
+ * This class does not provide delta coding because the lucene index
+ * structures already have that.
+ * <p>
+ * The implementation uses 0 as lower bound for the frame,
+ * so small positive integers will be most effectively compressed.
+ * <p>
+ * Some optimized code is used for decompression,
+ * see class ForDecompress and its subclasses.
+ * <br>Good decompression performance will depend on the performance
+ * of java.nio.IntBuffer indexed get() methods.
+ * <br>Use of the -server option helps performance for the Sun 1.6 jvm under Linux.
+ * <p>
+ * The start point of first exception is at its natural boundary:
+ * 2 byte exceptions at even byte position, 4 byte at quadruple.
+ * <p>
+ * To be done:
+ * <ul>
+ * <li>
+ * Optimize compression code.
+ * <li>
+ * IntBuffer.get() is somewhat faster that IntBuffer.get(index), adapt (de)compression for to
+ * use the relative get() method.
+ * <li>
+ * Check javadoc generation and generated javadocs. Add javadoc code references.
+ * </ul>
+ */
+//nocommit: make into static methods without state
+public class PForCompress extends ForCompress {
+ /** Index on input and in compressed frame of first exception, -1 when no exceptions */
+ private int firstExceptionIndex;
+
+ /** How to encode PFor exceptions: 0: byte, 1: short, 2:int, unused: 3: long */
+ private int exceptionCode = -1;
+
+ /** Total number of exception values */
+ private int numExceptions;
+
+ /** Compress the decompressed data into the buffer.
+ * Should only be used after setUnCompressedData().
+ * <br>
+ * When setCompressBuffer() was not done, no actual compression is done.
+ * Regardless of the use of setCompressBuffer(), bufferByteSize() will return
+ * a valid value after calling compress().
+ * <p>
+ * When a buffer is available, the following is done.
+ * A header is stored into the buffer, encoding a.o. numFrameBits and unComprSize.
+ * All ints < 2**numFrameBits are stored sequentially in compressed form
+ * in the buffer.
+ * All other ints are stored in the buffer as exceptions after the compressed sequential ints,
+ * using 1, 2 or 4 bytes per exception, starting at the first byte after the compressed
+ * sequential ints.
+ * <br>
+ * The index of the first exception is encoded in the header in the buffer,
+ * all later exceptions have the offset to the next exception as their value,
+ * the last one offset to just after the available input size.
+ * After the first exception, when the next exception index does not fit in
+ * numFrameBits bits, an exception after 2**numFrameBits inputs is forced and inserted.
+ * <br>
+ * Exception values are stored in the order of the exceptions.
+ * The number of bytes used for an exception is also encoded in the header.
+ * This depends on the maximum exception value and does not vary between the exceptions.
+ */
+ @Override
+ public void compress(int numFrameBits) {
+ assert numFrameBits >= 1;
+ assert numFrameBits <= 32;
+ this.numFrameBits = numFrameBits;
+ numExceptions = 0;
+ int maxException = -1;
+ firstExceptionIndex = -1;
+ int lastExceptionIndex = -1;
+ int i;
+ int[] exceptionValues = new int[unComprSize];
+ int maxNonExceptionMask = (int) ((1L << numFrameBits) - 1);
+ int maxChain = 254; // maximum value of firstExceptionIndex in header
+ // CHECKME: maxChain 1 off because of initial value of lastExceptionIndex and force exception test below?
+ for (i = 0; i < unComprSize; i++) {
+ int v = unCompressedData[i + offset];
+ // FIXME: split this loop to avoid if statement in loop.
+ // use predication for this: (someBool ? 1 : 0), and hope that the jit optimizes this.
+ if ( (((v & maxNonExceptionMask) == v) // no value exception
+ && (i < (lastExceptionIndex + maxChain)))) { // no forced exception
+ encodeCompressedValue(i, v); // normal encoding
+ } else { // exception
+ exceptionValues[numExceptions] = v;
+ numExceptions++;
+ if (firstExceptionIndex == -1) {
+ firstExceptionIndex = i;
+ assert firstExceptionIndex <= 254; // maximum value of firstExceptionIndex in header
+ maxException = v;
+ maxChain = 1 << ((30 < numFrameBits) ? 30 : numFrameBits); // fewer bits available for exception chain value.
+ } else if (v > maxException) {
+ maxException = v;
+ }
+ // encode the previous exception pointer
+ if (lastExceptionIndex >= 0) {
+ encodeCompressedValue(lastExceptionIndex, i - lastExceptionIndex - 1);
+ }
+ lastExceptionIndex = i;
+ }
+ }
+ if (lastExceptionIndex >= 0) {
+ encodeCompressedValue(lastExceptionIndex, i - lastExceptionIndex - 1); // end the exception chain.
+ }
+ //int bitsInArray = numFrameBits * unCompressedData.length;
+ //int bytesInArray = (bitsInArray + 7) / 8;
+ if (maxException < (1 << 8)) { // exceptions as byte
+ exceptionCode = 0;
+ } else if (maxException < (1 << 16)) { // exceptions as 2 bytes
+ exceptionCode = 1;
+ } else /* if (maxException < (1L << 32)) */ { // exceptions as 4 bytes
+ exceptionCode = 2;
+ }
+ encodeHeader(unComprSize, firstExceptionIndex);
+ encodeExceptionValues(exceptionValues);
+ }
+
+ /** Return the number bytes used for a single exception */
+ private int exceptionByteSize() {
+ assert exceptionCode >= 0;
+ assert exceptionCode <= 2;
+ return exceptionCode == 0 ? 1
+ : exceptionCode == 1 ? 2
+ : 4;
+ }
+
+ /** Return the number of exceptions.
+ * Only valid after compress() or decompress().
+ */
+ public int getNumExceptions() {
+ return numExceptions;
+ }
+
+ private int compressedArrayByteSize() {
+ assert unComprSize % 32 == 0;
+ return (unComprSize>>3)*numFrameBits;
+ }
+
+ /** Return the number of integers used in IntBuffer.
+ * Only valid after compress() or decompress().
+ */
+ @Override
+ public int compressedSize() {
+ // numExceptions only valid after compress() or decompress()
+ return ForConstants.HEADER_SIZE
+ + ((compressedArrayByteSize()
+ + exceptionByteSize() * numExceptions
+ + 3) >> 2); // round up to next multiple of 4 and divide by 4
+ }
+
+ private void encodeExceptionValues(int[] exceptionValues) {
+ if ((compressedBuffer == null) || (numExceptions == 0)) {
+ return;
+ }
+ int excByteOffset = compressedArrayByteSize();
+
+ switch (exceptionCode) {
+ case 0: { // 1 byte exceptions
+ int i = 0;
+ do {
+ int intIndex = ForConstants.COMPRESSED_INDEX + (excByteOffset >> 2); // round down here.
+ setBufferIntBits(intIndex, ((excByteOffset & 3) * 8), 8, exceptionValues[i]);
+ excByteOffset++;
+ } while (++i < numExceptions);
+ }
+ break;
+
+ case 1: { // 2 byte exceptions
+ int excShortOffset = (excByteOffset + 1) >> 1; // to next multiple of two bytes.
+ int intIndex = ForConstants.COMPRESSED_INDEX + (excShortOffset >> 1); // round down here.
+ int i = 0;
+ if ((excShortOffset & 1) != 0) { // encode first 2 byte exception in high 2 bytes of same int as last frame bits.
+ setBufferIntBits(intIndex, 16, 16, exceptionValues[i]);
+ intIndex++;
+ i++;
+ }
+ for (; i < (numExceptions-1); i += 2) {
+ compressedBuffer.put(intIndex++, (exceptionValues[i+1] << 16) | exceptionValues[i]);
+ }
+ if (i < numExceptions) {
+ compressedBuffer.put(intIndex, exceptionValues[i]); // also clear the high 16 bits
+ }
+ }
+ break;
+
+ case 2: { // 4 byte exceptions
+ int excIntOffSet = ForConstants.COMPRESSED_INDEX + ((excByteOffset + 3) >> 2); // to next multiple of four bytes, in ints.
+ int i = 0;
+ do {
+ compressedBuffer.put(excIntOffSet + i, exceptionValues[i]);
+ } while(++i < numExceptions);
+ }
+ break;
+ }
+ }
+
+ /** The 4 byte header (32 bits) contains:
+ *
+ * - 4 bits for the compression method: 0b0001 for PFor
+ * - 4 bits unused
+ *
+ * - 5 bits for (numFrameBits-1)
+ * - 2 bits for the exception code: 0b00: byte, 0b01: short, 0b10: int, 0b11: long (unused).
+ * - 1 bit unused
+ *
+ * - 8 bits for uncompressed input size - 1,
+ *
+ * - 8 bits for the index of the first exception + 1, (0 when no exceptions)
+ */
+ private void encodeHeader(int unComprSize, int firstExceptionIndex) {
+ assert exceptionCode >= 0;
+ assert exceptionCode <= 2; // 3 for long, but unused for now.
+ assert numFrameBits >= 1;
+ assert numFrameBits <= 32;
+ assert unComprSize >= 1;
+ assert unComprSize <= 128;
+ assert firstExceptionIndex >= -1;
+ assert firstExceptionIndex < unComprSize;
+ if (compressedBuffer != null) {
+ compressedBuffer.put(ForConstants.HEADER_INDEX,
+ ((firstExceptionIndex+1) << 24)
+ | ((unComprSize-1) << 16)
+ | ((exceptionCode & 3) << 13) | ((numFrameBits-1) << 8)
+ | (ForConstants.PFOR_COMPRESSION << 4));
+ }
+ }
+
+ /** Determine the number of frame bits to be used for compression.
+ * Use only after setUnCompressedData().
+ * This is done by taking a copy of the input, sorting it and using this
+ * to determine the compressed size for each possible numbits in a single pass,
+ * ignoring forced exceptions.
+ * Finally an estimation of the number of forced exceptions is reduced to
+ * less than 1 in 32 input numbers by increasing the number of frame bits.
+ * This implementation works by determining the total number of bytes needed for
+ * the compressed data, but does take into account alignment of exceptions
+ * at 2 or 4 byte boundaries.
+ */
+ @Override
+ public int frameBitsForCompression() {
+ if ((offset + unComprSize) > unCompressedData.length) {
+ throw new IllegalArgumentException( "(offset " + offset
+ + " + unComprSize " + unComprSize
+ + ") > unCompressedData.length " + unCompressedData.length);
+ }
+ int copy[] = Arrays.copyOfRange(unCompressedData, offset, offset + unComprSize);
+ assert copy.length == unComprSize;
+ Arrays.sort(copy);
+ int maxValue = copy[copy.length-1];
+ if (maxValue <= 1) {
+ return 1;
+ }
+ int bytesPerException = (maxValue < (1 << 8)) ? 1 : (maxValue < (1 << 16)) ? 2 : 4;
+ int frameBits = 1;
+ int bytesForFrame = (copy.length * frameBits + 7) / 8;
+ // initially assume all input is an exception.
+ int totalBytes = bytesForFrame + copy.length * bytesPerException; // excluding the header.
+ int bestBytes = totalBytes;
+ int bestFrameBits = frameBits;
+ int bestExceptions = copy.length;
+ for (int i = 0; i < copy.length; i++) {
+ // determine frameBits so that copy[i] is no more exception
+ while (copy[i] >= (1 << frameBits)) {
+ if (frameBits == 30) { // no point to increase further.
+ return bestFrameBits;
+ }
+ ++frameBits;
+ // increase bytesForFrame and totalBytes to correspond to frameBits
+ int newBytesForFrame = (copy.length * frameBits + 7) / 8;
+ totalBytes += newBytesForFrame - bytesForFrame;
+ bytesForFrame = newBytesForFrame;
+ }
+ totalBytes -= bytesPerException; // no more need to store copy[i] as exception
+ if (totalBytes <= bestBytes) { // <= : prefer fewer exceptions at higher number of frame bits.
+ bestBytes = totalBytes;
+ bestFrameBits = frameBits;
+ bestExceptions = (copy.length - i - 1);
+ }
+ }
+ if (bestExceptions > 0) { // check for forced exceptions.
+ // This ignores the position of the first exception, for which enough bits are available in the header.
+ int allowedNumExceptions = bestExceptions + (copy.length >> 5); // 1 in 32 is allowed to be forced.
+ // (copy.length >> bestFrameBits): Minimum exception chain size including forced ones,
+ // ignoring the position of the first exception.
+ while (allowedNumExceptions < (copy.length >> bestFrameBits)) { // Too many forced?
+ bestFrameBits++; // Reduce forced exceptions and perhaps reduce actual exceptions
+ // Dilemma: decompression speed reduces with increasing number of frame bits,
+ // so it may be better to increase no more than once or twice here.
+ }
+ }
+ return bestFrameBits;
+ }
+}
Copied: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForDecompress.java (from r1049682, lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PFor.java)
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForDecompress.java?p2=lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForDecompress.java&p1=lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PFor.java&r1=1049682&r2=1049731&rev=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PFor.java (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/PForDecompress.java Wed Dec 15 22:23:23 2010
@@ -19,8 +19,6 @@ package org.apache.lucene.util.pfor;
// nocommit need low level unit tests for this
// nocommit break out decompress seperately?
-import java.util.Arrays;
-
/** Patched Frame of Reference PFOR compression/decompression.
* <p>
* As defined in:<br>
@@ -56,102 +54,17 @@ import java.util.Arrays;
* Check javadoc generation and generated javadocs. Add javadoc code references.
* </ul>
*/
-public class PFor extends FrameOfRef {
+//nocommit: make into static methods without state
+public class PForDecompress extends ForDecompress {
/** Index on input and in compressed frame of first exception, -1 when no exceptions */
private int firstExceptionIndex;
- /** CHECKME: Move this to another class defining various decompression methods? */
- private final int PFOR_COMPRESSION = 2; /** to encode compression method in header */
-
/** How to encode PFor exceptions: 0: byte, 1: short, 2:int, unused: 3: long */
private int exceptionCode = -1;
/** Total number of exception values */
private int numExceptions;
-
- /** Create a PFor compressor/decompressor. */
- public PFor() {
- }
- /** Compress the decompressed data into the buffer.
- * Should only be used after setUnCompressedData().
- * <br>
- * When setCompressBuffer() was not done, no actual compression is done.
- * Regardless of the use of setCompressBuffer(), bufferByteSize() will return
- * a valid value after calling compress().
- * <p>
- * When a buffer is available, the following is done.
- * A header is stored into the buffer, encoding a.o. numFrameBits and unComprSize.
- * All ints < 2**numFrameBits are stored sequentially in compressed form
- * in the buffer.
- * All other ints are stored in the buffer as exceptions after the compressed sequential ints,
- * using 1, 2 or 4 bytes per exception, starting at the first byte after the compressed
- * sequential ints.
- * <br>
- * The index of the first exception is encoded in the header in the buffer,
- * all later exceptions have the offset to the next exception as their value,
- * the last one offset to just after the available input size.
- * After the first exception, when the next exception index does not fit in
- * numFrameBits bits, an exception after 2**numFrameBits inputs is forced and inserted.
- * <br>
- * Exception values are stored in the order of the exceptions.
- * The number of bytes used for an exception is also encoded in the header.
- * This depends on the maximum exception value and does not vary between the exceptions.
- */
- public void compress(int numFrameBits) {
- assert numFrameBits >= 1;
- assert numFrameBits <= 32;
- this.numFrameBits = numFrameBits;
- numExceptions = 0;
- int maxException = -1;
- firstExceptionIndex = -1;
- int lastExceptionIndex = -1;
- int i;
- int[] exceptionValues = new int[unComprSize];
- int maxNonExceptionMask = (int) ((1L << numFrameBits) - 1);
- int maxChain = 254; // maximum value of firstExceptionIndex in header
- // CHECKME: maxChain 1 off because of initial value of lastExceptionIndex and force exception test below?
- for (i = 0; i < unComprSize; i++) {
- int v = unCompressedData[i + offset];
- // FIXME: split this loop to avoid if statement in loop.
- // use predication for this: (someBool ? 1 : 0), and hope that the jit optimizes this.
- if ( (((v & maxNonExceptionMask) == v) // no value exception
- && (i < (lastExceptionIndex + maxChain)))) { // no forced exception
- encodeCompressedValue(i, v); // normal encoding
- } else { // exception
- exceptionValues[numExceptions] = v;
- numExceptions++;
- if (firstExceptionIndex == -1) {
- firstExceptionIndex = i;
- assert firstExceptionIndex <= 254; // maximum value of firstExceptionIndex in header
- maxException = v;
- maxChain = 1 << ((30 < numFrameBits) ? 30 : numFrameBits); // fewer bits available for exception chain value.
- } else if (v > maxException) {
- maxException = v;
- }
- // encode the previous exception pointer
- if (lastExceptionIndex >= 0) {
- encodeCompressedValue(lastExceptionIndex, i - lastExceptionIndex - 1);
- }
- lastExceptionIndex = i;
- }
- }
- if (lastExceptionIndex >= 0) {
- encodeCompressedValue(lastExceptionIndex, i - lastExceptionIndex - 1); // end the exception chain.
- }
- //int bitsInArray = numFrameBits * unCompressedData.length;
- //int bytesInArray = (bitsInArray + 7) / 8;
- if (maxException < (1 << 8)) { // exceptions as byte
- exceptionCode = 0;
- } else if (maxException < (1 << 16)) { // exceptions as 2 bytes
- exceptionCode = 1;
- } else /* if (maxException < (1L << 32)) */ { // exceptions as 4 bytes
- exceptionCode = 2;
- }
- encodeHeader(unComprSize, firstExceptionIndex);
- encodeExceptionValues(exceptionValues);
- }
-
/** Return the number bytes used for a single exception */
private int exceptionByteSize() {
assert exceptionCode >= 0;
@@ -176,60 +89,15 @@ public class PFor extends FrameOfRef {
/** Return the number of integers used in IntBuffer.
* Only valid after compress() or decompress().
*/
+ @Override
public int compressedSize() {
// numExceptions only valid after compress() or decompress()
- return HEADER_SIZE
+ return ForConstants.HEADER_SIZE
+ ((compressedArrayByteSize()
+ exceptionByteSize() * numExceptions
+ 3) >> 2); // round up to next multiple of 4 and divide by 4
}
- private void encodeExceptionValues(int[] exceptionValues) {
- if ((compressedBuffer == null) || (numExceptions == 0)) {
- return;
- }
- int excByteOffset = compressedArrayByteSize();
-
- switch (exceptionCode) {
- case 0: { // 1 byte exceptions
- int i = 0;
- do {
- int intIndex = COMPRESSED_INDEX + (excByteOffset >> 2); // round down here.
- setBufferIntBits(intIndex, ((excByteOffset & 3) * 8), 8, exceptionValues[i]);
- excByteOffset++;
- } while (++i < numExceptions);
- }
- break;
-
- case 1: { // 2 byte exceptions
- int excShortOffset = (excByteOffset + 1) >> 1; // to next multiple of two bytes.
- int intIndex = COMPRESSED_INDEX + (excShortOffset >> 1); // round down here.
- int i = 0;
- if ((excShortOffset & 1) != 0) { // encode first 2 byte exception in high 2 bytes of same int as last frame bits.
- setBufferIntBits(intIndex, 16, 16, exceptionValues[i]);
- intIndex++;
- i++;
- }
- for (; i < (numExceptions-1); i += 2) {
- compressedBuffer.put(intIndex++, (exceptionValues[i+1] << 16) | exceptionValues[i]);
- }
- if (i < numExceptions) {
- compressedBuffer.put(intIndex, exceptionValues[i]); // also clear the high 16 bits
- }
- }
- break;
-
- case 2: { // 4 byte exceptions
- int excIntOffSet = COMPRESSED_INDEX + ((excByteOffset + 3) >> 2); // to next multiple of four bytes, in ints.
- int i = 0;
- do {
- compressedBuffer.put(excIntOffSet + i, exceptionValues[i]);
- } while(++i < numExceptions);
- }
- break;
- }
- }
-
/** Decode the exception values while going through the exception chain.
* <br>For performance, delegate/subclass this to classes with fixed exceptionCode.
* <br> Also, decoding exceptions is preferably done from an int border instead of
@@ -287,37 +155,7 @@ public class PFor extends FrameOfRef {
}
}
- /** The 4 byte header (32 bits) contains:
- *
- * - 4 bits for the compression method: 0b0001 for PFor
- * - 4 bits unused
- *
- * - 5 bits for (numFrameBits-1)
- * - 2 bits for the exception code: 0b00: byte, 0b01: short, 0b10: int, 0b11: long (unused).
- * - 1 bit unused
- *
- * - 8 bits for uncompressed input size - 1,
- *
- * - 8 bits for the index of the first exception + 1, (0 when no exceptions)
- */
- private void encodeHeader(int unComprSize, int firstExceptionIndex) {
- assert exceptionCode >= 0;
- assert exceptionCode <= 2; // 3 for long, but unused for now.
- assert numFrameBits >= 1;
- assert numFrameBits <= 32;
- assert unComprSize >= 1;
- assert unComprSize <= 128;
- assert firstExceptionIndex >= -1;
- assert firstExceptionIndex < unComprSize;
- if (compressedBuffer != null) {
- compressedBuffer.put(HEADER_INDEX,
- ((firstExceptionIndex+1) << 24)
- | ((unComprSize-1) << 16)
- | ((exceptionCode & 3) << 13) | ((numFrameBits-1) << 8)
- | (PFOR_COMPRESSION << 4));
- }
- }
-
+ @Override
protected void decodeHeader() {
int header = compressedBuffer.get();
firstExceptionIndex = ((header >>> 24) & 255) - 1;
@@ -326,12 +164,13 @@ public class PFor extends FrameOfRef {
assert numFrameBits > 0: numFrameBits;
assert numFrameBits <= 32: numFrameBits;
// verify compression method:
- assert PFOR_COMPRESSION == ((header >>> 4) & 15);
+ assert ForConstants.PFOR_COMPRESSION == ((header >>> 4) & 15);
exceptionCode = (header >>> 13) & 3;
assert exceptionCode <= 2;
}
/** Decompress from the buffer into output from a given offset. */
+ @Override
public void decompress() {
super.decompress();
patchExceptions();
@@ -345,69 +184,4 @@ public class PFor extends FrameOfRef {
numExceptions++;
return nextExceptionIndex;
}
-
- /** Determine the number of frame bits to be used for compression.
- * Use only after setUnCompressedData().
- * This is done by taking a copy of the input, sorting it and using this
- * to determine the compressed size for each possible numbits in a single pass,
- * ignoring forced exceptions.
- * Finally an estimation of the number of forced exceptions is reduced to
- * less than 1 in 32 input numbers by increasing the number of frame bits.
- * This implementation works by determining the total number of bytes needed for
- * the compressed data, but does take into account alignment of exceptions
- * at 2 or 4 byte boundaries.
- */
- public int frameBitsForCompression() {
- if ((offset + unComprSize) > unCompressedData.length) {
- throw new IllegalArgumentException( "(offset " + offset
- + " + unComprSize " + unComprSize
- + ") > unCompressedData.length " + unCompressedData.length);
- }
- int copy[] = Arrays.copyOfRange(unCompressedData, offset, offset + unComprSize);
- assert copy.length == unComprSize;
- Arrays.sort(copy);
- int maxValue = copy[copy.length-1];
- if (maxValue <= 1) {
- return 1;
- }
- int bytesPerException = (maxValue < (1 << 8)) ? 1 : (maxValue < (1 << 16)) ? 2 : 4;
- int frameBits = 1;
- int bytesForFrame = (copy.length * frameBits + 7) / 8;
- // initially assume all input is an exception.
- int totalBytes = bytesForFrame + copy.length * bytesPerException; // excluding the header.
- int bestBytes = totalBytes;
- int bestFrameBits = frameBits;
- int bestExceptions = copy.length;
- for (int i = 0; i < copy.length; i++) {
- // determine frameBits so that copy[i] is no more exception
- while (copy[i] >= (1 << frameBits)) {
- if (frameBits == 30) { // no point to increase further.
- return bestFrameBits;
- }
- ++frameBits;
- // increase bytesForFrame and totalBytes to correspond to frameBits
- int newBytesForFrame = (copy.length * frameBits + 7) / 8;
- totalBytes += newBytesForFrame - bytesForFrame;
- bytesForFrame = newBytesForFrame;
- }
- totalBytes -= bytesPerException; // no more need to store copy[i] as exception
- if (totalBytes <= bestBytes) { // <= : prefer fewer exceptions at higher number of frame bits.
- bestBytes = totalBytes;
- bestFrameBits = frameBits;
- bestExceptions = (copy.length - i - 1);
- }
- }
- if (bestExceptions > 0) { // check for forced exceptions.
- // This ignores the position of the first exception, for which enough bits are available in the header.
- int allowedNumExceptions = bestExceptions + (copy.length >> 5); // 1 in 32 is allowed to be forced.
- // (copy.length >> bestFrameBits): Minimum exception chain size including forced ones,
- // ignoring the position of the first exception.
- while (allowedNumExceptions < (copy.length >> bestFrameBits)) { // Too many forced?
- bestFrameBits++; // Reduce forced exceptions and perhaps reduce actual exceptions
- // Dilemma: decompression speed reduces with increasing number of frame bits,
- // so it may be better to increase no more than once or twice here.
- }
- }
- return bestFrameBits;
- }
}
Modified: lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/gendecompress.py
URL: http://svn.apache.org/viewvc/lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/gendecompress.py?rev=1049731&r1=1049730&r2=1049731&view=diff
==============================================================================
--- lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/gendecompress.py (original)
+++ lucene/dev/branches/bulkpostings/lucene/src/java/org/apache/lucene/util/pfor/gendecompress.py Wed Dec 15 22:23:23 2010
@@ -82,7 +82,7 @@ decodeAnyMethod = ''' static void decod
'''
def genDecompress():
- className = "ForDecompress"
+ className = "ForDecompressImpl"
fileName = className + ".java"
imports = "import java.nio.IntBuffer;\n"
f = open(fileName, 'w')
@@ -111,7 +111,7 @@ def genDecompress():
w("import java.nio.IntBuffer;\n\n")
- w("final class ForDecompress {\n")
+ w("final class ForDecompressImpl {\n")
w('\n // nocommit: assess perf of this to see if specializing is really needed\n')