diff --git a/src/com/android/launcher3/AllAppsList.java b/src/com/android/launcher3/AllAppsList.java
index b641eb5..89b291f 100644
--- a/src/com/android/launcher3/AllAppsList.java
+++ b/src/com/android/launcher3/AllAppsList.java
@@ -32,7 +32,7 @@
  */
 class AllAppsList {
     public static final int DEFAULT_APPLICATIONS_NUMBER = 42;
-    
+
     /** The list off all apps. */
     public ArrayList<AppInfo> data =
             new ArrayList<AppInfo>(DEFAULT_APPLICATIONS_NUMBER);
@@ -115,8 +115,7 @@
                 data.remove(i);
             }
         }
-        // This is more aggressive than it needs to be.
-        mIconCache.flush();
+        mIconCache.remove(packageName);
     }
 
     /**
diff --git a/src/com/android/launcher3/IconCache.java b/src/com/android/launcher3/IconCache.java
index a55fce0..827718b 100644
--- a/src/com/android/launcher3/IconCache.java
+++ b/src/com/android/launcher3/IconCache.java
@@ -16,6 +16,8 @@
 
 package com.android.launcher3;
 
+import com.android.launcher3.backup.BackupProtos;
+
 import android.app.ActivityManager;
 import android.content.ComponentName;
 import android.content.Context;
@@ -25,10 +27,20 @@
 import android.content.pm.ResolveInfo;
 import android.content.res.Resources;
 import android.graphics.Bitmap;
+import android.graphics.BitmapFactory;
 import android.graphics.Canvas;
+import android.graphics.Paint;
 import android.graphics.drawable.Drawable;
+import android.util.Log;
 
+import java.io.ByteArrayOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.io.FileOutputStream;
+import java.io.IOException;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map.Entry;
 
@@ -40,6 +52,9 @@
     private static final String TAG = "Launcher.IconCache";
 
     private static final int INITIAL_ICON_CACHE_CAPACITY = 50;
+    private static final String RESOURCE_FILE_PREFIX = "icon_";
+
+    private static final boolean DEBUG = true;
 
     private static class CacheEntry {
         public Bitmap icon;
@@ -115,6 +130,7 @@
                 return getFullResIcon(resources, iconId);
             }
         }
+
         return getFullResDefaultActivityIcon();
     }
 
@@ -140,6 +156,21 @@
     }
 
     /**
+     * Remove any records for the supplied package name.
+     */
+    public void remove(String packageName) {
+        HashSet<ComponentName> forDeletion = new HashSet<ComponentName>();
+        for (ComponentName componentName: mCache.keySet()) {
+            if (componentName.getPackageName().equals(packageName)) {
+                forDeletion.add(componentName);
+            }
+        }
+        for (ComponentName condemned: forDeletion) {
+            remove(condemned);
+        }
+    }
+
+    /**
      * Empty out the cache.
      */
     public void flush() {
@@ -177,15 +208,22 @@
     }
 
     public Bitmap getIcon(Intent intent) {
+        return getIcon(intent, null);
+    }
+
+    public Bitmap getIcon(Intent intent, String title) {
         synchronized (mCache) {
             final ResolveInfo resolveInfo = mPackageManager.resolveActivity(intent, 0);
             ComponentName component = intent.getComponent();
 
-            if (resolveInfo == null || component == null) {
+            if (component == null) {
                 return mDefaultIcon;
             }
 
             CacheEntry entry = cacheLocked(component, resolveInfo, null);
+            if (title != null) {
+                entry.title = title;
+            }
             return entry.icon;
         }
     }
@@ -214,21 +252,35 @@
 
             mCache.put(componentName, entry);
 
-            ComponentName key = LauncherModel.getComponentNameFromResolveInfo(info);
-            if (labelCache != null && labelCache.containsKey(key)) {
-                entry.title = labelCache.get(key).toString();
+            if (info != null) {
+                ComponentName key = LauncherModel.getComponentNameFromResolveInfo(info);
+                if (labelCache != null && labelCache.containsKey(key)) {
+                    entry.title = labelCache.get(key).toString();
+                } else {
+                    entry.title = info.loadLabel(mPackageManager).toString();
+                    if (labelCache != null) {
+                        labelCache.put(key, entry.title);
+                    }
+                }
+                if (entry.title == null) {
+                    entry.title = info.activityInfo.name;
+                }
+
+                entry.icon = Utilities.createIconBitmap(
+                        getFullResIcon(info), mContext);
             } else {
-                entry.title = info.loadLabel(mPackageManager).toString();
-                if (labelCache != null) {
-                    labelCache.put(key, entry.title);
+                entry.title = "";
+                Bitmap preloaded = getPreloadedIcon(componentName);
+                if (preloaded != null) {
+                    if (DEBUG) Log.d(TAG, "using preloaded icon for " +
+                            componentName.toShortString());
+                    entry.icon = preloaded;
+                } else {
+                    if (DEBUG) Log.d(TAG, "using default icon for " +
+                            componentName.toShortString());
+                    entry.icon = mDefaultIcon;
                 }
             }
-            if (entry.title == null) {
-                entry.title = info.activityInfo.name;
-            }
-
-            entry.icon = Utilities.createIconBitmap(
-                    getFullResIcon(info), mContext);
         }
         return entry;
     }
@@ -243,4 +295,137 @@
             return set;
         }
     }
