Improve PackageGroupContents search from O(n) to O(1) Before Search in group content happened by iteration of all PackageSpecifications. this is O(n) and if package group has around 100K records, makes negative performance impact. Added Single package to HashSet, to make O(1) search time. Also added negative to separate collection, make search in it first as it is necessary and return result if match found. No test added, rely on PackageGroupTest. No API changes (only AutoCodec changes some getters because constructor arguments changed) RELNOTES:none PiperOrigin-RevId: 239199351
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageSpecification.java b/src/main/java/com/google/devtools/build/lib/packages/PackageSpecification.java index ec71a36..ea5f224 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/PackageSpecification.java +++ b/src/main/java/com/google/devtools/build/lib/packages/PackageSpecification.java
@@ -15,6 +15,7 @@ import com.google.common.base.Verify; import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableMap; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.cmdline.LabelSyntaxException; import com.google.devtools.build.lib.cmdline.PackageIdentifier; @@ -23,6 +24,7 @@ import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec; import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization; import com.google.devtools.build.lib.vfs.PathFragment; +import java.util.LinkedHashMap; import java.util.stream.Stream; /** @@ -59,11 +61,6 @@ */ protected abstract String toStringWithoutRepository(); - /** Returns {@code true} if the package specification represents a negated match. */ - protected boolean negative() { - return false; - } - /** * Parses the provided {@link String} into a {@link PackageSpecification}. * @@ -163,7 +160,7 @@ @AutoCodec @VisibleForSerialization - static class SinglePackage extends PackageSpecification { + static final class SinglePackage extends PackageSpecification { private PackageIdentifier singlePackageName; @VisibleForSerialization @@ -206,7 +203,7 @@ @AutoCodec @VisibleForSerialization - static class AllPackagesBeneath extends PackageSpecification { + static final class AllPackagesBeneath extends PackageSpecification { private PackageIdentifier prefix; @VisibleForSerialization @@ -254,7 +251,7 @@ /** A package specification for a negative match, e.g. {@code -//pkg/sub/...}. */ @AutoCodec @VisibleForSerialization - static class NegativePackageSpecification extends PackageSpecification { + static final class NegativePackageSpecification extends PackageSpecification { private final PackageSpecification delegate; NegativePackageSpecification(PackageSpecification delegate) { @@ -262,11 +259,6 @@ } @Override - protected boolean negative() { - return true; - } - - @Override protected boolean containsPackage(PackageIdentifier packageName) { return delegate.containsPackage(packageName); } @@ -298,7 +290,7 @@ @AutoCodec @VisibleForSerialization - static class AllPackages extends PackageSpecification { + static final class AllPackages extends PackageSpecification { private static final PackageSpecification EVERYTHING = new AllPackages(); @Override @@ -341,11 +333,23 @@ @Immutable @AutoCodec public static final class PackageGroupContents { - private final ImmutableList<PackageSpecification> packageSpecifications; + private final ImmutableMap<PackageIdentifier, PackageSpecification> singlePackages; + private final ImmutableList<PackageSpecification> negativePackageSpecifications; + private final ImmutableList<PackageSpecification> allSpecifications; @VisibleForSerialization - PackageGroupContents(ImmutableList<PackageSpecification> packageSpecifications) { - this.packageSpecifications = packageSpecifications; + PackageGroupContents( + ImmutableMap<PackageIdentifier, PackageSpecification> singlePackages, + ImmutableList<PackageSpecification> negativePackageSpecifications, + ImmutableList<PackageSpecification> allSpecifications) { + + this.singlePackages = singlePackages; + this.negativePackageSpecifications = negativePackageSpecifications; + this.allSpecifications = allSpecifications; + } + + public ImmutableList<PackageSpecification> getPackageSpecifications() { + throw new UnsupportedOperationException(); } /** @@ -354,7 +358,32 @@ */ public static PackageGroupContents create( ImmutableList<PackageSpecification> packageSpecifications) { - return new PackageGroupContents(packageSpecifications); + LinkedHashMap<PackageIdentifier, PackageSpecification> singlePackageBuilder = + new LinkedHashMap<>(); + ImmutableList.Builder<PackageSpecification> negativePackageSpecificationsBuilder = + ImmutableList.builder(); + ImmutableList.Builder<PackageSpecification> allSpecificationsBuilder = + ImmutableList.builder(); + + for (PackageSpecification packageSpecification : packageSpecifications) { + if (packageSpecification instanceof SinglePackage) { + singlePackageBuilder.put( + ((SinglePackage) packageSpecification).singlePackageName, packageSpecification); + } else if (packageSpecification instanceof NegativePackageSpecification) { + negativePackageSpecificationsBuilder.add(packageSpecification); + } else { + allSpecificationsBuilder.add(packageSpecification); + if (!(packageSpecification instanceof AllPackages) + && !(packageSpecification instanceof AllPackagesBeneath)) { + throw new IllegalStateException( + "Instance of unhandled class " + packageSpecification.getClass()); + } + } + } + return new PackageGroupContents( + ImmutableMap.copyOf(singlePackageBuilder), + negativePackageSpecificationsBuilder.build(), + allSpecificationsBuilder.build()); } /** @@ -363,17 +392,17 @@ * specifications match. */ public boolean containsPackage(PackageIdentifier packageIdentifier) { - boolean match = false; - for (PackageSpecification p : packageSpecifications) { - if (p.containsPackage(packageIdentifier)) { - if (p.negative()) { - return false; - } else { - match = true; - } - } + // if some negative matches, returns false immediately. + if (negativePackageSpecifications.stream() + .anyMatch(p -> p.containsPackage(packageIdentifier))) { + return false; } - return match; + + if (singlePackages.containsKey(packageIdentifier)) { + return true; + } + + return allSpecifications.stream().anyMatch(p -> p.containsPackage(packageIdentifier)); } /** @@ -381,7 +410,7 @@ * same format accepted by {@link #fromString}. */ public Stream<String> containedPackages() { - return packageSpecifications.stream().map(PackageSpecification::toString); + return getStream().map(PackageSpecification::toString); } /** @@ -392,7 +421,13 @@ * the {@link PackageSpecification}. */ public Stream<String> containedPackagesWithoutRepository() { - return packageSpecifications.stream().map(PackageSpecification::toStringWithoutRepository); + return getStream().map(PackageSpecification::toStringWithoutRepository); + } + + private Stream<PackageSpecification> getStream() { + return Stream.concat( + Stream.concat(allSpecifications.stream(), negativePackageSpecifications.stream()), + singlePackages.values().stream()); } } }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/PackageGroupTest.java b/src/test/java/com/google/devtools/build/lib/packages/PackageGroupTest.java index a16d7cc..518ed7d 100644 --- a/src/test/java/com/google/devtools/build/lib/packages/PackageGroupTest.java +++ b/src/test/java/com/google/devtools/build/lib/packages/PackageGroupTest.java
@@ -248,6 +248,25 @@ .containsExactly(PackageSpecification.everything().toString()); } + @Test + public void testDuplicatePackage() throws Exception { + scratch.file("pkg/BUILD"); + scratch.file("one/two/BUILD"); + + scratch.file( + "test/BUILD", + "package_group(", + " name = 'packages',", + " packages = [", + " '//one/two',", + " '//one/two',", + " ],", + ")"); + + PackageGroup grp = getPackageGroup("test", "packages"); + assertThat(grp.contains(getPackage("one/two"))).isTrue(); + } + private Package getPackage(String packageName) throws Exception { PathFragment buildFileFragment = PathFragment.create(packageName).getRelative("BUILD");