Avoid calling String.substring when possible.
Due to e.g. method inlining, the same strings occur over and over again.
Java's Map interface requires us to call String.substring to even do a
dedup, which creates garbage.
This change adds a small direct-mapped cache to avoid creating objects.
When fully parsing youtube.android_17.19, I found that
ProguardMapReader.substring is called about 5M times, and the new cache
has a hit rate of ~80%, avoiding creating ~3.9M Strings.
Bug: b/240037206
Change-Id: Iff054f814ce33dfe65f6afe5b03181630721239a
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 10a5fee..96609c9 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapReader.java
@@ -461,6 +461,16 @@
}
}
+ // Small direct-mapped cache for computing String.substring.
+ //
+ // Due to inlining, the same method names and parameter types will occur repeatedly on multiple
+ // lines. String.substring ends up allocating a lot of garbage, so we use this cache to find
+ // String objects without having to allocate memory.
+ //
+ // "Direct-mapped" is inspired from computer architecture, where having a lookup policy in
+ // which entries can only ever map to one cache line is often faster than a fancy LRU cache.
+ private static final int SUBSTRING_CACHE_SIZE = 64;
+ private final String[] substringCache = new String[SUBSTRING_CACHE_SIZE];
// Cache for canonicalizing strings.
// This saves 10% of heap space for large programs.
private final HashMap<String, String> identifierCache = new HashMap<>();
@@ -472,8 +482,21 @@
private final HashMap<Signature, Signature> signatureCache = new HashMap<>();
private String substring(int start) {
+ int cacheIdx;
+ {
+ // Check if there was a recent String accessed which matches the substring.
+ int len = lineOffset - start;
+ cacheIdx = len % SUBSTRING_CACHE_SIZE;
+ String candidate = substringCache[cacheIdx];
+ if (candidate != null
+ && candidate.length() == len
+ && line.regionMatches(start, candidate, 0, len)) {
+ return candidate;
+ }
+ }
+
String result = line.substring(start, lineOffset);
- return identifierCache.computeIfAbsent(result, Function.identity());
+ return substringCache[cacheIdx] = identifierCache.computeIfAbsent(result, Function.identity());
}
private String parseMethodName() {
