Cache localized, access filtered, URL resolved, and rendered menu trees

1. I think we have to accept #1 and make this a non page-specific cache. I agree that the caller can tweak from there. I'd be fine with tweaking happenning in PHP or JS.

3. The menu block is only relevant if we don't show the mobile toolbar to desktop sized browsers. Why would one want a the menu block along with a toolbar? The only other use case I can think of is quick-navigation widget like what some of the toolbar designs have shown. It would be an autocomplete which whisks you to the selected admin page upon submit.

@moshe, with the menu block I meant it'd be good if we could cache that more efficiently, currently that's some of the least efficient caching we have (has to be calculated, if not stored uniquely, per page, access checks (which can load entire views, entities etc.) run during runtime, full rendering from the big array that we store in the cache). It also happens to be in core already.

Not sure why we'd need to cache by both user ID and session ID, that potentially means different cache entries for anonymous users if they have a session and I can't think of a use case for that - maybe admin_menu has some per-session logic it specifically has to account for or something?

Tagging it with Spark, as it is relavant for Spark.

re: Personally, I'd like to see all of the menu state code (active, expanded, active-trail) move from the server to the client. It gives us the boost of eliminating per-page cacheing.

I think we have some room to explore different combinations of server-side versus client-side DOM list building. Our options are:

• Send the full menu tree, without page-specific state markup, as HTML from the server. This is results in highly-cacheable output.
• Send some subset of the full menu tree, again without page-specific state markup, and get sub-page trees asynchronously when the user drills down the menu. This reduces the initial page payload but might have deleterious effects on perceived page speed for users who frequently use deep menu structures to navigate their site.
• Send menu data as JSON asynchronously and render menus some time soon after post DOM load. This would add a hard dependency on JavaScript for admin functionality.

I just ran some base-line speed tests with a small and obscenely-large set of links in unordered lists. I used Charles to simulate throttled bandwidth and measured performance with Chrome's Network tab. Here are the results for combined wait/receive time:

110 links in a nested (2 levels) ul element.

unthrottled/cable: 3ms
256 kbps/DSL: 303ms
3g: 696ms

1110 links in a nested (3 levels) ul element.

unthrottled/cable: 4ms
256 kbps/DSL: 2670ms
3g: 1330ms

5555 links in a nested (3 levels) ul element.

unthrottled/cable: 4ms
256 kbps/DSL: 14048ms
3g: 4560ms

11,110 links in a nested (4 levels) ul element.

unthrottled/cable: 6ms
256 kbps/DSL: 27900ms
3g: 84300ms

A standard installation of D7 with the Administration module installed (so that we get dropdowns) has 154 links in the toolbar menu.

The Drupal Gardens site, which has the Administration menu installed and a lot of modules enabled has 683 menu links loaded on each page. That is still well shy of the 1110 links in the chart above where page load begins to be affected on 3g by a large menu. Still, it's enough time to warrant exploring hybrid options to load top levels of a menu and deeper sub-levels with some asynchronous method.

To sum up, we shouldn't have to treat the toolbar menu with special gloves in terms of cacheing. We put in sensible, per user cacheing (perhaps even per-role? I'm waiving my hands here, this is not my area of expertise), returned a rendered HTML list and leave the state decoration (current page, active path) for the client to deal with (that I can do). The Administration menu module already has a lot of excellent front end code we can leverage for that part of the built-out.

We could also get rid of this option for menu links, which has always driven me mad, especially when I need to edit every link in a complex menu to get it to display as a full tree.

I'm not comfortable with caching access/per-user. It will result in too many cache items on large sites (essentially: users x menus).

But the idea of caching the "rendered" link makes sense to me.

However, that requires a lot of additional context info for the cache item that contains the rendered links:

- HTTP vs. HTTPS
- conf_path() / HTTP_HOST / domain (in case an absolute link is contained)
- language
- last timestamp of a changed string tanslation
- theme key (also: theme vs. admin_theme)
[potentially more; these are the most obvious only]

- ?destination
- active trail
- session (link tokens)

Furthermore, the link rendering would have to happen in a special context that is exempt of user permissions; i.e., all links need to be accessible to be rendered and cached.

Inaccessible links would be removed when the cached menu link tree + cached menu links are rendered for the current user. This could potentially allow us to merge the rendered links into the cached menu link tree even.

[snip]

Now that I wrote this, I just added ?destination and active trail to above list of cache contexts. These are the two major problems that admin_menu solves after the fact on the client-side:

admin_menu makes sure that the cached output does not contain an active trail, and dynamically injects the active trail classes into the rendered menu links for the current page.

admin_menu also replaces every instance of ?destination=... in all links that have a destination for the currently rendered page.

Lastly, admin_menu caches per user, because links may contain drupal_get_token() session token query parameters.

Doing that makes sense for admin_menu, because there is usually only a very small subset of administrative users on a site, even on large-scale sites. E.g., even if there are 1,000,000 users on a community site, there are usually only ~10-500 users with access to the site administration, which results in the equivalent amount of caches.

Hrm. Overall, I do not think it is feasible to change this for all menus in core. The performance of rendering large menu trees is certainly a problem, but from my perspective, the current build/access/render process is well thought-out and takes all context possibilities into account that might have an impact on the final output.

admin_menu is only able to choose a different approach, because it is a single use-case, because it knows exactly how and where the rendered menu tree is used, and because it renders the specific menu tree of administration links. Without that advantage, the amount of contexts is factually unlimited.

Honestly, I think this is a lot of complexity that menu.inc should not contain.

It wasn't really easy to follow/understand what the new code is doing, and under which (special) conditions (and when not).

Is there any way we could allow modules/consumers to achieve the same, without adding even more complexity to menu.inc?

Although I'm still not sure whether it is appropriate to "hack" a core subsystem in this way, mainly to improve the performance of a number of core/contrib modules that I can probably count on one hand?

That said, I also wonder what the actual (performance) situation with the new Symfony router looks like - the new router itself shouldn't have an impact, but our current menu link tree building is deeply intertwined with the (old) router...

Reclassifying as a feature, since the only issue being blocked by this is a feature request as well, and I assume we surely don't want to block other, ready patches due to this issue.

#15 still caches per-user (and lacks session_id(), btw). An acceptable amount of caches for such a generic implementation would be per-role[s], but that would inherently break menu access checks/restrictions for link-specific endpoints being backed by e.g. node_access().

I'm confused by sun's per-user caching comment.

Current menu caching:

- menu trees are calculated on every page, then the hash of the tree is calculated.
- two cache entries are stored, a cid for the page, pointing to the hash. Then a cid with the hash, pointing to the tree.
This is designed to prevent massive filling-up of the menu cache bin (which was a critical Drupal 6 bug report).

If we move to per-user caching, then that doesn't necessarily mean more cache entries at all.

