I found that menu_breadcrumb_init() takes so much time when my site execute some jobs such as "poormanscron/run-cron-check". This kind of path did not need breadcrumb at all, but the hook_init() always execute. The worst thing is that when menu_breadcrumb_init() was executed under that kind of situation, drupal_get_breadcrumb() usually get breadcrumbs from navigation menu!! The "navigation" menu is the default active_menu_name and it usually contains very very many menu items. That's why it takes so much time to get breadcrumbs, but usually it is useless because the path which need breadcrumbs usually belong to some custom menu rather than "navigation".

Here's my hack for this issue.

@@ -313,6 +313,7 @@ function menu_breadcrumb_init() {
     $match_cache = variable_get('menu_breadcrumb_pattern_matches', array());
     $menu_list = array_filter(menu_breadcrumb_menu_list()); // enabled menus.

+    $active_menu_name_is_set = FALSE;
     foreach (array_keys($menu_list) as $menu_name) {
       $is_pattern = (substr($menu_name, 0, 1) == '/' && substr($menu_name, -1, 1) == '/');
       if ($is_pattern) {
@@ -321,6 +322,7 @@ function menu_breadcrumb_init() {
           if (array_key_exists($menu_link_menu_name, $match_cache)
               && $match_cache[$menu_link_menu_name] == $menu_name) {
             menu_set_active_menu_name($menu_link_menu_name);
+            $active_menu_name_is_set = TRUE;
             break 2;
           }
         }
@@ -328,29 +330,32 @@ function menu_breadcrumb_init() {
       else {
         if (array_key_exists($menu_name, $menu_link_menus)) {
           menu_set_active_menu_name($menu_name);
+          $active_menu_name_is_set = TRUE;
           break;
         }
       }
     }
   }

+  if ($active_menu_name_is_set) {
    // Generate the breadcrumbs using the active menu.
    $breadcrumb = drupal_get_breadcrumb();
 
    if (variable_get('menu_breadcrumb_append_node_title', 0) == 1) {
      if (variable_get('menu_breadcrumb_append_node_url', 0) == 1) {
        $breadcrumb[] = l(drupal_get_title(), $_GET['q'], array('html' => TRUE));
      }
      else {
        $breadcrumb[] = drupal_get_title();
      }
    }
 
    if (count($breadcrumb) == 1 && variable_get('menu_breadcrumb_hide_on_single_item', 0)) {
      $breadcrumb = array();
    }
 
    drupal_set_breadcrumb($breadcrumb);
+ }
}

I don't choose navigation menu, and move "navigation" menu lower in the settings of menu_breadcrumb, and this just works for me. FYR.