Author: mduerig
Date: Mon Nov 7 12:35:36 2016
New Revision: 1768507
URL: http://svn.apache.org/viewvc?rev=1768507&view=rev
Log:
OAK-5050: Optimise ImmutableRecordNumbers
Replace map based implementation with an array based one
Removed:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/RecordNumbersIterator.java
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbers.java
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/RecordNumbers.java
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbersTest.java
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbers.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbers.java?rev=1768507&r1=1768506&r2=1768507&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbers.java
(original)
+++
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbers.java
Mon Nov 7 12:35:36 2016
@@ -17,10 +17,11 @@
package org.apache.jackrabbit.oak.segment;
-import static com.google.common.collect.Maps.newLinkedHashMap;
-
import java.util.Iterator;
-import java.util.Map;
+
+import javax.annotation.Nonnull;
+
+import com.google.common.collect.AbstractIterator;
/**
* An immutable record table. It is initialized at construction time and can
@@ -30,32 +31,65 @@ import java.util.Map;
*/
class ImmutableRecordNumbers implements RecordNumbers {
- private final Map<Integer, RecordEntry> records;
+ @Nonnull
+ private final int[] offsets;
+
+ @Nonnull
+ private final byte[] type;
/**
- * Create a new immutable record table.
+ * Create a new instance based on arrays for the offsets and types.
+ * <p>
+ * <em>Note:</em> for performance reasons these arrays are directly
referenced
+ * by this class and must not anymore be modified from other places.
*
- * @param records a map of record numbers to record entries. It can't be
- * {@code null}.
+ * @param offsets Offsets per position. -1 if not mapped.
+ * @param type Types per position. Not defined if not mapped.
*/
- ImmutableRecordNumbers(Map<Integer, RecordEntry> records) {
- this.records = newLinkedHashMap(records);
+ public ImmutableRecordNumbers(@Nonnull int[] offsets, @Nonnull byte[]
type) {
+ this.offsets = offsets;
+ this.type = type;
}
+
@Override
public int getOffset(int recordNumber) {
- RecordEntry entry = records.get(recordNumber);
-
- if (entry == null) {
+ if (recordNumber < offsets.length) {
+ return offsets[recordNumber];
+ } else {
return -1;
}
-
- return entry.getOffset();
}
@Override
public Iterator<Entry> iterator() {
- return new RecordNumbersIterator(records.entrySet().iterator());
+ return new AbstractIterator<Entry>() {
+ private int pos = -1;
+ @Override
+ protected Entry computeNext() {
+ while (++pos < offsets.length && offsets[pos] < 0) { }
+ if (pos < offsets.length) {
+ return new Entry() {
+ @Override
+ public int getRecordNumber() {
+ return pos;
+ }
+
+ @Override
+ public int getOffset() {
+ return offsets[pos];
+ }
+
+ @Override
+ public RecordType getType() {
+ return RecordType.values()[type[pos]];
+ }
+ };
+ } else {
+ return endOfData();
+ }
+ }
+ };
}
}
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/RecordNumbers.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/RecordNumbers.java?rev=1768507&r1=1768506&r2=1768507&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/RecordNumbers.java
(original)
+++
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/RecordNumbers.java
Mon Nov 7 12:35:36 2016
@@ -17,6 +17,10 @@
package org.apache.jackrabbit.oak.segment;
+import static com.google.common.collect.Iterators.emptyIterator;
+
+import java.util.Iterator;
+
import org.apache.jackrabbit.oak.segment.RecordNumbers.Entry;
/**
@@ -25,6 +29,21 @@ import org.apache.jackrabbit.oak.segment
interface RecordNumbers extends Iterable<Entry> {
/**
+ * An always empty {@code RecordNumber} table.
+ */
+ RecordNumbers EMPTY_RECORD_NUMBERS = new RecordNumbers() {
+ @Override
+ public int getOffset(int recordNumber) {
+ return -1;
+ }
+
+ @Override
+ public Iterator<Entry> iterator() {
+ return emptyIterator();
+ }
+ };
+
+ /**
* Translate a record number to an offset.
*
* @param recordNumber A record number.
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java?rev=1768507&r1=1768506&r2=1768507&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java
(original)
+++
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java
Mon Nov 7 12:35:36 2016
@@ -22,8 +22,9 @@ import static com.google.common.base.Pre
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkPositionIndexes;
import static com.google.common.base.Preconditions.checkState;
-import static com.google.common.collect.Maps.newLinkedHashMap;
+import static java.util.Arrays.fill;
import static org.apache.jackrabbit.oak.commons.IOUtils.closeQuietly;
+import static
org.apache.jackrabbit.oak.segment.RecordNumbers.EMPTY_RECORD_NUMBERS;
import static org.apache.jackrabbit.oak.segment.SegmentId.isDataSegmentId;
import static org.apache.jackrabbit.oak.segment.SegmentVersion.LATEST_VERSION;
import static org.apache.jackrabbit.oak.segment.SegmentVersion.isValid;
@@ -38,7 +39,6 @@ import java.nio.channels.Channels;
import java.nio.channels.WritableByteChannel;
import java.util.Arrays;
import java.util.Iterator;
-import java.util.Map;
import java.util.UUID;
import javax.annotation.CheckForNull;
@@ -225,24 +225,29 @@ public class Segment {
* @return An instance of {@link RecordNumbers}, never {@code null}.
*/
private RecordNumbers readRecordNumberOffsets() {
- Map<Integer, RecordEntry> recordNumberOffsets = newLinkedHashMap();
-
- int position = data.position();
+ int recordNumberCount = getRecordNumberCount();
+ if (recordNumberCount == 0) {
+ return EMPTY_RECORD_NUMBERS;
+ }
- position += HEADER_SIZE;
- position += getReferencedSegmentIdCount() * SEGMENT_REFERENCE_SIZE;
+ int position = HEADER_SIZE + data.position()
+ + getReferencedSegmentIdCount() * SEGMENT_REFERENCE_SIZE;
+ int maxIndex = data.getInt(position + (recordNumberCount - 1) * 9);
+
+ byte[] types = new byte[maxIndex + 1];
+ int[] offsets = new int[maxIndex + 1];
+ fill(offsets, -1);
- for (int i = 0; i < getRecordNumberCount(); i++) {
+ for (int i = 0; i < recordNumberCount; i++) {
int recordNumber = data.getInt(position);
position += 4;
- int type = data.get(position);
+ types[recordNumber] = data.get(position);
position += 1;
- int offset = data.getInt(position);
+ offsets[recordNumber] = data.getInt(position);
position += 4;
- recordNumberOffsets.put(recordNumber, new
RecordEntry(RecordType.values()[type], offset));
}
- return new ImmutableRecordNumbers(recordNumberOffsets);
+ return new ImmutableRecordNumbers(offsets, types);
}
private SegmentReferences readReferencedSegments() {
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbersTest.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbersTest.java?rev=1768507&r1=1768506&r2=1768507&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbersTest.java
(original)
+++
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/ImmutableRecordNumbersTest.java
Mon Nov 7 12:35:36 2016
@@ -18,12 +18,13 @@
package org.apache.jackrabbit.oak.segment;
import static com.google.common.collect.Maps.newHashMap;
+import static java.util.Arrays.fill;
import static org.junit.Assert.assertEquals;
import java.util.HashMap;
import java.util.Map;
+import java.util.Set;
-import com.google.common.collect.Maps;
import org.apache.jackrabbit.oak.segment.RecordNumbers.Entry;
import org.junit.Test;
@@ -37,11 +38,13 @@ public class ImmutableRecordNumbersTest
entries.put(3, 4);
entries.put(5, 6);
- ImmutableRecordNumbers table = new
ImmutableRecordNumbers(recordEntries(entries));
+ ImmutableRecordNumbers table = new
ImmutableRecordNumbers(offsets(entries), types(entries));
assertEquals(2, table.getOffset(1));
assertEquals(4, table.getOffset(3));
assertEquals(6, table.getOffset(5));
+ assertEquals(-1, table.getOffset(2));
+ assertEquals(-1, table.getOffset(42));
}
@Test
@@ -52,7 +55,7 @@ public class ImmutableRecordNumbersTest
entries.put(3, 4);
entries.put(5, 6);
- ImmutableRecordNumbers table = new
ImmutableRecordNumbers(recordEntries(entries));
+ ImmutableRecordNumbers table = new
ImmutableRecordNumbers(offsets(entries), types(entries));
entries.put(1, 3);
entries.put(7, 8);
@@ -61,6 +64,8 @@ public class ImmutableRecordNumbersTest
assertEquals(2, table.getOffset(1));
assertEquals(4, table.getOffset(3));
assertEquals(6, table.getOffset(5));
+ assertEquals(-1, table.getOffset(2));
+ assertEquals(-1, table.getOffset(42));
}
@Test
@@ -71,7 +76,7 @@ public class ImmutableRecordNumbersTest
entries.put(3, 4);
entries.put(5, 6);
- ImmutableRecordNumbers table = new
ImmutableRecordNumbers(recordEntries(entries));
+ ImmutableRecordNumbers table = new
ImmutableRecordNumbers(offsets(entries), types(entries));
Map<Integer, Integer> iterated = new HashMap<>();
@@ -92,4 +97,31 @@ public class ImmutableRecordNumbersTest
return entries;
}
+ private int[] offsets(Map<Integer, Integer> entries) {
+ int[] offsets = new int[max(entries.keySet()) + 1];
+ fill(offsets, -1);
+
+ for (Map.Entry<Integer, Integer> entry : entries.entrySet()) {
+ offsets[entry.getKey()] = entry.getValue();
+ }
+
+ return offsets;
+ }
+
+ private byte[] types(Map<Integer, Integer> entries) {
+ byte[] types = new byte[max(entries.keySet()) + 1];
+ fill(types, (byte) RecordType.VALUE.ordinal());
+ return types;
+ }
+
+ private int max(Set<Integer> integers) {
+ int max = -1;
+ for (Integer integer : integers) {
+ if (integer > max) {
+ max = integer;
+ }
+ }
+ return max;
+ }
+
}