On most sites I work with, there's a vast quantity of traffic to tens or hundreds of thousands of unique paths every day from search engine crawlers. These currently require a cache entry for each individual page per menu. Per-user caching would mean a single entry per-menu for all of those bots, since they'd all be anonymous requests.

There'll be some sites with many, many authenticated users, but you'd need tens to hundreds of thousands of unique authenticated user requests each day to get anywhere close to the number of cache misses that there currently are with core.

Once we have a generator (the Symfony version of url() for internal paths), I'd expect menu tree generation to get more expensive, additionally if menu items become entities that'll probably come with some performance overhead as well. See also the discussion on #1793520: Add access control mechanism for new router system which is sort of the counterpart to the toolbar issue since they'll compound each other quite significantly.

Given #916388: Convert menu links into entities I think this is a more appropriate status. It may need to be bumped to critical again if either of those patches goes in before this one and we find a measurable performance regression.

I doubt that we have any sophisticated tests for menu caching and cached rendering currently. So if we want to change this, then I'd suggest to start with writing tests for all the special cases outlined in #14.

I would like to support Jesse's and eff idea of a JSON rendered output

The output can be embedded directly in the HTML (printed in the template), to avoid the delay. There is no need to make it via AJAX, but it could be used the same code to create an on-demand expanding tree. #1814932: Caching strategy for D8 toolbar

This solution will help to make a fast search/autocomplete, since the data is already in native format. No need to parse the html.

// Use it
// $tree = toolbar_get_menu_tree();
// json_encode (toolbar_get_filtered_tree($tree)); // output this in the toolbar template

function toolbar_get_filtered_tree($tree){
  // [[  Cache stuff here  ]]
  // Inject not-cached variables: Current path, language, etc and additional context info that @sun posted
  return toolbar_recursive_filter_tree($tree);
}

function toolbar_recursive_filter_tree($tree, $level = 0, &$result = array()){
  $i = 0;
  foreach ($tree as $key => $menu) {
    if (empty($menu['link'])) continue;
    $result[$i]['title'] = $menu['link']['title'];
    $result[$i]['href'] = $menu['link']['href'];
    $result[$i]['weight'] = $menu['link']['weight'];
    $result[$i]['depth'] = $level;
   // more attributes ?? (white-listing assignment )
    if (!empty($tree[$key]['below'])) {
      $result[$i]['below'] = toolbar_recursive_filter_tree($tree[$key]['below'], $level + 1);
    }
    $i++;
  }
  return $result;
}

I did it for a prototype, and it works (except that tasks are mixed with regular links). For a simple example of how to use the rendered json data in JavaScript to render a navigation menu: (see var jsontree)
http://drupalmotion.com/sites/default/files/demos/toolbar/demo1.js

The big caveat (the elephant in the room): This won't work in Javascript disabled browsers. So it's not a generic solution for every single menu. But it will adapt very well to the toolbar case (autocomplete, dynamic collapsing tree, etc )

