Repository: amzn/ion-java
Pull request #404 (2022-01-24 20:26:33)

Eliminates allocations in the binary writer
This patch changes some very hot code paths in the binary writer
to eliminate unnecessary allocations.

In particular:
* Setting the annotations list no longer constructs a temporary
  array of `SymbolToken`s.
* `prepareValue` (which is called for every value in the stream)
  now uses a plain `for` loop instead of an iterator to encode
  each annotation.
* `IonRawBinaryWriter` now uses a custom class called `IntList`
  to store its annotation symbol ID ints instead of a
  `List<Integer>`, which required each int to be boxed.

### Benchmark

This benchmark uses the `ion-java-benchmark-cli` to rewrite an existing ~335MB Ion file.

**Command**
```
java -Xmx8G -jar IJBC.jar write --format ion_binary --ion-flush-period 1024 FILENAME
```

**Before**
```
Benchmark                      Mode  Cnt          Score      Error   Units
Bench.run                        ss   10       5672.757 ±   69.382   ms/op
Bench.run:Heap usage             ss   10       3943.023 ±    0.010      MB
Bench.run:Serialized size        ss   10        335.809                 MB
Bench.run:·gc.alloc.rate         ss   10         33.237 ±    0.360  MB/sec
Bench.run:·gc.alloc.rate.norm    ss   10  216043304.800 ± 5156.126    B/op
Bench.run:·gc.count              ss   10            ≈ 0             counts
```

**After**
```
Benchmark                      Mode  Cnt       Score      Error   Units
Bench.run                        ss   10    5368.811 ±   91.221   ms/op
Bench.run:Heap usage             ss   10    3727.226 ±    1.010      MB
Bench.run:Serialized size        ss   10     335.809                 MB
Bench.run:·gc.alloc.rate         ss   10       0.074 ±    0.001  MB/sec
Bench.run:·gc.alloc.rate.norm    ss   10  457482.400 ± 5146.899    B/op
Bench.run:·gc.count              ss   10         ≈ 0             counts
```

Notice that the allocation rate fell from ~33.237MB/sec to ~0.074MB/sec. The time required also fell by 304ms, a speedup of 5.36%.


By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.


