Optimize _menu_navigation_links_rebuild()

I don't see that the new 3rd param to menu_link_save() is used any place.

     // Make sure no child comes before its parent.
     array_multisort($sort, SORT_NUMERIC, $menu_links);
 
-    foreach ($menu_links as $item) {
+    foreach ($menu_links as &$item) {
       $existing_item = db_select('menu_links')

...

       }
       if (!$existing_item || !$existing_item['customized']) {
         $item = _menu_link_build($item);
-        menu_link_save($item);
+        menu_link_save($item, $existing_item, $menu_links);
       }
     }
   }

vs:

+      foreach ($menu_links as $link) {
+        if (isset($link['mlid']) && $link['mlid'] == $mlid) {
+          $parent = $link;
+        }
+      }

The only items in $menu_links that can possibly have a mlid are those that have already been passed through menu_link_save(). As a consequence, it would make more sense to me to build a separate array keyed by mlid and avoid the expensive scan.

@catch: well you can progressively prune the initial array if you like.

I meant pruning the links from $menu_links when we have processed them. Also, it might make sense to *also* keep the customized links:

       if (!$existing_item || !$existing_item['customized']) {
         $item = _menu_link_build($item);
-        menu_link_save($item);
+        menu_link_save($item, $existing_item, $menu_links);
       }

... as this doesn't currently update $item with its mlid if an existing item exists and is customized.

subscribing

Looks reasonable to me. We're gonna need donquixote or chx or pwolanin here I think.

I'll take a look at it later today - maybe see you tonight Moshe.

@catch - query count is the same as the prior patch, or the same as without the patch? It seems like the patch must result in a significant reduction in queries compared to unpatched core.

The logic of the code looks good to me.

Can you backport this patch to 6.20 here http://drupal.org/node/593682 ?

subscribe

@Moshe (#23):
This is buried too deep in my head atm to review.
Still, I definitely want to be subscribed.

Looking at it:
I initially had the idea that we would totally bypass menu_link_save(), and have some kind of chunked bulk update instead.
That said, if this rather simple patch can significantly speed things up (which I have not tested yet), then I'm all for it.

I wonder if it can be backported to D6.

[side note]
For my own sites I was already thinking about skipping this part of menu rebuild (which would be a core hack, yes). I don't need the navigation menu, and I have my own solution for admin menu. I wonder if _menu_navigation_links_rebuild() is necessary for anything else? All other menus' items are considered "customized", so _menu_navigation_links_rebuild() leaves them untouched - afaik.
[/side note]

@catch: what do you suggest? No way to speed up admin UI on thousands D6 existing installations? Bad. If donquixote make something viable my big thanks to him!

subscribe

@catch, the best way I see to help developing is to implement automated testing system for D6 too :) - at least I know what SimpleTest module already backported to D6 in Pressflow. Probably testing architecture much complex than I know, but anyway this is a very good thing for all D6 users, much better than immediate upgrade to D7. I think, users will send D6 patches at least a year more.
You also do not reject patches only because you can't test it automatically. Yes, we can have side effects with these patches, but we can fix it manually... and fix again... and release finally, improving engine at the end. Performance issues ones of important thing for Drupal any version I think.
I create bug in Pressflow's Launchpad for that, but looks like they pre-moderate bugs and decline it by undefined cause. Or I misunderstand his UI :(

Getting stuff backported to D6 at this stage, if it's not a security bug, is probably impossible :) I haven't had any luck with #235673: Changes to block caching mode not caught. So I just end up applying a handful of patches to my production D6 sites manually.

Yes, we can have side effects with these patches, but we can fix it manually... and fix again... and release finally, improving engine at the end.

I disagree with this suggestion. The process of making improvements, discovering side effects, fixing them, and thereby improving Drupal, is what the version of Drupal that is in development is for. Which until recently was Drupal 7, and will soon be Drupal 8. A released and widely used version (e.g., 6) of Drupal core is frozen: minor updates (e.g., 6.20 to 6.21) are for bug fixes that are either critical (e.g., security) or without risk of side effects (e.g., fix a typo).

There may be a lot of people who will continue using Drupal 6 for a while, and they may want performance improvements, but they can get that by patching their installation, or using a distribution like Pressflow.

Creating a backported patch of #22 is worth doing, as is using the issue queue to collaborate, review, and share results about that patch. Anyone is welcome to create such a patch and open a new issue for it, or wait until this patch is committed to D7, and then continue using this issue for the D6 backport. But I don't think it makes sense to expect a D6 backport of this to be committed to CVS, unless it can be sufficiently shown to have 0 side effects. The D6 maintainers, Dries and Gabor, make the final call on what constitutes "sufficient", and they're both very reasonable in taking community input into account.

