diff options
author | 2015-05-11 18:23:47 +0000 | |
---|---|---|
committer | 2015-05-15 09:33:11 +0000 | |
commit | 4a57ce9b37f23b311df9564c13cb1e9fc61061e4 (patch) | |
tree | 8c49563f23caa35699e29b0bdcb05110221ca4c5 | |
parent | 3adbc49499572b8c6557bef089934ea0db7fd2db (diff) |
Optimize AggregatingAttributeMapper.visitAttribute (which returns
every possible value an attribute can take) for attributes with
multiple selects:
Given
attr = select({':a': 'w', ':b': 'x'}) + select({':a': 'y', ':b': 'z'}
the naive approach is to combine every possible value of the first select
with every possible value of the second select (producing 4 possible values
from 2^2 visitations). But since these selects have the same exact
conditions, only two values are actually possible ("wy", "xz") from 2
visitations.
This change efficiently considers that case. More generally, given n
concatenated selects with the same conditions, it brings evaluation time
down from O(2^n) to O(n) (assuming two conditions per select). It also
works for partial matches: given a concatenation of 6 selects where
1, 3, and 5 have the same conditions and 2, 4, and 6 have the same conditions,
evaluation time goes from O(2^6) to O(2^2).
--
MOS_MIGRATED_REVID=93325787
2 files changed, 105 insertions, 14 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java index dff87be011..61c4f3871b 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java +++ b/src/main/java/com/google/devtools/build/lib/packages/AggregatingAttributeMapper.java @@ -14,6 +14,7 @@ package com.google.devtools.build.lib.packages; import com.google.common.base.Preconditions; +import com.google.common.base.Verify; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableSet; @@ -30,7 +31,7 @@ import java.util.Set; import javax.annotation.Nullable; /** - * {@link AttributeMap} implementation that provides the ability to retrieve *all possible* + * {@link AttributeMap} implementation that provides the ability to retrieve <i>all possible</i> * values an attribute might take. */ public class AggregatingAttributeMapper extends AbstractAttributeMapper { @@ -168,7 +169,8 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper { Type.SelectorList<T> selectorList = getSelectorList(attributeName, type); if (selectorList != null) { ImmutableList.Builder<T> builder = ImmutableList.builder(); - visitConfigurableAttribute(selectorList.getSelectors(), type, null, builder); + visitConfigurableAttribute(selectorList.getSelectors(), new BoundSelectorPaths(), type, + null, builder); return builder.build(); } @@ -197,33 +199,103 @@ public class AggregatingAttributeMapper extends AbstractAttributeMapper { } /** - * Determines all possible values a configurable attribute can take and places each one into - * valuesBuilder. + * Determines all possible values a configurable attribute can take. Do not call this method + * unless really necessary (see TODO comment inside). + * + * @param selectors the selectors that make up this attribute assignment (in order) + * @param boundSelectorPaths paths that have already been chosen from previous selectors in an + * earlier recursive call of this method. For example, given + * <pre>cmd = select({':a': 'w', ':b': 'x'}) + select({':a': 'y', ':b': 'z'})</pre> + * the only possible values for <code>cmd</code> are <code>"wy"</code> and <code>"xz"</code>. + * This is because the selects have the same conditions, so whatever matches the first also + * matches the second. Note that this doesn't work for selects with overlapping but + * <i>different</i> key sets. That's because of key specialization (see + * {@link com.google.devtools.build.lib.analysis.ConfiguredAttributeMapper} - if the + * second select also included a condition <code>':c'</code> that includes both the flags + * in <code>':a'</code> and <code>':b'</code>, <code>':c'</code> would be chosen over + * them both. + * @param type the type of this attribute + * @param currentValueSoFar the partial value produced so far from earlier calls to this method + * @param valuesBuilder output container for full values this attribute can take */ - private <T> void visitConfigurableAttribute(List<Type.Selector<T>> selectors, Type<T> type, - T currentValueSoFar, ImmutableList.Builder<T> valuesBuilder) { - + private <T> void visitConfigurableAttribute(List<Type.Selector<T>> selectors, + BoundSelectorPaths boundSelectorPaths, Type<T> type, T currentValueSoFar, + ImmutableList.Builder<T> valuesBuilder) { // TODO(bazel-team): minimize or eliminate uses of this interface. It necessarily grows // exponentially with the number of selects in the attribute. Is that always necessary? // For example, dependency resolution just needs to know every possible label an attribute // might reference, but it doesn't need to know the exact combination of labels that make - // up a value. + // up a value. This may be even less important for non-label values (e.g. strings), which + // have no impact on the dependency structure. + if (selectors.isEmpty()) { valuesBuilder.add(Preconditions.checkNotNull(currentValueSoFar)); } else { Type.Selector<T> firstSelector = selectors.get(0); List<Type.Selector<T>> remainingSelectors = selectors.subList(1, selectors.size()); - for (T branchedValue : firstSelector.getEntries().values()) { - visitConfigurableAttribute(remainingSelectors, type, - currentValueSoFar == null - ? branchedValue - : type.concat(ImmutableList.of(currentValueSoFar, branchedValue)), - valuesBuilder); + + Map<Label, T> firstSelectorEntries = firstSelector.getEntries(); + Label boundKey = boundSelectorPaths.getChosenKey(firstSelectorEntries.keySet()); + if (boundKey != null) { + // If we've already followed some path from a previous selector with the same exact + // conditions as this one, we only need to visit that path (since the same key will + // match both selectors). + T boundValue = firstSelectorEntries.get(boundKey); + visitConfigurableAttribute(remainingSelectors, boundSelectorPaths, type, + currentValueSoFar == null + ? boundValue + : type.concat(ImmutableList.of(currentValueSoFar, boundValue)), + valuesBuilder); + } else { + // Otherwise, we need to iterate over all possible paths. + for (Map.Entry<Label, T> selectorBranch : firstSelectorEntries.entrySet()) { + // Bind this particular path for later selectors using the same conditions. + boundSelectorPaths.bind(firstSelectorEntries.keySet(), selectorBranch.getKey()); + visitConfigurableAttribute(remainingSelectors, boundSelectorPaths, type, + currentValueSoFar == null + ? selectorBranch.getValue() + : type.concat(ImmutableList.of(currentValueSoFar, selectorBranch.getValue())), + valuesBuilder); + // Unbind the path (so when we pop back up the recursive stack we can rebind it to new + // values if we visit this selector again). + boundSelectorPaths.unbind(firstSelectorEntries.keySet()); + } } } } /** + * Helper class for {@link #visitConfigurableAttribute}. See that method's comments for more + * details. + */ + private static class BoundSelectorPaths { + private final Map<Set<Label>, Label> bindings = new HashMap<>(); + + /** + * Binds the given config key set to the specified path. There should be no previous binding + * for this key set. + */ + public void bind(Set<Label> allKeys, Label chosenKey) { + Preconditions.checkState(allKeys.contains(chosenKey)); + Verify.verify(bindings.put(allKeys, chosenKey) == null); + } + + /** + * Unbinds the given config key set. + */ + public void unbind(Set<Label> allKeys) { + Verify.verifyNotNull(bindings.remove(allKeys)); + } + + /** + * Returns the key this config key set is bound to or null if no binding. + */ + public Label getChosenKey(Set<Label> allKeys) { + return bindings.get(allKeys); + } + } + + /** * Given (possibly configurable) attributes that a computed default depends on, creates an * {attrName -> attrValue} map for every possible combination of those attribute values and * returns a list of all the maps. This defines the complete dependency space that can affect diff --git a/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java b/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java index e894939f62..230e55e216 100644 --- a/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java +++ b/src/test/java/com/google/devtools/build/lib/analysis/select/AggregatingAttributeMapperTest.java @@ -89,6 +89,25 @@ public class AggregatingAttributeMapperTest extends AbstractAttributeMapperTest } /** + * Given a large number of selects, we expect better than the naive + * exponential performance from evaluating select1 x select2 x select3 x ... + */ + public void testGetPossibleValuesWithManySelects() throws Exception { + String pattern = " + select({'//conditions:a1': '%c', '//conditions:a2': '%s'})"; + StringBuilder ruleDef = new StringBuilder(); + ruleDef.append("genrule(name = 'gen', srcs = [], outs = ['gen.out'], cmd = ''"); + for (char c : "abcdefghijklmnopqrstuvwxyz".toCharArray()) { + ruleDef.append(String.format(pattern, c, Character.toUpperCase(c))); + } + ruleDef.append(")"); + Rule rule = createRule("a", "gen", ruleDef.toString()); + assertSameContents( + ImmutableList.of("abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"), + // Naive evaluation would visit 2^26 cases and either overflow memory or timeout the test. + AggregatingAttributeMapper.of(rule).visitAttribute("cmd", Type.STRING)); + } + + /** * Tests that, on rule visitation, {@link AggregatingAttributeMapper} visits *every* possible * value in a configurable attribute (including configuration key labels). */ |