Non-deterministic deduping of label target name strings. The approach was chosen experimentally. Saves ~1% memory, at no measurable CPU or wall time cost, in most scenarios. PiperOrigin-RevId: 964936344 Change-Id: I17a6b0e6efaf881883438b94958c64186f35500a
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/BUILD b/src/main/java/com/google/devtools/build/lib/cmdline/BUILD index c733d43..455aca9 100644 --- a/src/main/java/com/google/devtools/build/lib/cmdline/BUILD +++ b/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
@@ -21,6 +21,7 @@ "IgnoredSubdirectories.java", "Label.java", "LabelConstants.java", + "LabelNameDeduper.java", "LabelParser.java", "LabelSyntaxException.java", "PackageIdentifier.java", @@ -45,6 +46,7 @@ "//src/main/java/com/google/devtools/build/lib/io:inconsistent_filesystem_exception", "//src/main/java/com/google/devtools/build/lib/io:process_package_directory_exception", "//src/main/java/com/google/devtools/build/lib/packages/semantics", + "//src/main/java/com/google/devtools/build/lib/runtime:memory_optimizations", "//src/main/java/com/google/devtools/build/lib/skyframe:detailed_exceptions", "//src/main/java/com/google/devtools/build/lib/skyframe:sky_functions", "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java index 3d84817..64c4527 100644 --- a/src/main/java/com/google/devtools/build/lib/cmdline/Label.java +++ b/src/main/java/com/google/devtools/build/lib/cmdline/Label.java
@@ -104,13 +104,6 @@ // Used for the public and private visibility labels (not targets) "visibility"); - // Intern "__pkg__" and "__subpackages__" pseudo-targets, which appears in labels used for - // visibility specifications. This saves a couple tenths of a percent of RAM off the loading - // phase. Note that general interning of all values for `name` is *not* beneficial. See - // Google-internal cl/386077913 and cl/185394812 for more context. - private static final String PKG_VISIBILITY_NAME = "__pkg__"; - private static final String SUBPACKAGES_VISIBILITY_NAME = "__subpackages__"; - public static final SkyFunctionName TRANSITIVE_TRAVERSAL = SkyFunctionName.createHermetic("TRANSITIVE_TRAVERSAL"); @@ -323,17 +316,8 @@ * arbitrary {@code name} inputs */ public static Label createUnvalidated(PackageIdentifier packageIdentifier, String name) { - return interner.intern(new Label(packageIdentifier, internIfConstantName(name))); - } - - static String internIfConstantName(String name) { - if (name.equals(PKG_VISIBILITY_NAME)) { - return PKG_VISIBILITY_NAME; - } - if (name.equals(SUBPACKAGES_VISIBILITY_NAME)) { - return SUBPACKAGES_VISIBILITY_NAME; - } - return name; + return interner.intern( + new Label(packageIdentifier, LabelNameDeduper.deduplicateTargetName(name))); } /** The name and repository of the package. */
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/LabelNameDeduper.java b/src/main/java/com/google/devtools/build/lib/cmdline/LabelNameDeduper.java new file mode 100644 index 0000000..643ce97 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/cmdline/LabelNameDeduper.java
@@ -0,0 +1,56 @@ +// Copyright 2026 The Bazel Authors. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.cmdline; + +import com.google.devtools.build.lib.runtime.MemoryOptimizations; +import java.util.Arrays; + +/** + * Deduplicates target names in labels ("//pkg:name-to-dedup"). + * + * <p>Uses a simple cache implemented via an array in a lock-free manner. Advantages: no measurable + * CPU overhead, bounded memory overhead in the worst-case. Disadvantages: the deduping efficacy is + * non-deterministic (depends on the order of [concurrent] calls). + * + * <p>This approach (and the specific cache size) were chosen experimentally, with many other + * approaches considered and benchmarked. See b/545739944. + */ +public final class LabelNameDeduper { + private static final int CACHE_SIZE = 262144; + private static final String[] stringCache = new String[CACHE_SIZE]; + + private LabelNameDeduper() {} + + static String deduplicateTargetName(String name) { + if (!MemoryOptimizations.doNonDeterministicMemoryOptimizations.get()) { + return name; + } + int hash = name.hashCode(); + int idx = (hash ^ (hash >>> 16)) & (CACHE_SIZE - 1); + String existing = stringCache[idx]; + if (existing != null && existing.equals(name)) { + return existing; + } + // Clear can happen concurrently (when Blaze is under memory pressure; see HighWaterMarkLimiter) + // but this unsynchronized write is fine because we'd actually benefit from the ability to have + // the stringCache array to contain the string but it's also fine if it doesn't. The entire idea + // is a very low overhead memory optimization. + stringCache[idx] = name; + return name; + } + + public static void clear() { + Arrays.fill(stringCache, null); + } +}
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java index b401b48..98e9eb3 100644 --- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java +++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
@@ -49,6 +49,7 @@ import com.google.devtools.build.lib.buildtool.buildevent.ProfilerStartedEvent; import com.google.devtools.build.lib.clock.BlazeClock; import com.google.devtools.build.lib.clock.Clock; +import com.google.devtools.build.lib.cmdline.LabelNameDeduper; import com.google.devtools.build.lib.collect.nestedset.NestedSetInterner; import com.google.devtools.build.lib.events.Event; import com.google.devtools.build.lib.events.ExtendedEventHandler; @@ -847,6 +848,7 @@ env.getSkyframeExecutor().setEventBus(null); env.getSkyframeExecutor().setOutputService(null); NestedSetInterner.clear(); + LabelNameDeduper.clear(); // Some module's commandComplete() relies on the stoppage of profiler. And it is impossible the // profiler is needed after all `BlazeModule.afterCommand`s are executed.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/HighWaterMarkLimiter.java b/src/main/java/com/google/devtools/build/lib/skyframe/HighWaterMarkLimiter.java index 580db5f..b6f845f 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/HighWaterMarkLimiter.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/HighWaterMarkLimiter.java
@@ -19,6 +19,7 @@ import com.google.common.eventbus.Subscribe; import com.google.common.flogger.GoogleLogger; +import com.google.devtools.build.lib.cmdline.LabelNameDeduper; import com.google.devtools.build.lib.collect.nestedset.NestedSetInterner; import com.google.devtools.build.lib.runtime.MemoryPressure.MemoryPressureStats; import com.google.devtools.build.lib.runtime.MemoryPressureEvent; @@ -95,9 +96,21 @@ actual, threshold, remainingStat); } + // These caches trade temporary memory for CPU savings. Therefore if we're under memory + // pressure, clearing them is definitely a good idea. skyframeExecutor.dropUnnecessaryTemporarySkyframeState(); syscallCache.clear(); + + // These caches trade temporary memory for [non-deterministically hopeful!] retained memory + // savings. If we're under memory pressure, clearing them could either be a good idea or a bad + // idea. If they happen to be currently dominating a lot of memory, then clearing them is + // probably good. But if they happen to currently reference a lot of memory retained by popular + // objects, then clearing them is bad because it means that future creations of equivalent + // objects won't get deduped to the original instance. + // TODO(bazel-team): Consider being fancy here and instead removing just the entries for + // low-frequency objects. NestedSetInterner.clear(); + LabelNameDeduper.clear(); } /** Populate fields about cache drops. */