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
diff --git a/core/java/android/content/Intent.java b/core/java/android/content/Intent.java
index 6e3663e..e7b96e7 100644
--- a/core/java/android/content/Intent.java
+++ b/core/java/android/content/Intent.java
@@ -2794,7 +2794,7 @@
* @param action The Intent action, such as ACTION_VIEW.
*/
public Intent(String action) {
- mAction = action;
+ setAction(action);
}
/**
@@ -2814,7 +2814,7 @@
* @param uri The Intent data URI.
*/
public Intent(String action, Uri uri) {
- mAction = action;
+ setAction(action);
mData = uri;
}
@@ -2863,7 +2863,7 @@
*/
public Intent(String action, Uri uri,
Context packageContext, Class<?> cls) {
- mAction = action;
+ setAction(action);
mData = uri;
mComponent = new ComponentName(packageContext, cls);
}
@@ -2985,7 +2985,7 @@
// action
if (uri.startsWith("action=", i)) {
- intent.mAction = value;
+ intent.setAction(value);
}
// categories
@@ -4061,7 +4061,7 @@
* @see #getAction
*/
public Intent setAction(String action) {
- mAction = action;
+ mAction = action != null ? action.intern() : null;
return this;
}
@@ -4165,7 +4165,7 @@
if (mCategories == null) {
mCategories = new HashSet<String>();
}
- mCategories.add(category);
+ mCategories.add(category.intern());
return this;
}
@@ -5678,7 +5678,7 @@
}
public void readFromParcel(Parcel in) {
- mAction = in.readString();
+ setAction(in.readString());
mData = Uri.CREATOR.createFromParcel(in);
mType = in.readString();
mFlags = in.readInt();
@@ -5694,7 +5694,7 @@
mCategories = new HashSet<String>();
int i;
for (i=0; i<N; i++) {
- mCategories.add(in.readString());
+ mCategories.add(in.readString().intern());
}
} else {
mCategories = null;
diff --git a/core/java/android/content/IntentFilter.java b/core/java/android/content/IntentFilter.java
index 452fd8a..61d7424 100644
--- a/core/java/android/content/IntentFilter.java
+++ b/core/java/android/content/IntentFilter.java
@@ -461,7 +461,7 @@
* @return True if the action is explicitly mentioned in the filter.
*/
public final boolean hasAction(String action) {
- return mActions.contains(action);
+ return action != null && mActions.contains(action);
}
/**
@@ -470,14 +470,10 @@
*
* @param action The desired action to look for.
*
- * @return True if the action is listed in the filter or the filter does
- * not specify any actions.
+ * @return True if the action is listed in the filter.
*/
public final boolean matchAction(String action) {
- if (action == null || mActions == null || mActions.size() == 0) {
- return false;
- }
- return mActions.contains(action);
+ return hasAction(action);
}
/**
@@ -818,9 +814,9 @@
if (mDataPaths == null) {
return false;
}
- Iterator<PatternMatcher> i = mDataPaths.iterator();
- while (i.hasNext()) {
- final PatternMatcher pe = i.next();
+ final int numDataPaths = mDataPaths.size();
+ for (int i = 0; i < numDataPaths; i++) {
+ final PatternMatcher pe = mDataPaths.get(i);
if (pe.match(data)) {
return true;
}
@@ -849,9 +845,9 @@
if (mDataAuthorities == null) {
return NO_MATCH_DATA;
}
- Iterator<AuthorityEntry> i = mDataAuthorities.iterator();
- while (i.hasNext()) {
- final AuthorityEntry ae = i.next();
+ final int numDataAuthorities = mDataAuthorities.size();
+ for (int i = 0; i < numDataAuthorities; i++) {
+ final AuthorityEntry ae = mDataAuthorities.get(i);
int match = ae.match(data);
if (match >= 0) {
return match;
@@ -1098,7 +1094,7 @@
*/
public final int match(String action, String type, String scheme,
Uri data, Set<String> categories, String logTag) {
- if (action != null && !matchAction(action)) {
+ if (!matchAction(action)) {
if (Config.LOGV) Log.v(
logTag, "No matching action " + action + " for " + this);
return NO_MATCH_ACTION;
@@ -1119,11 +1115,11 @@
return dataMatch;
}
- String categoryMatch = matchCategories(categories);
- if (categoryMatch != null) {
- if (Config.LOGV) Log.v(
- logTag, "No matching category "
- + categoryMatch + " for " + this);
+ String categoryMismatch = matchCategories(categories);
+ if (categoryMismatch != null) {
+ if (Config.LOGV) {
+ Log.v(logTag, "No matching category " + categoryMismatch + " for " + this);
+ }
return NO_MATCH_CATEGORY;
}
@@ -1469,9 +1465,9 @@
if (typeLength == slashpos+2 && type.charAt(slashpos+1) == '*') {
// Need to look through all types for one that matches
// our base...
- final Iterator<String> it = t.iterator();
- while (it.hasNext()) {
- String v = it.next();
+ final int numTypes = t.size();
+ for (int i = 0; i < numTypes; i++) {
+ final String v = t.get(i);
if (type.regionMatches(0, v, 0, slashpos+1)) {
return true;
}
diff --git a/core/java/android/util/FastImmutableArraySet.java b/core/java/android/util/FastImmutableArraySet.java
new file mode 100644
index 0000000..4175c605
--- /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();
+ }
+ }
+}
diff --git a/services/java/com/android/server/IntentResolver.java b/services/java/com/android/server/IntentResolver.java
index a8b2840..e9ee12c 100644
--- a/services/java/com/android/server/IntentResolver.java
+++ b/services/java/com/android/server/IntentResolver.java
@@ -27,6 +27,8 @@
import java.util.Map;
import java.util.Set;
+import android.net.Uri;
+import android.util.FastImmutableArraySet;
import android.util.Log;
import android.util.PrintWriterPrinter;
import android.util.Slog;
@@ -207,10 +209,11 @@
final boolean debug = localLOGV ||
((intent.getFlags() & Intent.FLAG_DEBUG_LOG_RESOLUTION) != 0);
+ FastImmutableArraySet<String> categories = getFastIntentCategories(intent);
final String scheme = intent.getScheme();
int N = listCut.size();
for (int i = 0; i < N; ++i) {
- buildResolveList(intent, debug, defaultOnly,
+ buildResolveList(intent, categories, debug, defaultOnly,
resolvedType, scheme, listCut.get(i), resultList);
}
sortResults(resultList);
@@ -286,20 +289,21 @@
if (debug) Slog.v(TAG, "Action list: " + firstTypeCut);
}
+ FastImmutableArraySet<String> categories = getFastIntentCategories(intent);
if (firstTypeCut != null) {
- buildResolveList(intent, debug, defaultOnly,
+ buildResolveList(intent, categories, debug, defaultOnly,
resolvedType, scheme, firstTypeCut, finalList);
}
if (secondTypeCut != null) {
- buildResolveList(intent, debug, defaultOnly,
+ buildResolveList(intent, categories, debug, defaultOnly,
resolvedType, scheme, secondTypeCut, finalList);
}
if (thirdTypeCut != null) {
- buildResolveList(intent, debug, defaultOnly,
+ buildResolveList(intent, categories, debug, defaultOnly,
resolvedType, scheme, thirdTypeCut, finalList);
}
if (schemeCut != null) {
- buildResolveList(intent, debug, defaultOnly,
+ buildResolveList(intent, categories, debug, defaultOnly,
resolvedType, scheme, schemeCut, finalList);
}
sortResults(finalList);
@@ -478,9 +482,19 @@
return false;
}
- private void buildResolveList(Intent intent, boolean debug, boolean defaultOnly,
+ private static FastImmutableArraySet<String> getFastIntentCategories(Intent intent) {
+ final Set<String> categories = intent.getCategories();
+ if (categories == null) {
+ return null;
+ }
+ return new FastImmutableArraySet<String>(categories.toArray(new String[categories.size()]));
+ }
+
+ private void buildResolveList(Intent intent, FastImmutableArraySet<String> categories,
+ boolean debug, boolean defaultOnly,
String resolvedType, String scheme, List<F> src, List<R> dest) {
- Set<String> categories = intent.getCategories();
+ final String action = intent.getAction();
+ final Uri data = intent.getData();
final int N = src != null ? src.size() : 0;
boolean hasNonDefaults = false;
@@ -498,8 +512,7 @@
continue;
}
- match = filter.match(
- intent.getAction(), resolvedType, scheme, intent.getData(), categories, TAG);
+ match = filter.match(action, resolvedType, scheme, data, categories, TAG);
if (match >= 0) {
if (debug) Slog.v(TAG, " Filter matched! match=0x" +
Integer.toHexString(match));