diff -u -r gnome-menus-2.20.0/libmenu/desktop-entries.c gnome-menus-hack/libmenu/desktop-entries.c
--- gnome-menus-2.20.0/libmenu/desktop-entries.c	2007-11-20 17:04:23.000000000 +0000
+++ gnome-menus-hack/libmenu/desktop-entries.c	2007-11-21 11:57:32.000000000 +0000
@@ -65,10 +66,82 @@
  * Desktop entries
  */
 
-static guint
-get_flags_from_key_file (DesktopEntry *entry,
+static void
+check_tryexec (DesktopEntry *entry, const char *tryexec)
+{
+  char *path;
+
+  path = g_find_program_in_path (tryexec);
+  if (path == NULL)
+      entry->flags |= DESKTOP_ENTRY_TRYEXEC_FAILED;
+  g_free (path);
+}
+
+struct DesktopEntryScanState
+{
+    GArray *entries;
+};
+typedef struct {
+    DesktopEntry *entry;
+    char         *tryexec;
+} ScanEntry;
+
+static gint
+compare_by_path (ScanEntry *a, ScanEntry *b)
+{
+    return strcmp (a->tryexec, b->tryexec);
+}
+
+DesktopEntryScanState *
+desktop_entry_scan_state_new (void)
+{
+    return g_new0 (DesktopEntryScanState, 1);
+}
+
+void
+desktop_entry_scan_state_dispose (DesktopEntryScanState *state)
+{
+  int i;
+
+  g_return_if_fail (state != NULL);
+
+  if (state->entries)
+    {
+      // sort by directory to reduce disk I/O ...
+      g_array_sort (state->entries, (GCompareFunc) compare_by_path);
+
+      for (i = 0; i < state->entries->len; i++)
+        {
+          ScanEntry *e = &g_array_index (state->entries, ScanEntry, i);
+          check_tryexec (e->entry, e->tryexec);
+          desktop_entry_unref (e->entry);
+          g_free (e->tryexec);
+        }
+      g_array_free (state->entries, TRUE);
+    }
+  g_free (state);
+}
+
+static void
+desktop_entry_scan_state_add (DesktopEntryScanState *state,
+                              DesktopEntry          *entry,
+                              char                  *tryexec)
+{
+    ScanEntry e;
+
+    if (!state->entries)
+        state->entries = g_array_new (FALSE, FALSE, sizeof (ScanEntry));
+
+    e.entry = desktop_entry_ref (entry);
+    e.tryexec = tryexec;
+    g_array_append_val (state->entries, e);
+}
+
+static void
+set_flags_from_key_file (DesktopEntry *entry,
                          GKeyFile     *key_file,
-                         const char   *desktop_entry_group)
+                         const char   *desktop_entry_group,
+                         DesktopEntryScanState *state)
 {
   GError    *error;
   char     **strv;
@@ -78,9 +152,10 @@
   gboolean   tryexec_failed;
   gboolean   unimportant;
   char      *tryexec;
-  guint      flags;
   int        i;
 
+  entry->flags = 0;
+
   error = NULL;
   no_display = g_key_file_get_boolean (key_file,
                                        desktop_entry_group,
@@ -149,14 +224,16 @@
                                    NULL);
   if (tryexec)
     {
-      char *path;
-
-      path = g_find_program_in_path (g_strstrip (tryexec));
-
-      tryexec_failed = (path == NULL);
-
-      g_free (path);
-      g_free (tryexec);
+      g_strstrip (tryexec);
+      if (state) /* defer scattered I/O */
+        {
+          desktop_entry_scan_state_add (state, entry, tryexec);
+        }
+      else
+        {
+          check_tryexec (entry, tryexec);
+          g_free (tryexec);
+        }
     }
 
   error = NULL;
@@ -170,19 +247,14 @@
       g_error_free (error);
     }
 
-  flags = 0;
   if (no_display)
-    flags |= DESKTOP_ENTRY_NO_DISPLAY;
+    entry->flags |= DESKTOP_ENTRY_NO_DISPLAY;
   if (hidden)
-    flags |= DESKTOP_ENTRY_HIDDEN;
+    entry->flags |= DESKTOP_ENTRY_HIDDEN;
   if (show_in_gnome)
