Cache MatchCache results for all changes
Since walking changes ends up repeating many matches for the same
changes, store the results for all change matches instead of throwing
them away when moving to a new change. Although this change ends up
storing significantly more results, the space needs of this change
should not grow unreasonably. The approximate growth should be by the
size of a HashMap by query Strings populated with an Integer to point to
the results, plus a pointer to two bits sets per query, plus
approximately 2 bits per change (in the worse case) due to the space
efficient BitMap based Table used to store these results.
In a massive real world case where there are likely around 34K changes
and approximately max 6K query results per change (2K tasks * 3
queries). The extra storage for the HashMap likely works out likely
around at least 1.6MB + the size of the query Strings, i.e. likely less
than 34MB. The Pointers to the BitMaps will likely use around 6K queries
* 16B = 96K. And finally, an additional 8K for the result BitMaps. This
likely adds up to around 36MB for a status:open --task--aplicable query.
This should give a good enough picture to show that this should not have
a serious impact on memory, and testing confirms that is the case.
In the sample walking ancestors this caching saves a small but
measurable amount of the total time. In the case of a task.config which
walks all dependencies for a change when run with status:open --no-limit
--task--applicable the gain can be seen below.
Before this change: 4m18s 4m4s 4m37s 3m56s 4m5s
After this change: 3m37s 3m34s 4m6s 6m23s 3m42s
Change-Id: I5b2d2b948e30a2f410be3a400522b9d3db045518
diff --git a/src/main/java/com/google/gerrit/common/BooleanTable.java b/src/main/java/com/google/gerrit/common/BooleanTable.java
new file mode 100644
index 0000000..9e89eb9
--- /dev/null
+++ b/src/main/java/com/google/gerrit/common/BooleanTable.java
@@ -0,0 +1,69 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.common;
+
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * A space efficient Table for Booleans. This Table takes advantage of the fact that the values
+ * stored in it are all Booleans and uses BitSets to make this very space efficient.
+ */
+public class BooleanTable<R, C> {
+ protected class Row {
+ public final BitSet hasValues = new BitSet();
+ public final BitSet values = new BitSet();
+
+ public void setPosition(int position, Boolean value) {
+ if (value != null) {
+ values.set(position, value);
+ }
+ hasValues.set(position, value != null);
+ }
+
+ public Boolean getPosition(int position) {
+ if (hasValues.get(position)) {
+ return values.get(position);
+ }
+ return null;
+ }
+ }
+
+ protected Map<R, Row> rowByRow = new HashMap<>();
+ protected Map<C, Integer> positionByColumn = new HashMap<>();
+ protected int highestPosition = -1;
+
+ public void put(R r, C c, Boolean v) {
+ Row row = rowByRow.computeIfAbsent(r, k -> new Row());
+ Integer columnPosition = positionByColumn.computeIfAbsent(c, k -> nextPosition());
+ row.setPosition(columnPosition, v);
+ }
+
+ protected int nextPosition() {
+ return ++highestPosition;
+ }
+
+ public Boolean get(R r, C c) {
+ Row row = rowByRow.get(r);
+ if (row != null) {
+ Integer columnPosition = positionByColumn.get(c);
+ if (columnPosition != null) {
+ return row.getPosition(columnPosition);
+ }
+ }
+ return null;
+ }
+}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/HitBooleanTable.java b/src/main/java/com/googlesource/gerrit/plugins/task/HitBooleanTable.java
new file mode 100644
index 0000000..8271fb9
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/HitBooleanTable.java
@@ -0,0 +1,70 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.googlesource.gerrit.plugins.task;
+
+import com.google.gerrit.common.BooleanTable;
+
+/**
+ * A space efficient Table for Booleans. This Table takes advantage of the fact that the values
+ * stored in it are all Booleans and uses BitSets to make this very space efficient.
+ */
+public class HitBooleanTable<R, C> extends BooleanTable<R, C> implements TracksStatistics {
+ public static class Statistics {
+ public long hits;
+ public long misses;
+ public long size;
+ public int numberOfRows;
+ public int numberOfColumns;
+ }
+
+ protected Statistics statistics;
+
+ @Override
+ public Boolean get(R r, C c) {
+ Boolean value = super.get(r, c);
+ if (statistics != null) {
+ if (value != null) {
+ statistics.hits++;
+ } else {
+ statistics.misses++;
+ }
+ }
+ return value;
+ }
+
+ @Override
+ public void initStatistics() {
+ statistics = new Statistics();
+ }
+
+ @Override
+ public void ensureStatistics() {
+ if (statistics == null) {
+ initStatistics();
+ }
+ }
+
+ @Override
+ public Object getStatistics() {
+ statistics.numberOfRows = rowByRow.size();
+ statistics.numberOfColumns = positionByColumn.size();
+ statistics.size =
+ rowByRow.values().stream()
+ .map(r -> (long) r.hasValues.size() + (long) r.values.size())
+ .mapToLong(Long::longValue)
+ .sum();
+ return statistics;
+ }
+}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/MatchCache.java b/src/main/java/com/googlesource/gerrit/plugins/task/MatchCache.java
index ef5af15..7bdb95d 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/MatchCache.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/MatchCache.java
@@ -14,47 +14,53 @@
package com.googlesource.gerrit.plugins.task;
+import com.google.gerrit.entities.Change;
import com.google.gerrit.exceptions.StorageException;
import com.google.gerrit.index.query.QueryParseException;
import com.google.gerrit.server.query.change.ChangeData;
-import java.util.HashMap;
-import java.util.Map;
public class MatchCache {
+ protected final HitBooleanTable<String, Change.Id> resultByChangeByQuery =
+ new HitBooleanTable<>();
protected final PredicateCache predicateCache;
- protected final ChangeData changeData;
- protected final Map<String, Boolean> matchResultByQuery = new HashMap<>();
-
- public MatchCache(PredicateCache predicateCache, ChangeData changeData) {
+ public MatchCache(PredicateCache predicateCache) {
this.predicateCache = predicateCache;
- this.changeData = changeData;
}
- public boolean match(String query) throws StorageException, QueryParseException {
+ public boolean match(ChangeData changeData, String query)
+ throws StorageException, QueryParseException {
if (query == null) {
return true;
}
- Boolean isMatched = matchResultByQuery.get(query);
+ Boolean isMatched = resultByChangeByQuery.get(query, changeData.getId());
if (isMatched == null) {
isMatched = predicateCache.matchWithExceptions(changeData, query);
- matchResultByQuery.put(query, isMatched);
+ resultByChangeByQuery.put(query, changeData.getId(), isMatched);
}
return isMatched;
}
- public Boolean matchOrNull(String query) {
+ public Boolean matchOrNull(ChangeData changeData, String query) {
if (query == null) {
return null;
}
- Boolean isMatched = matchResultByQuery.get(query);
+ Boolean isMatched = resultByChangeByQuery.get(query, changeData.getId());
if (isMatched == null) {
try {
isMatched = predicateCache.matchWithExceptions(changeData, query);
} catch (QueryParseException | RuntimeException e) {
}
- matchResultByQuery.put(query, isMatched);
+ resultByChangeByQuery.put(query, changeData.getId(), isMatched);
}
return isMatched;
}
+
+ public void initStatistics() {
+ resultByChangeByQuery.initStatistics();
+ }
+
+ public Object getStatistics() {
+ return resultByChangeByQuery.getStatistics();
+ }
}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/TaskAttributeFactory.java b/src/main/java/com/googlesource/gerrit/plugins/task/TaskAttributeFactory.java
index 2821123..ec73199 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/TaskAttributeFactory.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/TaskAttributeFactory.java
@@ -57,6 +57,7 @@
public long numberOfNodes;
public long numberOfTaskPluginAttributes;
public Object predicateCache;
+ public Object matchCache;
public Preloader.Statistics preloader;
public TaskTree.Statistics treeCaches;
}
@@ -124,14 +125,13 @@
}
protected PluginDefinedInfo createWithExceptions(ChangeData c) {
- MatchCache matchCache = new MatchCache(definitions.predicateCache, c);
TaskPluginAttribute a = new TaskPluginAttribute();
try {
for (Node node : definitions.getRootNodes(c)) {
if (node instanceof Node.Invalid) {
a.roots.add(invalid());
} else {
- new AttributeFactory(node, matchCache).create().ifPresent(t -> a.roots.add(t));
+ new AttributeFactory(node).create().ifPresent(t -> a.roots.add(t));
}
}
} catch (ConfigInvalidException | IOException | StorageException e) {
@@ -147,13 +147,11 @@
protected class AttributeFactory {
public Node node;
- public MatchCache matchCache;
protected Task task;
protected TaskAttribute attribute;
- protected AttributeFactory(Node node, MatchCache matchCache) {
+ protected AttributeFactory(Node node) {
this.node = node;
- this.matchCache = matchCache;
this.task = node.task;
attribute = new TaskAttribute(task.name());
if (options.includeStatistics) {
@@ -174,7 +172,7 @@
attribute.evaluationMilliSeconds = millis();
}
- boolean applicable = matchCache.match(task.applicable);
+ boolean applicable = node.match(task.applicable);
if (!task.isVisible) {
if (!node.isTrusted() || (!applicable && !options.onlyApplicable)) {
return Optional.of(unknown());
@@ -204,7 +202,7 @@
}
if (!node.isDuplicate) {
if (task.inProgress != null) {
- attribute.inProgress = matchCache.matchOrNull(task.inProgress);
+ attribute.inProgress = node.matchOrNull(task.inProgress);
}
attribute.exported = task.exported.isEmpty() ? null : task.exported;
}
@@ -263,7 +261,7 @@
}
if (task.fail != null) {
- if (matchCache.match(task.fail)) {
+ if (node.match(task.fail)) {
// A FAIL definition is meant to be a hard blocking criteria
// (like a CodeReview -2). Thus, if hard blocked, it is
// irrelevant what the subtask states, or the PASS criteria are.
@@ -290,7 +288,7 @@
return Status.WAITING;
}
- if (task.pass != null && !matchCache.match(task.pass)) {
+ if (task.pass != null && !node.match(task.pass)) {
// Non-leaf tasks with no PASS criteria are supported in order
// to support "grouping tasks" (tasks with no function aside from
// organizing tasks). A task without a PASS criteria, cannot ever
@@ -315,15 +313,11 @@
throws ConfigInvalidException, IOException, StorageException {
List<TaskAttribute> subTasks = new ArrayList<>();
for (Node subNode :
- options.onlyApplicable ? node.getSubNodes(matchCache) : node.getSubNodes()) {
+ options.onlyApplicable ? node.getApplicableSubNodes() : node.getSubNodes()) {
if (subNode instanceof Node.Invalid) {
subTasks.add(invalid());
} else {
- MatchCache subMatchCache = matchCache;
- if (!matchCache.changeData.getId().equals(subNode.getChangeData().getId())) {
- subMatchCache = new MatchCache(definitions.predicateCache, subNode.getChangeData());
- }
- new AttributeFactory(subNode, subMatchCache).create().ifPresent(t -> subTasks.add(t));
+ new AttributeFactory(subNode).create().ifPresent(t -> subTasks.add(t));
}
}
if (subTasks.isEmpty()) {
@@ -334,9 +328,9 @@
protected boolean isValidQueries() {
try {
- matchCache.match(task.inProgress);
- matchCache.match(task.fail);
- matchCache.match(task.pass);
+ node.match(task.inProgress);
+ node.match(task.fail);
+ node.match(task.pass);
return true;
} catch (QueryParseException | RuntimeException e) {
return false;
@@ -352,6 +346,7 @@
if (options.includeStatistics) {
statistics = new Statistics();
definitions.predicateCache.initStatistics();
+ definitions.matchCache.initStatistics();
definitions.preloader.initStatistics();
definitions.initStatistics();
}
@@ -363,6 +358,7 @@
statistics.numberOfTaskPluginAttributes =
pluginInfosByChange.values().stream().filter(tpa -> tpa != null).count();
statistics.predicateCache = definitions.predicateCache.getStatistics();
+ statistics.matchCache = definitions.matchCache.getStatistics();
statistics.preloader = definitions.preloader.getStatistics();
statistics.treeCaches = definitions.getStatistics();
}
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/TaskTree.java b/src/main/java/com/googlesource/gerrit/plugins/task/TaskTree.java
index 2b89f90..bbca661 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/TaskTree.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/TaskTree.java
@@ -79,6 +79,7 @@
protected final AllUsersNameProvider allUsers;
protected final CurrentUser user;
protected final PredicateCache predicateCache;
+ protected final MatchCache matchCache;
protected final Preloader preloader;
protected final NodeList root = new NodeList();
protected final Provider<ChangeQueryBuilder> changeQueryBuilderProvider;
@@ -109,6 +110,7 @@
this.changeQueryProcessorProvider = changeQueryProcessorProvider;
this.changeQueryBuilderProvider = changeQueryBuilderProvider;
this.predicateCache = predicateCache;
+ this.matchCache = new MatchCache(predicateCache);
this.preloader = preloader;
}
@@ -272,12 +274,12 @@
return nodes;
}
- public List<Node> getSubNodes(MatchCache matchCache)
+ public List<Node> getApplicableSubNodes()
throws ConfigInvalidException, IOException, StorageException {
if (hasUnfilterableSubNodes) {
return getSubNodes();
}
- return new ApplicableNodeFilter(matchCache).getSubNodes();
+ return new ApplicableNodeFilter().getSubNodes();
}
@Override
@@ -332,6 +334,14 @@
return false;
}
+ public boolean match(String query) throws StorageException, QueryParseException {
+ return matchCache.match(getChangeData(), query);
+ }
+
+ public Boolean matchOrNull(String query) {
+ return matchCache.matchOrNull(getChangeData(), query);
+ }
+
protected class SubNodeAdder {
protected List<Node> nodes = new ArrayList<>();
protected SubNodeFactory factory = new SubNodeFactory();
@@ -457,18 +467,12 @@
}
public class ApplicableNodeFilter {
- protected MatchCache matchCache;
- protected PredicateCache pcache;
protected BranchNameKey branch = getChangeData().change().getDest();
protected SubSectionKey subSection = task.key.subSection();
protected Map<BranchNameKey, List<Task>> definitionsByBranch =
definitionsByBranchBySubSection.get(subSection);
- public ApplicableNodeFilter(MatchCache matchCache)
- throws ConfigInvalidException, IOException, StorageException {
- this.matchCache = matchCache;
- this.pcache = matchCache.predicateCache;
- }
+ public ApplicableNodeFilter() throws ConfigInvalidException, IOException, StorageException {}
public List<Node> getSubNodes() throws ConfigInvalidException, IOException, StorageException {
if (nodesByBranch != null) {
@@ -527,7 +531,7 @@
} else if (isApplicableCacheableByBranch(node)) {
filterable++;
try {
- if (!matchCache.match(node.task.applicable)) {
+ if (!node.match(node.task.applicable)) {
// Correctness will not be affected if more nodes are added than necessary
// (i.e. if isApplicableCacheableByBranch() does not realize a Node is cacheable
// based on its Branch), but it is incorrect to filter out a Node now that could
@@ -551,7 +555,7 @@
return false;
}
try {
- return pcache.isCacheableByBranch(applicable);
+ return predicateCache.isCacheableByBranch(applicable);
} catch (QueryParseException e) {
return false;
}
diff --git a/src/test/java/com/google/gerrit/common/BooleanTableTest.java b/src/test/java/com/google/gerrit/common/BooleanTableTest.java
new file mode 100644
index 0000000..746a0e9
--- /dev/null
+++ b/src/test/java/com/google/gerrit/common/BooleanTableTest.java
@@ -0,0 +1,81 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.common;
+
+import junit.framework.TestCase;
+
+public class BooleanTableTest extends TestCase {
+
+ public void testNulls() {
+ BooleanTable<String, String> cbt = new BooleanTable<>();
+ assertNull(cbt.get("r1", "c1"));
+ assertNull(cbt.get("r0", "c0"));
+
+ cbt.put("r1", "c0", true);
+ assertNull(cbt.get("r1", "c1"));
+ assertNull(cbt.get("r0", "c0"));
+
+ cbt.put("r0", "c1", true);
+ assertNull(cbt.get("r1", "c1"));
+ assertNull(cbt.get("r0", "c0"));
+ }
+
+ public void testRowColumn() {
+ BooleanTable<String, String> cbt = new BooleanTable<>();
+ cbt.put("r1", "c1", true);
+ cbt.put("r2", "c2", false);
+ assertTrue(cbt.get("r1", "c1"));
+ assertNull(cbt.get("r1", "c2"));
+ assertNull(cbt.get("r2", "c1"));
+ assertFalse(cbt.get("r2", "c2"));
+ }
+
+ public void testRowColumnOverride() {
+ BooleanTable<String, String> cbt = new BooleanTable<>();
+ cbt.put("r1", "c1", true);
+ assertTrue(cbt.get("r1", "c1"));
+
+ cbt.put("r1", "c1", false);
+ assertFalse(cbt.get("r1", "c1"));
+ }
+
+ public void testRepeatedColumns() {
+ BooleanTable<String, String> cbt = new BooleanTable<>();
+ cbt.put("r1", "c1", true);
+ cbt.put("r2", "c1", false);
+ assertTrue(cbt.get("r1", "c1"));
+ assertFalse(cbt.get("r2", "c1"));
+ }
+
+ public void testRepeatedRows() {
+ BooleanTable<String, String> cbt = new BooleanTable<>();
+ cbt.put("r1", "c1", true);
+ cbt.put("r1", "c2", false);
+ assertTrue(cbt.get("r1", "c1"));
+ assertFalse(cbt.get("r1", "c2"));
+ }
+
+ public void testRepeatedRowsAndColumns() {
+ BooleanTable<String, String> cbt = new BooleanTable<>();
+ cbt.put("r1", "c1", true);
+ cbt.put("r2", "c1", false);
+ cbt.put("r1", "c2", true);
+ cbt.put("r2", "c2", false);
+ assertTrue(cbt.get("r1", "c1"));
+ assertFalse(cbt.get("r2", "c1"));
+ assertTrue(cbt.get("r1", "c2"));
+ assertFalse(cbt.get("r2", "c2"));
+ }
+}