codecov[bot]: # [Codecov](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) Report
> Merging [#404](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) (7f1300a) into [master](https://codecov.io/gh/amzn/ion-java/commit/cf97f97c04cda01a9e2806b1a27e8d04394bda3f?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) (cf97f97) will **increase** coverage by `0.00%`.
> The diff coverage is `75.67%`.

[![Impacted file tree graph](https://codecov.io/gh/amzn/ion-java/pull/404/graphs/tree.svg?width=650&height=150&src=pr&token=M93Y3e3kKn&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)

```diff
@@            Coverage Diff            @@
##             master     #404   +/-   ##
=========================================
  Coverage     66.44%   66.44%           
- Complexity     5375     5387   +12     
=========================================
  Files           154      155    +1     
  Lines         22673    22701   +28     
  Branches       4090     4093    +3     
=========================================
+ Hits          15064    15084   +20     
- Misses         6250     6258    +8     
  Partials       1359     1359           
```


| [Impacted Files](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | Coverage Δ | |
|---|---|---|
| [src/com/amazon/ion/impl/bin/IntList.java](https://codecov.io/gh/amzn/ion-java/pull/404/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2NvbS9hbWF6b24vaW9uL2ltcGwvYmluL0ludExpc3QuamF2YQ==) | `68.96% <68.96%> (ø)` | |
| [...om/amazon/ion/impl/bin/IonManagedBinaryWriter.java](https://codecov.io/gh/amzn/ion-java/pull/404/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2NvbS9hbWF6b24vaW9uL2ltcGwvYmluL0lvbk1hbmFnZWRCaW5hcnlXcml0ZXIuamF2YQ==) | `85.88% <100.00%> (-0.04%)` | :arrow_down: |
| [...rc/com/amazon/ion/impl/bin/IonRawBinaryWriter.java](https://codecov.io/gh/amzn/ion-java/pull/404/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2NvbS9hbWF6b24vaW9uL2ltcGwvYmluL0lvblJhd0JpbmFyeVdyaXRlci5qYXZh) | `91.41% <100.00%> (ø)` | |
| [src/com/amazon/ion/impl/BlockedBuffer.java](https://codecov.io/gh/amzn/ion-java/pull/404/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2NvbS9hbWF6b24vaW9uL2ltcGwvQmxvY2tlZEJ1ZmZlci5qYXZh) | `51.45% <0.00%> (+0.12%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None). Last update [cf97f97...7f1300a](https://codecov.io/gh/amzn/ion-java/pull/404?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).

jobarr-amzn: Nice work, I love it.

Patch:
diff --git a/src/com/amazon/ion/impl/bin/IntList.java b/src/com/amazon/ion/impl/bin/IntList.java
new file mode 100644
index 00000000..8c0ba5c2
--- /dev/null
+++ b/src/com/amazon/ion/impl/bin/IntList.java
@@ -0,0 +1,105 @@
+package com.amazon.ion.impl.bin;
+
+/**
+ * A list of integer values that grows as necessary.
+ *
+ * Unlike {@link java.util.List}, IntList does not require each int to be boxed. This makes it helpful in use cases
+ * where storing {@link Integer} leads to excessive time spent in garbage collection.
+ */
+public class IntList {
+    public static final int DEFAULT_INITIAL_CAPACITY = 8;
+    private static final int GROWTH_MULTIPLIER = 2;
+    private int[] data;
+    private int numberOfValues;
+
+    /**
+     * Constructs a new IntList with a capacity of {@link IntList#DEFAULT_INITIAL_CAPACITY}.
+     */
+    public IntList() {
+        this(DEFAULT_INITIAL_CAPACITY);
+    }
+
+    /**
+     * Constructs a new IntList with the specified capacity.
+     * @param initialCapacity   The number of ints that can be stored in this IntList before it will need to be
+     *                          reallocated.
+     */
+    public IntList(final int initialCapacity) {
+        data = new int[initialCapacity];
+        numberOfValues = 0;
+    }
+
+    /**
+     * Accessor.
+     * @return  The number of ints currently stored in the list.
+     */
+    public int size() {
+        return numberOfValues;
+    }
+
+    /**
+     * @return {@code true} if there are ints stored in the list.
+     */
+    public boolean isEmpty() {
+        return numberOfValues == 0;
+    }
+
+    /**
+     * Empties the list.
+     *
+     * Note that this method does not shrink the size of the backing data store.
+     */
+    public void clear() {
+        numberOfValues = 0;
+    }
+
+    /**
+     * Returns the {@code index}th int in the list.
+     * @param index     The list index of the desired int.
+     * @return          The int at index {@code index} in the list.
+     * @throws IndexOutOfBoundsException    if the index is negative or greater than the number of ints stored in the
+     *                                      list.
+     */
+    public int get(int index) {
+        if (index < 0 || index >= numberOfValues) {
+            throw new IndexOutOfBoundsException(
+                    "Invalid index " + index + " requested from IntList with " + numberOfValues + " values."
+            );
+        }
+        return data[index];
+    }
+
+    /**
+     * Appends an int to the end of the list, growing the list if necessary.
+     * @param value     The int to add to the end of the list.
+     */
+    public void add(int value) {
+        if (numberOfValues == data.length) {
+            grow();
+        }
+        data[numberOfValues] = value;
+        numberOfValues += 1;
+    }
+
+    /**
+     * Reallocates the backing array to accommodate storing more ints.
+     */
+    private void grow() {
+        int[] newData = new int[data.length * GROWTH_MULTIPLIER];
+        System.arraycopy(data, 0, newData, 0, data.length);
+        data = newData;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder builder = new StringBuilder();
+        builder.append("IntList{data=[");
+        if (numberOfValues > 0) {
+            for (int m = 0; m < numberOfValues; m++) {
+                builder.append(data[m]).append(",");
+            }
+        }
+        builder.append("]}");
+        return builder.toString();
+    }
+}
diff --git a/src/com/amazon/ion/impl/bin/IonManagedBinaryWriter.java b/src/com/amazon/ion/impl/bin/IonManagedBinaryWriter.java
index 003dc70a..75ca54c5 100644
--- a/src/com/amazon/ion/impl/bin/IonManagedBinaryWriter.java
+++ b/src/com/amazon/ion/impl/bin/IonManagedBinaryWriter.java
@@ -927,18 +927,16 @@ import java.util.Map;
 
     public void setTypeAnnotations(final String... annotations)
     {
-        if (annotations == null)
-        {
-            user.setTypeAnnotationSymbols((SymbolToken[]) null);
+        // Clear the current list of annotations
+        user.setTypeAnnotationSymbols((SymbolToken[]) null);
+        if (annotations == null) {
+            return;
         }
-        else
-        {
-            final SymbolToken[] tokens = new SymbolToken[annotations.length];
-            for (int i = 0; i < tokens.length; i++)
-            {
-                tokens[i] = intern(annotations[i]);
-            }
-            user.setTypeAnnotationSymbols(tokens);
+
+        // Add each string to the annotations list.
+        // XXX: This is a very hot path. This code avoids allocating temporary iterators/arrays.
+        for (int i = 0; i < annotations.length; i++) {
+            addTypeAnnotation(annotations[i]);
         }
     }
 
diff --git a/src/com/amazon/ion/impl/bin/IonRawBinaryWriter.java b/src/com/amazon/ion/impl/bin/IonRawBinaryWriter.java
index de6a719b..8bc41582 100644
--- a/src/com/amazon/ion/impl/bin/IonRawBinaryWriter.java
+++ b/src/com/amazon/ion/impl/bin/IonRawBinaryWriter.java
@@ -498,7 +498,7 @@ import java.util.NoSuchElementException;
     private boolean                             hasWrittenValuesSinceConstructed;
 
     private int                     currentFieldSid;
-    private final List<Integer>     currentAnnotationSids;
+    private final IntList     currentAnnotationSids;
     // XXX this is for managed detection of TLV that is a LST--this is easier to track here than at the managed level
     private boolean                     hasTopLevelSymbolTableAnnotation;
 
@@ -540,7 +540,7 @@ import java.util.NoSuchElementException;
         this.hasWrittenValuesSinceConstructed = false;
 
         this.currentFieldSid                  = SID_UNASSIGNED;
-        this.currentAnnotationSids            = new ArrayList<Integer>();
+        this.currentAnnotationSids            = new IntList();
         this.hasTopLevelSymbolTableAnnotation = false;
 
         this.closed = false;
@@ -847,8 +847,10 @@ import java.util.NoSuchElementException;
             final long annotationsLengthPosition = buffer.position();
             buffer.writeVarUInt(0L);
             int annotationsLength = 0;
-            for (final int symbol : currentAnnotationSids)
+            // XXX: This is a very hot path. This code intentionally avoids creating iterators.
+            for (int m = 0; m < currentAnnotationSids.size(); m++)
             {
+                final int symbol = currentAnnotationSids.get(m);
                 checkSid(symbol);
                 final int symbolLength = buffer.writeVarUInt(symbol);
                 annotationsLength += symbolLength;


Test patch:
diff --git a/test/com/amazon/ion/impl/bin/IntListTest.java b/test/com/amazon/ion/impl/bin/IntListTest.java
new file mode 100644
index 00000000..4adcf57e
--- /dev/null
+++ b/test/com/amazon/ion/impl/bin/IntListTest.java
@@ -0,0 +1,59 @@
+package com.amazon.ion.impl.bin;
+
+import junit.framework.TestCase;
+
+public class IntListTest extends TestCase {
+
+    public void testSize() {
+        IntList intList = new IntList();
+        assertEquals(intList.size(), 0);
+        
+        intList.add(0);
+        assertEquals(intList.size(), 1);
+        
+        intList.add(0);
+        assertEquals(intList.size(), 2);
+        
+        intList.clear();
+        assertEquals(intList.size(), 0);
+    }
+
+    public void testIsEmpty() {
+        IntList intList = new IntList();
+        assertTrue(intList.isEmpty());
+        intList.add(1);
+        assertFalse(intList.isEmpty());
+    }
+
+    public void testClear() {
+        IntList intList = new IntList();
+        assertTrue(intList.isEmpty());
+        intList.add(1);
+        intList.add(2);
+        intList.add(3);
+        assertFalse(intList.isEmpty());
+        intList.clear();
+        assertTrue(intList.isEmpty());
+    }
+
+    public void testAddAndGet() {
+        IntList intList = new IntList();
+        intList.add(1);
+        intList.add(2);
+        intList.add(3);
+        assertEquals(intList.get(0), 1);
+        assertEquals(intList.get(1), 2);
+        assertEquals(intList.get(2), 3);
+    }
+
+    public void testGrow() {
+        // Create the list with insufficient capacity
+        IntList intList = new IntList(1);
+        intList.add(1);
+        intList.add(2);
+        intList.add(3);
+        assertEquals(intList.get(0), 1);
+        assertEquals(intList.get(1), 2);
+        assertEquals(intList.get(2), 3);
+    }
+}
\ No newline at end of file