object density estimate take 2

fix: count processed values explicitly
change: throw on failure

2 files changed, 213 insertions, 68 deletions

diff --git a/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java b/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java
index 920a25b96c9..99c63c91afc 100644
--- a/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java
+++ b/vespajlib/src/test/java/com/yahoo/slime/BinaryViewTest.java
@@ -100,7 +100,15 @@ public class BinaryViewTest {
         assertEquals(300, arr.entries());
         return arr;
     }
-    static final int numShapes = numLeafs + 6;
+    static Cursor insert10SimpleHits(Inserter dst) {
+        var arr = dst.insertARRAY();
+        for (int i = 0; i < 10; ++i) {
+            var obj = arr.addObject();
+            obj.setLong("id", 123456);
+        }
+        return arr;
+    }
+    static final int numShapes = numLeafs + 7;
     static Cursor insertRoot(Slime dst, int shape) {
         var root = new SlimeInserter(dst);
         if (shape < numLeafs) {
@@ -113,6 +121,7 @@ public class BinaryViewTest {
         case (numLeafs + 3) -> insertOuterArray(root); 
         case (numLeafs + 4) -> insertManySymbols(root);
         case (numLeafs + 5) -> insertLargeArray(root);
+        case (numLeafs + 6) -> insert10SimpleHits(root);
         default -> NixValue.invalid();
         };
     }
@@ -297,66 +306,49 @@ public class BinaryViewTest {
         }
     }
 
+    void assertFail(byte[] data, String reason) {
+        try {
+            var view = BinaryView.inspect(data);
+            fail("expected exception");
+        } catch (IllegalArgumentException e) {
+            assertEquals("bad input: " + reason, e.getMessage());
+        }
+    }
+
     @Test public void testTrivialView() {
         byte[] data = {0, 0};
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
+        var view = BinaryView.inspect(data);
         assertTrue(view.valid());
         assertEquals(Type.NIX, view.type());
-        assertFalse(input.failed());
     }
 
     @Test public void testUnderflow() {
         byte[] data = {};
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
-        assertFalse(view.valid());
-        assertTrue(input.failed());
-        assertEquals("underflow", input.getErrorMessage());
+        assertFail(data, "underflow");
     }
 
     @Test public void testMultiByteUnderflow() {
         byte[] data = { 0, encode_type_and_meta(Type.STRING.ID, 3), 65 };
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
-        assertFalse(view.valid());
-        assertTrue(input.failed());
-        assertEquals("underflow", input.getErrorMessage());
+        assertFail(data, "underflow");
     }
 
     @Test public void testCompressedIntOverflow() {
         byte[] data = { -1, -1, -1, -1, 8 };
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
-        assertFalse(view.valid());
-        assertTrue(input.failed());
-        assertEquals("compressed int overflow", input.getErrorMessage());
+        assertFail(data, "compressed int overflow");
     }
 
     @Test public void testExtBitsOverflow() {
         byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 2), -1, -1, -1, -1, 1 };
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
-        assertFalse(view.valid());
-        assertTrue(input.failed());
-        assertEquals("symbol id too big", input.getErrorMessage());
+        assertFail(data, "symbol id too big");
     }
 
     @Test public void testDecodeIndexOverflowArray() {
-        byte[] data = { 0, encode_type_and_meta(Type.ARRAY.ID, 4) };
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
-        assertFalse(view.valid());
-        assertTrue(input.failed());
-        assertEquals("decode index too big", input.getErrorMessage());
+        byte[] data = { 0, encode_type_and_meta(Type.ARRAY.ID, 20) };
+        assertFail(data, "decode index too big");
     }
 
     @Test public void testDecodeIndexOverflowObject() {
-        byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 4) };
-        var input = new BufferedInput(data);
-        var view = BinaryView.inspectImpl(input);
-        assertFalse(view.valid());
-        assertTrue(input.failed());
-        assertEquals("decode index too big", input.getErrorMessage());
+        byte[] data = { 0, encode_type_and_meta(Type.OBJECT.ID, 20) };
+        assertFail(data, "decode index too big");
     }
 }
diff --git a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java
index 223701fa2fd..c34a718d2bb 100644
--- a/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java
+++ b/vespajlib/src/test/java/com/yahoo/slime/DecodeIndexTest.java
@@ -3,83 +3,236 @@ 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();
-        int val1 = index.reserve(1);
-        int val2 = index.reserve(3);
-        int val3 = index.reserve(2);
-        assertEquals(0, val1);
+        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);
         assertEquals(1, val2);
         assertEquals(4, val3);
         assertEquals(6, index.size());
-        index.set(val1 + 0,    0, val2, 0);
+        index.set(root,        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, index.getByteOffset(i));
+            assertEquals(i * 100, byte_offset_for_testing(index, i));
             if (i == 0) {
-                assertEquals(1, index.getFirstChild(i));
+                assertEquals(1, first_child_for_testing(index, i));
             } else if (i == 2) {
-                assertEquals(4, index.getFirstChild(i));
+                assertEquals(4, first_child_for_testing(index, i));
             } else {
-                assertEquals(0, index.getFirstChild(i));
+                assertEquals(0, first_child_for_testing(index, i));
             }
             if (i < 4) {
-                assertEquals(i, index.getExtBits(i));
+                assertEquals(i, ext_bits_for_testing(index, i));
             } else {
-                assertEquals(0, index.getExtBits(i));
+                assertEquals(0, ext_bits_for_testing(index, i));
             }
         }
     }
 
     @Test
     public void testManyValues() {
-        DecodeIndex index = new DecodeIndex();
         int outer = 47;
         int inner = 73;
-        int expectOffset = 0;
+        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;
         for (int i = 0; i < outer; i++) {
-            int offset = index.reserve(inner);
+            int offset = index.tryReserveChildren(inner, indexOffset, binaryOffset);
+            capacity = checkCapacity(index, capacity);
             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(inner * outer, expectOffset);
-        assertEquals(inner * outer, index.size());
+        assertEquals(1 + inner * outer, expectOffset);
+        assertEquals(1 + inner * outer, index.size());
         for (int i = 0; i < outer; i++) {
             for (int j = 0; j < inner; j++) {
-                int offset = i * inner + j;
-                assertEquals(i * j, index.getByteOffset(offset));
-                assertEquals(i + j, index.getFirstChild(offset));
-                assertEquals(j & 3, index.getExtBits(offset));
+                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));
             }
         }
     }
 
     @Test
     public void testOverflowNoBleed() {
-        DecodeIndex index = new DecodeIndex();
-        index.reserve(3);
+        DecodeIndex index = new DecodeIndex(100, 10);
+        index.tryReserveChildren(2, 1, 20);
+        assertEquals(3, index.size());
         index.set(0, 0xffff_ffff, 0, 0);
         index.set(1, 0, 0xffff_ffff, 0);
         index.set(2, 0, 0, 0xffff_ffff);
-        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));
+        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());
     }
 }