-    flags |= DESKTOP_ENTRY_SHOW_IN_GNOME;
-  if (tryexec_failed)
-    flags |= DESKTOP_ENTRY_TRYEXEC_FAILED;
+    entry->flags |= DESKTOP_ENTRY_SHOW_IN_GNOME;
   if (unimportant)
-    flags |= DESKTOP_ENTRY_UNIMPORTANT;
-
-  return flags;
+    entry->flags |= DESKTOP_ENTRY_UNIMPORTANT;
 }
 
 static GQuark *
@@ -214,7 +286,8 @@
 }
 
 static DesktopEntry *
-desktop_entry_load (DesktopEntry *entry)
+desktop_entry_load (DesktopEntry *entry,
+                    DesktopEntryScanState *state)
 {
   DesktopEntry *retval = NULL;
   GKeyFile     *key_file;
@@ -301,7 +374,7 @@
   retval->name       = GET_LOCALE_STRING ("Name");
   retval->comment    = GET_LOCALE_STRING ("Comment");
   retval->icon       = GET_LOCALE_STRING ("Icon");
-  retval->flags      = get_flags_from_key_file (retval, key_file, desktop_entry_group);
+  set_flags_from_key_file (retval, key_file, desktop_entry_group, state);
   retval->categories = get_categories_from_key_file (retval, key_file, desktop_entry_group);
 
   if (entry->type == DESKTOP_ENTRY_DESKTOP)
@@ -333,7 +406,8 @@
 }
 
 DesktopEntry *
-desktop_entry_new (const char *path)
+desktop_entry_new_scan (const char *path,
+                        DesktopEntryScanState *state)
 {
   DesktopEntryType  type;
   DesktopEntry     *retval;
@@ -362,7 +436,13 @@
   retval->basename = g_path_get_basename (path);
   retval->path     = g_strdup (path);
 
-  return desktop_entry_load (retval);
+  return desktop_entry_load (retval, state);
+}
+
+DesktopEntry *
+desktop_entry_new (const char *path)
+{
+    return desktop_entry_new_scan (path, NULL);
 }
 
 DesktopEntry *
@@ -390,7 +470,7 @@
   entry->terminal = 0;
   entry->flags = 0;
 
-  return desktop_entry_load (entry);
+  return desktop_entry_load (entry, NULL);
 }
 
 DesktopEntry *
Only in gnome-menus-hack/libmenu: desktop-entries.c~
diff -u -r gnome-menus-2.20.0/libmenu/desktop-entries.h gnome-menus-hack/libmenu/desktop-entries.h
--- gnome-menus-2.20.0/libmenu/desktop-entries.h	2007-09-17 19:36:12.000000000 +0100
+++ gnome-menus-hack/libmenu/desktop-entries.h	2007-11-21 09:48:48.000000000 +0000
@@ -33,12 +33,17 @@
 
 typedef struct DesktopEntry DesktopEntry;
 
-DesktopEntry *desktop_entry_new (const char   *path);
+typedef struct DesktopEntryScanState DesktopEntryScanState;
+DesktopEntryScanState *desktop_entry_scan_state_new     (void);
+void                   desktop_entry_scan_state_dispose (DesktopEntryScanState *state);
+DesktopEntry *desktop_entry_new_scan (const char            *path,
+                                      DesktopEntryScanState *state);
 
+DesktopEntry *desktop_entry_new    (const char   *path);
 DesktopEntry *desktop_entry_ref    (DesktopEntry *entry);
+void          desktop_entry_unref  (DesktopEntry *entry);
 DesktopEntry *desktop_entry_copy   (DesktopEntry *entry);
 DesktopEntry *desktop_entry_reload (DesktopEntry *entry);
-void          desktop_entry_unref  (DesktopEntry *entry);
 
 DesktopEntryType  desktop_entry_get_type     (DesktopEntry *entry);
 const char       *desktop_entry_get_path     (DesktopEntry *entry);
