diff --git a/src/main/java/com/android/tools/r8/naming/PositionRangeAllocator.java b/src/main/java/com/android/tools/r8/naming/PositionRangeAllocator.java
new file mode 100644
index 0000000..957e660
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/naming/PositionRangeAllocator.java
@@ -0,0 +1,71 @@
+// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.naming;
+
+public abstract class PositionRangeAllocator {
+
+  private static final int MAX_POSITION = 256;
+  private static final int MAX_DELTA = 1;
+
+  final Range[] cache = new Range[MAX_POSITION];
+
+  public Range get(int index) {
+    return (index >= 0 && index < MAX_POSITION) ? cache[index] : new Range(index);
+  }
+
+  public static CardinalPositionRangeAllocator createCardinalPositionRangeAllocator() {
+    return new CardinalPositionRangeAllocator();
+  }
+
+  public static NonCardinalPositionRangeAllocator createNonCardinalPositionRangeAllocator() {
+    return new NonCardinalPositionRangeAllocator();
+  }
+
+  public static class CardinalPositionRangeAllocator extends PositionRangeAllocator {
+
+    private CardinalPositionRangeAllocator() {
+      super();
+      for (int i = 0; i < MAX_POSITION; i++) {
+        cache[i] = new Range(i);
+      }
+    }
+  }
+
+  public static class NonCardinalPositionRangeFixedDeltaCache extends PositionRangeAllocator {
+
+    public NonCardinalPositionRangeFixedDeltaCache(int delta) {
+      super();
+      for (int i = 0; i < MAX_POSITION; i++) {
+        cache[i] = new Range(i, i + delta);
+      }
+    }
+  }
+
+  public static class NonCardinalPositionRangeAllocator extends PositionRangeAllocator {
+
+    private final NonCardinalPositionRangeFixedDeltaCache[] cache =
+        new NonCardinalPositionRangeFixedDeltaCache[MAX_DELTA + 1];
+
+    private NonCardinalPositionRangeAllocator() {
+      for (int i = 0; i <= MAX_DELTA; i++) {
+        cache[i] = new NonCardinalPositionRangeFixedDeltaCache(i);
+      }
+    }
+
+    public Range get(int from, int to) {
+      if (from >= MAX_POSITION) {
+        return new Range(from, to);
+      }
+      int thisDelta = to - from;
+      if (thisDelta < 0) {
+        return new Range(from, to);
+      }
+      if (thisDelta > MAX_DELTA) {
+        return new Range(from, to);
+      }
+      return cache[thisDelta].get(from);
+    }
+  }
+}
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
index 6bde14bf..a3a3aa0 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
@@ -8,6 +8,8 @@
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
 import com.android.tools.r8.naming.MemberNaming.Signature;
+import com.android.tools.r8.naming.PositionRangeAllocator.CardinalPositionRangeAllocator;
+import com.android.tools.r8.naming.PositionRangeAllocator.NonCardinalPositionRangeAllocator;
 import com.android.tools.r8.naming.mappinginformation.MapVersionMappingInformation;
 import com.android.tools.r8.naming.mappinginformation.MappingInformation;
 import com.android.tools.r8.naming.mappinginformation.MappingInformationDiagnostics;
@@ -68,6 +70,11 @@
   private final boolean allowEmptyMappedRanges;
   private final boolean allowExperimentalMapping;
 
