Minor cleanup of PackageSplitPopulator prior to emitting startup classes
Change-Id: Id50bc906bd010c9d37afbf7f1c47b7443a3b4018
diff --git a/src/main/java/com/android/tools/r8/dex/VirtualFile.java b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
index 827f43bd..d58916c 100644
--- a/src/main/java/com/android/tools/r8/dex/VirtualFile.java
+++ b/src/main/java/com/android/tools/r8/dex/VirtualFile.java
@@ -39,20 +39,20 @@
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Iterators;
import com.google.common.collect.Sets;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
-import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
-import java.util.TreeSet;
-import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.function.Function;
@@ -62,12 +62,6 @@
public static final int MAX_ENTRIES = Constants.U16BIT_MAX + 1;
- /**
- * When distributing classes across files we aim to leave some space. The amount of space left is
- * driven by this constant.
- */
- private static final int MAX_PREFILL_ENTRIES = MAX_ENTRIES - 5000;
-
private final int id;
private final VirtualFileIndexedItemCollection indexedItems;
private final IndexedItemTransaction transaction;
@@ -187,22 +181,6 @@
return originalNames;
}
- private static String extractPrefixToken(int prefixLength, String className, boolean addStar) {
- int index = 0;
- int lastIndex = 0;
- int segmentCount = 0;
- while (lastIndex != -1 && segmentCount++ < prefixLength) {
- index = lastIndex;
- lastIndex = className.indexOf('.', index + 1);
- }
- String prefix = className.substring(0, index);
- if (addStar && segmentCount >= prefixLength) {
- // Full match, add a * to also match sub-packages.
- prefix += ".*";
- }
- return prefix;
- }
-
private ObjectToOffsetMapping objectMapping = null;
public ObjectToOffsetMapping getObjectMapping() {
@@ -427,38 +405,6 @@
mainDexFile.throwIfFull(true, options.reporter);
}
- TreeSet<DexProgramClass> sortClassesByPackage(Set<DexProgramClass> classes,
- Map<DexProgramClass, String> originalNames) {
- TreeSet<DexProgramClass> sortedClasses = new TreeSet<>(
- (DexProgramClass a, DexProgramClass b) -> {
- String originalA = originalNames.get(a);
- String originalB = originalNames.get(b);
- int indexA = originalA.lastIndexOf('.');
- int indexB = originalB.lastIndexOf('.');
- if (indexA == -1 && indexB == -1) {
- // Empty package, compare the class names.
- return originalA.compareTo(originalB);
- }
- if (indexA == -1) {
- // Empty package name comes first.
- return -1;
- }
- if (indexB == -1) {
- // Empty package name comes first.
- return 1;
- }
- String prefixA = originalA.substring(0, indexA);
- String prefixB = originalB.substring(0, indexB);
- int result = prefixA.compareTo(prefixB);
- if (result != 0) {
- return result;
- }
- return originalA.compareTo(originalB);
- });
- sortedClasses.addAll(classes);
- return sortedClasses;
- }
-
protected Map<FeatureSplit, Set<DexProgramClass>> removeFeatureSplitClassesGetMapping() {
assert appView.appInfo().hasClassHierarchy() == appView.enableWholeProgramOptimizations();
if (!appView.appInfo().hasClassHierarchy()) {
@@ -482,8 +428,8 @@
return featureSplitClasses;
}
- protected void addFeatureSplitFiles(Map<FeatureSplit, Set<DexProgramClass>> featureSplitClasses)
- throws IOException {
+ protected void addFeatureSplitFiles(
+ Map<FeatureSplit, Set<DexProgramClass>> featureSplitClasses) {
if (featureSplitClasses.isEmpty()) {
return;
}
@@ -499,19 +445,15 @@
featureSplitSetEntry.getKey());
virtualFiles.add(featureFile);
addMarkers(featureFile);
- Set<DexProgramClass> featureClasses =
- sortClassesByPackage(featureSplitSetEntry.getValue(), originalNames);
filesForDistribution = virtualFiles.subList(virtualFiles.size() - 1, virtualFiles.size());
-
new PackageSplitPopulator(
filesForDistribution,
appView,
- featureClasses,
+ featureSplitSetEntry.getValue(),
originalNames,
0,
- writer.namingLens,
- options)
- .call();
+ writer.namingLens)
+ .run();
}
}
}
@@ -564,18 +506,14 @@
executorService)
.distribute();
} else {
- // Sort the remaining classes based on the original names.
- // This with make classes from the same package be adjacent.
- classes = sortClassesByPackage(classes, originalNames);
new PackageSplitPopulator(
filesForDistribution,
appView,
classes,
originalNames,
fileIndexOffset,
- writer.namingLens,
- options)
- .call();
+ writer.namingLens)
+ .run();
}
addFeatureSplitFiles(featureSplitClasses);
@@ -974,7 +912,63 @@
* <p>The populator cycles through the files until all classes have been successfully placed and
* adds new files to the passed in map if it can't fit in the existing files.
*/
- private static class PackageSplitPopulator implements Callable<Map<String, Integer>> {
+ private static class PackageSplitPopulator {
+
+ static class PackageSplitClassPartioning {
+
+ // The set of classes that must be written, sorted by original names so that classes in the
+ // same package are adjacent.
+ private final List<DexProgramClass> nonStartupClasses;
+
+ private PackageSplitClassPartioning(List<DexProgramClass> nonStartupClasses) {
+ this.nonStartupClasses = nonStartupClasses;
+ }
+
+ public static PackageSplitClassPartioning create(
+ Collection<DexProgramClass> classes, Map<DexProgramClass, String> originalNames) {
+ return create(classes, getClassesByPackageComparator(originalNames));
+ }
+
+ private static PackageSplitClassPartioning create(
+ Collection<DexProgramClass> classes, Comparator<DexProgramClass> comparator) {
+ List<DexProgramClass> nonStartupClasses = new ArrayList<>(classes);
+ nonStartupClasses.sort(comparator);
+ return new PackageSplitClassPartioning(nonStartupClasses);
+ }
+
+ private static Comparator<DexProgramClass> getClassesByPackageComparator(
+ Map<DexProgramClass, String> originalNames) {
+ return (a, b) -> {
+ String originalA = originalNames.get(a);
+ String originalB = originalNames.get(b);
+ int indexA = originalA.lastIndexOf('.');
+ int indexB = originalB.lastIndexOf('.');
+ if (indexA == -1 && indexB == -1) {
+ // Empty package, compare the class names.
+ return originalA.compareTo(originalB);
+ }
+ if (indexA == -1) {
+ // Empty package name comes first.
+ return -1;
+ }
+ if (indexB == -1) {
+ // Empty package name comes first.
+ return 1;
+ }
+ String prefixA = originalA.substring(0, indexA);
+ String prefixB = originalB.substring(0, indexB);
+ int result = prefixA.compareTo(prefixB);
+ if (result != 0) {
+ return result;
+ }
+ return originalA.compareTo(originalB);
+ };
+ }
+
+ public List<DexProgramClass> getNonStartupClasses() {
+ return nonStartupClasses;
+ }
+ }
/**
* Android suggests com.company.product for package names, so the components will be at level 4
@@ -988,7 +982,7 @@
*/
private static final int MIN_FILL_FACTOR = 5;
- private final List<DexProgramClass> classes;
+ private final PackageSplitClassPartioning classPartioning;
private final Map<DexProgramClass, String> originalNames;
private final DexItemFactory dexItemFactory;
private final InternalOptions options;
@@ -997,15 +991,14 @@
PackageSplitPopulator(
List<VirtualFile> files,
AppView<?> appView,
- Set<DexProgramClass> classes,
+ Collection<DexProgramClass> classes,
Map<DexProgramClass, String> originalNames,
int fileIndexOffset,
- NamingLens namingLens,
- InternalOptions options) {
- this.classes = new ArrayList<>(classes);
+ NamingLens namingLens) {
+ this.classPartioning = PackageSplitClassPartioning.create(classes, originalNames);
this.originalNames = originalNames;
this.dexItemFactory = appView.dexItemFactory();
- this.options = options;
+ this.options = appView.options();
this.cycler = new VirtualFileCycler(files, appView, namingLens, fileIndexOffset);
}
@@ -1022,17 +1015,21 @@
}
private String getOriginalName(DexProgramClass clazz) {
- return originalNames != null ? originalNames.get(clazz) : clazz.toString();
+ return originalNames.get(clazz);
}
- @Override
- public Map<String, Integer> call() throws IOException {
+ public void run() {
+ List<DexProgramClass> nonPackageClasses = addNonStartupClasses();
+ addNonPackageClasses(cycler, nonPackageClasses);
+ }
+
+ private List<DexProgramClass> addNonStartupClasses() {
int prefixLength = MINIMUM_PREFIX_LENGTH;
int transactionStartIndex = 0;
- int fileStartIndex = 0;
String currentPrefix = null;
- Map<String, Integer> newPackageAssignments = new LinkedHashMap<>();
+ Object2IntMap<String> packageAssignments = new Object2IntOpenHashMap<>();
VirtualFile current = cycler.next();
+ List<DexProgramClass> classes = classPartioning.getNonStartupClasses();
List<DexProgramClass> nonPackageClasses = new ArrayList<>();
for (int classIndex = 0; classIndex < classes.size(); classIndex++) {
DexProgramClass clazz = classes.get(classIndex);
@@ -1040,10 +1037,9 @@
if (!coveredByPrefix(originalName, currentPrefix)) {
if (currentPrefix != null) {
current.commitTransaction();
+ assert verifyPackageToVirtualFileAssignment(packageAssignments, currentPrefix, current);
// Reset the cycler to again iterate over all files, starting with the current one.
cycler.restart();
- assert !newPackageAssignments.containsKey(currentPrefix);
- newPackageAssignments.put(currentPrefix, current.id);
// Try to reduce the prefix length if possible. Only do this on a successful commit.
prefixLength = MINIMUM_PREFIX_LENGTH - 1;
}
@@ -1067,58 +1063,93 @@
}
transactionStartIndex = classIndex;
}
- if (currentPrefix != null) {
- assert clazz.superType != null || clazz.type == dexItemFactory.objectType;
- current.addClass(clazz);
- } else {
+
+ if (currentPrefix == null) {
assert clazz.superType != null;
// We don't have a package, add this to a list of classes that we will add last.
- assert current.transaction.classes.isEmpty();
+ assert current.transaction.isEmpty();
nonPackageClasses.add(clazz);
continue;
}
- if (isFullEnough(current, options)) {
- current.abortTransaction();
- // We allow for a final rollback that has at most 20% of classes in it.
- // This is a somewhat random number that was empirically chosen.
- if (classIndex - transactionStartIndex > (classIndex - fileStartIndex) / MIN_FILL_FACTOR
- && prefixLength < MAXIMUM_PREFIX_LENGTH) {
- prefixLength++;
- } else {
- // Reset the state to after the last commit and cycle through files.
- // The idea is that we do not increase the number of files, so it has to fit
- // somewhere.
- fileStartIndex = transactionStartIndex;
- if (!cycler.hasNext()) {
- // Special case where we simply will never be able to fit the current package into
- // one dex file. This is currently the case for Strings in jumbo tests, see:
- // b/33227518
- if (current.transaction.getNumberOfClasses() == 0) {
- for (int j = transactionStartIndex; j <= classIndex; j++) {
- nonPackageClasses.add(classes.get(j));
- }
- transactionStartIndex = classIndex + 1;
- }
- // All files are filled up to the 20% mark.
- cycler.addFile();
- }
- current = cycler.next();
- }
- currentPrefix = null;
+
+ assert clazz.superType != null || clazz.type == dexItemFactory.objectType;
+ current.addClass(clazz);
+
+ if (hasSpaceForTransaction(current, options)) {
+ continue;
+ }
+
+ int numberOfClassesInTransaction = classIndex - transactionStartIndex + 1;
+ int numberOfClassesInVirtualFileWithTransaction = current.getNumberOfClasses();
+
+ current.abortTransaction();
+
+ // We allow for a final rollback that has at most 20% of classes in it.
+ // This is a somewhat random number that was empirically chosen.
+ if (numberOfClassesInTransaction
+ > numberOfClassesInVirtualFileWithTransaction / MIN_FILL_FACTOR
+ && prefixLength < MAXIMUM_PREFIX_LENGTH) {
// Go back to previous start index.
classIndex = transactionStartIndex - 1;
- assert current != null;
+ currentPrefix = null;
+ prefixLength++;
+ continue;
}
+
+ // Reset the state to after the last commit and cycle through files.
+ // The idea is that we do not increase the number of files, so it has to fit somewhere.
+ if (!cycler.hasNext()) {
+ // Special case where we simply will never be able to fit the current package into
+ // one dex file. This is currently the case for Strings in jumbo tests, see b/33227518.
+ if (current.isEmpty()) {
+ for (int j = transactionStartIndex; j <= classIndex; j++) {
+ nonPackageClasses.add(classes.get(j));
+ }
+ transactionStartIndex = classIndex + 1;
+ }
+ // All files are filled up to the 20% mark.
+ cycler.addFile();
+ }
+
+ // Go back to previous start index.
+ classIndex = transactionStartIndex - 1;
+ current = cycler.next();
+ currentPrefix = null;
+ prefixLength = MINIMUM_PREFIX_LENGTH;
}
+
current.commitTransaction();
- assert !newPackageAssignments.containsKey(currentPrefix);
- if (currentPrefix != null) {
- newPackageAssignments.put(currentPrefix, current.id);
+ assert currentPrefix == null
+ || verifyPackageToVirtualFileAssignment(packageAssignments, currentPrefix, current);
+
+ return nonPackageClasses;
+ }
+
+ private static String extractPrefixToken(int prefixLength, String className, boolean addStar) {
+ int index = 0;
+ int lastIndex = 0;
+ int segmentCount = 0;
+ while (lastIndex != -1 && segmentCount++ < prefixLength) {
+ index = lastIndex;
+ lastIndex = className.indexOf('.', index + 1);
}
- if (nonPackageClasses.size() > 0) {
- addNonPackageClasses(cycler, nonPackageClasses);
+ String prefix = className.substring(0, index);
+ if (addStar && segmentCount >= prefixLength) {
+ // Full match, add a * to also match sub-packages.
+ prefix += ".*";
}
- return newPackageAssignments;
+ return prefix;
+ }
+
+ private boolean verifyPackageToVirtualFileAssignment(
+ Object2IntMap<String> packageAssignments, String packageName, VirtualFile virtualFile) {
+ assert !packageAssignments.containsKey(packageName);
+ packageAssignments.put(packageName, virtualFile.getId());
+ return true;
+ }
+
+ private boolean hasSpaceForTransaction(VirtualFile current, InternalOptions options) {
+ return !isFullEnough(current, options);
}
private boolean isFullEnough(VirtualFile current, InternalOptions options) {
@@ -1131,6 +1162,9 @@
private void addNonPackageClasses(
VirtualFileCycler cycler, List<DexProgramClass> nonPackageClasses) {
+ if (nonPackageClasses.isEmpty()) {
+ return;
+ }
cycler.restart();
VirtualFile current;
current = cycler.next();
