diff --git a/src/com/android/launcher3/AppInfo.java b/src/com/android/launcher3/AppInfo.java
index 2910525..a132d04 100644
--- a/src/com/android/launcher3/AppInfo.java
+++ b/src/com/android/launcher3/AppInfo.java
@@ -49,6 +49,9 @@
 
     public ComponentName componentName;
 
+    // Section name used for indexing.
+    public String sectionName = "";
+
     public AppInfo() {
         itemType = LauncherSettings.Favorites.ITEM_TYPE_APPLICATION;
     }
diff --git a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
index 1369441..0c4be62 100644
--- a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
+++ b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
@@ -21,16 +21,13 @@
 import com.android.launcher3.AppInfo;
 import com.android.launcher3.Launcher;
 import com.android.launcher3.Utilities;
-import com.android.launcher3.compat.AlphabeticIndexCompat;
 import com.android.launcher3.shortcuts.DeepShortcutManager;
-import com.android.launcher3.testing.TestProtocol;
 import com.android.launcher3.util.ComponentKey;
 import com.android.launcher3.util.ItemInfoMatcher;
 import com.android.launcher3.util.LabelComparator;
 
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.List;
 import java.util.Locale;
 import java.util.Map;
@@ -145,9 +142,7 @@
 
     // The of ordered component names as a result of a search query
     private ArrayList<ComponentKey> mSearchResults;
-    private HashMap<CharSequence, String> mCachedSectionNames = new HashMap<>();
     private AllAppsGridAdapter mAdapter;
-    private AlphabeticIndexCompat mIndexer;
     private AppInfoComparator mAppNameComparator;
     private final int mNumAppsPerRow;
     private int mNumAppRowsInAdapter;
@@ -156,7 +151,6 @@
     public AlphabeticalAppsList(Context context, AllAppsStore appsStore, boolean isWork) {
         mAllAppsStore = appsStore;
         mLauncher = Launcher.getLauncher(context);
-        mIndexer = new AlphabeticIndexCompat(context);
         mAppNameComparator = new AppInfoComparator(context);
         mIsWork = isWork;
         mNumAppsPerRow = mLauncher.getDeviceProfile().inv.numColumns;
@@ -263,7 +257,7 @@
             TreeMap<String, ArrayList<AppInfo>> sectionMap = new TreeMap<>(new LabelComparator());
             for (AppInfo info : mApps) {
                 // Add the section to the cache
-                String sectionName = getAndUpdateCachedSectionName(info.title);
+                String sectionName = info.sectionName;
 
                 // Add it to the mapping
                 ArrayList<AppInfo> sectionApps = sectionMap.get(sectionName);
@@ -279,12 +273,6 @@
             for (Map.Entry<String, ArrayList<AppInfo>> entry : sectionMap.entrySet()) {
                 mApps.addAll(entry.getValue());
             }
-        } else {
-            // Just compute the section headers for use below
-            for (AppInfo info : mApps) {
-                // Add the section to the cache
-                getAndUpdateCachedSectionName(info.title);
-            }
         }
 
         // Recompose the set of adapter items from the current set of apps
@@ -320,7 +308,7 @@
         // Recreate the filtered and sectioned apps (for convenience for the grid layout) from the
         // ordered set of sections
         for (AppInfo info : getFiltersAppInfos()) {
-            String sectionName = getAndUpdateCachedSectionName(info.title);
+            String sectionName = info.sectionName;
 
             // Create a new section if the section names do not match
             if (!sectionName.equals(lastSectionName)) {
@@ -428,18 +416,4 @@
         }
         return result;
     }
-
-    /**
-     * Returns the cached section name for the given title, recomputing and updating the cache if
-     * the title has no cached section name.
-     */
-    private String getAndUpdateCachedSectionName(CharSequence title) {
-        String sectionName = mCachedSectionNames.get(title);
-        if (sectionName == null) {
-            sectionName = mIndexer.computeSectionName(title);
-            mCachedSectionNames.put(title, sectionName);
-        }
-        return sectionName;
-    }
-
 }
