You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@orc.apache.org by go...@apache.org on 2017/11/08 02:51:18 UTC
orc git commit: ORC-187: BitFieldReader has an unnecessary loop
Repository: orc
Updated Branches:
refs/heads/master c52c494e3 -> 0ee4b1070
ORC-187: BitFieldReader has an unnecessary loop
Fixes #186
Signed-off-by: Gopal V <go...@apache.org>
Project: http://git-wip-us.apache.org/repos/asf/orc/repo
Commit: http://git-wip-us.apache.org/repos/asf/orc/commit/0ee4b107
Tree: http://git-wip-us.apache.org/repos/asf/orc/tree/0ee4b107
Diff: http://git-wip-us.apache.org/repos/asf/orc/diff/0ee4b107
Branch: refs/heads/master
Commit: 0ee4b1070f1236c8bf5d399393fdf17e758a53e6
Parents: c52c494
Author: Rajesh Balamohan <rb...@apache.org>
Authored: Tue Nov 7 18:45:01 2017 -0800
Committer: Gopal V <go...@apache.org>
Committed: Tue Nov 7 18:50:45 2017 -0800
----------------------------------------------------------------------
.../org/apache/orc/impl/BitFieldReader.java | 145 +++----------------
.../org/apache/orc/impl/TreeReaderFactory.java | 8 +-
.../org/apache/orc/impl/TestBitFieldReader.java | 35 +----
3 files changed, 27 insertions(+), 161 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/orc/blob/0ee4b107/java/core/src/java/org/apache/orc/impl/BitFieldReader.java
----------------------------------------------------------------------
diff --git a/java/core/src/java/org/apache/orc/impl/BitFieldReader.java b/java/core/src/java/org/apache/orc/impl/BitFieldReader.java
index b6ac667..9102555 100644
--- a/java/core/src/java/org/apache/orc/impl/BitFieldReader.java
+++ b/java/core/src/java/org/apache/orc/impl/BitFieldReader.java
@@ -22,112 +22,34 @@ import java.io.IOException;
import org.apache.hadoop.hive.ql.exec.vector.LongColumnVector;
-public class BitFieldReader {
+public final class BitFieldReader {
private final RunLengthByteReader input;
/** The number of bits in one item. Non-test code always uses 1. */
- private final int bitSize;
private int current;
- private int bitsLeft;
- private final int mask;
+ private byte currentIdx;
- public BitFieldReader(InStream input,
- int bitSize) {
+ public BitFieldReader(InStream input) {
this.input = new RunLengthByteReader(input);
- this.bitSize = bitSize;
- mask = (1 << bitSize) - 1;
- }
-
- public void setInStream(InStream inStream) {
- this.input.setInStream(inStream);
}
private void readByte() throws IOException {
if (input.hasNext()) {
current = 0xff & input.next();
- bitsLeft = 8;
+ currentIdx = 0;
} else {
throw new EOFException("Read past end of bit field from " + this);
}
}
public int next() throws IOException {
- int result = 0;
- int bitsLeftToRead = bitSize;
- while (bitsLeftToRead > bitsLeft) {
- result <<= bitsLeft;
- result |= current & ((1 << bitsLeft) - 1);
- bitsLeftToRead -= bitsLeft;
+ // mod 8
+ if ((currentIdx & 7) == 0) {
readByte();
}
- if (bitsLeftToRead > 0) {
- result <<= bitsLeftToRead;
- bitsLeft -= bitsLeftToRead;
- result |= (current >>> bitsLeft) & ((1 << bitsLeftToRead) - 1);
- }
- return result & mask;
- }
- /**
- * Unlike integer readers, where runs are encoded explicitly, in this one we have to read ahead
- * to figure out whether we have a run. Given that runs in booleans are likely it's worth it.
- * However it means we'd need to keep track of how many bytes we read, and next/nextVector won't
- * work anymore once this is called. These is trivial to fix, but these are never interspersed.
- */
- private boolean lastRunValue;
- private int lastRunLength = -1;
- private void readNextRun(int maxRunLength) throws IOException {
- assert bitSize == 1;
- if (lastRunLength > 0) return; // last run is not exhausted yet
- if (bitsLeft == 0) {
- readByte();
- }
- // First take care of the partial bits.
- boolean hasVal = false;
- int runLength = 0;
- if (bitsLeft != 8) {
- int partialBitsMask = (1 << bitsLeft) - 1;
- int partialBits = current & partialBitsMask;
- if (partialBits == partialBitsMask || partialBits == 0) {
- lastRunValue = (partialBits == partialBitsMask);
- if (maxRunLength <= bitsLeft) {
- lastRunLength = maxRunLength;
- return;
- }
- maxRunLength -= bitsLeft;
- hasVal = true;
- runLength = bitsLeft;
- bitsLeft = 0;
- } else {
- // There's no run in partial bits. Return whatever we have.
- int prefixBitsCount = 32 - bitsLeft;
- runLength = Integer.numberOfLeadingZeros(partialBits) - prefixBitsCount;
- lastRunValue = (runLength > 0);
- lastRunLength = Math.min(maxRunLength, lastRunValue ? runLength :
- (Integer.numberOfLeadingZeros(~(partialBits | ~partialBitsMask)) - prefixBitsCount));
- return;
- }
- assert bitsLeft == 0;
- readByte();
- }
- if (!hasVal) {
- lastRunValue = ((current >> 7) == 1);
- hasVal = true;
- }
- // Read full bytes until the run ends.
- assert bitsLeft == 8;
- while (maxRunLength >= 8
- && ((lastRunValue && (current == 0xff)) || (!lastRunValue && (current == 0)))) {
- runLength += 8;
- maxRunLength -= 8;
- readByte();
- }
- if (maxRunLength > 0) {
- int extraBits = Integer.numberOfLeadingZeros(
- lastRunValue ? (~(current | ~255)) : current) - 24;
- bitsLeft -= extraBits;
- runLength += extraBits;
- }
- lastRunLength = runLength;
+ currentIdx++;
+ // Highest bit is the first val
+ return ((current >>> (8 - currentIdx)) & 1);
}
public void nextVector(LongColumnVector previous,
@@ -162,53 +84,28 @@ public class BitFieldReader {
consumed + " in " + input);
} else if (consumed != 0) {
readByte();
- bitsLeft = 8 - consumed;
+ currentIdx = (byte) consumed;
} else {
- bitsLeft = 0;
+ currentIdx = 0;
}
}
- public void skip(long items) throws IOException {
- long totalBits = bitSize * items;
- if (bitsLeft >= totalBits) {
- bitsLeft -= totalBits;
+ public void skip(long totalBits) throws IOException {
+ final int availableBits = 8 - currentIdx;
+ if (totalBits <= availableBits) {
+ currentIdx += totalBits;
} else {
- totalBits -= bitsLeft;
- input.skip(totalBits / 8);
+ final long bitsToSkip = (totalBits - availableBits);
+ input.skip(bitsToSkip / 8);
current = input.next();
- bitsLeft = (int) (8 - (totalBits % 8));
+ currentIdx = (byte) (bitsToSkip % 8);
}
}
@Override
public String toString() {
- return "bit reader current: " + current + " bits left: " + bitsLeft +
- " bit size: " + bitSize + " from " + input;
- }
-
- boolean hasFullByte() {
- return bitsLeft == 8 || bitsLeft == 0;
- }
-
- int peekOneBit() throws IOException {
- assert bitSize == 1;
- if (bitsLeft == 0) {
- readByte();
- }
- return (current >>> (bitsLeft - 1)) & 1;
- }
-
- int peekFullByte() throws IOException {
- assert bitSize == 1;
- assert bitsLeft == 8 || bitsLeft == 0;
- if (bitsLeft == 0) {
- readByte();
- }
- return current;
- }
-
- void skipInCurrentByte(int bits) throws IOException {
- assert bitsLeft >= bits;
- bitsLeft -= bits;
+ return "bit reader current: " + current
+ + " current bit index: " + currentIdx
+ + " from " + input;
}
}
http://git-wip-us.apache.org/repos/asf/orc/blob/0ee4b107/java/core/src/java/org/apache/orc/impl/TreeReaderFactory.java
----------------------------------------------------------------------
diff --git a/java/core/src/java/org/apache/orc/impl/TreeReaderFactory.java b/java/core/src/java/org/apache/orc/impl/TreeReaderFactory.java
index 1de18e2..3e84a87 100644
--- a/java/core/src/java/org/apache/orc/impl/TreeReaderFactory.java
+++ b/java/core/src/java/org/apache/orc/impl/TreeReaderFactory.java
@@ -110,7 +110,7 @@ public class TreeReaderFactory {
if (in == null) {
present = null;
} else {
- present = new BitFieldReader(in, 1);
+ present = new BitFieldReader(in);
}
vectorColumnCount = -1;
}
@@ -151,7 +151,7 @@ public class TreeReaderFactory {
if (in == null) {
present = null;
} else {
- present = new BitFieldReader(in, 1);
+ present = new BitFieldReader(in);
}
}
@@ -298,7 +298,7 @@ public class TreeReaderFactory {
protected BooleanTreeReader(int columnId, InStream present, InStream data) throws IOException {
super(columnId, present, null);
if (data != null) {
- reader = new BitFieldReader(data, 1);
+ reader = new BitFieldReader(data);
}
}
@@ -308,7 +308,7 @@ public class TreeReaderFactory {
) throws IOException {
super.startStripe(streams, stripeFooter);
reader = new BitFieldReader(streams.get(new StreamName(columnId,
- OrcProto.Stream.Kind.DATA)), 1);
+ OrcProto.Stream.Kind.DATA)));
}
@Override
http://git-wip-us.apache.org/repos/asf/orc/blob/0ee4b107/java/core/src/test/org/apache/orc/impl/TestBitFieldReader.java
----------------------------------------------------------------------
diff --git a/java/core/src/test/org/apache/orc/impl/TestBitFieldReader.java b/java/core/src/test/org/apache/orc/impl/TestBitFieldReader.java
index e4c6f6b..156f10a 100644
--- a/java/core/src/test/org/apache/orc/impl/TestBitFieldReader.java
+++ b/java/core/src/test/org/apache/orc/impl/TestBitFieldReader.java
@@ -49,7 +49,7 @@ public class TestBitFieldReader {
inBuf.flip();
BitFieldReader in = new BitFieldReader(InStream.create("test",
new ByteBuffer[]{inBuf}, new long[]{0}, inBuf.remaining(),
- codec, 500), 1);
+ codec, 500));
for(int i=0; i < COUNT; ++i) {
int x = in.next();
if (i < COUNT / 2) {
@@ -80,37 +80,6 @@ public class TestBitFieldReader {
}
@Test
- public void testBiggerItems() throws Exception {
- TestInStream.OutputCollector collect = new TestInStream.OutputCollector();
- final int COUNT = 16384;
- BitFieldWriter out = new BitFieldWriter(
- new OutStream("test", 500, null, collect), 3);
- for(int i=0; i < COUNT; ++i) {
- // test runs, non-runs
- if (i < COUNT / 2) {
- out.write(i & 7);
- } else {
- out.write((i/3) & 7);
- }
- }
- out.flush();
- ByteBuffer inBuf = ByteBuffer.allocate(collect.buffer.size());
- collect.buffer.setByteBuffer(inBuf, 0, collect.buffer.size());
- inBuf.flip();
- BitFieldReader in = new BitFieldReader(InStream.create("test",
- new ByteBuffer[]{inBuf}, new long[]{0}, inBuf.remaining(),
- null, 500), 3);
- for(int i=0; i < COUNT; ++i) {
- int x = in.next();
- if (i < COUNT / 2) {
- assertEquals(i & 7, x);
- } else {
- assertEquals((i/3) & 7, x);
- }
- }
- }
-
- @Test
public void testSkips() throws Exception {
TestInStream.OutputCollector collect = new TestInStream.OutputCollector();
BitFieldWriter out = new BitFieldWriter(
@@ -128,7 +97,7 @@ public class TestBitFieldReader {
collect.buffer.setByteBuffer(inBuf, 0, collect.buffer.size());
inBuf.flip();
BitFieldReader in = new BitFieldReader(InStream.create("test", new ByteBuffer[]{inBuf},
- new long[]{0}, inBuf.remaining(), null, 100), 1);
+ new long[]{0}, inBuf.remaining(), null, 100));
for(int i=0; i < COUNT; i += 5) {
int x = (int) in.next();
if (i < COUNT/2) {