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!
Empty depsets should be optimized out of structs the same as they are optimized out of providers
### 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.
src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
src/main/java/com/google/devtools/build/lib/collect/nestedset/Depset.java src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
src/test/java/com/google/devtools/build/lib/collect/nestedset/DepsetTest.java
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;
   }

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"));
+  }
 }
