Optimize fro the most common case where the lists are either empty or has 1-2 elements.

Do not use the ArraryList until it is necessary.

3 files changed, 131 insertions, 58 deletions

diff --git a/container-search/src/main/java/com/yahoo/search/grouping/vespa/ResultBuilder.java b/container-search/src/main/java/com/yahoo/search/grouping/vespa/ResultBuilder.java
index d7592d4f97a..2b8ab938347 100644
--- a/container-search/src/main/java/com/yahoo/search/grouping/vespa/ResultBuilder.java
+++ b/container-search/src/main/java/com/yahoo/search/grouping/vespa/ResultBuilder.java
@@ -202,7 +202,7 @@ class ResultBuilder {
                     results = Arrays.copyOf(results, tag+8);
                 }
                 if ( ! results[tag] ) {
-                    this.group.getAggregationResults().add(res);
+                    this.group.addAggregationResult(res);
                     results[tag] = true;
                 }
             }
diff --git a/searchlib/src/main/java/com/yahoo/searchlib/aggregation/Group.java b/searchlib/src/main/java/com/yahoo/searchlib/aggregation/Group.java
index 6168a7a89ae..20c19c8e6a1 100644
--- a/searchlib/src/main/java/com/yahoo/searchlib/aggregation/Group.java
+++ b/searchlib/src/main/java/com/yahoo/searchlib/aggregation/Group.java
@@ -12,23 +12,45 @@ import com.yahoo.vespa.objects.ObjectVisitor;
 import com.yahoo.vespa.objects.Serializer;
 
 import java.util.ArrayList;
