Optimize IntentResolver to reduce lookup time by 50%.

IntentResolver frequently iterates over hundreds of different IntentFilters
and spends much of its time creating iterators and comparing strings.
This change avoids reduces the amount of garbage created by eschewing
iterators where possible.  The FastImmutableArraySet type on its own
provides a 2.5x speed boost compared to repeatedly iterating over a HashSet.

In absolute terms, during orientation changes we spent about 160ms resolving
11 intents and performing 1129 calls to IntentFilter.match.  Now we spend
half of that time.

Change-Id: Ia120e0082c8cf0b572a0317b9ef4a22c766dbad6

1 files changed, 78 insertions, 0 deletions

diff --git a/core/java/android/util/FastImmutableArraySet.java b/core/java/android/util/FastImmutableArraySet.java
new file mode 100644
index 0000000..4175c60
--- /dev/null
+++ b/core/java/android/util/FastImmutableArraySet.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2011 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 java.util.AbstractSet;
+import java.util.Iterator;
+
+/**
+ * A fast immutable set wrapper for an array that is optimized for non-concurrent iteration.
+ * The same iterator instance is reused each time to avoid creating lots of garbage.
+ * Iterating over an array in this fashion is 2.5x faster than iterating over a {@link HashSet}
+ * so it is worth copying the contents of the set to an array when iterating over it
+ * hundreds of times.
+ * @hide
+ */
+public final class FastImmutableArraySet<T> extends AbstractSet<T> {
+    FastIterator<T> mIterator;
+    T[] mContents;
+
+    public FastImmutableArraySet(T[] contents) {
+        mContents = contents;
+    }
+
+    @Override
+    public Iterator<T> iterator() {
+        FastIterator<T> it = mIterator;
+        if (it == null) {
+            it = new FastIterator<T>(mContents);
+            mIterator = it;
+        } else {
+            it.mIndex = 0;
+        }
+        return it;
+    }
+
+    @Override
+    public int size() {
+        return mContents.length;
+    }
+
+    private static final class FastIterator<T> implements Iterator<T> {
+        private final T[] mContents;
+        int mIndex;
+
+        public FastIterator(T[] contents) {
+            mContents = contents;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return mIndex != mContents.length;
+        }
+
+        @Override
+        public T next() {
+            return mContents[mIndex++];
+        }
+
+        @Override
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+    }
+}