diff --git a/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java b/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java
index 8ad22c7..b03cab4 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/PrefixRewritingMapper.java
@@ -13,6 +13,7 @@
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 import java.util.Map;
 import java.util.Set;
@@ -47,6 +48,8 @@
 
   public abstract boolean isRewriting();
 
+  public abstract boolean shouldRewriteTypeName(String typeName);
+
   public abstract void forAllRewrittenTypes(Consumer<DexType> consumer);
 
   public static class DesugarPrefixRewritingMapper extends PrefixRewritingMapper {
@@ -54,6 +57,7 @@
     private final Set<DexType> notRewritten = Sets.newConcurrentHashSet();
     private final Map<DexType, DexType> rewritten = new ConcurrentHashMap<>();
     private final Map<DexString, DexString> initialPrefixes;
+    private final Set<String> initialPrefixStrings;
     private final DexItemFactory factory;
     private final boolean l8Compilation;
 
@@ -62,10 +66,13 @@
       this.factory = itemFactory;
       this.l8Compilation = libraryCompilation;
       ImmutableMap.Builder<DexString, DexString> builder = ImmutableMap.builder();
+      ImmutableSet.Builder<String> prefixStringBuilder = ImmutableSet.builder();
       for (String key : prefixes.keySet()) {
+        prefixStringBuilder.add(key);
         builder.put(toDescriptorPrefix(key), toDescriptorPrefix(prefixes.get(key)));
       }
       this.initialPrefixes = builder.build();
+      this.initialPrefixStrings = prefixStringBuilder.build();
       validatePrefixes(prefixes);
     }
 
@@ -184,6 +191,17 @@
     public boolean isRewriting() {
       return true;
     }
+
+    @Override
+    public boolean shouldRewriteTypeName(String typeName) {
+      // TODO(b/154800164): We could use tries instead of looking-up everywhere.
+      for (DexString prefix : initialPrefixes.keySet()) {
+        if (typeName.startsWith(prefix.toString())) {
+          return true;
+        }
+      }
+      return false;
+    }
   }
 
   public static class EmptyPrefixRewritingMapper extends PrefixRewritingMapper {
@@ -202,6 +220,11 @@
     }
 
     @Override
+    public boolean shouldRewriteTypeName(String typeName) {
+      return false;
+    }
+
+    @Override
     public void forAllRewrittenTypes(Consumer<DexType> consumer) {}
   }
 }
diff --git a/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java b/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
index b9fc4cb..a775a72 100644
--- a/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/IdentifierMinifier.java
@@ -16,7 +16,6 @@
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexString;
-import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.DexValue;
 import com.android.tools.r8.graph.DexValue.DexItemBasedValueString;
 import com.android.tools.r8.graph.DexValue.DexValueString;
@@ -25,7 +24,6 @@
 import com.android.tools.r8.utils.ThreadUtils;
 import java.util.ArrayList;
 import java.util.List;
-import java.util.Map;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 
@@ -104,21 +102,10 @@
   }
 
   private DexString getRenamedStringLiteral(DexString originalLiteral) {
-    String originalString = originalLiteral.toString();
-    Map<String, DexType> renamedYetMatchedTypes =
-        lens.getRenamedItems(
-            DexType.class,
-            type -> type.toSourceString().equals(originalString),
-            DexType::toSourceString);
-    DexType type = renamedYetMatchedTypes.get(originalString);
-    if (type != null) {
-      DexString renamed = lens.lookupDescriptor(type);
-      // Create a new DexString only when the corresponding string literal will be replaced.
-      if (renamed != originalLiteral) {
-        return appView.dexItemFactory().createString(descriptorToJavaType(renamed.toString()));
-      }
-    }
-    return originalLiteral;
+    DexString rewrittenString = lens.lookupDescriptorForJavaTypeName(originalLiteral.toString());
+    return rewrittenString == null
+        ? originalLiteral
+        : appView.dexItemFactory().createString(descriptorToJavaType(rewrittenString.toString()));
   }
 
   private void replaceDexItemBasedConstString(ExecutorService executorService)
diff --git a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
index b7bfcdb..eb4e9ca 100644
--- a/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
+++ b/src/main/java/com/android/tools/r8/naming/MinifiedRenaming.java
@@ -20,13 +20,10 @@
 import com.android.tools.r8.naming.NamingLens.NonIdentityNamingLens;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
-import com.google.common.collect.ImmutableMap;
 import java.util.ArrayList;
 import java.util.IdentityHashMap;
 import java.util.List;
 import java.util.Map;
