Repository: bazelbuild/bazel
Issue: Empty depsets should be optimized out of structs the same as they are optimized out of providers
Labels: type: feature request
untriaged
team-Starlark-Interpreter
team-Starlark-Integration

### Description of the feature request:


Empty depsets are optimized out of providers, but not structs. This can lead to increased memory usage for some code patterns.

### Which category does this issue belong to?


Starlark Integration, Starlark Interpreter

### What underlying problem are you trying to solve with this feature?


In rules_xcodeproj we marshal a lot of data collected in aspects down the dependency tree. When doing Starlark memory profiling we noticed that creating new empty `depset` instances would drastically increase our memory usage. So instead we create frozen instances of empty values and use them when possible: https://github.com/MobileNativeFoundation/rules_xcodeproj/blob/31a9e114dac0e20625fb7d9119fe5a117ecb3608/xcodeproj/internal/memory_efficiency.bzl, which helped us reduce our memory usage.

### Which operating system are you running Bazel on?


macOS 13.4.1 (c)

### What is the output of `bazel info release`?


release 6.3.2

### If `bazel info release` returns `development version` or `(@non-git)`, tell us how you built Bazel.


_No response_

### What's the output of `git remote get-url origin; git rev-parse master; git rev-parse HEAD` ?


_No response_

### Have you found anything relevant by searching the web?

_No response_

### Any other information, logs, or outputs that you want to share?

https://bazelbuild.slack.com/archives/CA31HN1T3/p1693484609534579 where @fmeum requested I open this issue.

Issue comments:
A fix for this issue has been included in [Bazel 6.4.0 RC1](https://releases.bazel.build/6.4.0/rc1/index.html). Please test out the release candidate and report any issues as soon as possible. Thanks!

Pull request review comments:

Patch that resolved the issue:
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
index b013822bdf49e6..332092a04e0b39 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java
@@ -95,7 +95,7 @@ public final class Depset implements StarlarkValue, Debug.ValueWithDebugAttribut
   private final ElementType elemType;
   private final NestedSet<?> set;
 
-  private Depset(ElementType elemType, NestedSet<?> set) {
+  Depset(ElementType elemType, NestedSet<?> set) {
     this.elemType = Preconditions.checkNotNull(elemType, "element type cannot be null");
     this.set = set;
   }
@@ -189,6 +189,9 @@ private static void checkElement(Object x, boolean strict) throws EvalException
   // two arguments: of(Class<T> elemType, NestedSet<T> set). We could also avoid the allocations
   // done by ElementType.of().
   public static <T> Depset of(ElementType elemType, NestedSet<T> set) {
+    if (set.isEmpty()) {
+      return set.getOrder().emptyDepset();
+    }
     return new Depset(elemType, set);
   }
 
@@ -280,15 +283,11 @@ public static <T> NestedSet<T> cast(Object x, Class<T> type, String what) throws
   public static <T> NestedSet<T> noneableCast(Object x, Class<T> type, String what)
       throws EvalException {
     if (x == Starlark.NONE) {
-      @SuppressWarnings("unchecked")
-      NestedSet<T> empty = (NestedSet<T>) EMPTY;
-      return empty;
+      return NestedSetBuilder.emptySet(Order.STABLE_ORDER);
     }
     return cast(x, type, what);
   }
 
-  private static final NestedSet<?> EMPTY = NestedSetBuilder.<Object>emptySet(Order.STABLE_ORDER);
-
   public boolean isEmpty() {
     return set.isEmpty();
   }
@@ -390,6 +389,9 @@ static Depset fromDirectAndTransitive(
       }
     }
 
+    if (builder.isEmpty()) {
+      return builder.getOrder().emptyDepset();
+    }
     return new Depset(type, builder.build());
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
index 1a62d054fba06c..3f0ea09422ad4c 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
@@ -112,10 +112,12 @@ public enum Order {
 
   private final String starlarkName;
   private final NestedSet<?> emptySet;
+  private final Depset emptyDepset;
 
-  private Order(String starlarkName) {
+  Order(String starlarkName) {
     this.starlarkName = starlarkName;
     this.emptySet = new NestedSet<>(this);
+    this.emptyDepset = new Depset(Depset.ElementType.EMPTY, this.emptySet);
   }
 
   @SerializationConstant @AutoCodec.VisibleForSerialization
@@ -150,6 +152,11 @@ <E> NestedSet<E> emptySet() {
     return (NestedSet<E>) emptySet;
   }
 
+  /** Returns an empty depset of the given ordering. */
+  Depset emptyDepset() {
+    return emptyDepset;
+  }
+
   public String getStarlarkName() {
     return starlarkName;
   }


Test patch:
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
index cc6d597833fdd0..a2139858beb8f6 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
@@ -404,4 +404,17 @@ ev.new Scenario()
                 + " NoneType'",
             "depset(direct='hello')");
   }
+
+  @Test
+  public void testEmptyDepsetInternedPerOrder() throws Exception {
+    ev.exec(
+        "stable1 = depset()",
+        "stable2 = depset()",
+        "preorder1 = depset(order = 'preorder')",
+        "preorder2 = depset(order = 'preorder')");
+    assertThat(ev.lookup("stable1")).isSameInstanceAs(ev.lookup("stable2"));
+    assertThat(ev.lookup("preorder1")).isSameInstanceAs(ev.lookup("preorder2"));
+    assertThat(ev.lookup("stable1")).isNotSameInstanceAs(ev.lookup("preorder1"));
+    assertThat(ev.lookup("stable2")).isNotSameInstanceAs(ev.lookup("preorder2"));
+  }
 }