diff --git a/src/com/android/launcher3/compat/AlphabeticIndexCompat.java b/src/com/android/launcher3/compat/AlphabeticIndexCompat.java
index dfdcc70..46c9006 100644
--- a/src/com/android/launcher3/compat/AlphabeticIndexCompat.java
+++ b/src/com/android/launcher3/compat/AlphabeticIndexCompat.java
@@ -3,7 +3,6 @@
 import android.content.Context;
 import android.icu.text.AlphabeticIndex;
 import android.os.LocaleList;
-import android.util.Log;
 
 import com.android.launcher3.Utilities;
 
@@ -12,28 +11,32 @@
 import androidx.annotation.NonNull;
 
 public class AlphabeticIndexCompat {
-    private static final String TAG = "AlphabeticIndexCompat";
 
     private static final String MID_DOT = "\u2219";
-    private final BaseIndex mBaseIndex;
     private final String mDefaultMiscLabel;
 
+    private final AlphabeticIndex.ImmutableIndex mBaseIndex;
+
     public AlphabeticIndexCompat(Context context) {
-        BaseIndex index = null;
+        this(context.getResources().getConfiguration().getLocales());
+    }
 
-        try {
-            index = new AlphabeticIndexVN(context);
-        } catch (Exception e) {
-            Log.d(TAG, "Unable to load the system index", e);
+    public AlphabeticIndexCompat(LocaleList locales) {
+        int localeCount = locales.size();
+
+        Locale primaryLocale = localeCount == 0 ? Locale.ENGLISH : locales.get(0);
+        AlphabeticIndex indexBuilder = new AlphabeticIndex(primaryLocale);
+        for (int i = 1; i < localeCount; i++) {
+            indexBuilder.addLabels(locales.get(i));
         }
+        indexBuilder.addLabels(Locale.ENGLISH);
+        mBaseIndex = indexBuilder.buildImmutableIndex();
 
-        mBaseIndex = index == null ? new BaseIndex() : index;
-
-        if (context.getResources().getConfiguration().locale
-                .getLanguage().equals(Locale.JAPANESE.getLanguage())) {
+        if (primaryLocale.getLanguage().equals(Locale.JAPANESE.getLanguage())) {
             // Japanese character 他 ("misc")
             mDefaultMiscLabel = "\u4ed6";
-            // TODO(winsonc, omakoto): We need to handle Japanese sections better, especially the kanji
+            // TODO(winsonc, omakoto): We need to handle Japanese sections better,
+            // especially the kanji
         } else {
             // Dot
             mDefaultMiscLabel = MID_DOT;
@@ -45,7 +48,7 @@
      */
     public String computeSectionName(@NonNull CharSequence cs) {
         String s = Utilities.trim(cs);
-        String sectionName = mBaseIndex.getBucketLabel(mBaseIndex.getBucketIndex(s));
+        String sectionName = mBaseIndex.getBucket(mBaseIndex.getBucketIndex(s)).getLabel();
         if (Utilities.trim(sectionName).isEmpty() && s.length() > 0) {
             int c = s.codePointAt(0);
             boolean startsWithDigit = Character.isDigit(c);
@@ -66,71 +69,4 @@
         }
         return sectionName;
     }
-
-    /**
-     * Base class to support Alphabetic indexing if not supported by the framework.
-     * TODO(winsonc): disable for non-english locales
-     */
-    private static class BaseIndex {
-
-        private static final String BUCKETS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ-";
-        private static final int UNKNOWN_BUCKET_INDEX = BUCKETS.length() - 1;
-
-        /**
-         * Returns the index of the bucket in which the given string should appear.
-         */
-        protected int getBucketIndex(@NonNull String s) {
-            if (s.isEmpty()) {
-                return UNKNOWN_BUCKET_INDEX;
-            }
-            int index = BUCKETS.indexOf(s.substring(0, 1).toUpperCase());
-            if (index != -1) {
-                return index;
-            }
-            return UNKNOWN_BUCKET_INDEX;
-        }
-
-        /**
-         * Returns the label for the bucket at the given index (as returned by getBucketIndex).
-         */
-        protected String getBucketLabel(int index) {
-            return BUCKETS.substring(index, index + 1);
-        }
-    }
-
-    /**
-     * Implementation based on {@link AlphabeticIndex}.
-     */
-    private static class AlphabeticIndexVN extends BaseIndex {
-
-        private final AlphabeticIndex.ImmutableIndex mAlphabeticIndex;
-
-        public AlphabeticIndexVN(Context context) {
-            LocaleList locales = context.getResources().getConfiguration().getLocales();
-            int localeCount = locales.size();
-
-            Locale primaryLocale = localeCount == 0 ? Locale.ENGLISH : locales.get(0);
-            AlphabeticIndex indexBuilder = new AlphabeticIndex(primaryLocale);
-            for (int i = 1; i < localeCount; i++) {
-                indexBuilder.addLabels(locales.get(i));
-            }
-            indexBuilder.addLabels(Locale.ENGLISH);
-
-            mAlphabeticIndex = indexBuilder.buildImmutableIndex();
-        }
-
-        /**
-         * Returns the index of the bucket in which {@param s} should appear.
-         */
-        protected int getBucketIndex(String s) {
-            return mAlphabeticIndex.getBucketIndex(s);
-        }
-
-        /**
-         * Returns the label for the bucket at the given index
-         */
-        protected String getBucketLabel(int index) {
-            return mAlphabeticIndex.getBucket(index).getLabel();
-        }
-    }
 }
diff --git a/src/com/android/launcher3/model/AllAppsList.java b/src/com/android/launcher3/model/AllAppsList.java
index 2fddbaa..370a812 100644
--- a/src/com/android/launcher3/model/AllAppsList.java
+++ b/src/com/android/launcher3/model/AllAppsList.java
@@ -23,6 +23,7 @@
 import android.content.Context;
 import android.content.pm.ApplicationInfo;
 import android.content.pm.LauncherActivityInfo;
+import android.os.LocaleList;
 import android.os.Process;
 import android.os.UserHandle;
 import android.util.Log;
@@ -30,6 +31,7 @@
 import com.android.launcher3.AppFilter;
 import com.android.launcher3.AppInfo;
 import com.android.launcher3.PromiseAppInfo;
+import com.android.launcher3.compat.AlphabeticIndexCompat;
 import com.android.launcher3.compat.LauncherAppsCompat;
 import com.android.launcher3.compat.PackageInstallerCompat;
 import com.android.launcher3.compat.PackageInstallerCompat.PackageInstallInfo;
@@ -68,12 +70,15 @@
     private boolean mDataChanged = false;
     private Consumer<AppInfo> mRemoveListener = NO_OP_CONSUMER;
 
+    private AlphabeticIndexCompat mIndex;
+
     /**
      * Boring constructor.
      */
     public AllAppsList(IconCache iconCache, AppFilter appFilter) {
         mIconCache = iconCache;
         mAppFilter = appFilter;
+        mIndex = new AlphabeticIndexCompat(LocaleList.getDefault());
     }
 
     /**
@@ -99,6 +104,7 @@
             return;
         }
         mIconCache.getTitleAndIcon(info, activityInfo, true /* useLowResIcon */);
+        info.sectionName = mIndex.computeSectionName(info.title);
 
         data.add(info);
         mDataChanged = true;
@@ -112,6 +118,8 @@
         if (applicationInfo == null) {
             PromiseAppInfo info = new PromiseAppInfo(installInfo);
             mIconCache.getTitleAndIcon(info, info.usingLowResIcon());
+            info.sectionName = mIndex.computeSectionName(info.title);
+
             data.add(info);
             mDataChanged = true;
         }
@@ -148,6 +156,8 @@
     public void clear() {
         data.clear();
         mDataChanged = false;
+        // Reset the index as locales might have changed
+        mIndex = new AlphabeticIndexCompat(LocaleList.getDefault());
     }
 
     /**
@@ -194,6 +204,7 @@
         for (AppInfo info : data) {
             if (info.user.equals(user) && packages.contains(info.componentName.getPackageName())) {
                 mIconCache.updateTitleAndIcon(info);
+                info.sectionName = mIndex.computeSectionName(info.title);
                 mDataChanged = true;
             }
         }
@@ -228,6 +239,8 @@
                     add(new AppInfo(context, info, user), info);
                 } else {
                     mIconCache.getTitleAndIcon(applicationInfo, info, true /* useLowResIcon */);
+                    applicationInfo.sectionName = mIndex.computeSectionName(applicationInfo.title);
+
                     mDataChanged = true;
                 }
             }