| Project: | Drupal core |
| Version: | 8.x-dev |
| Component: | menu system |
| Category: | task |
| Priority: | major |
| Assigned: | Unassigned |
| Status: | needs review |
| Issue tags: | D8 cacheability, Needs issue summary update, Spark |
Issue Summary
#1137920: Fix toolbar on small screen sizes and redesign toolbar for desktop is a critical feature: otherwise, D8 ships with a terrible mobile experience. Therefore, making this issue a critical task.
One of the aspects of the current design in that issue is to from any page, be able to drill down to any admin link with purely client-side logic. In this way, it shares a resemblance to Admin menu.
Since rendering (whether all the way to HTML, or to a JSON tree containing access filtered and argument resolved URLs) an entire menu tree is expensive, this requires caching. Admin menu 3.x implements its own caching with fully rendered HTML cached in {cache_menu} with cid of 'admin_menu:' . $user->uid . ':' . session_id() . ':' . $language->language;. In other words, a per-user cache scoped to admin_menu.
In comment 110 of that issue, catch requested that we not port that approach to a toolbar-specific cache, but rather solve the problem generally in the menu system.
I see this issue as having three parts (perhaps not all of them need to be solved as part of this issue):
- Make the output of menu_build_tree() not page-specific. Because the output is already user-specific (access filtered), and a cache that is both per-user and per-page is close to useless. However, it can only be non-page-specific when called with empty 'expanded', 'active_trail', and 'only_in_active_trail' build parameters. I think it's fine if we only cache the output when those conditions are met, and assume that consumers of this cache are therefore use cases that can implement their own tree collapsing client-side. Any thoughts on this or whether there's any other subtle problems with reusing this information across different pages?
- Instead of caching menu_build_tree(), we'd get more performance gains by caching a client-consumable rendered form of it, either the result of menu_tree_output() (fully rendered HTML with ULs and LIs), or a JSON tree (possibly with anchor tags rendered but not the UL/LI wrappers). If we only render a JSON tree with anchor tags, then we just need to make sure the 'active' class isn't added, which isn't hard. But then the JS code that adds ULs and LIs potentially needs to be made consistent with whatever theme overrides of theme_menu_tree() and theme_menu_link() are in use by the active theme. OTOH, if we render the full HTML, then we need to make menu_tree_output() not page-specific, both for its active trail handling, and by documenting that preprocess and theme overrides of 'menu_tree' and 'menu_link' shouldn't have page-specific logic.
- If this is to be truly reusable outside of toolbar, it would be helpful to have some other use case to work with in designing it. Catch suggested core's menu block. However, this would imply converting that to a JS-based solution (for rendering what's expanded vs. what's collapsed based on the current page), and we'd have to figure what the no-js behavior should be. This could actually be a nice performance gain for Drupal as long as we can come up with a no-js fallback that's acceptable.
Any thoughts on the above, or something I missed?
Comments
#1
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.
#2
@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?
#3
Tagging it with Spark, as it is relavant for Spark.
#4
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:
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)
ulelement.unthrottled/cable: 3ms
256 kbps/DSL: 303ms
3g: 696ms
1110 links in a nested (3 levels)
ulelement.unthrottled/cable: 4ms
256 kbps/DSL: 2670ms
3g: 1330ms
5555 links in a nested (3 levels)
ulelement.unthrottled/cable: 4ms
256 kbps/DSL: 14048ms
3g: 4560ms
11,110 links in a nested (4 levels)
ulelement.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.
#5
Just wanted to post a work in progress patch. I'm working with a devel generated menu block with 300 links upto a depth of 4, caching the result of menu_build_tree() per-user, but not per-page. I'm caching subtrees, since retrieving a fully expanded tree from cache is both memory intensive and slow.
I'm not seeing any performance benefit from it yet, but that's because most of the savings can come from caching the result of l(), and I'm not doing that yet, but will work on that next.
#6
Ok, this once caches the l().
#7
The last submitted patch, menu-cache.patch, failed testing.
#8
#6: menu-cache.patch queued for re-testing.
#9
The last submitted patch, menu-cache.patch, failed testing.
#10
#11
Here's a benchmarking script that can be applied on top of #1137920-114: Fix toolbar on small screen sizes and redesign toolbar for desktop. It requires devel module enabled.
#12
#10 includes a hunk that outputs some times above menu blocks of devel generated menus. On a 300 link menu where all links are node links and I have no node access module in use, when viewing a node page that returns 25 links to the browser (only menu items that are not children of collapsed parents), I get:
HEAD:
- time to get the access filtered and localized tree: 3ms
- time to build the render array and render it: 8ms
With #10:
- time to get the access filtered and localized tree: 3ms (no change, despite caching menu_tree_check_access())
- time to build the render array and render it: 4ms (2x improvement due to no runtime l() calls)
#11 can be applied to the toolbar patch in that other issue. That benchmarks the time to get, build, and render a fully expanded Management menu. For that, I get:
HEAD:
- time to get the access filtered and localized tree: 20ms
- time to build the render array and render it: 18ms
With #10:
- time to get the access filtered and localized tree: 5ms (4x improvement due to caching menu_tree_check_access())
- time to build the render array and render it: 9ms (2x improvement due to no runtime l() calls)
These numbers are relative to an approximately 100ms total page response, so correspond roughly to percentages.
#13
The last submitted patch, menu-cache.patch, failed testing.
#14
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.
#15
Thanks for the review, sun. Ok, how about this instead?
I removed the calling of l() from _menu_link_translate() for all the reasons given in #14. I think this is worth looking into more, but perhaps in a different issue. Also, we shouldn't really be caching l(), just url(), but all the same issues apply to that as well.
I also changed menu_build_tree() to only cache localized menus that aren't dealing with active trail, per the issue summary. This means this caching is no longer being automatically applied to regular menu blocks. Applying it to menu blocks would need to be done in a separate issue, together with the javascript for applying the active(-trail) classes client-side.
Note that since even the existing toolbar builds a menu tree (with depth=1) with no active trail handling, this patch does implement per-user caching of that. That might not actually be a good thing, since localizing a 1 deep toolbar takes very little time, but meanwhile, we're adding a cache record per user (who has access to the toolbar). But, since catch asked to explore this issue generically, that's the current patch behavior.
I also changed theme_menu_link() to not call l(), but render the anchor tag directly. First of all, at DrupalCon Munich, when discussing template conversions to twig, the themers present all asked for putting anchor tags in menu(-link).twig instead of calling l() on TX grounds alone. Secondly, decoupling from l() lets us override 'active' class handling, and pre-generating/caching url().
Finally, this patch adds a demo hunk to toolbar.module to (in the presence of a 'toolbar-tmp-depth' query string) append an expanded Management menu of the desired depth along with the number of ms it took to build the tree and render it. It is here that I also added render caching for it. Given #14, I don't think we want to add render caching into menu_tree_output() itself (and therefore, this patch doesn't), but doing so in the use-case specific code is easy as this patch demonstrates.
By employing both menu_build_tree() caching and render caching, this I think solves all server-side performance issues of #1137920: Fix toolbar on small screen sizes and redesign toolbar for desktop. We still might want to implement client-side localStorage caching in that issue though for mobile bandwidth optimization. However, sun is calling into question the premise of per-user caching on sites with many users, so additional feedback from people about that would be helpful.
#16
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...
#17
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().
#18
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.
#19
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.
#20
Per #18, I think this issue continues to be appropriate, even as a major task, for reasons other than Toolbar. For Toolbar though, I think #1814932: Caching strategy for D8 toolbar is better.
#21
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.
#22
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 )
#23
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.
#24
#15: menu-cache.patch queued for re-testing.
#25
The last submitted patch, menu-cache.patch, failed testing.
#26
re-roll
#27
The last submitted patch, 1805054-26.patch, failed testing.
#28
#26: 1805054-26.patch queued for re-testing.
#29
The last submitted patch, 1805054-26.patch, failed testing.
#30
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?
#31
Maybe check the testbot number...
this might also provide a clue: #1878216: Bot #664 disabled (repeatedly failed to run tests)
#32
nope no conflicts simple merges
here is the merge if it helps.
git rebase 8.xFirst, 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
#33
#26: 1805054-26.patch queued for re-testing.
#34
The last submitted patch, 1805054-26.patch, failed testing.
#35
Replaced a call to
drupal_array_set_nested_value()withNestedArray::setValue()as per#1705920: Convert all calls to procedural drupal_array_*() functions to Drupal\Component\Utility\NestedArray
#36
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.
#37
#38
Raised related #1927174: Complete the work to make the Toolbar administration menu sub tree rendering more efficient to critical.