tree 7c0143d868e682feb6e0fe2a53a2b408c451ef79
parent 9b882d88ee900feb056c25f332966c0d6088cc06
author Kweku Adams <kwekua@google.com> 1540428934 -0700
committer Kweku Adams <kwekua@google.com> 1541119175 -0700

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