-import java.util.Collections;
+import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
+import java.util.stream.Collectors;
 
 public class Group extends Identifiable {
 
     public static final int classId = registerClass(0x4000 + 90, Group.class);
     private static final ObjectPredicate REF_LOCATOR = new RefLocator();
-    private List<Integer> orderByIdx = new ArrayList<>();
-    private List<ExpressionNode> orderByExp = new ArrayList<>();
-    private List<AggregationResult> aggregationResults = new ArrayList<>();
-    private List<Group> children = new ArrayList<>();
+    private List<Integer> orderByIdx = List.of();
+    private List<ExpressionNode> orderByExp = List.of();
+    private List<AggregationResult> aggregationResults = List.of();
+    private List<Group> children = List.of();
     private ResultNode id = null;
     private double rank;
     private int tag = -1;
     private SortType sortType = SortType.UNSORTED;
 
+    private static <T> List<T> add(List<T> oldList, T obj) {
+        if (oldList.isEmpty()) {
+            return List.of(obj);
+        }
+        if (oldList.size() == 1) {
+            return List.of(oldList.get(0), obj);
+        }
+        List<T> newList = (oldList instanceof ArrayList) ? oldList : new ArrayList<>(oldList);
+        newList.add(obj);
+        return newList;
+    }
+
+    private static <T> List<T> sort(List<T> list, Comparator<T> cmp) {
+        if (list instanceof ArrayList) {
+            list.sort(cmp);
+            return list;
+        } else {
+            return list.stream().sorted(cmp).collect(Collectors.toList());
+        }
+    }
+
     /**
      * This tells you if the children are ranked by the pure relevance or by a more complex expression.
      * That indicates if the rank score from the child can be used for ordering.
@@ -62,7 +84,7 @@ public class Group extends Identifiable {
         if (lhsChild.hasNext() && rhsChild.hasNext()) {
             Group lhsGroup = lhsChild.next();
             Group rhsGroup = rhsChild.next();
-            for (; (lhsGroup != null) && (rhsGroup != null); ) {
+            while ((lhsGroup != null) && (rhsGroup != null)) {
                 int cmp = lhsGroup.getId().compareTo(rhsGroup.getId());
                 if (cmp < 0) {
                     merged.add(lhsGroup);
@@ -140,7 +162,7 @@ public class Group extends Identifiable {
         if (sortType == SortType.BYID) {
             return;
         }
-        Collections.sort(children, (Group lhs, Group rhs) -> lhs.compareId(rhs));
+        children = sort(children, Group::compareId);
         sortType = SortType.BYID;
     }
 
@@ -149,8 +171,7 @@ public class Group extends Identifiable {
         if (sortType == SortType.BYRANK) {
             return;
         }
-        Collections.sort(children, (Group lhs, Group rhs) ->  lhs.compareRank(rhs) );
-
+        children = sort(children, Group::compareRank);
         sortType = SortType.BYRANK;
     }
 
@@ -200,13 +221,13 @@ public class Group extends Identifiable {
         if (child == null) {
             throw new IllegalArgumentException("Child can not be null.");
         }
-        children.add(child);
+        children = add(children, child);
         return this;
     }
 
     /** Returns the list of child groups to this. */
     public List<Group> getChildren() {
-        return children;
+        return List.copyOf(children);
     }
 
     /**
@@ -234,7 +255,7 @@ public class Group extends Identifiable {
      * @return the aggregation results
      */
     public List<AggregationResult> getAggregationResults() {
-        return aggregationResults;
+        return List.copyOf(aggregationResults);
     }
 
     /**
@@ -244,7 +265,7 @@ public class Group extends Identifiable {
      * @return this, to allow chaining
      */
     public Group addAggregationResult(AggregationResult result) {
-        aggregationResults.add(result);
+        aggregationResults = add(aggregationResults, result);
         return this;
     }
 
@@ -261,18 +282,20 @@ public class Group extends Identifiable {
         if (exp instanceof AggregationResult) {
             exp = new AggregationRefNode((AggregationResult)exp);
         }
-        exp.select(REF_LOCATOR, new RefResolver(this));
-        orderByExp.add(exp);
-        orderByIdx.add((asc ? 1 : -1) * orderByExp.size());
+        RefResolver refResolver = new RefResolver(aggregationResults);
+        exp.select(REF_LOCATOR, refResolver);
+        aggregationResults = refResolver.results;
+        orderByExp = add(orderByExp, exp);
+        orderByIdx = add(orderByIdx, (asc ? 1 : -1) * orderByExp.size());
         return this;
     }
 
     public List<Integer> getOrderByIndexes() {
-        return Collections.unmodifiableList(orderByIdx);
+        return List.copyOf(orderByIdx);
     }
 
     public List<ExpressionNode> getOrderByExpressions() {
-        return Collections.unmodifiableList(orderByExp);
+        return List.copyOf(orderByExp);
     }
 
     private int compareId(Group rhs) {
@@ -334,28 +357,50 @@ public class Group extends Identifiable {
         super.onDeserialize(buf);
         id = (ResultNode)deserializeOptional(buf);
         rank = buf.getDouble(null);
-        orderByIdx.clear();
+        orderByIdx = List.of();
         int orderByCount = buf.getInt(null);
-        for (int i = 0; i < orderByCount; i++) {
-            orderByIdx.add(buf.getInt(null));
+        if (orderByCount > 0) {
+            Integer [] idxes = new Integer[orderByCount];
+            for (int i = 0; i < orderByCount; i++) {
+                idxes[i] = buf.getInt(null);
+            }
+            orderByIdx = List.of(idxes);
         }
         int numResults = buf.getInt(null);
-        for (int i = 0; i < numResults; i++) {
-            AggregationResult e = (AggregationResult)deserializeOptional(buf);
-            aggregationResults.add(e);
+        if (numResults > 0) {
+            AggregationResult [] results = new AggregationResult[numResults];
+            for (int i = 0; i < numResults; i++) {
+                results[i] = (AggregationResult) deserializeOptional(buf);
+            }
+            aggregationResults = List.of(results);
+        } else {
+            aggregationResults = List.of();
         }
         int numExpressionResults = buf.getInt(null);
-        RefResolver resolver = new RefResolver(this);
-        for (int i = 0; i < numExpressionResults; i++) {
-            ExpressionNode exp = (ExpressionNode)deserializeOptional(buf);
-            exp.select(REF_LOCATOR, resolver);
-            orderByExp.add(exp);
+        if (numExpressionResults > 0) {
+            RefResolver resolver = new RefResolver(aggregationResults);
+            ExpressionNode[] orderBy = new ExpressionNode[numExpressionResults];
+            for (int i = 0; i < numExpressionResults; i++) {
+                ExpressionNode exp = (ExpressionNode) deserializeOptional(buf);
+                exp.select(REF_LOCATOR, resolver);
+                orderBy[i] = exp;
+            }
+            aggregationResults = resolver.results;
+            orderByExp = List.of(orderBy);
+        } else {
+            orderByExp = List.of();
         }
         int numGroups = buf.getInt(null);
-        for (int i = 0; i < numGroups; i++) {
-            Group g = new Group();
-            g.deserializeWithId(buf);
-            children.add(g);
+        if (numGroups > 0) {
+            Group [] groups = new Group[numGroups];
+            for (int i = 0; i < numGroups; i++) {
+                Group g = new Group();
+                g.deserializeWithId(buf);
+                groups[i] = g;
+            }
+            children = List.of(groups);
+        } else {
+            children = List.of();
         }
         tag = buf.getInt(null);
     }
@@ -386,21 +431,36 @@ public class Group extends Identifiable {
         if (id != null) {
             obj.id = (ResultNode)id.clone();
         }
-        obj.aggregationResults = new ArrayList<>();
-        for (AggregationResult result : aggregationResults) {
-            obj.aggregationResults.add(result.clone());
-        }
-        obj.orderByIdx = new ArrayList<>(orderByIdx);
-        obj.orderByExp = new ArrayList<>();
-        RefResolver resolver = new RefResolver(obj);
-        for (ExpressionNode exp : orderByExp) {
-            exp = exp.clone();
-            exp.select(REF_LOCATOR, resolver);
-            obj.orderByExp.add(exp);
-        }
-        obj.children = new ArrayList<>();
-        for (Group child : children) {
-            obj.children.add(child.clone());
+
+        if ( ! aggregationResults.isEmpty() ) {
+            AggregationResult [] results = new AggregationResult[aggregationResults.size()];
+            int i = 0;
+            for (AggregationResult result : aggregationResults) {
+                results[i++] = result.clone();
+            }
+            obj.aggregationResults = List.of(results);
+        }
+        obj.orderByIdx = List.copyOf(orderByIdx);
+        if ( ! orderByExp.isEmpty()) {
+            obj.orderByExp = new ArrayList<>();
+            RefResolver resolver = new RefResolver(obj.aggregationResults);
+            ExpressionNode[] orderBy = new ExpressionNode[orderByExp.size()];
+            int i = 0;
+            for (ExpressionNode exp : orderByExp) {
+                exp = exp.clone();
+                exp.select(REF_LOCATOR, resolver);
+                orderBy[i++] = exp;
+            }
+            obj.orderByExp = List.of(orderBy);
+            obj.aggregationResults = resolver.results;
+        }
+        if ( ! children.isEmpty() ) {
+            Group [] groups = new Group[children.size()];
+            int i = 0;
+            for (Group child : children) {
+                groups[i++] = child.clone();
+            }
+            obj.children = List.of(groups);
         }
         return obj;
     }
@@ -443,10 +503,10 @@ public class Group extends Identifiable {
 
     private static class RefResolver implements ObjectOperation {
 
-        final List<AggregationResult> results;
+        List<AggregationResult> results;
 
-        RefResolver(Group group) {
-            this.results = group.aggregationResults;
+        RefResolver(List<AggregationResult> initial) {
+            this.results = initial;
         }
 
         @Override
@@ -458,7 +518,7 @@ public class Group extends Identifiable {
                 idx = indexOf(res);
                 if (idx < 0) {
                     idx = results.size();
-                    results.add(res);
+                    results = add(results, res);
                 }
                 ref.setIndex(idx);
             } else {
diff --git a/searchlib/src/test/java/com/yahoo/searchlib/aggregation/GroupTestCase.java b/searchlib/src/test/java/com/yahoo/searchlib/aggregation/GroupTestCase.java
index fd126ec2a82..c9898ec65fc 100644
--- a/searchlib/src/test/java/com/yahoo/searchlib/aggregation/GroupTestCase.java
+++ b/searchlib/src/test/java/com/yahoo/searchlib/aggregation/GroupTestCase.java
@@ -1,14 +1,22 @@
 // Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 package com.yahoo.searchlib.aggregation;
 
-import com.yahoo.searchlib.expression.*;
+import com.yahoo.searchlib.expression.AggregationRefNode;
+import com.yahoo.searchlib.expression.ConstantNode;
+import com.yahoo.searchlib.expression.ExpressionNode;
+import com.yahoo.searchlib.expression.IntegerResultNode;
+import com.yahoo.searchlib.expression.NegateFunctionNode;
 import com.yahoo.vespa.objects.BufferSerializer;
 import com.yahoo.vespa.objects.Identifiable;
 import org.junit.Test;
 
 import java.util.Arrays;
+import java.util.List;
 
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.fail;
 
 /**
  * @author Simon Thoresen Hult
@@ -25,9 +33,14 @@ public class GroupTestCase {
     }
 
     @Test
-    public void requireThatAggregationResultListIsNotImmutable() {
+    public void requireThatAggregationResultListIsImmutable() {
         Group group = new Group();
-        group.getAggregationResults().add(new AverageAggregationResult());
+        try {
+            group.getAggregationResults().add(new AverageAggregationResult());
+            fail();
+        } catch (UnsupportedOperationException e) {
+
+        }
     }
 
     @Test
@@ -37,7 +50,7 @@ public class GroupTestCase {
         group.addOrderBy(foo, true);
         assertEquals(1, group.getOrderByExpressions().size());
         assertSame(foo, group.getOrderByExpressions().get(0));
-        assertEquals(Arrays.asList(1), group.getOrderByIndexes());
+        assertEquals(List.of(1), group.getOrderByIndexes());
 
         ExpressionNode bar = new ConstantNode(new IntegerResultNode(9));
         group.addOrderBy(bar, false);