Avoid unnecessary ULocale.addLikelySubtags()

This CL gets rid of unnecessary operations from
LocaleUtils.filterByLanguage() to speed it up, especially for the case
where there is an IME that has many subtypes.

ULocale.addLikelySubtags(ULocale) is known to be slow. Given an IME
that has N IME subtypes, LocaleUtils.filterByLanguage() calls it no
less than N times even when the only one system language is selected.
This has contributed to device boot time (Bug 32343335) time and user
switching time (Bug 28750507) since Android N where IME support
started taking multi-locale into account.

With this CL, LocaleUtils.filterByLanguage() no longer calls it
for a subtype unless its language part of the locale matches one of
user-selected system locales.

The only assumption we made here is

 for any Locale objects l1 and l2
   TextUtils.equals(l1.getLanguage(), l2.getLanguage())
 and
   TextUtils.equals(ul1.getLanguage(), ul2.getLanguage())
 are equivalent, where
   ul1 = ULocale.addLikelySubtags(ULocale.forLocale(l1)) and
   ul2 = ULocale.addLikelySubtags(ULocale.forLocale(l2))

This should be reasonable assumption, at least for locales we want to
care about for IMEs. Under this assumption there is no behavior
change at all.

Test: bit FrameworksCoreTests:com.android.internal.inputmethod.LocaleUtilsTest
Bug: 37647204
Change-Id: Ic96900fcaf3db8b7046a50b3fe6ad65aceada369

diff --git a/core/java/com/android/internal/inputmethod/LocaleUtils.java b/core/java/com/android/internal/inputmethod/LocaleUtils.java
index b18f83c..eeb3854 100644 (file)
--- a/core/java/com/android/internal/inputmethod/LocaleUtils.java
+++ b/core/java/com/android/internal/inputmethod/LocaleUtils.java
@@ -23,6 +23,7 @@ import android.annotation.NonNull;
 import android.annotation.Nullable;
 import android.icu.util.ULocale;
 import android.os.LocaleList;
