New ArrayMap class.

This is a new kind of key/value mapping that stores its data
as an array, so it doesn't need to create an extra Entry object
for every mapping placed in to it.  It is also optimized to reduce
memory overhead in other ways, by keeping the base object small,
being fairly aggressive about keeping the array data structures
small, etc.

There are some unit and performance tests dropped in to some
random places; they will need to be put somewhere else once I
decided what we are going to do with this for the next release
(for example if we make it public the unit tests should go in
to CTS).

Switch IntentResolver to using ArrayMap instead of HashMap.

Also get rid of a bunch of duplicate implementations of binarySearch,
and add an optimization to the various sparse arrays where you can
supply an explicit 0 capacity to prevent it from doing an initial
array allocation; use this new optimization in a few places where it
makes sense.

Change-Id: I01ef2764680f8ae49938e2a2ed40dc01606a056b

1 files changed, 208 insertions, 0 deletions

diff --git a/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java b/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java
index 5f4f006..309ce34 100644
--- a/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java
+++ b/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java
@@ -21,7 +21,11 @@ import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
 import java.io.IOException;
 import java.io.RandomAccessFile;
+import java.lang.String;
+import java.util.HashMap;
+import java.util.Random;
 
+import android.util.ArrayMap;
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
 
@@ -142,6 +146,18 @@ public class TestService extends Service {
             new LoadRecycleLargeBitmapOp(),
             new LoadSmallScaledBitmapOp(),
             new LoadLargeScaledBitmapOp(),
+            new GrowTinyHashMapOp(),
+            new GrowTinyArrayMapOp(),
+            new GrowSmallHashMapOp(),
+            new GrowSmallArrayMapOp(),
+            new GrowLargeHashMapOp(),
+            new GrowLargeArrayMapOp(),
+            new LookupTinyHashMapOp(),
+            new LookupTinyArrayMapOp(),
+            new LookupSmallHashMapOp(),
+            new LookupSmallArrayMapOp(),
+            new LookupLargeHashMapOp(),
+            new LookupLargeArrayMapOp(),
     };
 
     static final int CMD_START_TEST = 1;
@@ -1111,4 +1127,196 @@ public class TestService extends Service {
             mFile.delete();
         }
     }
+
+    static abstract class GenericMapOp extends Op {
+        final int mSize;
+        String[] mKeys;
+        String[] mValues;
+
+        GenericMapOp(String name, String longName, int size) {
+            super(name, longName);
+            mSize = size;
+        }
+
+        void onInit(Context context, boolean foreground) {
+            mKeys = new String[mSize];
+            mValues = new String[mSize];
+            Random random = new Random(0);
+            for (int i=0; i<mSize; i++) {
+                int chars = random.nextInt(10);
+                StringBuilder builder = new StringBuilder(chars);
+                for (int j=0; j<chars; j++) {
+                    builder.append('a' + random.nextInt(100));
+                }
+                mKeys[i] = builder.toString();
+                mValues[i] = Integer.toString(i);
+            }
+        }
+
+        int getOpsPerRun() {
+            return mSize;
+        }
+    }
+
+    static class GrowTinyHashMapOp extends GenericMapOp {
+        GrowTinyHashMapOp() {
+            super("GrowTinyHashMap", "Add 5 items to a HashMap", 5);
+        }
+
+        boolean onRun() {
+            HashMap<String, String> map = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowTinyArrayMapOp extends GenericMapOp {
+        GrowTinyArrayMapOp() {
+            super("GrowTinyArrayMap", "Add 5 items to a ArrayMap", 5);
+        }
+
+        boolean onRun() {
+            ArrayMap<String, String> map = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowSmallHashMapOp extends GenericMapOp {
+        GrowSmallHashMapOp() {
+            super("GrowSmallHashMap", "Add 100 items to a HashMap", 100);
+        }
+
+        boolean onRun() {
+            HashMap<String, String> map = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowSmallArrayMapOp extends GenericMapOp {
+        GrowSmallArrayMapOp() {
+            super("GrowSmallArrayMap", "Add 100 items to a ArrayMap", 100);
+        }
+
+        boolean onRun() {
+            ArrayMap<String, String> map = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowLargeHashMapOp extends GenericMapOp {
+        GrowLargeHashMapOp() {
+            super("GrowLargeHashMap", "Add 10000 items to a HashMap", 10000);
+        }
+
+        boolean onRun() {
+            HashMap<String, String> map = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowLargeArrayMapOp extends GenericMapOp {
+        GrowLargeArrayMapOp() {
+            super("GrowLargeArrayMap", "Add 10000 items to a ArrayMap", 10000);
+        }
+
+        boolean onRun() {
+            ArrayMap<String, String> map = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class LookupTinyHashMapOp extends LookupSmallHashMapOp {
+        LookupTinyHashMapOp() {
+            super("LookupTinyHashMap", "Lookup items in 5 entry HashMap", 5);
+        }
+    }
+
+    static class LookupTinyArrayMapOp extends LookupSmallArrayMapOp {
+        LookupTinyArrayMapOp() {
+            super("LookupTinyArrayMap", "Lookup items in 5 entry ArrayMap", 5);
+        }
+    }
+
+    static class LookupSmallHashMapOp extends GenericMapOp {
+        HashMap<String, String> mHashMap;
+
+        LookupSmallHashMapOp() {
+            super("LookupSmallHashMap", "Lookup items in 100 entry HashMap", 100);
+        }
+
+        LookupSmallHashMapOp(String name, String longname, int size) {
+            super(name, longname, size);
+        }
+
+        void onInit(Context context, boolean foreground) {
+            super.onInit(context, foreground);
+            mHashMap = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                mHashMap.put(mKeys[i], mValues[i]);
+            }
+        }
+
+        boolean onRun() {
+            for (int i=0; i<mSize; i++) {
+                mHashMap.get(mKeys[i]);
+            }
+            return true;
+        }
+    }
+
+    static class LookupSmallArrayMapOp extends GenericMapOp {
+        ArrayMap<String, String> mArrayMap;
+
+        LookupSmallArrayMapOp() {
+            super("LookupSmallArrayMap", "Lookup items in 100 entry ArrayMap", 100);
+        }
+
+        LookupSmallArrayMapOp(String name, String longname, int size) {
+            super(name, longname, size);
+        }
+
+        void onInit(Context context, boolean foreground) {
+            super.onInit(context, foreground);
+            mArrayMap = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                mArrayMap.put(mKeys[i], mValues[i]);
+            }
+        }
+
+        boolean onRun() {
+            for (int i=0; i<mSize; i++) {
+                mArrayMap.get(mKeys[i]);
+            }
+            return true;
+        }
+    }
+
+    static class LookupLargeHashMapOp extends LookupSmallHashMapOp {
+        LookupLargeHashMapOp() {
+            super("LookupLargeHashMap", "Lookup items in 10000 entry HashMap", 10000);
+        }
+    }
+
+    static class LookupLargeArrayMapOp extends LookupSmallArrayMapOp {
+        LookupLargeArrayMapOp() {
+            super("LookupLargeArrayMap", "Lookup items in 10000 entry ArrayMap", 10000);
+        }
+    }
 }