+
+    /**
+     * Pre-load an icon into the persistent cache.
+     *
+     * <P>Queries for a component that does not exist in the package manager
+     * will be answered by the persistent cache.
+     *
+     * @param context application context
+     * @param componentName the icon should be returned for this component
+     * @param icon the icon to be persisted
+     * @param dpi the native density of the icon
+     */
+    public static void preloadIcon(Context context, ComponentName componentName, Bitmap icon,
+            int dpi) {
+        // TODO rescale to the correct native DPI
+        try {
+            PackageManager packageManager = context.getPackageManager();
+            packageManager.getActivityIcon(componentName);
+            // component is present on the system already, do nothing
+            return;
+        } catch (PackageManager.NameNotFoundException e) {
+            // pass
+        }
+
+        final String key = componentName.flattenToString();
+        FileOutputStream resourceFile = null;
+        try {
+            resourceFile = context.openFileOutput(getResourceFilename(componentName),
+                    Context.MODE_PRIVATE);
+            ByteArrayOutputStream os = new ByteArrayOutputStream();
+            if (icon.compress(android.graphics.Bitmap.CompressFormat.PNG, 75, os)) {
+                byte[] buffer = os.toByteArray();
+                resourceFile.write(buffer, 0, buffer.length);
+            } else {
+                Log.w(TAG, "failed to encode cache for " + key);
+                return;
+            }
+        } catch (FileNotFoundException e) {
+            Log.w(TAG, "failed to pre-load cache for " + key, e);
+        } catch (IOException e) {
+            Log.w(TAG, "failed to pre-load cache for " + key, e);
+        } finally {
+            if (resourceFile != null) {
+                try {
+                    resourceFile.close();
+                } catch (IOException e) {
+                    Log.d(TAG, "failed to save restored icon for: " + key, e);
+                }
+            }
+        }
+    }
+
+    /**
+     * Read a pre-loaded icon from the persistent icon cache.
+     *
+     * @param componentName the component that should own the icon
+     * @returns a bitmap if one is cached, or null.
+     */
+    private Bitmap getPreloadedIcon(ComponentName componentName) {
+        final String key = componentName.flattenToShortString();
+
+        if (DEBUG) Log.v(TAG, "looking for pre-load icon for " + key);
+        Bitmap icon = null;
+        FileInputStream resourceFile = null;
+        try {
+            resourceFile = mContext.openFileInput(getResourceFilename(componentName));
+            byte[] buffer = new byte[1024];
+            ByteArrayOutputStream bytes = new ByteArrayOutputStream();
+            int bytesRead = 0;
+            while(bytesRead >= 0) {
+                bytes.write(buffer, 0, bytesRead);
+                bytesRead = resourceFile.read(buffer, 0, buffer.length);
+            }
+            if (DEBUG) Log.d(TAG, "read " + bytes.size());
+            icon = BitmapFactory.decodeByteArray(bytes.toByteArray(), 0, bytes.size());
+            if (icon == null) {
+                Log.w(TAG, "failed to decode pre-load icon for " + key);
+            }
+        } catch (FileNotFoundException e) {
+            if (DEBUG) Log.d(TAG, "there is no restored icon for: " + key, e);
+        } catch (IOException e) {
+            Log.w(TAG, "failed to read pre-load icon for: " + key, e);
+        } finally {
+            if(resourceFile != null) {
+                try {
+                    resourceFile.close();
+                } catch (IOException e) {
+                    Log.d(TAG, "failed to manage pre-load icon file: " + key, e);
+                }
+            }
+        }
+
+        if (icon != null) {
+            // TODO: handle alpha mask in the view layer
+            Bitmap b = Bitmap.createBitmap(Math.max(icon.getWidth(), 1),
+                    Math.max(icon.getHeight(), 1),
+                    Bitmap.Config.ARGB_8888);
+            Canvas c = new Canvas(b);
+            Paint paint = new Paint();
+            paint.setAlpha(127);
+            c.drawBitmap(icon, 0, 0, paint);
+            c.setBitmap(null);
+            icon.recycle();
+            icon = b;
+        }
+
+        return icon;
+    }
+
+    /**
+     * Remove a pre-loaded icon from the persistent icon cache.
+     *
+     * @param componentName the component that should own the icon
+     * @returns true on success
+     */
+    public boolean deletePreloadedIcon(ComponentName componentName) {
+        if (componentName == null) {
+            return false;
+        }
+        if (mCache.remove(componentName) != null) {
+            if (DEBUG) Log.d(TAG, "removed pre-loaded icon from the in-memory cache");
+        }
+        boolean success = mContext.deleteFile(getResourceFilename(componentName));
+        if (DEBUG && success) Log.d(TAG, "removed pre-loaded icon from persistent cache");
+
+        return success;
+    }
+
+    private static String getResourceFilename(ComponentName component) {
+        String resourceName = component.flattenToShortString();
+        String filename = resourceName.replace(File.separatorChar, '_');
+        return RESOURCE_FILE_PREFIX + filename;
+    }
 }
