Reduce iterator usage on hot code paths

Micro-optimize a few hot code paths which have a habit of iterating over short O(1)-access
lists.

RELNOTES: None
PiperOrigin-RevId: 171347524

4 files changed, 31 insertions, 17 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
index e0fdbff39e..4842374765 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Eval.java
@@ -14,6 +14,7 @@
 
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.collect.ImmutableList;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
@@ -58,9 +59,7 @@ public class Eval {
 
   void execIfBranch(IfStatement.ConditionalStatements node)
       throws EvalException, InterruptedException {
-    for (Statement stmt : node.getStatements()) {
-      exec(stmt);
-    }
+    execStatements(node.getStatements());
   }
 
   void execFor(ForStatement node) throws EvalException, InterruptedException {
@@ -72,9 +71,7 @@ public class Eval {
         node.getVariable().assign(it, env, node.getLocation());
 
         try {
-          for (Statement stmt : node.getBlock()) {
-            exec(stmt);
-          }
+          execStatements(node.getBlock());
         } catch (FlowException ex) {
           if (ex == breakException) {
             return;
@@ -123,9 +120,7 @@ public class Eval {
         return;
       }
     }
-    for (Statement stmt : node.getElseBlock()) {
-      exec(stmt);
-    }
+    execStatements(node.getElseBlock());
   }
 
   void execLoad(LoadStatement node) throws EvalException, InterruptedException {
@@ -216,4 +211,12 @@ public class Eval {
         break;
     }
   }
+
+  private void execStatements(ImmutableList<Statement> statements)
+      throws EvalException, InterruptedException {
+    // Hot code path, good chance of short lists which don't justify the iterator overhead.
+    for (int i = 0; i < statements.size(); i++) {
+      exec(statements.get(i));
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 133cc00fda..1b943ece94 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -192,11 +192,11 @@ public final class FuncallExpression extends Expression {
 
   private final Expression function;
 
-  private final List<Argument.Passed> arguments;
+  private final ImmutableList<Argument.Passed> arguments;
 
   private final int numPositionalArgs;
 
-  public FuncallExpression(Expression function, List<Argument.Passed> arguments) {
+  public FuncallExpression(Expression function, ImmutableList<Argument.Passed> arguments) {
     this.function = Preconditions.checkNotNull(function);
     this.arguments = Preconditions.checkNotNull(arguments);
     this.numPositionalArgs = countPositionalArguments();
@@ -679,7 +679,10 @@ public final class FuncallExpression extends Expression {
     // or star arguments, because the argument list was already validated by
     // Argument#validateFuncallArguments, as called by the Parser,
     // which should be the only place that build FuncallExpression-s.
-    for (Argument.Passed arg : arguments) {
+    // Argument lists are typically short and functions are frequently called, so go by index
+    // (O(1) for ImmutableList) to avoid the iterator overhead.
+    for (int i = 0; i < arguments.size(); i++) {
+      Argument.Passed arg = arguments.get(i);
       Object value = arg.getValue().eval(env);
       if (arg.isPositional()) {
         posargs.add(value);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
index 979c63b4e3..6d457267ba 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
@@ -481,7 +481,7 @@ public class Parser {
 
   // funcall_suffix ::= '(' arg_list? ')'
   private Expression parseFuncallSuffix(int start, Expression function) {
-    List<Argument.Passed> args = Collections.emptyList();
+    ImmutableList<Argument.Passed> args = ImmutableList.of();
     expect(TokenKind.LPAREN);
     int end;
     if (token.kind == TokenKind.RPAREN) {
@@ -509,8 +509,8 @@ public class Parser {
   }
 
   // arg_list ::= ( (arg ',')* arg ','? )?
-  private List<Argument.Passed> parseFuncallArguments() {
-    List<Argument.Passed> arguments = parseFunctionArguments(this::parseFuncallArgument);
+  private ImmutableList<Argument.Passed> parseFuncallArguments() {
+    ImmutableList<Argument.Passed> arguments = parseFunctionArguments(this::parseFuncallArgument);
     try {
       Argument.validateFuncallArguments(arguments);
     } catch (Argument.ArgumentException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Type.java b/src/main/java/com/google/devtools/build/lib/syntax/Type.java
index 032a939ee0..8fb5643165 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Type.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Type.java
@@ -568,8 +568,16 @@ public abstract class Type<T> {
     @Override
     public <T> void visitLabels(LabelVisitor<T> visitor, Object value, T context)
         throws InterruptedException {
-      for (ElemT elem : cast(value)) {
-        elemType.visitLabels(visitor, elem, context);
+      List<ElemT> elems = cast(value);
+      // Hot code path. Optimize for lists with O(1) access to avoid iterator garbage.
+      if (elems instanceof ImmutableList || elems instanceof ArrayList) {
+        for (int i = 0; i < elems.size(); i++) {
+          elemType.visitLabels(visitor, elems.get(i), context);
+        }
+      } else {
+        for (ElemT elem : elems) {
+          elemType.visitLabels(visitor, elem, context);
+        }
       }
     }