Only in gnome-menus-hack/libmenu: desktop-entries.h~
diff -u -r gnome-menus-2.20.0/libmenu/entry-directories.c gnome-menus-hack/libmenu/entry-directories.c
--- gnome-menus-2.20.0/libmenu/entry-directories.c	2007-11-20 17:04:23.000000000 +0000
+++ gnome-menus-hack/libmenu/entry-directories.c	2007-11-21 11:56:41.000000000 +0000
@@ -239,11 +239,12 @@
 static gboolean
 cached_dir_add_entry (CachedDir  *dir,
                       const char *basename,
-                      const char *path)
+                      const char *path,
+                      DesktopEntryScanState *state)
 {
   DesktopEntry *entry;
 
-  entry = desktop_entry_new (path);
+  entry = desktop_entry_new_scan (path, state);
   if (entry == NULL)
     return FALSE;
 
@@ -275,7 +276,7 @@
       tmp = tmp->next;
     }
 
-  return cached_dir_add_entry (dir, basename, path);
+  return cached_dir_add_entry (dir, basename, path, NULL);
 }
 
 static gboolean
@@ -495,6 +496,19 @@
   g_free (uri);
 }
 
+typedef struct {
+    gchar *name;
+    ino_t  ino; 
+} FileEntry;
+
+static gint
+compare_by_inode (FileEntry *a, FileEntry *b)
+{
+    if (a->ino == b->ino)
+        return 0;
+    return a->ino > b->ino ? 1 : -1;
+}
+
 static gboolean
 cached_dir_load_entries_recursive (CachedDir  *dir,
                                    const char *dirname)
@@ -503,6 +517,9 @@
   struct dirent *dent;
   GString       *fullpath;
   gsize          fullpath_len;
+  DesktopEntryScanState *state;
+  GArray        *files;
+  int            i;
 
   g_assert (dir != NULL);
 
@@ -522,14 +539,11 @@
 
   cached_dir_ensure_monitor (dir, dirname);
 
-  fullpath = g_string_new (dirname);
-  if (fullpath->str[fullpath->len - 1] != G_DIR_SEPARATOR)
-    g_string_append_c (fullpath, G_DIR_SEPARATOR);
-
-  fullpath_len = fullpath->len;
-
+  files = g_array_new (FALSE, FALSE, sizeof (FileEntry));
   while ((dent = readdir (dp)) != NULL)
     {
+      FileEntry ent;
+
       /* ignore . and .. */
       if (dent->d_name[0] == '.' &&
           (dent->d_name[1] == '\0' ||
@@ -537,23 +551,45 @@
             dent->d_name[2] == '\0')))
         continue;
 
-      g_string_append (fullpath, dent->d_name);
+      ent.name = g_strdup (dent->d_name);
+      ent.ino = dent->d_ino;
+      g_array_append_val (files, ent);
+    }
+  closedir (dp);
 
-      if (g_str_has_suffix (dent->d_name, ".desktop") ||
-          g_str_has_suffix (dent->d_name, ".directory"))
+  // sort by inode to reduce disk I/O ...
+  g_array_sort (files, (GCompareFunc) compare_by_inode);
+
+  fullpath = g_string_new (dirname);
+  if (fullpath->str[fullpath->len - 1] != G_DIR_SEPARATOR)
+    g_string_append_c (fullpath, G_DIR_SEPARATOR);
+
+  fullpath_len = fullpath->len;
+
+  state = desktop_entry_scan_state_new();
+
+  for (i = 0; i < files->len; i++) 
+    { 
+      char *name = g_array_index (files, FileEntry, i).name;
+      g_string_append (fullpath, name);
+
+      if (g_str_has_suffix (name, ".desktop") ||
+          g_str_has_suffix (name, ".directory"))
         {
-          cached_dir_add_entry (dir, dent->d_name, fullpath->str);
+          cached_dir_add_entry (dir, name, fullpath->str, state);
         }
       else /* Try recursing */
         {
-          cached_dir_add_subdir (dir, dent->d_name, fullpath->str);
+          cached_dir_add_subdir (dir, name, fullpath->str);
         }
 
       g_string_truncate (fullpath, fullpath_len);
+      g_free (name);
     }
 
-  closedir (dp);
+  desktop_entry_scan_state_dispose (state);
 
+  g_array_free (files, TRUE);
   g_string_free (fullpath, TRUE);
 
   dir->have_read_entries = TRUE;