This could probably use a issue summary update (doc: http://drupal.org/node/1427826)

since this is at needs review, instead of needs work... I'm guessing a reroll (http://drupal.org/patch/reroll) might be useful.

#15: menu-cache.patch queued for re-testing.

re-roll

#26: 1805054-26.patch queued for re-testing.

I'm not sure what "failed to run tests" indicates.

the testbot faq: http://drupal.org/project/testbot might help

@jibran, where there any conflicts when you did the re-roll?

Maybe check the testbot number...
this might also provide a clue: #1878216: Bot #664 disabled (repeatedly failed to run tests)

nope no conflicts simple merges
here is the merge if it helps.

git rebase 8.x
First, rewinding head to replay your work on top of it...
Applying: Patch from http://drupal.org/node/1805054#comment-6596618
Using index info to reconstruct a base tree...
M       core/includes/menu.inc
M       core/modules/toolbar/toolbar.module
Falling back to patching base and 3-way merge...
Auto-merging core/modules/toolbar/toolbar.module
Auto-merging core/includes/menu.inc

#26: 1805054-26.patch queued for re-testing.

Replaced a call to drupal_array_set_nested_value() with NestedArray::setValue() as per
#1705920: Convert all calls to procedural drupal_array_*() functions to Drupal\Component\Utility\NestedArray

Another reroll had conflict in menu.inc

@@@ -1398,8 -1483,12 +1471,17 @@@ function _menu_build_tree($menu_name, a
  
      // Build an ordered array of links using the query result object.
      $links = array();
++<<<<<<< HEAD
 +    if ($result = $query->execute()) {
 +      $links = menu_link_load_multiple($result);
++=======
+     $min_depth = 0;
+     foreach ($query->execute() as $item) {
+       $links[] = $item;
+       if (!$min_depth || ($item['depth'] < $min_depth)) {
+         $min_depth = $item['depth'];
+       }
++>>>>>>> patch from 35
      }
      $active_trail = (isset($parameters['active_trail']) ? $parameters['active_trail'] : array());
      $data['tree'] = menu_tree_data($links, $active_trail, $min_depth);

Resolved like this

     if ($result = $query->execute()) {
+      $min_depth = 0;
       $links = menu_link_load_multiple($result);
+      $min = min(array_map(function($item){ return $item['depth'];}, $links));
+      if (!$min_depth || ($min < $min_depth)) {
+        $min_depth = $min;
+      }
     }

Next reroll will be in next 2 months.

Raised related #1927174: Complete the work to make the Toolbar administration menu sub tree rendering more efficient to critical.

#36: 1805054-36.patch queued for re-testing.

I will work on the issue summary

#36: 1805054-36.patch queued for re-testing.

#36: 1805054-36.patch queued for re-testing.

updated issue summary

Updated issue summary. Test bot was misbehaving at the time of the retest.

Updated issue summary.

Updated issue summary.

Updated issue summary.

Updated issue summary.

Related: #2005644-35: Use client-side cache tags & caching to eliminate 1 HTTP requests/page for in-place editing metadata, introduce drupalSettings.user.permissionsHash, especially the "More generally…" part.

Rerolled and fixed the constant notice issue.

Eliminate use of global $user and document new arguments (and add type hints). Reviews welcome!

Of course languages also changed to have 'id' properties not 'langcode' in the meantime :)

I don't know where did I get 'account' from as the attribute name. It should be '_account'. Also uid is not a public property, so we need to use id(). Should be better.

I ran into a problem with the output of the cache_menu, as well. I had to change the bin name from cache_menu to menu.

Calling language() has apparently been deprecated as well.

Let's go testbot!

Same patch as #54, this time without the do-not-test, so that testbot takes notice.

effulgentsia, Gábor Hojtsy and I had a chat about how to further improve the cacheability of the menus. We came up with two changes that reduce the contextual variability of a rendered menu, shifting context and behavior decisions from the server to the client.

1. Deliver the full menu tree to a specified depth; qualify expanded branches with a data attribute; hide unexpanded, non-active-trail branches with client-side code.

Whether or not a menu is expanded is a decision that should be made on the client side, where context is available. The suggestion to expand a menu can be made on the client side, as is done today, but instead of shifting the content that gets returned based on the context of the request path, we simply deliver the same menu structure, with an attribute like data-drupal-menu-expand on the li elements that should be opened, and let client-side code do the proper presentation and behavior embellishments.

2. Render the active trail qualification on the client-side using the currentPath setting.

Active trail in a menu is easily derived on the client side. We shouldn't have to make menus uncacheable just to inject this highly contextual bit of information.

Implementation

These changes will require some tweaking to the PHP code for menus, but not much. I will build the menu client side code to do the expansion and active trail marking. Much of this code exists in the Toolbar module, so I plan to pull that code into more generic files and make the behaviors available to any module.

Is data-drupal-menu-expand a kind of data that the toolbar would need or does it keep track of what was opened on its own anyway? Eg. if I navigate to http://myd8site/#overlay=admin/config/content/formats now via the menu, so long as I reload the page, the menu will not be open. The configuration item will be marked as active (based on it being generated from the menu system with active trail I guess) but none of the rest of the items are open. Is this the expected behaviour? Then I don't see a need for additional context specific data in the menu tree. (Not having that would let us cache the menu client side for multiple pages as well, which would be a huge win). If we don't need that info, then this issue is getting pretty close I think?

The data-drupal-menu-expand would indicate the state of the expand checkbox on the menu link config. Presently, if the checkbox is unchecked, we don't deliver the HTML for the sub tree. Under this the proposed behavior, we deliver the full tree for all links (to the depth requested) and those links that have the expand checkbox checked will have the data-drupal-menu-expand attribute applied to them.

Oh, great. The menu code does expansion based on the expand flag and the active trail, so I mashed up the two too much. Thanks for the clarification! That sounds good. Looks like an easy addition to this patch.

nod_ has been working on active link decoration in the client (removing the 'active' class from the l() function) here: #1979468: ".active" from linkGenerator(), l() and theme_links() forces an upper limit of per-page caching for all content containing links.

After an epic debug session I figured out the patch fails because on 403 pages (in general!), the request does not contain an _account at the point when the menu system wants to get it (for toolbar_toolbar()). I reproduced this with other 403 pages like the filter format delete page. Only the shortcut set test catches this because the toolbar tests have no 403 testing and only the shortcut tests have toolbar enabled as well.

This is pretty late in the request in toolbar_toolbar() (my original assumption was that it is related to routing items being resolved, but that was a dead end), so why that would be is not entirely clear to me. However, if we don't have a user, we cannot really cache it for the user anyway (and we should not cache it for anonymous), so I added one more condition and no caching when there was no user identified. This works on 403 pages for me now.

Did not yet add the data attribute, but that would be next.

@Gabor sounds like you ran into #2062151: Create a current user service to ensure that current account is always available.

And #2064585: Shortcuts missing if you view a route's page, that doesn't have a corresponding hook_menu().

More 403 problems if that's your thing: #2063303: A Drupal 8 AjaxResponse that must return a 403, returns a 403 and prints "A fatal error occurred: ".

So we can work around #2062151: Create a current user service to ensure that current account is always available pretty simply here for now. Any concerns with this patch specifically? :)

However, if we don't have a user, we cannot really cache it for the user anyway (and we should not cache it for anonymous), so I added one more condition and no caching when there was no user identified.

Since we're optimizing the generic menu building code, it might be possible to render a menu for a anonymous user, no? So what about cacheing menu output for the anonymous user? A list of navigation links exposed to non-authenticated users seems a likely case where we'd want to cache the rendering for anon users.

Nonono, we can and should (and already do) cache for anonymous. If the user is not there, we cannot tell if it was an anonymous user or not, so my comment just concerned that situation. If the user is there, the uid may still be 0 (drupal_is_anonymous() used to be useful for this, now there may be a method on the user). So long as we don't have a user, we cannot cache it by user :)

I polled a few themers/site builders in my office to get some diversity of opinion on this topic. Here's what I came away with:

It's very frustrating to create a sub-menu item, go out to your site to preview the menu and find that the menu item isn't displayed on the page. This happens when the user fails to click the expand checkbox on the menu item's parent.

Solution: The expand checkbox should be selected by default.

We only want to hide sub-menus when JavaScript is functioning. In the case that a JavaScript error occurs on the page or JavaScript is disabled, we want sub-menus to be accessible, so a blanket display none of non-expanded sub-menus is not desired. For instance, the following code would be bad

/* This is a negative example */
.menu .menu {
  display: none;
}
.menu .expanded {
  display:block;
}

Because it assumes that sub-menus are hidden until exposed. We rather want sub-menus to be accessible/visible by default and condensed/hidden as the context demands (progressive enhancement). We'll get this by adding a data attribute to sub-menu parent items that do not have their expand check box setting checked.

Solution: add a data attribute data-drupal-menu-collapse to sub-menu item parents that are not configured to be expanded.

This seems to be the place in menu_tree_output where we want to intervene to get the data attribute data-drupal-menu-collapse

// Set a class for the <li>-tag. Since $data['below'] may contain local
// tasks, only set 'expanded' class if the link also has children within
// the current menu.
if ($data['link']['has_children'] && $data['below']) {
  $class[] = 'expanded';
}
elseif ($data['link']['has_children']) {
  $class[] = 'collapsed';
}
else {
  $class[] = 'leaf';
}

The problem I'm having is that $data['below'] is not populated if the menu item has sub-items in general; it's only populated if the current request for data has resulted in sub-items being rendered. So maybe we need to intervene before getting to this function. If we always render the entire tree, then $data['below'] should be true when the menu item is a parent of sub-items.

Solution: The expand checkbox should be selected by default.

I think this is out of scope for this issue. We deal with performance improvements here. Arguing about form defaults may push this off too far :/

Solution: add a data attribute data-drupal-menu-collapse to sub-menu item parents that are not configured to be expanded.

Sounds like you suggest either having an expand or a collapse data attribute then (and none if the item is a leaf?). Can you clarify that?

I'm spinning on the PHP part of this patch, so I'm going to jam in whatever I need to get the approximate output of the attribute I want on menu links with sub-items. I'll get the JS bits into the patch and hopefully someone else will correct the PHP part :)

I see you may have hit some issues (also based on your recent tweets). Here is a simple version I worked out. This will put on a collapse or an expand attribute based on the setting for the menu item.

Note that the caching on the menu is pretty aggressive, so editing the menu item will not make it appear properly changed in the rendered tree. You need to clear cache for now.

Is this what you have been looking for? I double-checked that this makes collapse appear on items that did not have the checkbox checked and expand only on those that did.

Also fixed the performance proof code to do something useful :D On my machine the cached version is over 2x as fast. 11.6ms vs. 4.3ms.

Maybe > 0 bytes would be better :D

I'm working in #1979468-101: ".active" from linkGenerator(), l() and theme_links() forces an upper limit of per-page caching for all content containing links to get the active link and trail marking resolved.

#75: 1805054-74.patch queued for re-testing.

This seems really premature given how much change is left to do for menu links to make them work properly with routes.

@pwolanin: Wait, what this patch does it allows to skip active trail marking, so the rendered menu can be cached. How is that related to where the menu data comes from (routes or whatnot)?

@Gabor - ok, maybe it doesn't' need to be postponed, but a bunch of it will need to be re-written since e.g. url() will not be the way most links are rendered.

Is there an expected timeframe on those conversions? We'd love to have this in sooner than later. :)

Dear core/ D8 menu maintainers, apologies for this cross-post.
Please take a look at the #1978176: Build menu_tree without loading so many objects, which contains a D7/D8 performance patch for the menu build (see the 'related issues' in the issue summary for the symptoms). (One error is a problem with cached menus..)
My main question is:
- is the proposed patch/solution also valid for D8? Since it does not touch the new menu router system?
- Is the current D7-menu building system still supported in D8, will it be fased out, or will it exist next to the new system?
Depending on the answer, I will continue to work on that issue.

Updated issue summary.

Bumping to critical again. We can stick it back to major if profiling shows there's no problem, but that seems extremely unlikely.

Patch no longer applies.

Capturing a brainstorm on this with @effulgentsia and @msonnabaum. We noted that discussion on this issue predates #post_render_cache. So,

1. Render cache a localized menu that varies per page but not per user. Let's call this A.
2. In a #post_render_cache, apply menu access checks for the current user, If we are still too slow ...
   1. Inside of A, cache the ids of the menu items in the menu.
   2. In a separate cache, cache the results of entity access check for each menu item.
   3. In #post_render_cache, use those cache results to quickly filter out inaccessible menu items.

We also discussed that we will hopefully soon have #597236: Add entity caching to core. This affects the discussion here but it isn't quite clear how.

Wim just educated me about menu block caching since #2158003: Remove Block Cache API in favor of blocks returning #cache with cache tags. We now cache menu blocks per language and per role. Sites that do more crazy access checks can disable caching for this block and implement other strategy. Should we call this issue Won't Fix?

OK, lets go with Won't Fix as per #88. Feel free to reopen if you disagree.

@effulgentsia - yes, I think the bug you outline could happen. In Drupal 7 unpublished nodes were never shown in menu blocks. In Drupal 8 they are.

However, this seems like this could happen for any entity where you can have per-user access be different based on status or some other flag.

Yes 'view own unpublished content' makes this critical.

@pwolanin we have #2099137: Entity/field access and node grants not taken into account with core cache contexts for contrib modules to affect render cache granularity, and #post_render_cache, so contrib has at least two methods to ensure cache correctness. However where the cache granularity is broken in core we should fix that in core.

I worked on #2254865: toolbar_pre_render() runs on every page and is responsible for ~15ms/17000 function calls yesterday, which showed huge perf win potential. 15% speed win on a full node page. 33 DB queries less. Turns out it was because I had stupidly failed to notice I was caching a menu tree… incorrectly, of course. Which brings me to this issue. I'm taking this on because it's sorely needed.

By making menu blocks cacheable, I also introduced that "view own unpublished content" bug.

I will be able to leverage some of #2224861: Cache SystemMenuBlock and BookNavigationBlock per active trail (currently cached per URL, this breaks on very long URLs). I'll first read through the entire issue, but will probably apply a strategy like the on in #86.

I've now been working on this quasi non-stop since #94 — a week ago. I'll post 2 comments: one with the general approach, and one with the patch that I have so far — but it will not apply to HEAD since I haven't found the time yet to rebase. You should be able to review the overall approach though.

The 90% of the problem space that already has solutions

Having read this entire issue, I think sun's comment in #14 is the single most important comment:

[…] the idea of caching the "rendered" link makes sense to me.

However, that requires a lot of additional context info for the cache item that contains the rendered links:

- HTTP vs. HTTPS
- conf_path() / HTTP_HOST / domain (in case an absolute link is contained)
- language
- last timestamp of a changed string tanslation
- theme key (also: theme vs. admin_theme)
[potentially more; these are the most obvious only]

- ?destination
- active trail
- session (link tokens)

Context, context, context. And in fact: dependencies, dependencies, dependencies. That's what this issue is all about and what makes it so complex: our menu system is so incredibly flexible, because it allows so many contexts/dependencies to affect the rendered result. At the same time, that's precisely why it performs so poorly!

Let's number all of these contexts, plus missing ones (emphasized):

1. URI scheme. (HTTP/HTTPS, and HTTP/2 aka SPDY in the future)
2. Site in a multisite. (conf_path()/HTTP host/domain)
3. Language.
4. Last string (UI) translation.
5. Theme key.
6. The <code>.active class. (Page-specific.)
7. Active menu trail.
8. ?destination.
9. Session. (Session tokens in menu links.)
10. Last change to contained menu link or containing menu.

Now, I think a few patches from the past few months greatly help with addressing this (same order as the above numbered list):

1. The "scheme" (1) and "site in a multisite" (2) contexts haven't been addressed yet, but #2158003: Remove Block Cache API in favor of blocks returning #cache with cache tags introduced (see corresponding change notice) the concept of "cache contexts" to address precisely this problem. Cache contexts allow you to expose a global (i.e. request) context to Drupal's cache system. We already have LanguageCacheContext, ThemeCacheContext, UrlCacheContext, UserCacheContext and UserRolesCacheContext. By adding a DomainCacheContext, we can easily cache per protocol/site in a multisite combination. Note that this also allows for site-specific contexts, such as CountryCacheContext, CurrencyCacheContext or WeatherCacheContext.
2. The "language" context has already been addressed, see first bullet: LanguageCacheContext.
3. The "theme" context has already been addressed, see first bullet: ThemeCacheContext.
4. "Last string translation" is not a cache context (in that it doesn't make sense to cache "per version of the string translation"), but whenever any string translation changes, the locale cache tag is deleted, which will cause all cache items tagged with it to be invalidated.
5. The .active class problem was addressed in #1979468: ".active" from linkGenerator(), l() and theme_links() forces an upper limit of per-page caching for all content containing links, by introducing data- attributes on links that should get that class when applicable plus a #post_render_cache callback that is applied to the entire page.
6. The active menu trail problem was addressed in #2224861: Cache SystemMenuBlock and BookNavigationBlock per active trail (currently cached per URL, this breaks on very long URLs) for menu blocks, by introducing MenuTreeInterface::getActiveTrailIds(), which allows us to generate an active trail cache key, and hence cache per-active trail instead of per-page (which is much better because many pages have the same active trail). An even better solution might include
7. The ?destination problem was addressed in #2136507: Use client-side cache tags & caching to eliminate 1 HTTP requests/page for rendering Contextual Links for contextual links, but we can apply it here also (uses drupalSettings.path.currentPath plus a tiny amount of JS).
8. The session link tokens can be addressed in an analogous manner.
9. "Last menu link/menu change" is not a cache context for the same reasons "last string translation" isn't. Here, too, we have corresponding cache tags that are invalidated.

Combined, this allows us to (again matching the above numbered list):

1. Cache per domain (scheme + domain + port). It's fine to do this *always*, not just when there's >=1 links in the menu tree that has absolute => TRUE, because the number of domains is always going to be limited.
2. Cache per language — simple & essential.
3. Cache per theme — simple & essential.
4. Invalidate whenever translations change.
5. Ignore the (page-specific) .active class problem; we can consider that a now-irrelevant cache context.
6. Cache across pages, thanks to menu trail-specific caching.
7. Ignore the (page-specific) ?destination problem; we can turn that into an irrelevant cache context.
8. Ignore the (session-specific) session link tokens problem; we can turn that into an irrelevant cache context.
9. Invalidate whenever contained menu links or the menu in question change.

It should also be possible to alter a menu tree's rendering to depend on more cache contexts, because that way, you can retain the same cacheability, but allow for e.g. menu links that have access dependent on one of those cache contexts ("this link can only be accessed by people in Belgium").

The 10% of the problem space (that will be 90% of the work) that is not yet solved

This is, once again, the "arbitrary access checks" problem. i.e. hook_entity_access()/hook_node_access().

The solution that catch and I came up with together:

1. We render cache the entire menu tree by role/language/theme/active trail/… (see the above).
2. Access-wise, we render cache those items whose router information only has a _permission requirement (or more generally, whose access checks are cacheable per role).
3. If any other route requirement is present, we don't render that menu link, but render a render cache placeholder instead, with an associated #post_render_cache callback. This will allow us to render cache the entire menu tree per role/language/theme/active trail/…, but still render those links that need dynamic access checks.
4. To ensure that that #post_render_cache can run as efficiently as possible, we calculate and cache the results of the dynamic access checks in a menu per user, and associate the cache tags of the route parameters that turn out to be entities after route parameter enhancing (all entities have cache tags as of #2217749: Entity base class should provide standardized cache tags and built-in invalidation!), so that whenever any of those entities change, the dynamic access checks results that are cached per user & menu are recalculated (e.g. a menu link to an unpublished node, and then suddenly that node gets published — cache tags ensure the correct invalidation happens).

Helper at #2268971: Helper for #1805054.

Child issues created while working on this so far:

1. #2271025: Don't let menu_navigation_links() set the "active" class, the drupal.active-links library does that for us (plus, it's setting it incorrectly)
2. #2271659: Split up _menu_link_translate() to unblock render caching of menus
3. #2271763: Split active trail handling from MenuTree(Interface) into MenuActiveTrail(Interface)
4. #2272081: BlockAccessController::checkAccess() should run the block plugin's access check last

A few of these have landed, which allow this patch to become simpler.

Also filed #2273277: Figure out a solution for the problematic interaction between the render system and the theme system when using #pre_render, which has been extremely problematic for some time now.

Patch is against 71287c867fc06483b2f0b73b2241efa4842102f6, from now 10 days ago. Hence marked as "do not test".

Attached patch still needs quite a bit of cleanup, but I hope that by reading MenuTreeInterface and MenuTree, the approach is clear (and if not, see the above, that should help also).

This patch converts all rendered menus:

• menu blocks
• "navigation links" (primary & secondary menu)
• toolbar tray
• menu tree select widgets in the UI

Into the exact same pipeline. It makes all of them cacheable.

It also fixes the critical regression of dynamic access checking no longer happening in menu blocks. As of #2158003: Remove Block Cache API in favor of blocks returning #cache with cache tags, menu blocks are cached per role. Which means that any menu link that needs dynamic access checks (e.g. "view own unpublished content") simply is cached for the first user with a given role.

This also removes all caching in the MenuTree::build*() functions — we now rely solely on render caching, plus of course the cached versions of "access cacheability analysis" for each menu tree. Overall, this allows us to use caches much more effectively.

Good news is that e.g. the admin menu has ZERO non-role cacheable access checks by default (and probably nearly always). Which also means that we'll be able to change the toolbar tray caching to be per-role :) (or even better: detect whether it should be cached per user or per role).

Finally, note that menu blocks in their "Cache settings" now tell you which menu links are costly. This needs UX love, and is questionable (because scary), but at least this is now possible.

Benchmarks

Note:

• "Before" is with caching of menu blocks disabled, because only then we get correct results.
• "BeforeWrong" is with caching of menu blocks enabled, but keep in mind that this yields incorrect results.
• "After" compares to "Before" — that's the only apples-to-apples comparison possible here.

(Measured using the excellent https://drupal.org/project/webprofiler), using PHP 5.5 with OpCache enabled, XDebug disabled.)

Default menu

The default menu, with 1 link: "Home" (which is role-dependent).

/

	BeforeWrong	Before	After	Δ
DB queries	189	193	165	-28
Response time (ms)	240	255	230	-25
Memory (MB)	14.2	14.5	13.8	-0.7
Cache gets	78	83	70	-13
Config gets	50	51	49	-2

/contact

	BeforeWrong	Before	After	Δ
DB queries	139	142	111	-31
Response time (ms)	190	200	180	-20
Memory (MB)	11.0	11.5	10.5	-1
Cache gets	46	51	38	-13
Config gets	41	42	41	-1

Typical menu

I configured the "main menu" with 3 links: 3 role-dependent ones ("Home", "Contact", "Admin").

/

	BeforeWrong	Before	After	Δ
DB queries	195	198	165	-33
Response time (ms)	250	260	230	-30
Memory (MB)	14.2	14.5	13.8	-0.7
Cache gets	80	84	70	-14
Config gets	50	51	49	-2

/contact

	BeforeWrong	Before	After	Δ
DB queries	139	142	111	-31
Response time (ms)	210	220	180	-40
Memory (MB)	11.2	11.5	10.5	-1
Cache gets	48	52	38	-14
Config gets	41	42	41	-1

Typical complex menu

I configured the "main menu" with 6 links: 3 role-dependent ones ("Home", "Contact", "Admin") and 3 non-role-dependent ones (to nodes 1, 2, 3).

/

	BeforeWrong	Before	After	Δ
DB queries	205	207	166	-41
Response time (ms)	250	260	230	-30
Memory (MB)	14.5	14.5	13.8	-0.7
Cache gets	84	87	71	-16
Config gets	50	51	49	-2

/contact

	BeforeWrong	Before	After	Δ
DB queries	170	172	113	-59
Response time (ms)	220	230	180	-50
Memory (MB)	12.2	12.2	10.5	-1.7
Cache gets	58	61	39	-22
Config gets	48	49	41	-8

Profiling

I profiled the typical complex menu scenario with XHProf, with the following results:

/ — Before vs. After

/contact — Before vs. After

/ — BeforeWrong vs. After

/contact — BeforeWrong vs. After

i.e. 12–20K less function calls per page load (out of 80–90K calls per page load).

I'm concerned about the approach in the issue summary. A menu tree can be arbitrarily large. Loading the whole thing and doing later collapsing and filtering is fine for the toolbar, but not for the general use case.

Is the summary up to date?

I'd prefer to discuss the approach here in more detail.

#98: pwolanin: please read #96. I think #96 with some minor adjustments will make for a fine "proposed resolution" section in the issue summary.

#96 seems reasonable to me, and the patch looks like a solid improvement already. Looking forward to the cleaned up version.

Straight reroll to apply to HEAD. It still appears to be working :)

(#2222719: Use parameter matching via reflection for access checks instead of pulling variables from request attributes landed a few days ago, which made rerolling this more painful than if it were just #2247991: [May 27] Move all module code from …/lib/Drupal/… to …/src/… for PSR-4, which landed yesterday. But it was actually still surprisingly easy, considering this was rolled against a now ~2 weeks old Drupal 8!)

Clean-up phase 1. Refactored the determining of 'access check is cacheable per role' to be sane.

Updated the issue summary at a high level. As I clean up different parts of the patch, I'll continue expanding the issue summary.

Patch no longer applies ..

I will re-roll this patch.

I can't find a commit where this patch succeeds so, being a new contributor, I'll let someone else handle this. ;o)

#108: thanks for the attempt; this is definitely a very non-trivial reroll :)

High-level changes in this reroll:

• Last two patches didn't include DomainCacheContext; now included. That was the main cause of the ~6500 test failures.
• Full unit test coverage! This represents the majority of the patch. 2500 lines of additional unit test coverage!
• • MenuTree(Interface) is now much more focused: it's only purposes are to build a menu tree and render it.
  • For a large part, this is thanks to splitting the convoluted-and-impossible-to-grok logic in MenuTree::buildAllData(), MenuTree::buildPageData() and MenuTree::buildTreeData() into smaller pieces that are reusable, rather than the same logic being repeated in multiple places with subtle differences. The logic responsible for determining the query to retrieve a menu's menu links according to certain parameters now lives in a new MenuTreeParameters object
  • The access checking, translating, active trail-expanding etc. logic no longer lives partially in menu.inc and partially in MenuTree (partially in those); it now all lives in MenuDefaultTreeManipulators
  • The active trail handling is unchanged, but now lives in MenuActiveTrail(Interface)
  • A MenuTreeItem value object has been added, to make the resulting menu tree (of MenuTreeInterface::build()) more well-defined/formalized and hence more reliable/less brittle. A menu tree now consists of menu tree items, just like before, but instead of it being a particularly structured array, it's now a tree of MenuTreeItems. Menu tree manipulators receive and manipulate these.
• The only reason links with the expanded flag enabled are not expanded if the current response is a 404, is performance: that used to cause a cache miss, but thanks to per-active trail caching, that's no longer a cost. So we don't need to special case it anymore, especially not because this "optimization" actually hurts performance now :)
• MenuLinkStorage::loadModuleAdminTasks() is obsolete now, so it's been removed.
• Note that despite all this, the exact same logic is still used in 98% of the scenarios, it's now just been split up in logically independent parts with unit test coverage.

Next steps

1. This patch includes #2247779: Allow #pre_render, #post_render and #post_render_cache callbacks to be service methods.
2. The access check cacheability metadata functionality that was cleaned up in #104 can go in in a separate issue.

Getting both of those in separately will already make this patch much more digestable. Once those have landed, I'll split off more parts if desired.

Apologies

… for posting such a huge patch. I indicated earlier that I wanted to update the patch (and the issue summary) in phases, but it turned out to be impossible, because every single part I tried to change caused ripple effects everywhere else: the current ingrokkable, convoluted spaghetti code base made step-by-step cleanups infeasible. That's also why I wrote unit tests for All The Things: so that this patch becomes easier to iterate, and so that once it lands, future bug fixes, regression tests, feature additions and refactorings become significantly easier.

Also apologies because I've been under the radar for 2 weeks, but if I'd been posting patches that are impossible to follow without unit test coverage, that would also only have been an annoying distraction. I felt my time would be best spent presenting a solid patch, rather than a series of rough patches.

There's still room for improvement, of course, but now it's been proven to work. If you think there's an edge case that's uncovered, please just add a new unit test case that fails :)

Before

wim.leers at wimleers-acquia in ~/Work/drupal-duo/core on 8.x*
$ php vendor/bin/phpunit --group menu_link
PHPUnit 3.7.21 by Sebastian Bergmann.

Configuration read from /Users/wim.leers/Work/drupal-duo/core/phpunit.xml.dist

...........

Time: 1 second, Memory: 66.25Mb

OK (11 tests, 35 assertions)

After

wim.leers at wimleers-acquia in ~/Work/drupal-tres/core on 1805054_menu_render_cache_FINAL*
$ php vendor/bin/phpunit --group menu_link
PHPUnit 3.7.21 by Sebastian Bergmann.

Configuration read from /Users/wim.leers/Work/drupal-tres/core/phpunit.xml.dist

.............................................................   61 / 5219 (  1%)
...............

Time: 0 seconds, Memory: 71.25Mb

OK (76 tests, 556 assertions)

d.o--

I'm on PHP 5.5. That's probably why I didn't notice that pesky invalid syntax problem :)

testbot's not picking up #112. Reuploading.

This should fix all fails except for those in Drupal\rest\Tests\CsrfTest. How the changes in this patch can break X-CSRF-Token header authentication, is beyond me. If someone else knows how to efficiently debug that, please do so.

HAHA :D Thanks, Alex :)

