Slight improvements to ArraySet.
1. There are cases where valueAt could return null even though the given
index was out of bounds. I've added a check for that in the code.
2. The default implementation of Collection.removeIf() uses the
iterator(). This change avoids that since the iterator is an inefficient
way to access the array contents.
Benchmark tests. Note that these times are in nanoseconds:
Before:
INSTRUMENTATION_STATUS: removeIf_Small_Base_mean=163679
INSTRUMENTATION_STATUS: removeIf_Small_Base_median=158215
INSTRUMENTATION_STATUS: removeIf_Small_Base_min=129564
INSTRUMENTATION_STATUS: removeIf_Small_Base_standardDeviation=24779
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_mean=5645195
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_median=5584964
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_min=5448560
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_standardDeviation=206915
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_mean=1316514
INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_median=1282442
INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_min=1216533
INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_standardDeviation=109087
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_Base_mean=571712
INSTRUMENTATION_STATUS: removeIf_Large_Base_median=566500
INSTRUMENTATION_STATUS: removeIf_Large_Base_min=535726
INSTRUMENTATION_STATUS: removeIf_Large_Base_standardDeviation=26374
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_mean=946
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_median=896
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_min=841
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_standardDeviation=106
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_mean=2196954
INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_median=2163910
INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_min=2136283
INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_standardDeviation=91149
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_mean=356644
INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_median=350376
INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_min=337067
INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_standardDeviation=17354
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_mean=1044645
INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_median=1040981
INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_min=1010144
INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_standardDeviation=35016
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_mean=507561
INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_median=503419
INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_min=471564
INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_standardDeviation=33141
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_mean=300889
INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_median=295486
INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_min=282948
INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_standardDeviation=19869
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: valueAt_InBounds_mean=644
INSTRUMENTATION_STATUS: valueAt_InBounds_median=584
INSTRUMENTATION_STATUS: valueAt_InBounds_min=528
INSTRUMENTATION_STATUS: valueAt_InBounds_standardDeviation=141
INSTRUMENTATION_STATUS_CODE: -1
After:
INSTRUMENTATION_STATUS: removeIf_Small_Base_mean=143926
INSTRUMENTATION_STATUS: removeIf_Small_Base_median=145985
INSTRUMENTATION_STATUS: removeIf_Small_Base_min=125700
INSTRUMENTATION_STATUS: removeIf_Small_Base_standardDeviation=11112
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_mean=5173581
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_median=5168995
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_min=5108405
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_Negative_standardDeviation=45739
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_mean=695812
INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_median=690070
INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_min=679793
INSTRUMENTATION_STATUS: removeIf_Large_RemoveHalf_standardDeviation=17959
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_Base_mean=591815
INSTRUMENTATION_STATUS: removeIf_Large_Base_median=588499
INSTRUMENTATION_STATUS: removeIf_Large_Base_min=573707
INSTRUMENTATION_STATUS: removeIf_Large_Base_standardDeviation=14348
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_mean=4010666
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_median=4017245
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_min=3970170
INSTRUMENTATION_STATUS: valueAt_OutOfBounds_EdgeCase_standardDeviation=28577
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_mean=734297
INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_median=732576
INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_min=720065
INSTRUMENTATION_STATUS: removeIf_Large_RemoveAll_standardDeviation=14906
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_mean=195026
INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_median=194430
INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_min=190400
INSTRUMENTATION_STATUS: removeIf_Small_RemoveHalf_standardDeviation=4012
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_mean=772914
INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_median=785834
INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_min=737947
INSTRUMENTATION_STATUS: removeIf_Large_RemoveNothing_standardDeviation=23808
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_mean=194325
INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_median=196492
INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_min=186998
INSTRUMENTATION_STATUS: removeIf_Small_RemoveAll_standardDeviation=5091
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_mean=187122
INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_median=187292
INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_min=182272
INSTRUMENTATION_STATUS: removeIf_Small_RemoveNothing_standardDeviation=4902
INSTRUMENTATION_STATUS_CODE: -1
.INSTRUMENTATION_STATUS: valueAt_InBounds_mean=918
INSTRUMENTATION_STATUS: valueAt_InBounds_median=919
INSTRUMENTATION_STATUS: valueAt_InBounds_min=801
INSTRUMENTATION_STATUS: valueAt_InBounds_standardDeviation=80
INSTRUMENTATION_STATUS_CODE: -1
Perf test command:
mmma -j ./frameworks/base/apct-tests/perftests/core/;
adb install -r $OUT/data/app/CorePerfTests/CorePerfTests.apk;
adb shell cmd package compile -m speed -f com.android.perftests.core;
adb shell am instrument -w -e class android.util.ArraySetPerfTest com.android.perftests.core/android.support.test.runner.AndroidJUnitRunner
Bug: 118339123
Bug: 117846754
Test: atest android.util.cts.ArraySetTest
and benchmark tests (see above)
Change-Id: Ic4b10fd2bbc7a745ca4e4029ca4829847812fabe
diff --git a/apct-tests/perftests/core/src/android/util/ArraySetPerfTest.java b/apct-tests/perftests/core/src/android/util/ArraySetPerfTest.java
new file mode 100644
index 0000000..0c1f289
--- /dev/null
+++ b/apct-tests/perftests/core/src/android/util/ArraySetPerfTest.java
@@ -0,0 +1,212 @@
+/*
+ * Copyright (C) 2018 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 android.util;
+
+import android.perftests.utils.BenchmarkState;
+import android.perftests.utils.PerfStatusReporter;
+import android.support.test.filters.LargeTest;
+import android.support.test.runner.AndroidJUnit4;
+
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.util.function.Predicate;
+
+@RunWith(AndroidJUnit4.class)
+@LargeTest
+public class ArraySetPerfTest {
+ private static final int NUM_ITERATIONS = 100;
+ private static final int SET_SIZE_SMALL = 10;
+ private static final int SET_SIZE_LARGE = 50;
+
+ @Rule
+ public PerfStatusReporter mPerfStatusReporter = new PerfStatusReporter();
+
+ @Test
+ public void testValueAt_InBounds() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ ArraySet<Integer> set = new ArraySet<>();
+ set.add(0);
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ set.valueAt(0);
+ }
+ }
+ }
+
+ @Test
+ public void testValueAt_OutOfBounds_Negative() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ ArraySet<Integer> set = new ArraySet<>();
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ try {
+ set.valueAt(-1);
+ } catch (ArrayIndexOutOfBoundsException expected) {
+ // expected
+ }
+ }
+ }
+ }
+
+ /**
+ * Tests the case where ArraySet could index into its array even though the index is out of
+ * bounds.
+ */
+ @Test
+ public void testValueAt_OutOfBounds_EdgeCase() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ ArraySet<Integer> set = new ArraySet<>();
+ set.add(0);
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ try {
+ set.valueAt(1);
+ } catch (ArrayIndexOutOfBoundsException expected) {
+ // expected
+ }
+ }
+ }
+ }
+
+ /**
+ * This is the same code as testRemoveIf_Small_* without the removeIf in order to measure
+ * the performance of the rest of the code in the loop.
+ */
+ @Test
+ public void testRemoveIf_Small_Base() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> i % 2 == 0;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_SMALL; ++j) {
+ set.add(j);
+ }
+ }
+ }
+ }
+
+ @Test
+ public void testRemoveIf_Small_RemoveNothing() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> false;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_SMALL; ++j) {
+ set.add(j);
+ }
+ set.removeIf(predicate);
+ }
+ }
+ }
+
+ @Test
+ public void testRemoveIf_Small_RemoveAll() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> true;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_SMALL; j++) {
+ set.add(j);
+ }
+ set.removeIf(predicate);
+ }
+ }
+ }
+
+ @Test
+ public void testRemoveIf_Small_RemoveHalf() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> i % 2 == 0;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_SMALL; ++j) {
+ set.add(j);
+ }
+ set.removeIf(predicate);
+ }
+ }
+ }
+
+ /**
+ * This is the same code as testRemoveIf_Large_* without the removeIf in order to measure
+ * the performance of the rest of the code in the loop.
+ */
+ @Test
+ public void testRemoveIf_Large_Base() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> i % 2 == 0;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+ set.add(j);
+ }
+ }
+ }
+ }
+
+ @Test
+ public void testRemoveIf_Large_RemoveNothing() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> false;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+ set.add(j);
+ }
+ set.removeIf(predicate);
+ }
+ }
+ }
+
+ @Test
+ public void testRemoveIf_Large_RemoveAll() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> true;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+ set.add(j);
+ }
+ set.removeIf(predicate);
+ }
+ }
+ }
+
+ @Test
+ public void testRemoveIf_Large_RemoveHalf() {
+ BenchmarkState state = mPerfStatusReporter.getBenchmarkState();
+ Predicate<Integer> predicate = (i) -> i % 2 == 0;
+ while (state.keepRunning()) {
+ for (int i = 0; i < NUM_ITERATIONS; ++i) {
+ ArraySet<Integer> set = new ArraySet<>();
+ for (int j = 0; j < SET_SIZE_LARGE; ++j) {
+ set.add(j);
+ }
+ set.removeIf(predicate);
+ }
+ }
+ }
+}
diff --git a/api/test-current.txt b/api/test-current.txt
index 463c9d3..e4fc552 100644
--- a/api/test-current.txt
+++ b/api/test-current.txt
@@ -1320,6 +1320,14 @@
}
+package android.util {
+
+ public final class ArraySet<E> implements java.util.Collection java.util.Set {
+ method public E valueAtUnchecked(int);
+ }
+
+}
+
package android.util.proto {
public final class EncodedBuffer {
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index d74a0fe..4bd43d0 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -16,14 +16,17 @@
package android.util;
+import android.annotation.TestApi;
+import android.annotation.UnsupportedAppUsage;
+
import libcore.util.EmptyArray;
-import android.annotation.UnsupportedAppUsage;
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
+import java.util.function.Predicate;
/**
* ArraySet is a generic set data structure that is designed to be more memory efficient than a
@@ -357,6 +360,22 @@
* @return Returns the value stored at the given index.
*/
public E valueAt(int index) {
+ if (index >= mSize) {
+ // The array might be slightly bigger than mSize, in which case, indexing won't fail.
+ throw new ArrayIndexOutOfBoundsException(index);
+ }
+ return valueAtUnchecked(index);
+ }
+
+ /**
+ * Returns the value at the given index in the array without checking that the index is within
+ * bounds. This allows testing values at the end of the internal array, outside of the
+ * [0, mSize) bounds.
+ *
+ * @hide
+ */
+ @TestApi
+ public E valueAtUnchecked(int index) {
return (E) mArray[index];
}
@@ -491,26 +510,40 @@
return false;
}
+ /** Returns true if the array size should be decreased. */
+ private boolean shouldShrink() {
+ return mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3;
+ }
+
+ /**
+ * Returns the new size the array should have. Is only valid if {@link #shouldShrink} returns
+ * true.
+ */
+ private int getNewShrunkenSize() {
+ // We don't allow it to shrink smaller than (BASE_SIZE*2) to avoid flapping between that
+ // and BASE_SIZE.
+ return mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);
+ }
+
/**
* Remove the key/value mapping at the given index.
* @param index The desired index, must be between 0 and {@link #size()}-1.
* @return Returns the value that was stored at this index.
*/
public E removeAt(int index) {
+ if (index >= mSize) {
+ // The array might be slightly bigger than mSize, in which case, indexing won't fail.
+ throw new ArrayIndexOutOfBoundsException(index);
+ }
final Object old = mArray[index];
if (mSize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
- freeArrays(mHashes, mArray, mSize);
- mHashes = EmptyArray.INT;
- mArray = EmptyArray.OBJECT;
- mSize = 0;
+ clear();
} else {
- if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3) {
- // Shrunk enough to reduce size of arrays. We don't allow it to
- // shrink smaller than (BASE_SIZE*2) to avoid flapping between
- // that and BASE_SIZE.
- final int n = mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);
+ if (shouldShrink()) {
+ // Shrunk enough to reduce size of arrays.
+ final int n = getNewShrunkenSize();
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
@@ -568,6 +601,62 @@
}
/**
+ * Removes all values that satisfy the predicate. This implementation avoids using the
+ * {@link #iterator()}.
+ *
+ * @param filter A predicate which returns true for elements to be removed
+ */
+ @Override
+ public boolean removeIf(Predicate<? super E> filter) {
+ if (mSize == 0) {
+ return false;
+ }
+
+ // Intentionally not using removeAt() to avoid unnecessary intermediate resizing.
+
+ int replaceIndex = 0;
+ int numRemoved = 0;
+ for (int i = 0; i < mSize; ++i) {
+ if (filter.test((E) mArray[i])) {
+ numRemoved++;
+ } else {
+ if (replaceIndex != i) {
+ mArray[replaceIndex] = mArray[i];
+ mHashes[replaceIndex] = mHashes[i];
+ }
+ replaceIndex++;
+ }
+ }
+
+ if (numRemoved == 0) {
+ return false;
+ } else if (numRemoved == mSize) {
+ clear();
+ return true;
+ }
+
+ mSize -= numRemoved;
+ if (shouldShrink()) {
+ // Shrunk enough to reduce size of arrays.
+ final int n = getNewShrunkenSize();
+ final int[] ohashes = mHashes;
+ final Object[] oarray = mArray;
+ allocArrays(n);
+
+ System.arraycopy(ohashes, 0, mHashes, 0, mSize);
+ System.arraycopy(oarray, 0, mArray, 0, mSize);
+ } else {
+ // Null out values at the end of the array. Not doing it in the loop above to avoid
+ // writing twice to the same index or writing unnecessarily if the array would have been
+ // discarded anyway.
+ for (int i = mSize; i < mArray.length; ++i) {
+ mArray[i] = null;
+ }
+ }
+ return true;
+ }
+
+ /**
* Return the number of items in this array map.
*/
@Override