+  private final CardinalPositionRangeAllocator cardinalRangeCache =
+      PositionRangeAllocator.createCardinalPositionRangeAllocator();
+  private final NonCardinalPositionRangeAllocator nonCardinalRangeCache =
+      PositionRangeAllocator.createNonCardinalPositionRangeAllocator();
+
   @Override
   public void close() throws IOException {
     reader.close();
@@ -623,12 +630,12 @@
     int from = parseNumber();
     skipWhitespace();
     if (peekChar(0) != ':') {
-      return new Range(from);
+      return cardinalRangeCache.get(from);
     }
     expect(':');
     skipWhitespace();
     int to = parseNumber();
-    return new Range(from, to);
+    return nonCardinalRangeCache.get(from, to);
   }
 
   private int parseNumber() {
diff --git a/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java b/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
index 74b7b06..a0a2a74 100644
--- a/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
+++ b/src/main/java/com/android/tools/r8/utils/LineNumberOptimizer.java
@@ -57,6 +57,9 @@
 import com.android.tools.r8.naming.MemberNaming;
 import com.android.tools.r8.naming.MemberNaming.FieldSignature;
 import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.naming.PositionRangeAllocator;
+import com.android.tools.r8.naming.PositionRangeAllocator.CardinalPositionRangeAllocator;
+import com.android.tools.r8.naming.PositionRangeAllocator.NonCardinalPositionRangeAllocator;
 import com.android.tools.r8.naming.ProguardMapSupplier;
 import com.android.tools.r8.naming.ProguardMapSupplier.ProguardMapId;
 import com.android.tools.r8.naming.Range;
@@ -509,6 +512,11 @@
             ? new NativePcSupport()
             : new Pc2PcMappingSupport(appView.options().allowDiscardingResidualDebugInfo());
 
+    CardinalPositionRangeAllocator cardinalRangeCache =
+        PositionRangeAllocator.createCardinalPositionRangeAllocator();
+    NonCardinalPositionRangeAllocator nonCardinalRangeCache =
+        PositionRangeAllocator.createNonCardinalPositionRangeAllocator();
+
     // Collect which files contain which classes that need to have their line numbers optimized.
     for (DexProgramClass clazz : appView.appInfo().classes()) {
       boolean isSyntheticClass = appView.getSyntheticItems().isSyntheticClass(clazz);
@@ -718,10 +726,11 @@
                 && definition.getCode().asDexCode().getDebugInfo()
                     == DexDebugInfoForSingleLineMethod.getInstance()) {
               assert firstPosition.originalLine == lastPosition.originalLine;
-              obfuscatedRange = new Range(0, MAX_LINE_NUMBER);
+              obfuscatedRange = nonCardinalRangeCache.get(0, MAX_LINE_NUMBER);
             } else {
               obfuscatedRange =
-                  new Range(firstPosition.obfuscatedLine, lastPosition.obfuscatedLine);
+                  nonCardinalRangeCache.get(
+                      firstPosition.obfuscatedLine, lastPosition.obfuscatedLine);
             }
             ClassNaming.Builder classNamingBuilder = onDemandClassNamingBuilder.computeIfAbsent();
             MappedRange lastMappedRange =
@@ -732,9 +741,11 @@
                     firstPosition.method,
                     obfuscatedName,
                     obfuscatedRange,
-                    new Range(firstPosition.originalLine, lastPosition.originalLine),
+                    nonCardinalRangeCache.get(
+                        firstPosition.originalLine, lastPosition.originalLine),
                     firstPosition.caller,
-                    prunedInlinedClasses);
+                    prunedInlinedClasses,
+                    cardinalRangeCache);
             for (MappingInformation info : methodMappingInfo) {
               lastMappedRange.addMappingInformation(info, Unreachable::raise);
             }
@@ -758,10 +769,12 @@
                         classNamingBuilder,
                         position.getMethod(),
                         obfuscatedName,
-                        new Range(placeHolderLineToBeFixed, placeHolderLineToBeFixed),
-                        new Range(position.getLine(), position.getLine()),
+                        nonCardinalRangeCache.get(
+                            placeHolderLineToBeFixed, placeHolderLineToBeFixed),
+                        nonCardinalRangeCache.get(position.getLine(), position.getLine()),
                         position.getCallerPosition(),
-                        prunedInlinedClasses);
+                        prunedInlinedClasses,
+                        cardinalRangeCache);
                   });
               outlinesToFix
                   .computeIfAbsent(
@@ -838,7 +851,8 @@
       Range obfuscatedRange,
       Range originalLine,
       Position caller,
-      Map<DexType, String> prunedInlineHolder) {
+      Map<DexType, String> prunedInlineHolder,
+      CardinalPositionRangeAllocator cardinalRangeCache) {
     MappedRange lastMappedRange =
         classNamingBuilder.addMappedRange(
             obfuscatedRange,
@@ -859,7 +873,8 @@
           classNamingBuilder.addMappedRange(
               obfuscatedRange,
               getOriginalMethodSignature.apply(caller.getMethod()),
-              new Range(Math.max(caller.getLine(), 0)), // Prevent against "no-position".
+              cardinalRangeCache.get(
+                  Math.max(caller.getLine(), 0)), // Prevent against "no-position".
               obfuscatedName);
       if (caller.isRemoveInnerFramesIfThrowingNpe()) {
         lastMappedRange.addMappingInformation(