Continuing the discussion from Making accessible menus:
What I do is save each menu output in a transient. See https://codex.wordpress.org/Transients_API
If there’s a difference between a menu when logged-in and logged-out, then I also save the output of each of those in its own transient. As with all caching, it’s important to ensure that the transients get deleted automatically whenever the menu needs updating, and it’s also useful to provide a manual method (though you could use the Transients Manager or the WP Optimize plugins for the manual method instead).
I like to give my transients a long lifetime but the precise length doesn’t matter much to me. If a menu needs updating, its transient will get automatically deleted anyway.
This method on its own speeds sites up tremendously and (depending on the menu size) can cut down dramatically on the number of database queries.
But if you have Memcached or Redis installed on your server, you can then connect up your site to use one of them, and they will automatically take control of all the transients for full object caching. My host uses Litespeed servers, so this is easy for me because I can just use the Litespeed Cache WordPress plugin, configure its Advanced Settings to use Memcached, and voilà!