diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
index 96ec012..216817a 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.collect.nestedset;
 
-import static com.google.common.collect.ImmutableSet.toImmutableSet;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
@@ -101,10 +100,13 @@
     if (!(set instanceof Object[])) {
       return ImmutableSet.of();
     }
-    return Arrays.stream((Object[]) set)
-        .filter(c -> c instanceof Object[])
-        .map(c -> new NestedSetView<E>(c))
-        .collect(toImmutableSet());
+    ImmutableSet.Builder<NestedSetView<E>> nestedSetViewSetBuilder = new ImmutableSet.Builder<>();
+    for (Object c : (Object[]) set) {
+      if (c instanceof Object[]) {
+        nestedSetViewSetBuilder.add(new NestedSetView<>(c));
+      }
+    }
+    return nestedSetViewSetBuilder.build();
   }
 
   /**
@@ -118,9 +120,12 @@
     if (!(set instanceof Object[])) {
       return ImmutableSet.of((E) set);
     }
-    return Arrays.stream((Object[]) set)
-        .filter(c -> !(c instanceof Object[]))
-        .map(c -> (E) c)
-        .collect(toImmutableSet());
+    ImmutableSet.Builder<E> setBuilder = new ImmutableSet.Builder<>();
+    for (Object c : (Object[]) set) {
+      if (!(c instanceof Object[])) {
+        setBuilder.add((E) c);
+      }
+    }
+    return setBuilder.build();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index 89ec541..a51d334 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -392,6 +392,10 @@
    */
   private static boolean evalInputsAsNestedSet(
       int nestedSetSizeThreshold, NestedSet<Artifact> inputs) {
+    if (nestedSetSizeThreshold == 1) {
+      // Don't even flatten in this case.
+      return true;
+    }
     return nestedSetSizeThreshold > 0
         && (inputs.memoizedFlattenAndGetSize() >= nestedSetSizeThreshold);
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java
index 9a57788..a716922 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java
@@ -15,14 +15,12 @@
 
 import com.google.common.base.MoreObjects;
 import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
-import java.util.Arrays;
 import java.util.Collections;
-import java.util.stream.Collectors;
 
 /** SkyKey for {@code NestedSet<Artifact>}. */
 public class ArtifactNestedSetKey implements SkyKey {
@@ -88,11 +86,15 @@
    */
   Iterable<Object> transitiveMembers() {
     if (!(rawChildren instanceof Object[])) {
-      return ImmutableSet.of();
+      return ImmutableList.of();
     }
-    return Arrays.stream((Object[]) rawChildren)
-        .filter(c -> c instanceof Object[])
-        .collect(Collectors.toList());
+    ImmutableList.Builder<Object> listBuilder = new ImmutableList.Builder<>();
+    for (Object c : (Object[]) rawChildren) {
+      if (c instanceof Object[]) {
+        listBuilder.add(c);
+      }
+    }
+    return listBuilder.build();
   }
 
   /**
@@ -107,9 +109,12 @@
     if (!(rawChildren instanceof Object[])) {
       return Collections.singletonList(Artifact.key((Artifact) rawChildren));
     }
-    return Arrays.stream((Object[]) rawChildren)
-        .filter(c -> !(c instanceof Object[]))
-        .map(c -> Artifact.key((Artifact) c))
-        .collect(Collectors.toList());
+    ImmutableList.Builder<SkyKey> listBuilder = new ImmutableList.Builder<>();
+    for (Object c : (Object[]) rawChildren) {
+      if (!(c instanceof Object[])) {
+        listBuilder.add(Artifact.key((Artifact) c));
+      }
+    }
+    return listBuilder.build();
   }
 }