Optimize menu_tree_page_data() performance

@markus_petrux

If you have even a proof of concept patch for this, I will be happy to test D7 and D6 with and without the patch, in order to see if it has a measurable effect.

While the patches might be against Drupal 6, this really needs review and testing against 7.

I benchmarked the D7 version with 5 concurrent users, with a 2 minute test duration

Without patch

Response time:                  0.22 secs
Transaction rate:              23.12 trans/sec
Successful transactions:        2780
Longest transaction:            2.39
Shortest transaction:           0.01

With patch

Response time:                  0.23 secs
Transaction rate:              21.53 trans/sec
Successful transactions:        2569
Longest transaction:            3.69
Shortest transaction:           0.01

So the patch is slower as it stands ... :-(

I ran the test again, with the same parameters (5 users, 2 minute stress test), but hitting only the front page, instead of a combination of the front page (which has lots of nodes on it) and individual node pages.

Before the patch:

Response time:                  0.65 secs
Transaction rate:               7.65 trans/sec
Successful transactions:         919

After the patch:

Response time:                  0.64 secs
Transaction rate:               7.76 trans/sec
Successful transactions:         935

There is a very slight improvement with the patch.

Can others please benchmark this with different scenarios?

Benchmarked with ab, front page with 30 nodes, then an individual node with 90 comments. Results are pretty close to kbahey's:

node
HEAD:
6.54 reqs/sec

Patch:
6.79 reqs/sec

node/n
HEAD:
13.39 reqs/sec

Patch:
12.86 reqs/sec

I used the performance module (part of devel), and this is what I got.

Without the patch 6.75 MB avg

With the patch 6.50 MB avg

So, slight savings on a front page of a relatively simple site.

Did kcachegrind of the front page.

Incl. is total time spent in menu_tree_page_data() and all the functions it calls. Self is time spent only in menu_tree_page_data()

HEAD:
Incl: 116879
Self: 3332

Patch:
Incl: 28075
Self: 602

and node/n
HEAD:
Incl: 54411
Self: 637

Patch:
Incl: 39620
Self: 475

This doesn't explain the reproducible slowdown on node/n pages though.

resetting.

Make sure you don't remove menu items that have their 'alter' flag set to TRUE.

Its possible to dynamically modify those types of menu items so that they are no longer hidden. See http://api.drupal.org/api/function/hook_translated_menu_link_alter/6

HOOK_translated_menu_link_alter() is called during _menu_link_translate() which is called during _menu_tree_check_access(). Which means that HOOK_translated_menu_link_alter() will be called after your trimming of hidden menu items. :-(

Note that none of the performance tests has any kind of error margin. This makes the results worthless for assessing whether this is an improvement.

Physis Lab: FAIL.

subscribing

The issue was marked as a duplicate of #519046: Clean up toolbar menu code, though it seems like the scope of that issue later changed. It contains a reference to #509584: APi fixes for menu_tree_data() including depth param that also contained an optimization, but AFAICT this doesn't completely address the point raised here. Access control is still done on a lot more items than necessarty, so I think it is relevant to reopen this issue.

Markus, do you agree?

How about this? Instead of looking up all items on each level on the menu tree, menu_tree_page_data() can now return only the items in the active trail. This prevents access checks on items outside the active trail when invoked from menu_set_active_trail() that is used by menu_get_active_breadcrumb() and menu_get_active_title().

In an empty D7 install on a randomly selected page, admin/config/regional/settings, the number of calls to _menu_link_translate() is reduced from 46 to 23.

The D6 backport is straight forward (I have attached it for those interested in benchmarking on an existing site). On a D6 site with a lot of menu items, this patch cuts ~15% of the total page generation time on frontend pages, i.e. pages that do not utilize the "navigation" menu. In particular, quite a lot is saved by not retrieving the items with plid == 0 and hidden <> 0.

The menu system is still somewhat black magic to me, so please give this a thorough review.

#27: menu-tree-page-data-1.patch queued for re-testing.

Interesting. Need to think about the non-obvious implications of this patch.

Sidenote: How does this patch relate to #620618: Optimize menu tree building and use it for toolbar ?

From a visual inspection, I think the two patches will complement each other. AFAICT the new menu_build_tree() only kicks in in menu_tree_page_data(), after the $only_active_trail argument has reduced the number of menu items fetched from the database.

Based on a visual inspection I think the two patches will complement each other. AFAICT the new menu_build_tree() only kicks in in menu_tree_page_data(), after the $only_active_trail argument has reduced the number of menu items fetched from the database.

Reroll.

Reroll (what happened to automatic retesting of patches?).

We have been running with the D6 version of this in production on several large sites for two weeks, so far without problems but with a considerable performance boost (in particular on our test server - for some reason).

In the beginning we were a bit confused, because the title of our front page suddenly changed, but it turned out that we had two different links with different titles pointing to the same path. AFAICT the old code makes no guarantee about which trail it returned by menu_set_active_trail() in that case (see the following line in menu_tree_page_data() - there is no ORDER BY), but at least it is stable. This stableness is broken by this patch - it is still stable after the patch, but the trail returned is not the same as before the patch.

  $parents = db_fetch_array(db_query("SELECT p1, p2, p3, p4, p5, p6, p7, p8 FROM {menu_links} WHERE menu_name = '%s' AND link_path IN (". $placeholders .")", $args));

This and #327918: Optimize menu_tree_page_data() performance are duplicates of each other, although the patches are pretty different. I haven't compared the results or anything yet.

@catch: This is #327918 :-)

I always do that :( #620618: Optimize menu tree building and use it for toolbar

Did you see my comment in #32? The issues may be duplicate, but I think the patches in the two issues will complement each other.

#34: menu-tree-page-data-3.patch queued for re-testing.

#34: menu-tree-page-data-3.patch queued for re-testing.

This implements the same optimization as in earlier patches following the refactoring made in #620618: Optimize menu tree building and use it for toolbar.

The 'expanded' and 'only_active_trail' options for menu_build_tree() are mutually exclusive. I don't know if there is a more intuitive way to do this ...

Do we have an actual use-case for this in core?

I think that this new option might make things even worse, since the only use-case I can think of would be breadcrumbs. However, all of the current code can re-use already cached menu tree parameters + cached menu trees, even if those may contain more items than actually needed, but that should still be faster than re-building everything from scratch instead of re-using caches.

I may be mistaken though. Can't really evaluate without actual use-case.

subscribe

The problem in D7 in definitely smaller that it is in D6.

In D7, menu_tree_page_data() is only called from menu_set_active_trail() if the current menu path is found in an active menu (by default the active menus are "navigation", "management", "user-menu" and "main-menu"). In D6 it was always called

menu_get_active_trail() can reuse the cached tree if that has already been generated in the current request (the tree is saved to {cache} also, but the expensive call to menu_tree_check_access() is not). This is the case if the menu is displayed somewhere. However, a lot of modules expose their URLs to the Navigation menu (e.g. each Panels page is exposed this way), and this menu may not be enabled on the site.

On a fresh D7 install, if you disable the Navigation menu on admin/structure/block/list/garland and then load filter/tips as the anonymous user, the patch reduces the number of calls to user_access() from 34 to 27.

Note that I've merged this patch into #576290: Breadcrumbs don't work for dynamic paths & local tasks

This was fixed as part of #907690: Breadcrumbs don't work for dynamic paths & local tasks #2. The D6 patch in #27 still applies.

As mentioned in #35 we have been running with the D6 version in production on several large sites since June without problems. #27 lists some performance metrics.

mmm... note that this patch wasn't merged as is. It required quite some adjustments to make it work correctly and not make it lead to major performance slowdown. Not sure whether it is a good idea to attempt to backport that.

This adopts some ideas from the D7 patch that was committed. Now the static cache ($tree) in menu_tree_page_data() can be reused if the function was already called with $only_active_trail == FALSE.

If scenarios where this reuse fails, there will be a performance hit, because the active trail is looked up twice. In the event that menu_tree_page_data() is only called with $only_active_trail there is a performance win, because we don't have to do access checks on the whole menu tree but only on the active trail. If you have a large menu tree, I would expect the potential win is greater than the potential hit. But I'm not sure how often you would fall into the former case ...

Subscribe - I've traced some performance issues to this function on two of my sites.

+1 for 6.x patch

Reroll.

The patch still applies. The testbot fails due to #961172: All D6 Core patches are failing.

#54: menu-tree-page-data-D6-3.patch queued for re-testing.

59: menu-tree-page-data-D6-4.patch queued for re-testing.