From f70d05fab5b02a1c262a244f66b1ce0b15465c04 Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Fri, 21 Apr 2023 19:18:42 +0200 Subject: Revert "use value density to estimate needed decode index size" --- .../src/main/java/com/yahoo/slime/BinaryView.java | 90 ++++----- .../src/main/java/com/yahoo/slime/DecodeIndex.java | 60 +++--- .../test/java/com/yahoo/slime/BinaryViewTest.java | 4 +- .../test/java/com/yahoo/slime/DecodeIndexTest.java | 217 +++------------------ 4 files changed, 94 insertions(+), 277 deletions(-) (limited to 'vespajlib') diff --git a/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java b/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java index c54c9e7930e..0e111d42061 100644 --- a/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java +++ b/vespajlib/src/main/java/com/yahoo/slime/BinaryView.java @@ -14,24 +14,15 @@ public final class BinaryView implements Inspector { private final byte[] data; private final SymbolTable names; - private final long[] index; + private final DecodeIndex index; private final int self; - private BinaryView(byte[] data, SymbolTable names, long[] index, int self) { + private BinaryView(byte[] data, SymbolTable names, DecodeIndex index, int self) { this.data = data; this.names = names; this.index = index; this.self = self; } - private int byte_offset(int idx) { - return (int)(index[idx] >> 33) & 0x7fff_ffff; - } - private int first_child(int idx) { - return (int)(index[idx] >> 2) & 0x7fff_ffff; - } - private int ext_bits(int idx) { - return (int)index[idx] & 0x3; - } private int peek_cmpr_int(int idx) { long next = data[idx++]; long value = (next & 0x7f); @@ -101,8 +92,8 @@ public final class BinaryView implements Inspector { } private Inspector find_field(int pos, int len, int sym) { for (int i = 0; i < len; ++i) { - int idx = byte_offset(pos + i); - if (peek_cmpr_int(idx - (ext_bits(pos + i) + 1)) == sym) { + int idx = index.getByteOffset(pos + i); + if (peek_cmpr_int(idx - (index.getExtBits(pos + i) + 1)) == sym) { return new BinaryView(data, names, index, pos + i); } } @@ -111,110 +102,110 @@ public final class BinaryView implements Inspector { @Override public boolean valid() { return true; } @Override public void ifValid(Consumer consumer) { consumer.accept(this); } - @Override public Type type() { return decode_type(data[byte_offset(self)]); } + @Override public Type type() { return decode_type(data[index.getByteOffset(self)]); } @Override public int children() { return switch (type()) { - case OBJECT, ARRAY -> extract_children(byte_offset(self)); + case OBJECT, ARRAY -> extract_children(index.getByteOffset(self)); default -> 0; }; } @Override public int entries() { return switch (type()) { - case ARRAY -> extract_children(byte_offset(self)); + case ARRAY -> extract_children(index.getByteOffset(self)); default -> 0; }; } @Override public int fields() { return switch (type()) { - case OBJECT -> extract_children(byte_offset(self)); + case OBJECT -> extract_children(index.getByteOffset(self)); default -> 0; }; } @Override public boolean asBool() { return switch (type()) { - case BOOL -> (decode_meta(data[byte_offset(self)]) != 0); + case BOOL -> (decode_meta(data[index.getByteOffset(self)]) != 0); default -> false; }; } @Override public long asLong() { return switch (type()) { - case LONG -> extract_long(byte_offset(self)); - case DOUBLE -> (long)extract_double(byte_offset(self)); + case LONG -> extract_long(index.getByteOffset(self)); + case DOUBLE -> (long)extract_double(index.getByteOffset(self)); default -> 0; }; } @Override public double asDouble() { return switch (type()) { - case LONG -> extract_long(byte_offset(self)); - case DOUBLE -> extract_double(byte_offset(self)); + case LONG -> extract_long(index.getByteOffset(self)); + case DOUBLE -> extract_double(index.getByteOffset(self)); default -> 0.0; }; } @Override public String asString() { return switch (type()) { - case STRING -> extract_string(byte_offset(self)); + case STRING -> extract_string(index.getByteOffset(self)); default -> Value.emptyString; }; } @Override public byte[] asUtf8() { return switch (type()) { - case STRING -> extract_bytes(byte_offset(self)); + case STRING -> extract_bytes(index.getByteOffset(self)); default -> Value.emptyData; }; } @Override public byte[] asData() { return switch (type()) { - case DATA -> extract_bytes(byte_offset(self)); + case DATA -> extract_bytes(index.getByteOffset(self)); default -> Value.emptyData; }; } @Override public void accept(Visitor v) { switch (type()) { case NIX: v.visitNix(); break; - case BOOL: v.visitBool(decode_meta(data[byte_offset(self)]) != 0); break; - case LONG: v.visitLong(extract_long(byte_offset(self))); break; - case DOUBLE: v.visitDouble(extract_double(byte_offset(self))); break; - case STRING: v.visitString(extract_bytes(byte_offset(self))); break; - case DATA: v.visitData(extract_bytes(byte_offset(self))); break; + case BOOL: v.visitBool(decode_meta(data[index.getByteOffset(self)]) != 0); break; + case LONG: v.visitLong(extract_long(index.getByteOffset(self))); break; + case DOUBLE: v.visitDouble(extract_double(index.getByteOffset(self))); break; + case STRING: v.visitString(extract_bytes(index.getByteOffset(self))); break; + case DATA: v.visitData(extract_bytes(index.getByteOffset(self))); break; case ARRAY: v.visitArray(this); break; case OBJECT: v.visitObject(this); break; default: throw new RuntimeException("should not be reached"); } } @Override public void traverse(ArrayTraverser at) { - int pos = first_child(self); + int pos = index.getFirstChild(self); int len = entries(); for (int i = 0; i < len; ++i) { at.entry(i, new BinaryView(data, names, index, pos + i)); } } @Override public void traverse(ObjectSymbolTraverser ot) { - int pos = first_child(self); + int pos = index.getFirstChild(self); int len = fields(); for (int i = 0; i < len; ++i) { - int sym = peek_cmpr_int(byte_offset(pos + i) - (ext_bits(pos + i) + 1)); + int sym = peek_cmpr_int(index.getByteOffset(pos + i) - (index.getExtBits(pos + i) + 1)); ot.field(sym, new BinaryView(data, names, index, pos + i)); } } @Override public void traverse(ObjectTraverser ot) { - int pos = first_child(self); + int pos = index.getFirstChild(self); int len = fields(); for (int i = 0; i < len; ++i) { - int sym = peek_cmpr_int(byte_offset(pos + i) - (ext_bits(pos + i) + 1)); + int sym = peek_cmpr_int(index.getByteOffset(pos + i) - (index.getExtBits(pos + i) + 1)); ot.field(names.inspect(sym), new BinaryView(data, names, index, pos + i)); } } @Override public Inspector entry(int idx) { int limit = entries(); if (idx >= 0 && idx < limit) { - return new BinaryView(data, names, index, first_child(self) + idx); + return new BinaryView(data, names, index, index.getFirstChild(self) + idx); } return NixValue.invalid(); } @Override public Inspector field(int sym) { int limit = fields(); if (limit > 0 && sym != SymbolTable.INVALID) { - return find_field(first_child(self), limit, sym); + return find_field(index.getFirstChild(self), limit, sym); } return NixValue.invalid(); } @@ -223,7 +214,7 @@ public final class BinaryView implements Inspector { if (limit > 0) { int sym = names.lookup(name); if (sym != SymbolTable.INVALID) { - return find_field(first_child(self), limit, sym); + return find_field(index.getFirstChild(self), limit, sym); } } return NixValue.invalid(); @@ -252,11 +243,11 @@ public final class BinaryView implements Inspector { break; } case ARRAY: { int size = input.read_size(meta); - int firstChild = index.tryReserveChildren(size, self + 1, input.getPosition()); - if (firstChild < 0) { + if (size > input.getBacking().length - index.size()) { input.fail("decode index too big"); return; } + int firstChild = index.reserve(size); index.set(self, pos, firstChild, extBits); for (int i = 0; i < size; ++i) { buildIndex(input, index, firstChild + i, 0); @@ -264,11 +255,11 @@ public final class BinaryView implements Inspector { break; } case OBJECT: { int size = input.read_size(meta); - int firstChild = index.tryReserveChildren(size, self + 1, input.getPosition()); - if (firstChild < 0) { + if (size > input.getBacking().length - index.size()) { input.fail("decode index too big"); return; } + int firstChild = index.reserve(size); index.set(self, pos, firstChild, extBits); for (int i = 0; i < size; ++i) { int childExtBits = input.skip_cmpr_int(); @@ -285,13 +276,13 @@ public final class BinaryView implements Inspector { static Inspector inspectImpl(BufferedInput input) { var names = new SymbolTable(); + var index = new DecodeIndex(); BinaryDecoder.decodeSymbolTable(input, names); - var index = new DecodeIndex(input.getBacking().length, input.getPosition()); - buildIndex(input, index, 0, 0); + buildIndex(input, index, index.reserve(1), 0); if (input.failed()) { return NixValue.invalid(); } - return new BinaryView(input.getBacking(), names, index.getBacking(), 0); + return new BinaryView(input.getBacking(), names, index, 0); } public static Inspector inspect(byte[] data) { @@ -313,13 +304,4 @@ public final class BinaryView implements Inspector { static double extract_double_for_testing(byte[] data, int idx) { return new BinaryView(data, null, null, -1).extract_double(idx); } - static int byte_offset_for_testing(DecodeIndex index, int idx) { - return new BinaryView(null, null, index.getBacking(), -1).byte_offset(idx); - } - static int first_child_for_testing(DecodeIndex index, int idx) { - return new BinaryView(null, null, index.getBacking(), -1).first_child(idx); - } - static int ext_bits_for_testing(DecodeIndex index, int idx) { - return new BinaryView(null, null, index.getBacking(), -1).ext_bits(idx); - } } diff --git a/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java b/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java index 5df24154a08..17c7a86730e 100644 --- a/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java +++ b/vespajlib/src/main/java/com/yahoo/slime/DecodeIndex.java @@ -6,46 +6,23 @@ package com.yahoo.slime; * encoded in binary format. **/ final class DecodeIndex { - private long[] data; - private int reserved; - private final int totalSize; - private final int rootOffset; - - private int binarySize() { return totalSize - rootOffset; } - - private int adjustSize(int minSize, int maxSize, int cnt, int byteOffset) { - double density = (double)cnt / (double)(byteOffset - rootOffset); - double estSize = 1.1 * density * binarySize(); - double expSize = 1.25 * data.length; - double wantedSize = (estSize > expSize) ? estSize : expSize; - if (wantedSize < minSize) { - return minSize; + static final int initial_capacity = 16; + private long[] data = new long[initial_capacity]; + private int reserved = 0; + + private int adjustSize(int minSize) { + int capacity = initial_capacity; + while (capacity < minSize) { + capacity = capacity << 1; } - if (wantedSize > maxSize) { - return maxSize; - } - return (int)wantedSize; - } - - DecodeIndex(int totalSize, int rootOffset) { - this.totalSize = totalSize; - this.rootOffset = rootOffset; - int initialCapacity = Math.max(16, binarySize() / 24); - data = new long[initialCapacity]; - reserved = 1; + return capacity; } - long[] getBacking() { return data; } - - int tryReserveChildren(int n, int cnt, int byteOffset) { + int reserve(int n) { int offset = reserved; - if (n > data.length - reserved) { - final int maxSize = (totalSize - byteOffset) + cnt; - if (n > maxSize - reserved) { - return -1; // error; too much space requested - } + if (reserved + n > data.length) { long[] old = data; - data = new long[adjustSize(reserved + n, maxSize, cnt, byteOffset)]; + data = new long[adjustSize(reserved + n)]; System.arraycopy(old, 0, data, 0, reserved); } reserved += n; @@ -53,11 +30,22 @@ final class DecodeIndex { } int size() { return reserved; } - int capacity() { return data.length; } void set(int idx, int byteOffset, int firstChild, int extBits) { data[idx] = (long)(byteOffset & 0x7fff_ffff) << 33 | (long)(firstChild & 0x7fff_ffff) << 2 | extBits & 0x3; } + + int getByteOffset(int idx) { + return (int)(data[idx] >> 33) & 0x7fff_ffff; + } + + int getFirstChild(int idx) { + return (int)(data[idx] >> 2) & 0x7fff_ffff; + } + + int getExtBits(int idx) { + return (int)data[idx] & 0x3; + } } diff --git a/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java b/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java index c45d7a9c59e..920a25b96c9 100644 --- a/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java +++ b/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java @@ -343,7 +343,7 @@ public class BinaryViewTest { } @Test public void testDecodeIndexOverflowArray() { - byte[] data = { 0, encode_type_and_meta(Type.ARRAY.ID, 20) }; + byte[] data = { 0, encode_type_and_meta(Type.ARRAY.ID, 4) }; var input = new BufferedInput(data); var view = BinaryView.inspectImpl(input); assertFalse(view.valid()); @@ -352,7 +352,7 @@ public class BinaryViewTest { } @Test public void testDecodeIndexOverflowObject() { - byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 20) }; + byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 4) }; var input = new BufferedInput(data); var view = BinaryView.inspectImpl(input); assertFalse(view.valid()); diff --git a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java index c34a718d2bb..223701fa2fd 100644 --- a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java +++ b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java @@ -3,236 +3,83 @@ package com.yahoo.slime; import org.junit.Test; import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; -import static com.yahoo.slime.BinaryView.byte_offset_for_testing; -import static com.yahoo.slime.BinaryView.first_child_for_testing; -import static com.yahoo.slime.BinaryView.ext_bits_for_testing; public class DecodeIndexTest { - int checkCapacity(DecodeIndex index, int oldCapacity) { - int capacity = index.capacity(); - if (oldCapacity == -1) { - System.out.println("DecodeIndex initial capacity " + capacity); - } else if (capacity != oldCapacity) { - System.out.println("DecodeIndex capacity increased to " + capacity); - } - return capacity; - } - @Test public void testSimpleUsage() { - DecodeIndex index = new DecodeIndex(100, 10); - assertEquals(1, index.size()); - int capacity = checkCapacity(index, -1); - int root = 0; - capacity = checkCapacity(index, capacity); - int val2 = index.tryReserveChildren(3, 1, 15); - capacity = checkCapacity(index, capacity); - int val3 = index.tryReserveChildren(2, 2, 20); - capacity = checkCapacity(index, capacity); + DecodeIndex index = new DecodeIndex(); + int val1 = index.reserve(1); + int val2 = index.reserve(3); + int val3 = index.reserve(2); + assertEquals(0, val1); assertEquals(1, val2); assertEquals(4, val3); assertEquals(6, index.size()); - index.set(root, 0, val2, 0); + index.set(val1 + 0, 0, val2, 0); index.set(val2 + 0, 100, 0, 1); index.set(val2 + 1, 200, val3, 2); index.set(val2 + 2, 300, 0, 3); index.set(val3 + 0, 400, 0, 0); index.set(val3 + 1, 500, 0, 0); for (int i = 0; i < 6; i++) { - assertEquals(i * 100, byte_offset_for_testing(index, i)); + assertEquals(i * 100, index.getByteOffset(i)); if (i == 0) { - assertEquals(1, first_child_for_testing(index, i)); + assertEquals(1, index.getFirstChild(i)); } else if (i == 2) { - assertEquals(4, first_child_for_testing(index, i)); + assertEquals(4, index.getFirstChild(i)); } else { - assertEquals(0, first_child_for_testing(index, i)); + assertEquals(0, index.getFirstChild(i)); } if (i < 4) { - assertEquals(i, ext_bits_for_testing(index, i)); + assertEquals(i, index.getExtBits(i)); } else { - assertEquals(0, ext_bits_for_testing(index, i)); + assertEquals(0, index.getExtBits(i)); } } } @Test public void testManyValues() { + DecodeIndex index = new DecodeIndex(); int outer = 47; int inner = 73; - int symSize = 128; - int bytesPerValue = 5; - DecodeIndex index = new DecodeIndex(symSize + inner * outer * bytesPerValue, symSize); - int capacity = checkCapacity(index, -1); - int indexOffset = 1; - int binaryOffset = symSize + bytesPerValue; - int expectOffset = 1; + int expectOffset = 0; for (int i = 0; i < outer; i++) { - int offset = index.tryReserveChildren(inner, indexOffset, binaryOffset); - capacity = checkCapacity(index, capacity); + int offset = index.reserve(inner); assertEquals(expectOffset, offset); expectOffset += inner; for (int j = 0; j < inner; j++) { index.set(offset + j, (i * j), (i + j), (j & 3)); - ++indexOffset; - binaryOffset += bytesPerValue; } } - assertEquals(1 + inner * outer, expectOffset); - assertEquals(1 + inner * outer, index.size()); + assertEquals(inner * outer, expectOffset); + assertEquals(inner * outer, index.size()); for (int i = 0; i < outer; i++) { for (int j = 0; j < inner; j++) { - int offset = 1 + i * inner + j; - assertEquals(i * j, byte_offset_for_testing(index, offset)); - assertEquals(i + j, first_child_for_testing(index, offset)); - assertEquals(j & 3, ext_bits_for_testing(index, offset)); + int offset = i * inner + j; + assertEquals(i * j, index.getByteOffset(offset)); + assertEquals(i + j, index.getFirstChild(offset)); + assertEquals(j & 3, index.getExtBits(offset)); } } } @Test public void testOverflowNoBleed() { - DecodeIndex index = new DecodeIndex(100, 10); - index.tryReserveChildren(2, 1, 20); - assertEquals(3, index.size()); + DecodeIndex index = new DecodeIndex(); + index.reserve(3); index.set(0, 0xffff_ffff, 0, 0); index.set(1, 0, 0xffff_ffff, 0); index.set(2, 0, 0, 0xffff_ffff); - assertEquals(0x7fff_ffff, byte_offset_for_testing(index, 0)); - assertEquals(0, byte_offset_for_testing(index, 1)); - assertEquals(0, byte_offset_for_testing(index, 2)); - assertEquals(0, first_child_for_testing(index, 0)); - assertEquals(0x7fff_ffff, first_child_for_testing(index, 1)); - assertEquals(0, first_child_for_testing(index, 2)); - assertEquals(0, ext_bits_for_testing(index, 0)); - assertEquals(0, ext_bits_for_testing(index, 1)); - assertEquals(3, ext_bits_for_testing(index, 2)); - } - - @Test - public void testMinimalInitialCapacity() { - DecodeIndex index = new DecodeIndex(2, 1); - assertEquals(16, index.capacity()); - } - - @Test - public void testInitialCapacityEstimate() { - DecodeIndex index = new DecodeIndex((33 * 24) + 167, 167); - assertEquals(33, index.capacity()); - } - - void assertWithinRange(int low, int high, int actual) { - if (actual >= low && actual <= high) { - System.out.println("value " + actual + " in range [" + low + "," + high + "]"); - } else { - fail("value " + actual + " not in range [" + low + "," + high + "]"); - } - } - - void assertGreater(int limit, int actual) { - if (actual > limit) { - System.out.println("value " + actual + " is greater than " + limit); - } else { - fail("value " + actual + " is not greater than " + limit); - } - } - - void assertLess(int limit, int actual) { - if (actual < limit) { - System.out.println("value " + actual + " is less than " + limit); - } else { - fail("value " + actual + " is not less than " + limit); - } - } - - DecodeIndex prepareIndex(int symSize, int numValues) { - DecodeIndex index = new DecodeIndex((numValues * 24) + symSize, symSize); - assertEquals(1, index.tryReserveChildren(numValues - 1, 1, symSize + 24)); - assertEquals(numValues, index.size()); - assertEquals(numValues, index.capacity()); - return index; - } - - @Test - public void testDensityBasedCapacityEstimate() { - var index = prepareIndex(167, 33); - double exp = 1.25 * index.capacity(); - assertEquals(33, index.tryReserveChildren(10, 20, 167 + (20 * 4))); - int doneCnt = 20; - double bytesPerObject = 4.0; - int pendingData = (33 * 24) - (20 * 4); - double est = (doneCnt + pendingData / bytesPerObject); - int maxSize = doneCnt + pendingData; - assertGreater((int)(exp * 1.05), index.capacity()); - assertWithinRange((int)(1.05 * est), (int)(1.15 * est), index.capacity()); - assertLess(maxSize, index.capacity()); - } - - @Test - public void testExpCapacityGrowth() { - var index = prepareIndex(167, 33); - double exp = 1.25 * index.capacity(); - assertEquals(33, index.tryReserveChildren(1, 20, 167 + (20 * 32))); - int doneCnt = 20; - double bytesPerObject = 32.0; - int pendingData = (33 * 24) - (20 * 32); - double est = (doneCnt + pendingData / bytesPerObject); - int maxSize = doneCnt + pendingData; - assertWithinRange((int)(0.95 * exp), (int)(1.05 * exp), index.capacity()); - assertGreater((int)(est * 1.15), index.capacity()); - assertLess(maxSize, index.capacity()); - } - - @Test - public void testMinCapacityGrowth() { - var index = prepareIndex(167, 33); - double exp = 1.25 * index.capacity(); - assertEquals(33, index.tryReserveChildren(20, 20, 167 + (20 * 32))); - int doneCnt = 20; - double bytesPerObject = 32.0; - int pendingData = (33 * 24) - (20 * 32); - double est = (doneCnt + pendingData / bytesPerObject); - int maxSize = doneCnt + pendingData; - assertGreater((int)(exp * 1.05), index.capacity()); - assertGreater((int)(est * 1.15), index.capacity()); - assertEquals(33 + 20, index.capacity()); - assertLess(maxSize, index.capacity()); - } - - @Test - public void testMaxCapacityGrowth() { - var index = prepareIndex(167, 33); - double exp = 1.25 * index.capacity(); - assertEquals(33, index.tryReserveChildren(1, 32, 167 + (33 * 24) - 3)); - int minSize = 33 + 1; - int maxSize = 32 + 3; - assertLess((int)(exp * 0.95), index.capacity()); - assertGreater(minSize, index.capacity()); - assertEquals(maxSize, index.capacity()); - } - - @Test - public void testMinMaxCapacityGrowth() { - var index = prepareIndex(167, 33); - assertEquals(-1, index.tryReserveChildren(5, 32, 167 + (33 * 24) - 3)); - assertEquals(33, index.capacity()); - } - - @Test - public void testExpNanCapacityGrowth() { - var index = prepareIndex(167, 33); - double exp = 1.25 * index.capacity(); - assertEquals(33, index.tryReserveChildren(1, 0, 167)); - assertWithinRange((int)(0.95 * exp), (int)(1.05 * exp), index.capacity()); - } - - @Test - public void testMaxInfCapacityGrowth() { - var index = prepareIndex(167, 17); - double exp = 1.25 * index.capacity(); - assertEquals(17, index.tryReserveChildren(1, 10, 167)); - int maxSize = 10 + (17 * 24); - assertEquals(maxSize, index.capacity()); + assertEquals(0x7fff_ffff, index.getByteOffset(0)); + assertEquals(0, index.getByteOffset(1)); + assertEquals(0, index.getByteOffset(2)); + assertEquals(0, index.getFirstChild(0)); + assertEquals(0x7fff_ffff, index.getFirstChild(1)); + assertEquals(0, index.getFirstChild(2)); + assertEquals(0, index.getExtBits(0)); + assertEquals(0, index.getExtBits(1)); + assertEquals(3, index.getExtBits(2)); } } -- cgit v1.2.3