#2247779: Allow #pre_render, #post_render and #post_render_cache callbacks to be service methods landed, which was also included in this patch. Removing that from this patch.

The next step (working on that right now) is to move the addition of cacheability metadata (see #104) into a separate issue.

Access checker cacheability metadata has been split off into its own patch now: #2287071: Add cacheability metadata to access checks.

This patch is still ready for reviews though — just feel free to ignore the changes to access checks!

1. The handling of primary/seconday menus is obviously not very DRY, but assuming https://drupal.org/node/1869476 goes in as the comment suggests, that's a non-issue.

2. The naming here is awkward, and I had to dig into the code to figure out what was going on:

if (!$cacheable_access_check->willBeEmptyForAccount($main_links_source, $account, $main_tree_parameters)) {

I think the source of the awkwardness is that the method is on $cacheable_access_check, so it doesn't read quite right. willBeEmptyForAccount would be a fine method name if it was on something like MenuTree, but here, it would probably work better as something like willMenuBeEmptyForAccount.

3. It took me a while to get the whole menu tree manipulator concept, but it still looks considerably simpler than what was there before. A few things threw me, but I think they are fixable.

$parameters->appendManipulator('menu_link.cacheable_access_check_tree_manipulator:checkNonDynamicAccess')
    ->appendManipulator('menu_link.default_tree_manipulators:translate')
    ->appendManipulator('menu_link.default_tree_manipulators:generateIndexAndSort')
    ->appendManipulator('menu_link.default_tree_manipulators:setHrefPropertyIfExternal')
    ->appendManipulator('menu_link.default_tree_manipulators:setTreeItemClass');

Using the servicename:method notation with two different services makes me think that this is an extensible system, where contrib could define new services to be added to menus in core. I don't think this is the case, which makes sense, but I think we can suggest it more in code.

I'd prefer to see all the manipulator methods on DefaultMenuTreeManipulators, regardless of who is doing the work. We'd just need a proxy for checkNonDynamicAccess:

class DefaultMenuTreeManipulators {

  public function checkNonDynamicAccess(array $tree) {
   return $this->cacheableAccessCheckMenuTreeManipulator->checkNonDynamicAccess($tree);
 }

Then the previous section could be simplified to:

$parameters->appendManipulator('checkNonDynamicAccess')
  ->appendManipulator('translate')
  ->appendManipulator('generateIndexAndSort')
  ->appendManipulator('setHrefPropertyIfExternal')
  ->appendManipulator('setTreeItemClass');

4. This class name is awkward, as I'm not sure whether "Check" is a verb or a noun until I read the whole thing, but it is accurate.

namespace Drupal\menu_link;

class CacheableAccessCheckMenuTreeManipulator {

Maybe we could do this instead?

namespace Drupal\menu_link\MenuTreeManipulator;

class CacheableAccessCheck {

That said, the docs on this class are *amazing*.

Overall, this patch is looking great. Huge step forward.

#122: done: #2289033: Refactor MenuTree to be simpler and have full unit test coverage.

That, together with #2287071: Add cacheability metadata to access checks, will allow this patch to become much more reviewable. It should end up in the sub 100K range, probably 50–70K.

#121: thank you so much for the review! :) Points 1, 2 and 4 apply only to the render caching that's being introduced here. Your 3rd point applies partially to #2289033 now, but the second half applies to this issue. I addressed the first half of point 3 at #2289033-3: Refactor MenuTree to be simpler and have full unit test coverage.

The conflict with #2256521: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module is possibly very fundamental in terms of this approach of "manipulators". I think Wim and I need to talk to figure out a common plan.

Siamese twin comments were posted to #2289033-8: Refactor MenuTree to be simpler and have full unit test coverage and #2256521-75: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module, respectively. In short: pwolanin and I have had a long discussion today on how to move forward; the conclusion is that #2289033 (my issue) will be closed and will be combined with #2256521 (pwolanin's issue).

So, that's my next big focus: helping bring that to completion. Once that's done, and perhaps in between, I'll continue working on #2287071, which has been hugely expanded in scope on effulgentsia's request.

I'll update the issue summary of this issue as soon as either of those land.

All 5 parts of #2256521: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module have been committed by now. Which means that #2289033: Refactor MenuTree to be simpler and have full unit test coverage has been committed as part of that, though in slightly changed form.

The only other blocker for this issue is #2287071: Add cacheability metadata to access checks.

I've been working on that one for the past week, and I just posted the first patch there that's actually reviewable: #2287071-15: Add cacheability metadata to access checks.
effulgentsia insisted in that issue that we widen the scope to fully resolve the lack of access check result cacheability metadata, so including the entity access hooks (that's why it took so long to get a reviewable patch going). While this is the cause of the significant increase of work and patch size, at the same time that will allow us to cache almost every menu link, because we will then finally know whether e.g. a node is accessible and that this result is valid per role, or per language, or per role and per language, or per group, or … In other words: we will finally no longer need to treat entity access checks as a "black box", of which the results are per definition uncacheable. That should mean that this patch will become even more effective! :)

I'm not clear why #2287071: Add cacheability metadata to access checks blocks this as opposed to allowing a further optimization?

#127: I just replied to your comment in #2287071: Add cacheability metadata to access checks, perhaps it's clear after reading that?

While working on this, it became clear that #2273277: Figure out a solution for the problematic interaction between the render system and the theme system when using #pre_render needs to be fixed in order for this issue to be fixed. I now have a reviewable (and hopefully RTBCable) patch there. #2287071: Add cacheability metadata to access checks has also been pushed forward significantly in the past few weeks. I'm blocked on reviews on both of those.

This patch is unnecessarily complicated by the fact that primary and secondary menu links still are special snowflakes with their own rendering pipeline dating back to Drupal <=5 — they're rendered inside the theme preprocessing layer rather than as blocks. #474004: Add options to system menu block so primary and secondary menus can be blocks rather than variables and #1869476: Convert global menus (primary links, secondary links) into blocks will fix that.

So, the effective list of blockers is now:

• #2287071: Add cacheability metadata to access checks (must-have)
• #2273277: Figure out a solution for the problematic interaction between the render system and the theme system when using #pre_render (must-have)
• #474004: Add options to system menu block so primary and secondary menus can be blocks rather than variables (should-have)
• #1869476: Convert global menus (primary links, secondary links) into blocks (should-have)

(I'm leading the first two and helping with the last two.)

I'm currently working on a reroll of this that's based on top of the latest patches in #2287071 and #2273277.

In the mean time, #2273277: Figure out a solution for the problematic interaction between the render system and the theme system when using #pre_render has landed, making this issue only blocked on a single remaining issue: #2287071: Add cacheability metadata to access checks. That one is also very close. I've been working on rerolling this patch already :)

There's also news for the two soft blockers: #474004: Add options to system menu block so primary and secondary menus can be blocks rather than variables landed today, and I rolled an initial (rough, incomplete) patch for #1869476: Convert global menus (primary links, secondary links) into blocks. The former already having landed doesn't help this issue at all, but hopefully the second will land, which will greatly simplify the work for this issue.

The last patch that "completely" addressed this issue did not yet address the case of "dynamic menu links": menu links where the link title is dynamic, or it has a ?destination=<current_path> query string, a session token, or a CSRF token.

Since #2256521: [META] New plan, Phase 2: Implement menu links as plugins, including static admin links and views, and custom links with menu_link_content entity, all managed via menu_ui module, we now have MenuLinkInterface::isCacheable() that gives us that information. Such dynamic links can not be render cached. The only way we can render them is either through JavaScript or through #post_render_cache, otherwise they'd "infect" a render cached menu. They're rare enough that it isn't worthwhile to spend the time building a JavaScript-based solution which is potentially more efficient. Therefore, we must render them via #post_render_cache.

So, we must be able to rely on the return value of isCacheable(), or otherwise we'll end up render caching e.g. link with CSRF tokens. Turns out that we currently cannot rely on isCacheable(), indeed causing render cached CSRF tokens. I've opened #2335661: Outbound path & route processors must specify cacheability metadata to fix that, and have posted an initial patch.

Woot, #2287071: Add cacheability metadata to access checks just landed!

I opened #2351015: URL generation does not bubble cache contexts as an alternate approach to unpostpone this issue.

Added new blockers to issue summary

I'm not sure but I believe that this issue is now postponed on #2351015: URL generation does not bubble cache contexts so noting this in the issue summary.

It is, however we discussed this a bit last week

1. 99.9% of menu links don't actually use CSRF protection.

2. There's no hard code dependency between the two issues.

So given the menu link CSRF protection issue is critical, I think it'd be OK to un-postpone this and handle them in parallel.

Actually un-postponing this time.

From the #drupal-performance IRC channel, March 10, 2015:

18:20:35 WimLeers|afk: Fabianx-screen: catch: So having thought about it, I think the combination of:
1. default cache contexts
2. the introduction of #pre_render_cache (in addition to #pre_render)
3. ability to mark cache contexts as "high frequency"
4. the combination of 2+3 to have automatically do placeholdering
5. association the proper cache contexts with URLs themselves (notably a 'host' cache context)
6. small changes to menu link tree rendering (to use #pre_render_cache)

… will allow us to close https://drupal.org/node/1805054 by only doing point 6, which would be a tiny, tiny patch

So, basically postponing this on #2429287: [meta] Finalize the cache contexts API & DX/usage, enable a leap forward in performance. See the Google doc in that IS for details.

According to the issue summary of #2335661: Outbound path & route processors must specify cacheability metadata that is also blocking this one.

Just #2335661: Outbound path & route processors must specify cacheability metadata already presents a big step forward: it makes it so that the generated links themselves have the right cacheability metadata. That's the biggest blocker to this issue. And that patch is green and close to RTBC.

From the work I had lying around from long ago, I also split off #2479363: Cache MenuActiveTrail::getActiveIds() for *all* menus per route match: 1 cache get instead of N DB queries, saves 1 ms/response into a child issue already. That removes a few unnecessary queries.

After that, there are basically two problems left:

1. also applying access results cacheability metadata
2. excluding the parts that are not cacheable or "too dynamic to cache" (high-cardinality cache contexts such as "per user") and render them using placeholders. (This includes links with CSRF tokens.)

But… in reality:

• almost no links are uncacheable (how often does one add a link with a CSRF token to a menu?)
• almost no access checks are uncacheable (pretty much every access check is cacheable)

In other words: the 99.99% case — and that's not an exaggeration — doesn't have uncacheable links or access checks in menus. The use case of menu links being hyperdynamic (the "Hello, Wim" use case) works just fine too: they'd be cached per user, which would mean the menu is cached per user. Sites that want to do that sort of thing therefore will just have menus that are cached per-user. That's fine: only those sites will have that problem.

That allows us to move forward with a solution for the 99.99% (i.e. this is then no longer postponed on #2429287: [meta] Finalize the cache contexts API & DX/usage, enable a leap forward in performance as described in #141). The remaining 0.01% can happen in 8.x.0 without an API break, or in contrib: it is possible to placeholder the uncacheable parts and still cache the cacheable portions of a rendered menu. But it will make the code significantly more complex. The analysis I made in #141 is incorrect; it oversimplifies things: the tricky thing with menus is that child menu items affect the parent menu item: the expanded and collapsed classes.

Note again that HEAD IS BROKEN: it caches menu blocks, but it actually doesn't know how: therefore it may show links to a user that should not even be able to see them. So, below, "HEAD-fixed" is HEAD with the menu block no longer cached (by adding getCacheMaxAge() { return 0; }.

This is profiled as UID 1 on the frontpage, using the Standard install profile. Zero extra menu links, so only the "Add content" menu link. UID 1 because that is *cheaper* in terms of access checking (lots of things return early for UID 1) and because that user can access the toolbar.

In other words: the numbers below present the minimum expected improvement, for more complex set-ups and for non-admin users, the improvement will be much bigger. (See #97 for an indication of the performance improvements in other scenarios; they should be roughly comparable still.

Profiling (XHProf)

HEAD

Function calls: 64427

Mem: 22.4 MB

Peak mem: 22.7 MB

HEAD-fixed

Function calls: 68091

Mem: 22.6 MB

Peak mem: 22.8 MB

Patch

Function calls: 61444

Mem: 22.0 MB

Peak mem: 22.3 MB

Benchmarking (ab -n 1000 -c 1)

HEAD

Requests per second:    9.30 [#/sec] (mean)
Time per request:       107.557 [ms] (mean)
Time per request:       107.557 [ms] (mean, across all concurrent requests)
Transfer rate:          184.41 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:   102  107   2.2    107     124
Waiting:       92   96   2.1     96     113
Total:        102  108   2.2    107     124a

HEAD-fixed

Requests per second:    8.90 [#/sec] (mean)
Time per request:       112.305 [ms] (mean)
Time per request:       112.305 [ms] (mean, across all concurrent requests)
Transfer rate:          176.62 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:   106  112   2.7    112     135
Waiting:       95  101   2.7    100     124
Total:        106  112   2.7    112     136

After

Requests per second:    9.57 [#/sec] (mean)
Time per request:       104.454 [ms] (mean)
Time per request:       104.454 [ms] (mean, across all concurrent requests)
Transfer rate:          189.79 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       0
Processing:    98  104   2.5    104     132
Waiting:       88   93   2.4     93     120
Total:         99  104   2.5    104     132

HEAD vs. patch

(i.e. fast-but-broken HEAD)

HEAD-fixed vs. patch

(i.e. slower-but-correct HEAD)

The included patches are:

• #2335661-108: Outbound path & route processors must specify cacheability metadata
• #2479363-4: Cache MenuActiveTrail::getActiveIds() for *all* menus per route match: 1 cache get instead of N DB queries, saves 1 ms/response
• #2479767-8: Fix MenuLinkInterface::isCacheable(): remove it in favor of implementing CacheableDependencyInterface

As you can see, the actual patch is only ~20 KB!

So, the failures in:

• PageCacheTagsIntegrationTest: one small oversight (user.roles is no longer present, because SystemMenuBlock no longer stupidly hardcodes it) and one actual bug (the changes I made in BlockViewBuilder), because I should've just updated the existing logic rather than adding my own.
• DefaultMenuLinkTreeManipulatorsTest were due to a silly bug in this patch, now fixed
• FieldWebTest were due to #2335661-108: Outbound path & route processors must specify cacheability metadata, now fixed in #2335661-112: Outbound path & route processors must specify cacheability metadata, so that patch is now included

Therefore, the included patches are now:

• #2335661-112: Outbound path & route processors must specify cacheability metadata
• #2479363-4: Cache MenuActiveTrail::getActiveIds() for *all* menus per route match: 1 cache get instead of N DB queries, saves 1 ms/response
• #2479767-12: Fix MenuLinkInterface::isCacheable(): remove it in favor of implementing CacheableDependencyInterface (was just updated; I'm now rerolling the patch to take advantage of improvements there)