+import android.text.TextUtils;
 
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -41,7 +42,7 @@ public final class LocaleUtils {
     /**
      * Calculates a matching score for the single desired locale.
      *
-     * @see LocaleUtils#calculateMatchingScore(ULocale, LocaleList, byte[])
+     * @see LocaleUtils#filterByLanguage(List, LocaleExtractor, LocaleList, ArrayList)
      *
      * @param supported The locale supported by IME subtype.
      * @param desired The locale preferred by user.
@@ -72,48 +73,6 @@ public final class LocaleUtils {
         return 3;
     }
 
-    /**
-     * Calculates a matching score for the desired locale list.
-     *
-     * <p>The supported locale gets a matching score of 3 if all language, script and country of the
-     * supported locale matches with the desired locale.  The supported locale gets a matching
-     * score of 2 if the language and script of the supported locale matches with the desired
-     * locale. The supported locale gets a matching score of 1 if only language of the supported
-     * locale matches with the desired locale.  The supported locale gets a matching score of 0 if
-     * the language of the supported locale doesn't match with the desired locale.</p>
-     *
-     * @param supported The locale supported by IME subtyle.
-     * @param desired The locale list preferred by user. Typically system locale list.
-     * @param out The output buffer to be stored the individual score for the desired language list.
-     * The length of {@code out} must be same as the length of {@code desired} language list.
-     * @return {@code false} if supported locale doesn't match with any desired locale list.
-     * Otherwise {@code true}.
-     */
-    private static boolean calculateMatchingScore(@NonNull final ULocale supported,
-            @NonNull final LocaleList desired, @NonNull byte[] out) {
-        if (desired.isEmpty()) {
-            return false;
-        }
-
-        boolean allZeros = true;
-        final int N = desired.size();
-        for (int i = 0; i < N; ++i) {
-            final Locale locale = desired.get(i);
-
-            if (!locale.getLanguage().equals(supported.getLanguage())) {
-                // TODO: cache the result of addLikelySubtags if it is slow.
-                out[i] = 0;
-            } else {
-                out[i] = calculateMatchingSubScore(
-                        supported, ULocale.addLikelySubtags(ULocale.forLocale(locale)));
-                if (allZeros && out[i] != 0) {
-                    allZeros = false;
-                }
-            }
-        }
-        return !allZeros;
-    }
-
     private static final class ScoreEntry implements Comparable<ScoreEntry> {
         public int mIndex = -1;
         @NonNull public final byte[] mScore;  // matching score of the i-th system languages.
@@ -175,17 +134,17 @@ public final class LocaleUtils {
     /**
      * Filters the given items based on language preferences.
      *
-     * <p>For each language found in {@code preferredLanguages}, this method tries to copy at most
+     * <p>For each language found in {@code preferredLocales}, this method tries to copy at most
      * one best-match item from {@code source} to {@code dest}.  For example, if
-     * {@code "en-GB", "ja", "en-AU", "fr-CA", "en-IN"} is specified to {@code preferredLanguages},
+     * {@code "en-GB", "ja", "en-AU", "fr-CA", "en-IN"} is specified to {@code preferredLocales},
      * this method tries to copy at most one English locale, at most one Japanese, and at most one
      * French locale from {@code source} to {@code dest}.  Here the best matching English locale
      * will be searched from {@code source} based on matching score. For the score design, see
-     * {@link LocaleUtils#calculateMatchingScore(ULocale, LocaleList, byte[])}</p>
+     * {@link LocaleUtils#calculateMatchingSubScore(ULocale, ULocale)}</p>
      *
      * @param sources Source items to be filtered.
      * @param extractor Type converter from the source items to {@link Locale} object.
-     * @param preferredLanguages Ordered list of locales with which the input items will be
+     * @param preferredLocales Ordered list of locales with which the input items will be
      * filtered.
      * @param dest Destination into which the filtered items will be added.
      * @param <T> Type of the data items.
@@ -194,17 +153,43 @@ public final class LocaleUtils {
     public static <T> void filterByLanguage(
             @NonNull List<T> sources,
             @NonNull LocaleExtractor<T> extractor,
-            @NonNull LocaleList preferredLanguages,
+            @NonNull LocaleList preferredLocales,
             @NonNull ArrayList<T> dest) {
+        if (preferredLocales.isEmpty()) {
+            return;
+        }
+
+        final int numPreferredLocales = preferredLocales.size();
         final HashMap<String, ScoreEntry> scoreboard = new HashMap<>();
-        final byte[] score = new byte[preferredLanguages.size()];
+        final byte[] score = new byte[numPreferredLocales];
+        final ULocale[] preferredULocaleCache = new ULocale[numPreferredLocales];
 
         final int sourceSize = sources.size();
         for (int i = 0; i < sourceSize; ++i) {
             final Locale locale = extractor.get(sources.get(i));
-            if (locale == null ||
-                    !calculateMatchingScore(ULocale.addLikelySubtags(ULocale.forLocale(locale)),
-                            preferredLanguages, score)) {
+            if (locale == null) {
+                continue;
+            }
+
+            boolean canSkip = true;
+            for (int j = 0; j < numPreferredLocales; ++j) {
+                final Locale preferredLocale = preferredLocales.get(j);
+                if (!TextUtils.equals(locale.getLanguage(), preferredLocale.getLanguage())) {
+                    score[j] = 0;
+                    continue;
+                }
+                if (preferredULocaleCache[j] == null) {
+                    preferredULocaleCache[j] = ULocale.addLikelySubtags(
+                            ULocale.forLocale(preferredLocale));
+                }
+                score[j] = calculateMatchingSubScore(
+                        preferredULocaleCache[j],
+                        ULocale.addLikelySubtags(ULocale.forLocale(locale)));
+                if (canSkip && score[j] != 0) {
+                    canSkip = false;
+                }
+            }
+            if (canSkip) {
                 continue;
             }