diff --git a/src/com/android/launcher3/model/WidgetsAndShortcutNameComparator.java b/src/com/android/launcher3/model/WidgetsAndShortcutNameComparator.java
index 61e8952..b990560 100644
--- a/src/com/android/launcher3/model/WidgetsAndShortcutNameComparator.java
+++ b/src/com/android/launcher3/model/WidgetsAndShortcutNameComparator.java
@@ -1,13 +1,14 @@
 package com.android.launcher3.model;
 
+import android.content.ComponentName;
 import android.content.Context;
 import android.content.pm.PackageManager;
 import android.content.pm.ResolveInfo;
-
 import com.android.launcher3.LauncherAppWidgetProviderInfo;
 import com.android.launcher3.Utilities;
 import com.android.launcher3.compat.AppWidgetManagerCompat;
 import com.android.launcher3.compat.UserHandleCompat;
+import com.android.launcher3.util.ComponentKey;
 
 import java.text.Collator;
 import java.util.Comparator;
@@ -16,53 +17,81 @@
 public class WidgetsAndShortcutNameComparator implements Comparator<Object> {
     private final AppWidgetManagerCompat mManager;
     private final PackageManager mPackageManager;
-    private final HashMap<Object, String> mLabelCache;
+    private final HashMap<ComponentKey, String> mLabelCache;
     private final Collator mCollator;
     private final UserHandleCompat mMainHandle;
 
     public WidgetsAndShortcutNameComparator(Context context) {
         mManager = AppWidgetManagerCompat.getInstance(context);
         mPackageManager = context.getPackageManager();
-        mLabelCache = new HashMap<Object, String>();
+        mLabelCache = new HashMap<>();
         mCollator = Collator.getInstance();
         mMainHandle = UserHandleCompat.myUserHandle();
     }
 
+    /**
+     * Resets any stored state.
+     */
+    public void reset() {
+        mLabelCache.clear();
+    }
+
     @Override
-    public final int compare(Object a, Object b) {
-        String labelA, labelB;
-        if (mLabelCache.containsKey(a)) {
-            labelA = mLabelCache.get(a);
-        } else {
-            labelA = (a instanceof LauncherAppWidgetProviderInfo)
-                    ? Utilities.trim(mManager.loadLabel((LauncherAppWidgetProviderInfo) a))
-                    : Utilities.trim(((ResolveInfo) a).loadLabel(mPackageManager));
-            mLabelCache.put(a, labelA);
-        }
-        if (mLabelCache.containsKey(b)) {
-            labelB = mLabelCache.get(b);
-        } else {
-            labelB = (b instanceof LauncherAppWidgetProviderInfo)
-                    ? Utilities.trim(mManager.loadLabel((LauncherAppWidgetProviderInfo) b))
-                    : Utilities.trim(((ResolveInfo) b).loadLabel(mPackageManager));
-            mLabelCache.put(b, labelB);
-        }
-
-        // Currently, there is no work profile shortcuts, hence only considering the widget cases.
-
-        boolean aWorkProfile = (a instanceof LauncherAppWidgetProviderInfo) &&
-                !mMainHandle.equals(mManager.getUser((LauncherAppWidgetProviderInfo) a));
-        boolean bWorkProfile = (b instanceof LauncherAppWidgetProviderInfo) &&
-                !mMainHandle.equals(mManager.getUser((LauncherAppWidgetProviderInfo) b));
+    public final int compare(Object objA, Object objB) {
+        ComponentKey keyA = getComponentKey(objA);
+        ComponentKey keyB = getComponentKey(objB);
 
         // Independent of how the labels compare, if only one of the two widget info belongs to
         // work profile, put that one in the back.
+        boolean aWorkProfile = !mMainHandle.equals(keyA.user);
+        boolean bWorkProfile = !mMainHandle.equals(keyB.user);
         if (aWorkProfile && !bWorkProfile) {
             return 1;
         }
         if (!aWorkProfile && bWorkProfile) {
             return -1;
         }
+
+        // Get the labels for comparison
+        String labelA = mLabelCache.get(keyA);
+        String labelB = mLabelCache.get(keyB);
+        if (labelA == null) {
+            labelA = getLabel(objA);
+            mLabelCache.put(keyA, labelA);
+        }
+        if (labelB == null) {
+            labelB = getLabel(objB);
+            mLabelCache.put(keyB, labelB);
+        }
         return mCollator.compare(labelA, labelB);
     }
+
+    /**
+     * @return a component key for the given widget or shortcut info.
+     */
+    private ComponentKey getComponentKey(Object o) {
+        if (o instanceof LauncherAppWidgetProviderInfo) {
+            LauncherAppWidgetProviderInfo widgetInfo = (LauncherAppWidgetProviderInfo) o;
+            return new ComponentKey(widgetInfo.provider, mManager.getUser(widgetInfo));
+        } else {
+            ResolveInfo shortcutInfo = (ResolveInfo) o;
+            ComponentName cn = new ComponentName(shortcutInfo.activityInfo.packageName,
+                    shortcutInfo.activityInfo.name);
+            // Currently, there are no work profile shortcuts
+            return new ComponentKey(cn, UserHandleCompat.myUserHandle());
+        }
+    }
+
+    /**
+     * @return the label for the given widget or shortcut info.  This may be an expensive call.
+     */
+    private String getLabel(Object o) {
+        if (o instanceof LauncherAppWidgetProviderInfo) {
+            LauncherAppWidgetProviderInfo widgetInfo = (LauncherAppWidgetProviderInfo) o;
+            return Utilities.trim(mManager.loadLabel(widgetInfo));
+        } else {
+            ResolveInfo shortcutInfo = (ResolveInfo) o;
+            return Utilities.trim(shortcutInfo.loadLabel(mPackageManager));
+        }
+    }
 };
diff --git a/src/com/android/launcher3/model/WidgetsModel.java b/src/com/android/launcher3/model/WidgetsModel.java
index 185dfca..cabff14 100644
--- a/src/com/android/launcher3/model/WidgetsModel.java
+++ b/src/com/android/launcher3/model/WidgetsModel.java
@@ -39,7 +39,7 @@
     private ArrayList<Object> mRawList;
 
     private final AppWidgetManagerCompat mAppWidgetMgr;
-    private final Comparator mWidgetAndShortcutNameComparator;
+    private final WidgetsAndShortcutNameComparator mWidgetAndShortcutNameComparator;
     private final Comparator mAppNameComparator;
     private final IconCache mIconCache;
     private final AppFilter mAppFilter;
@@ -103,6 +103,7 @@
         // clear the lists.
         mWidgetsList.clear();
         mPackageItemInfos.clear();
+        mWidgetAndShortcutNameComparator.reset();
 
         // add and update.
         for (Object o: rawWidgetsShortcuts) {
@@ -139,7 +140,7 @@
             if (widgetsShortcutsList != null) {
                 widgetsShortcutsList.add(o);
             } else {
-                widgetsShortcutsList = new ArrayList<Object>();
+                widgetsShortcutsList = new ArrayList<>();
                 widgetsShortcutsList.add(o);
                 pInfo = new PackageItemInfo(packageName);
                 mIconCache.getTitleAndIconForApp(packageName, userHandle,