diff --git a/src/com/android/launcher3/LauncherBackupHelper.java b/src/com/android/launcher3/LauncherBackupHelper.java
index a45f293..c706cf1 100644
--- a/src/com/android/launcher3/LauncherBackupHelper.java
+++ b/src/com/android/launcher3/LauncherBackupHelper.java
@@ -50,7 +50,9 @@
 import android.util.Log;
 
 import java.io.ByteArrayOutputStream;
+import java.io.File;
 import java.io.FileInputStream;
+import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
 import java.io.IOException;
 import java.net.URISyntaxException;
@@ -136,6 +138,8 @@
 
     private static final int SCREEN_RANK_INDEX = 2;
 
+    private static IconCache mIconCache;
+
     private final Context mContext;
 
     private final boolean mRestoreEnabled;
@@ -441,14 +445,12 @@
     private void backupIcons(Journal in, BackupDataOutput data, Journal out,
             ArrayList<Key> keys) throws IOException {
         // persist icons that haven't been persisted yet
-        final LauncherAppState appState = LauncherAppState.getInstanceNoCreate();
-        if (appState == null) {
+        if (!initializeIconCache()) {
             dataChanged(); // try again later
             if (DEBUG) Log.d(TAG, "Launcher is not initialized, delaying icon backup");
             return;
         }
         final ContentResolver cr = mContext.getContentResolver();
-        final IconCache iconCache = appState.getIconCache();
         final int dpi = mContext.getResources().getDisplayMetrics().densityDpi;
 
         // read the old ID set
@@ -487,9 +489,9 @@
                         if (DEBUG) Log.d(TAG, "I can count this high: " + out.rows);
                         if ((out.rows - startRows) < MAX_ICONS_PER_PASS) {
                             if (VERBOSE) Log.v(TAG, "saving icon " + backupKey);
-                            Bitmap icon = iconCache.getIcon(intent);
+                            Bitmap icon = mIconCache.getIcon(intent);
                             keys.add(key);
-                            if (icon != null && !iconCache.isDefaultIcon(icon)) {
+                            if (icon != null && !mIconCache.isDefaultIcon(icon)) {
                                 byte[] blob = packIcon(dpi, icon);
                                 writeRowToBackup(key, blob, out, data);
                             }
@@ -530,25 +532,33 @@
         if (VERBOSE) Log.v(TAG, "unpacking icon " + key.id);
         if (DEBUG) Log.d(TAG, "read (" + buffer.length + "): " +
                 Base64.encodeToString(buffer, 0, dataSize, Base64.NO_WRAP));
+
         try {
             Resource res = unpackIcon(buffer, 0, dataSize);
-            if (DEBUG) Log.d(TAG, "unpacked " + res.dpi + " dpi icon");
-            if (DEBUG_PAYLOAD) Log.d(TAG, "read " +
-                    Base64.encodeToString(res.data, 0, res.data.length,
-                            Base64.NO_WRAP));
+            if (DEBUG) {
+                Log.d(TAG, "unpacked " + res.dpi + " dpi icon");
+            }
+            if (DEBUG_PAYLOAD) {
+                Log.d(TAG, "read " +
+                        Base64.encodeToString(res.data, 0, res.data.length,
+                                Base64.NO_WRAP));
+            }
             Bitmap icon = BitmapFactory.decodeByteArray(res.data, 0, res.data.length);
             if (icon == null) {
                 Log.w(TAG, "failed to unpack icon for " + key.name);
             }
 
             if (!mRestoreEnabled) {
-                if (VERBOSE) Log.v(TAG, "restore not enabled: skipping database mutation");
+                if (VERBOSE) {
+                    Log.v(TAG, "restore not enabled: skipping database mutation");
+                }
                 return;
             } else {
-                // future site of icon cache mutation
+                IconCache.preloadIcon(mContext, ComponentName.unflattenFromString(key.name),
+                        icon, res.dpi);
             }
-        } catch (InvalidProtocolBufferNanoException e) {
-            Log.e(TAG, "failed to decode icon", e);
+        } catch (IOException e) {
+            Log.d(TAG, "failed to save restored icon for: " + key.name, e);
         }
     }
 
@@ -566,15 +576,13 @@
             ArrayList<Key> keys) throws IOException {
         // persist static widget info that hasn't been persisted yet
         final LauncherAppState appState = LauncherAppState.getInstanceNoCreate();
-        if (appState == null) {
-            dataChanged(); // try again later
-            if (DEBUG) Log.d(TAG, "Launcher is not initialized, delaying widget backup");
+        if (appState == null || !initializeIconCache()) {
+            Log.w(TAG, "Failed to get icon cache during restore");
             return;
         }
         final ContentResolver cr = mContext.getContentResolver();
         final WidgetPreviewLoader previewLoader = new WidgetPreviewLoader(mContext);
         final PagedViewCellLayout widgetSpacingLayout = new PagedViewCellLayout(mContext);
-        final IconCache iconCache = appState.getIconCache();
         final int dpi = mContext.getResources().getDisplayMetrics().densityDpi;
         final DeviceProfile profile = appState.getDynamicGrid().getDeviceProfile();
         if (DEBUG) Log.d(TAG, "cellWidthPx: " + profile.cellWidthPx);
@@ -617,7 +625,7 @@
                         if (VERBOSE) Log.v(TAG, "saving widget " + backupKey);
                         previewLoader.setPreviewSize(spanX * profile.cellWidthPx,
                                 spanY * profile.cellHeightPx, widgetSpacingLayout);
-                        byte[] blob = packWidget(dpi, previewLoader, iconCache, provider);
+                        byte[] blob = packWidget(dpi, previewLoader, mIconCache, provider);
                         keys.add(key);
                         writeRowToBackup(key, blob, out, data);
 
@@ -882,7 +890,7 @@
     }
 
     /** Deserialize an icon resource from persistence, after verifying checksum wrapper. */
-    private Resource unpackIcon(byte[] buffer, int offset, int dataSize)
+    private static Resource unpackIcon(byte[] buffer, int offset, int dataSize)
             throws InvalidProtocolBufferNanoException {
         Resource res = new Resource();
         MessageNano.mergeFrom(res, readCheckedBytes(buffer, offset, dataSize));
@@ -1080,7 +1088,7 @@
     }
 
     /** Unwrap a proto message from a CheckedMessage, verifying the checksum. */
-    private byte[] readCheckedBytes(byte[] buffer, int offset, int dataSize)
+    private static byte[] readCheckedBytes(byte[] buffer, int offset, int dataSize)
             throws InvalidProtocolBufferNanoException {
         CheckedMessage wrapper = new CheckedMessage();
         MessageNano.mergeFrom(wrapper, buffer, offset, dataSize);
@@ -1104,6 +1112,23 @@
         return mWidgetMap.get(component);
     }
 
+
+    private boolean initializeIconCache() {
+        if (mIconCache != null) {
+            return true;
+        }
+
+        final LauncherAppState appState = LauncherAppState.getInstanceNoCreate();
+        if (appState == null) {
+            Throwable stackTrace = new Throwable();
+            stackTrace.fillInStackTrace();
+            Log.w(TAG, "Failed to get app state during backup/restore", stackTrace);
+            return false;
+        }
+        mIconCache = appState.getIconCache();
+        return mIconCache != null;
+    }
+
     private class KeyParsingException extends Throwable {
         private KeyParsingException(Throwable cause) {
             super(cause);
diff --git a/src/com/android/launcher3/LauncherModel.java b/src/com/android/launcher3/LauncherModel.java
index f4fa10f..007fd7a 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -318,10 +318,16 @@
                     public void run() {
                         Callbacks cb = mCallbacks != null ? mCallbacks.get() : null;
                         if (callbacks == cb && cb != null) {
-                            callbacks.bindAppsAdded(null, null, null, allAppsApps);
                             if (!restoredAppsFinal.isEmpty()) {
+                                for (AppInfo info : restoredAppsFinal) {
+                                    final Intent intent = info.getIntent();
+                                    if (intent != null) {
+                                        mIconCache.deletePreloadedIcon(intent.getComponent());
+                                    }
+                                }
                                 callbacks.bindAppsUpdated(restoredAppsFinal);
                             }
+                            callbacks.bindAppsAdded(null, null, null, allAppsApps);
                         }
                     }
                 });
@@ -2667,6 +2673,7 @@
                 case OP_ADD:
                     for (int i=0; i<N; i++) {
                         if (DEBUG_LOADERS) Log.d(TAG, "mAllAppsList.addPackage " + packages[i]);
+                        mIconCache.remove(packages[i]);
                         mBgAllAppsList.addPackage(context, packages[i]);
                     }
                     break;
@@ -2862,13 +2869,12 @@
      */
     public ShortcutInfo getRestoredItemInfo(Cursor cursor, int titleIndex, Intent intent) {
         final ShortcutInfo info = new ShortcutInfo();
-        info.usingFallbackIcon = true;
-        info.setIcon(getFallbackIcon());
         if (cursor != null) {
             info.title =  cursor.getString(titleIndex);
         } else {
             info.title = "";
         }
+        info.setIcon(mIconCache.getIcon(intent, info.title.toString()));
         info.itemType = LauncherSettings.Favorites.ITEM_TYPE_SHORTCUT;
         info.restoredIntent = intent;
         return info;