Add a TopKeyMap to HitHashMap statistics
A TopKeyMap is a lightweight limited size (5) map with 'long' keys
designed to store only the elements with the top five largest keys. Use
the TopKeyMap in the HitHashMap to track the keys of the elements which
took the longest to load using the StopWatch. Modify all the HitHashMap
users to use the new API and thus benefit from these new statistics.
Change-Id: I19ed563bf6d81f0d72b14906edd676712b8973fe
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMap.java b/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMap.java
index 82cedf7..433b091 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMap.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMap.java
@@ -23,16 +23,17 @@
import java.util.function.Function;
public class HitHashMap<K, V> extends HashMap<K, V> implements StatisticsMap<K, V> {
- public static class Statistics {
+ public static class Statistics<K> {
public long hits;
public int size;
public Long sumNanosecondsLoading;
+ public TopKeyMap<K> topNanosecondsLoadingKeys = new TopKeyMap<>();
public List<Object> elements;
}
public static final long serialVersionUID = 1;
- protected Statistics statistics;
+ protected Statistics<K> statistics;
public HitHashMap() {}
@@ -75,10 +76,11 @@
@Override
@SuppressWarnings("try")
- public V computeIfAbsentTimed(K key, Function<? super K, ? extends V> mappingFunction) {
+ public V computeIfAbsentTimed(
+ K key, Function<? super K, ? extends V> mappingFunction, boolean isVisible) {
V v = get(key);
if (v == null) {
- try (StopWatch stopWatch = createLoadingStopWatch()) {
+ try (StopWatch stopWatch = createLoadingStopWatch(key, isVisible)) {
v = mappingFunction.apply(key);
}
if (v != null) {
@@ -143,7 +145,7 @@
@Override
public void initStatistics() {
- statistics = new Statistics();
+ statistics = new Statistics<>();
}
@Override
@@ -153,14 +155,21 @@
}
}
- public StopWatch createLoadingStopWatch() {
+ public StopWatch createLoadingStopWatch(K key, boolean isVisible) {
if (statistics == null) {
return StopWatch.DISABLED;
}
if (statistics.sumNanosecondsLoading == null) {
statistics.sumNanosecondsLoading = 0L;
}
- return new StopWatch.Enabled().setNanosConsumer(ns -> statistics.sumNanosecondsLoading += ns);
+ return new StopWatch.Enabled()
+ .setNanosConsumer(
+ ns -> statistics.sumNanosecondsLoading += updateTopLoadingTimes(ns, key, isVisible));
+ }
+
+ public long updateTopLoadingTimes(long nanos, K key, boolean isVisible) {
+ statistics.topNanosecondsLoadingKeys.addIfTop(nanos, isVisible ? key : null);
+ return nanos;
}
@Override
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMapOfCollection.java b/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMapOfCollection.java
index 422418b..82d04fc 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMapOfCollection.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/HitHashMapOfCollection.java
@@ -22,14 +22,14 @@
import java.util.List;
public class HitHashMapOfCollection<K, V extends Collection<?>> extends HitHashMap<K, V> {
- public static class Statistics extends HitHashMap.Statistics {
+ public static class Statistics<K> extends HitHashMap.Statistics<K> {
public List<Integer> top5CollectionSizes;
public List<Integer> bottom5CollectionSizes;
}
public static final long serialVersionUID = 1;
- protected Statistics statistics;
+ protected Statistics<K> statistics;
public HitHashMapOfCollection() {}
@@ -42,7 +42,7 @@
@Override
public void initStatistics() {
super.initStatistics();
- statistics = new Statistics();
+ statistics = new Statistics<>();
}
@Override
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 b1dcda5..c7f7e41 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/MatchCache.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/MatchCache.java
@@ -29,23 +29,23 @@
this.predicateCache = predicateCache;
}
- public Boolean matchOrNull(ChangeData changeData, String query) {
+ public Boolean matchOrNull(ChangeData changeData, String query, boolean isVisible) {
try {
- return match(changeData, query);
+ return match(changeData, query, isVisible);
} catch (StorageException | QueryParseException e) {
}
return null;
}
@SuppressWarnings("try")
- public boolean match(ChangeData changeData, String query)
+ public boolean match(ChangeData changeData, String query, boolean isVisible)
throws StorageException, QueryParseException {
if (query == null || "true".equalsIgnoreCase(query)) {
return true;
}
Boolean isMatched = resultByChangeByQuery.get(query, changeData.getId());
if (isMatched == null) {
- Matchable<ChangeData> matchable = predicateCache.getPredicate(query).asMatchable();
+ Matchable<ChangeData> matchable = predicateCache.getPredicate(query, isVisible).asMatchable();
try (StopWatch stopWatch = resultByChangeByQuery.createLoadingStopWatch()) {
isMatched = matchable.match(changeData);
resultByChangeByQuery.put(query, changeData.getId(), isMatched);
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/PredicateCache.java b/src/main/java/com/googlesource/gerrit/plugins/task/PredicateCache.java
index 39c99b4..279729e 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/PredicateCache.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/PredicateCache.java
@@ -76,14 +76,15 @@
}
@SuppressWarnings("try")
- public Predicate<ChangeData> getPredicate(String query) throws QueryParseException {
+ public Predicate<ChangeData> getPredicate(String query, boolean isVisible)
+ throws QueryParseException {
ThrowingProvider<Predicate<ChangeData>, QueryParseException> predProvider =
predicatesByQuery.get(query);
if (predProvider != null) {
return predProvider.get();
}
// never seen 'query' before
- try (StopWatch stopWatch = predicatesByQuery.createLoadingStopWatch()) {
+ try (StopWatch stopWatch = predicatesByQuery.createLoadingStopWatch(query, isVisible)) {
Predicate<ChangeData> pred = cqb.parse(query);
predicatesByQuery.put(query, new ThrowingProvider.Entry<>(pred));
return pred;
@@ -97,14 +98,14 @@
* Can this query's output be assumed to be constant given any Change destined for the same
* Branch.NameKey?
*/
- public boolean isCacheableByBranch(String query) throws QueryParseException {
+ public boolean isCacheableByBranch(String query, boolean isVisible) throws QueryParseException {
if (query == null
|| "".equals(query)
|| "false".equalsIgnoreCase(query)
|| "true".equalsIgnoreCase(query)) {
return true;
}
- return isCacheableByBranch(getPredicate(query));
+ return isCacheableByBranch(getPredicate(query, isVisible));
}
protected boolean isCacheableByBranch(Predicate<ChangeData> predicate) {
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/StatisticsMap.java b/src/main/java/com/googlesource/gerrit/plugins/task/StatisticsMap.java
index 7c401a9..9141fe9 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/StatisticsMap.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/StatisticsMap.java
@@ -18,7 +18,8 @@
import java.util.function.Function;
public interface StatisticsMap<K, V> extends Map<K, V>, TracksStatistics {
- V computeIfAbsentTimed(K key, Function<? super K, ? extends V> mappingFunction);
+ V computeIfAbsentTimed(
+ K key, Function<? super K, ? extends V> mappingFunction, boolean isVisible);
- StopWatch createLoadingStopWatch();
+ StopWatch createLoadingStopWatch(K key, boolean isVisible);
}
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 4a7d0fd..70cd039 100644
--- a/src/main/java/com/googlesource/gerrit/plugins/task/TaskTree.java
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/TaskTree.java
@@ -266,7 +266,8 @@
}
definitionsBySubSection.computeIfAbsentTimed(
task.key().subSection(),
- k -> nodes.stream().map(n -> n.getDefinition()).collect(toList()));
+ k -> nodes.stream().map(n -> n.getDefinition()).collect(toList()),
+ task.isVisible);
} else {
hasUnfilterableSubNodes = true;
cachedNodeByTask.clear();
@@ -339,11 +340,11 @@
}
public boolean match(String query) throws StorageException, QueryParseException {
- return matchCache.match(getChangeData(), query);
+ return matchCache.match(getChangeData(), query, task.isVisible);
}
public Boolean matchOrNull(String query) {
- return matchCache.matchOrNull(getChangeData(), query);
+ return matchCache.matchOrNull(getChangeData(), query, task.isVisible);
}
protected class SubNodeAdder {
@@ -431,7 +432,7 @@
throws ConfigInvalidException, IOException, StorageException {
try {
if (namesFactory.changes != null) {
- for (ChangeData changeData : query(namesFactory.changes)) {
+ for (ChangeData changeData : query(namesFactory.changes, task.isVisible)) {
addPreloaded(
preloader.preload(
task.config.new Task(tasksFactory, changeData.getId().toString())),
@@ -559,7 +560,7 @@
return false;
}
try {
- return predicateCache.isCacheableByBranch(applicable);
+ return predicateCache.isCacheableByBranch(applicable, task.isVisible);
} catch (QueryParseException e) {
return false;
}
@@ -593,10 +594,12 @@
}
@SuppressWarnings("try")
- public List<ChangeData> query(String query) throws StorageException, QueryParseException {
+ public List<ChangeData> query(String query, boolean isVisible)
+ throws StorageException, QueryParseException {
List<ChangeData> changeDataList = changesByNamesFactoryQuery.get(query);
if (changeDataList == null) {
- try (StopWatch stopWatch = changesByNamesFactoryQuery.createLoadingStopWatch()) {
+ try (StopWatch stopWatch =
+ changesByNamesFactoryQuery.createLoadingStopWatch(query, isVisible)) {
changeDataList =
changeQueryProcessorProvider
.get()
diff --git a/src/main/java/com/googlesource/gerrit/plugins/task/TopKeyMap.java b/src/main/java/com/googlesource/gerrit/plugins/task/TopKeyMap.java
new file mode 100644
index 0000000..a23d59f
--- /dev/null
+++ b/src/main/java/com/googlesource/gerrit/plugins/task/TopKeyMap.java
@@ -0,0 +1,71 @@
+// Copyright (C) 2023 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;
+
+/**
+ * A TopKeyMap is a lightweight limited size (5) map with 'long' keys designed to store only the
+ * elements with the top five largest keys.
+ *
+ * <p>A TopKeyMap is array based and has O(n) insertion time. Despite not having O(1) insertion
+ * times, it should likely be much faster than a hash based map for small n sizes. It also is more
+ * memory efficient than a hash based map, although both are likely O(n) in space usage. The
+ * TopKeyMap allocates all of its entries up front so it does not change its memory utilization at
+ * all, and it does not have to create or free any Objects during its post constructor lifespan.
+ *
+ * <p>While a TopKeyMap currently only uses 'long's as keys, it is possible to easiy upgrade this
+ * collection to use any type of Comparable key.
+ *
+ * <p>Although not currently thread safe, due to the simplicity of the data structures used, and the
+ * insertion approach, it is easy to make a TopKeyMap efficiently thread safe.
+ */
+public class TopKeyMap<V> {
+ protected class Entry {
+ public long key;
+ public V value;
+
+ protected void set(long key, V value) {
+ this.key = key;
+ this.value = value;
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ protected Entry[] entries = (Entry[]) new Object[5];
+
+ public TopKeyMap() {
+ for (int i = 0; i < entries.length; i++) {
+ entries[i] = new Entry();
+ }
+ }
+
+ public void addIfTop(long key, V value) {
+ addIfTop(0, key, value);
+ }
+
+ protected void addIfTop(int i, long key, V value) {
+ if (entries[entries.length - 1].key < key) {
+ for (; i < entries.length; i++) {
+ Entry e = entries[i];
+ if (e.key < key) {
+ long eKValue = e.key;
+ V eValue = e.value;
+ e.set(key, value);
+ addIfTop(i + 1, eKValue, eValue);
+ return;
+ }
+ }
+ }
+ }
+}
