Remove use of AtomicReferenceArray in RadixTreeCache

mcculls · mcculls · commit 7403c1a852d3 · 2026-02-16T12:21:17.000Z
Instead we tolerate racing to cache sub-arrays, like we do for individual values.
This does mean two or more threads might create the same sub-array, with only one
winning, but this should be rare with later calls picking up the same sub-array.
diff --git a/internal-api/src/main/java/datadog/trace/api/cache/RadixTreeCache.java b/internal-api/src/main/java/datadog/trace/api/cache/RadixTreeCache.java
@@ -1,8 +1,6 @@
 package datadog.trace.api.cache;
 
 import datadog.trace.bootstrap.instrumentation.api.UTF8BytesString;
-import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
-import java.util.concurrent.atomic.AtomicReferenceArray;
 import java.util.function.IntFunction;
 
 /** Sparse cache of values associated with a small integer */
@@ -25,11 +23,11 @@ public final class RadixTreeCache<T> {
   private final int shift;
   private final int mask;
 
-  private final AtomicReferenceArray<Object[]> tree;
+  private final Object[][] tree;
   private final IntFunction<T> mapper;
 
   public RadixTreeCache(int level1, int level2, IntFunction<T> mapper, int... commonValues) {
-    this.tree = new AtomicReferenceArray<>(level1);
+    this.tree = new Object[level1][];
     this.mapper = mapper;
     this.level1 = level1;
     this.level2 = level2;
@@ -50,31 +48,15 @@ public T get(int primitive) {
   }
 
   @SuppressWarnings("unchecked")
-  @SuppressFBWarnings("DCN") // only interested in catching NullPointerException (see note below)
   private T computeIfAbsent(int prefix, int primitive) {
-    Object[] page = tree.get(prefix);
-    if (null == page) {
-      try {
-        page = new Object[level2];
-        if (!tree.compareAndSet(prefix, null, page)) {
-          page = tree.get(prefix);
-        }
-      } catch (NullPointerException e) {
-        // Intermittent NPE observed in JDK code on Semeru 11.0.29: java.lang.NullPointerException:
-        // at j.l.i.ArrayVarHandle$...Operations$OpObject.computeOffset(ArrayVarHandle.java:142)
-        // at j.l.i.ArrayVarHandle$...Operations$OpObject.compareAndSet(ArrayVarHandle.java:201)
-        // at j.u.c.atomic.AtomicReferenceArray.compareAndSet(AtomicReferenceArray.java:152)
-        // at datadog.trace.api.cache.RadixTreeCache.computeIfAbsent(RadixTreeCache.java:59)
-        // Location indicates JDK's VarHandle used to access the backing array has returned null
-        // To mitigate this rare JDK bug we still map the primitive but skip caching the result
-        return mapper.apply(primitive);
-      }
+    Object[] page = tree[prefix];
+    if (page == null) {
+      page = tree[prefix] = new Object[level2]; // tolerate race to cache sub-array
     }
-    // it's safe to race here
     int suffix = primitive & mask;
     Object cached = page[suffix];
     if (cached == null) {
-      cached = page[suffix] = mapper.apply(primitive);
+      cached = page[suffix] = mapper.apply(primitive); // tolerate race to cache value
     }
     return (T) cached;
   }
