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

1 files changed, 99 insertions, 10 deletions

diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index d74a0fe8d2c1..4bd43d05ae61 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 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
      * @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 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
         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 @@ public final class ArraySet<E> implements Collection<E>, Set<E> {
     }
 
     /**
+     * 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