-import java.util.function.Function;
-import java.util.function.Predicate;
 
 class MinifiedRenaming extends NonIdentityNamingLens {
 
@@ -39,7 +36,7 @@
       ClassRenaming classRenaming,
       MethodRenaming methodRenaming,
       FieldRenaming fieldRenaming) {
-    super(appView.dexItemFactory());
+    super(appView.dexItemFactory(), classRenaming.classRenaming);
     this.appView = appView;
     this.packageRenaming = classRenaming.packageRenaming;
     renaming.putAll(classRenaming.classRenaming);
@@ -123,15 +120,6 @@
     return renaming.getOrDefault(field, field.name);
   }
 
-  @Override
-  public <T extends DexItem> Map<String, T> getRenamedItems(
-      Class<T> clazz, Predicate<T> predicate, Function<T, String> namer) {
-    return renaming.keySet().stream()
-        .filter(item -> (clazz.isInstance(item) && predicate.test(clazz.cast(item))))
-        .map(clazz::cast)
-        .collect(ImmutableMap.toImmutableMap(namer, i -> i));
-  }
-
   /**
    * Checks that the renaming of the method reference {@param method} is consistent with the
    * renaming of the resolution target of {@param method}.
diff --git a/src/main/java/com/android/tools/r8/naming/NamingLens.java b/src/main/java/com/android/tools/r8/naming/NamingLens.java
index 9147b84..bdd0e70 100644
--- a/src/main/java/com/android/tools/r8/naming/NamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/NamingLens.java
@@ -8,7 +8,6 @@
 import com.android.tools.r8.graph.DexEncodedField;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexItem;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -20,13 +19,11 @@
 import com.android.tools.r8.optimize.MemberRebindingAnalysis;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.InternalOptions;
-import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Sets;
 import java.util.Arrays;
+import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
-import java.util.function.Function;
-import java.util.function.Predicate;
 
 /**
  * Implements a translation of the Dex graph from original names to new names produced by the {@link
@@ -45,6 +42,8 @@
 
   public abstract DexString lookupDescriptor(DexType type);
 
+  public abstract DexString lookupDescriptorForJavaTypeName(String typeName);
+
   public DexString lookupClassDescriptor(DexType type) {
     assert type.isClassType();
     return internalLookupClassDescriptor(type);
@@ -147,9 +146,6 @@
     return DescriptorUtils.descriptorToInternalName(lookupDescriptor(type).toString());
   }
 
-  public abstract <T extends DexItem> Map<String, T> getRenamedItems(
-      Class<T> clazz, Predicate<T> predicate, Function<T, String> namer);
-
   /**
    * Checks whether the target will be translated properly by this lens.
    *
@@ -189,9 +185,13 @@
   public abstract static class NonIdentityNamingLens extends NamingLens {
 
     private final DexItemFactory dexItemFactory;
+    private final Map<String, DexString> typeStringMapping;
 
-    protected NonIdentityNamingLens(DexItemFactory dexItemFactory) {
+    protected NonIdentityNamingLens(
+        DexItemFactory dexItemFactory, Map<DexType, DexString> typeMapping) {
       this.dexItemFactory = dexItemFactory;
+      typeStringMapping = new HashMap<>();
+      typeMapping.forEach((k, v) -> typeStringMapping.put(k.toSourceString(), v));
     }
 
     protected DexItemFactory dexItemFactory() {
@@ -211,6 +211,11 @@
       assert type.isClassType();
       return lookupClassDescriptor(type);
     }
+
+    @Override
+    public DexString lookupDescriptorForJavaTypeName(String typeName) {
+      return typeStringMapping.get(typeName);
+    }
   }
 
   private static final class IdentityLens extends NamingLens {
@@ -225,6 +230,11 @@
     }
 
     @Override
+    public DexString lookupDescriptorForJavaTypeName(String typeName) {
+      return null;
+    }
+
+    @Override
     protected DexString internalLookupClassDescriptor(DexType type) {
       return type.descriptor;
     }
@@ -250,12 +260,6 @@
     }
 
     @Override
-    public <T extends DexItem> Map<String, T> getRenamedItems(
-        Class<T> clazz, Predicate<T> predicate, Function<T, String> namer) {
-      return ImmutableMap.of();
-    }
-
-    @Override
     public boolean verifyRenamingConsistentWithResolution(DexMethod item) {
       return true;
     }
diff --git a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
index e987def..04f235f 100644
--- a/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
+++ b/src/main/java/com/android/tools/r8/naming/PrefixRewritingNamingLens.java
@@ -6,20 +6,13 @@
 
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexItem;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexString;
 import com.android.tools.r8.graph.DexType;
 import com.android.tools.r8.graph.InnerClassAttribute;
 import com.android.tools.r8.naming.NamingLens.NonIdentityNamingLens;
 import com.android.tools.r8.utils.InternalOptions;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.Map;
-import java.util.function.Function;
-import java.util.function.Predicate;
-import java.util.stream.Collectors;
-import java.util.stream.Stream;
+import java.util.IdentityHashMap;
 
 // Naming lens for rewriting type prefixes.
 public class PrefixRewritingNamingLens extends NonIdentityNamingLens {
@@ -41,7 +34,7 @@
   }
 
   public PrefixRewritingNamingLens(NamingLens namingLens, AppView<?> appView) {
-    super(appView.dexItemFactory());
+    super(appView.dexItemFactory(), new IdentityHashMap<>());
     this.appView = appView;
     this.namingLens = namingLens;
     this.options = appView.options();
@@ -103,6 +96,18 @@
   }
 
   @Override
+  public DexString lookupDescriptorForJavaTypeName(String typeName) {
+    if (appView.rewritePrefix.shouldRewriteTypeName(typeName)) {
+      DexType rewrittenType =
+          appView.rewritePrefix.rewrittenType(dexItemFactory().createType(typeName), appView);
+      if (rewrittenType != null) {
+        return rewrittenType.descriptor;
+      }
+    }
+    return namingLens.lookupDescriptorForJavaTypeName(typeName);
+  }
+
+  @Override
   public String lookupPackageName(String packageName) {
     // Used for resource shrinking.
     // Desugared libraries do not have resources.
@@ -122,30 +127,6 @@
   }
 
   @Override
-  public <T extends DexItem> Map<String, T> getRenamedItems(
-      Class<T> clazz, Predicate<T> predicate, Function<T, String> namer) {
-    Map<String, T> renamedItemsPrefixRewritting;
-    if (clazz == DexType.class) {
-      renamedItemsPrefixRewritting = new HashMap<>();
-      appView.rewritePrefix.forAllRewrittenTypes(
-          item -> {
-            T cast = clazz.cast(item);
-            if (predicate.test(cast)) {
-              renamedItemsPrefixRewritting.put(namer.apply(cast), cast);
-            }
-          });
-    } else {
-      renamedItemsPrefixRewritting = Collections.emptyMap();
-    }
-    Map<String, T> renamedItemsMinifier = namingLens.getRenamedItems(clazz, predicate, namer);
-    // The Collector throws an exception for duplicated keys.
-    return Stream.concat(
-            renamedItemsPrefixRewritting.entrySet().stream(),
-            renamedItemsMinifier.entrySet().stream())
-        .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
-  }
-
-  @Override
   public boolean verifyRenamingConsistentWithResolution(DexMethod item) {
     return namingLens.verifyRenamingConsistentWithResolution(item);
   }
diff --git a/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java b/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java
index 09ca5bd..3a5902a 100644
--- a/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java
+++ b/src/main/java/com/android/tools/r8/relocator/SimplePackagesRewritingMapper.java
@@ -7,7 +7,6 @@
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexEncodedMethod;
 import com.android.tools.r8.graph.DexField;
-import com.android.tools.r8.graph.DexItem;
 import com.android.tools.r8.graph.DexItemFactory;
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexProgramClass;
@@ -22,8 +21,6 @@
 import com.google.common.collect.ImmutableMap;
 import java.util.IdentityHashMap;
 import java.util.Map;
-import java.util.function.Function;
-import java.util.function.Predicate;
 
 class SimplePackagesRewritingMapper {
 
@@ -105,7 +102,7 @@
         Map<DexType, DexString> typeMappings,
         Map<String, String> packageMappings,
         DexItemFactory factory) {
-      super(factory);
+      super(factory, typeMappings);
       this.typeMappings = typeMappings;
       this.packageMappings = packageMappings;
     }
@@ -136,15 +133,6 @@
     }
 
     @Override
-    public <T extends DexItem> Map<String, T> getRenamedItems(
-        Class<T> clazz, Predicate<T> predicate, Function<T, String> namer) {
-      return typeMappings.keySet().stream()
-          .filter(item -> (clazz.isInstance(item) && predicate.test(clazz.cast(item))))
-          .map(clazz::cast)
-          .collect(ImmutableMap.toImmutableMap(namer, i -> i));
-    }
-
-    @Override
     public boolean verifyRenamingConsistentWithResolution(DexMethod item) {
       return true;
     }