Every once in a while, people bring up the desire to have more improvements happening in minor updates instead of all being pushed into the next major one. With Drupal 7 released and including good automated test coverage, it's a good time to have that discussion again, with respect to how frozen we want D7 to be now that it's released. But that discussion won't change what we do for D6, and please, let's not have that discussion here. Here's one place: #586146: [policy, no patch] Decide if and how to implement semantic versioning for Drupal 8.x, though if anyone knows of a better one, please add a comment to that issue linking to it.

BTW: I support this patch going into D7, because although it too is an already released version, we've always been a little more liberal in what we allow into the first few minor updates of a new major version.

Can't we add an _menu_link_save(&$item, $existing_item = array(), $parent_candidates = array())? So we don't alter the API?

menu_link_save() could call _menu_link_save(), no need for duplication.

Another optimization: #1034732: API additions: menu_link_load_multiple() and menu_link_delete_multiple(). that one could use the $existing_item parameter too, in _menu_link_delete_multiple().

subscribe (I would definitely love to see a D6 version of this, even if it's something that doesn't make it in. Still useful, and as mentioned above, it could be Pressflowed...)

I don't want to stop this patch, but I'd like to point out two related things, that might make an even faster nav links rebuild possible.

#512962: Optimize menu_router_build() / _menu_router_save()
The latest patch will make it possible to let the nav links rebuild know which of the router items have changed.
Btw, this thing needs attention / feedback.

#1170278: Introduce hook_menu_router_update()
This would be the mechanism to let nav links rebuild know about the changes.
Depends on the other issue.

Doing this does not mean we no longer want this patch. There might be situations where no router diff is available, or the full router table has changed.

Almost RTBC but

+        $parent_candidates[$item['mlid']] = $item;
+         unset($menu_links[$key]);

that's a whitespace error before unset.

Well then

This seems like a great little backwards-compatible performance improvement. Really sorry, I have no idea how it stayed off the radar so long. :(

Committed and pushed to 8.x and 7.x. Thanks!

Confused about the status of this patch; which (if any) is the d6 version of the patch to review?

Some feedback:
I did some xdebug on a D7 test site, with a recent version of D7, and this is still undesirably slow.

drupal_flush_all_caches            = 15,26 seconds
  menu_rebuild                     = 9,33 seconds
    _menu_navigation_links_rebuild = 7,07 seconds
    menu_router_build              = 1,54 seconds
    _menu_router_save              = 0,43 seconds
  [..] (e.g. features_flush_caches     = 2,14 seconds)
  registry_rebuild                   = 2,58 seconds

Re #63
Probably the current solution is still the best that we can get without breaking anything.

------

I am currently working on a rewrite of _menu_navigation_links_rebuild(), which promises to be quite fast. That is, it will really make a difference.

Unfortunately, it might be a bit fragile when backported to D7, due to hook_menu_link_alter().
I have the feeling this is not a very well-designed hook.

The way out:

• #1170278: Introduce hook_menu_router_update()
  This will allow contrib to kick the smelly core implementation of _menu_navigation_links_rebuild() and replace it with something else, without being overly concerned about compatibility.
• #512962: Optimize menu_router_build() / _menu_router_save()
  Diff-based rebuild of menu_router, so that the diff can be available to _menu_navigation_links_rebuild().
  I originally thought this should be done before we introduce hook_menu_router_update(), but actually it doesn't matter. We simply extend the signature of hook_menu_router_update(), adding additional arguments for the diff.
• D8 will revamp all of this with Symfony stuff?
  Well, this might be the case. But we still want these improvements for D7.
  So we should get them into D8 for backport to D7, before Symfony makes all of this unportable.

I am working on a rewrite in a separate issue.
#1830274: Support a parent_path setting in hook_menu(). / hook_menu_link_alter() should not touch the plid.
Speed improvement is between 2x and 3x.

As mentioned, what makes this more difficult is the drupal_alter('menu_link').
This hook itself is ok, but the pain comes when modules alter the plid of the item.

If this stops to happen, we can have a more predictable logic:
- non-customized items always get their parent link id only from hook_menu().
- customized items either keep the parent link they had before, or they move up.

hook_menu_link_alter() should not have a say in this.

Not much activity here, and Drupal 6 is depreciated.
Fixed in 8.x and 7.x according to #59

Putting this back to the last fixed version, in that case.