Graceful Menu Cache

Graceful Menu Cache flags menu caches as stale instead of clearing them.
At cron run, it generates new caches and then replaces the old caches.
Doing so, users only have to wait for the cache to build, the first time it gets loaded.
This gives a major performance boost to Drupal installations with a lot of menu items.

The disadvantage is that it takes longer for anonymous users to see menu changes. It takes as long as the cron frequency.

I didn't get it to work as it should.
I checked with Wim Leers. He said this module is a good attempt to fix the problem in Drupal 7 but it needs cache tags. Cache tags are introduced in Drupal 8 by #1805054: Cache localized, access filtered, URL resolved, and rendered menu trees. So, use Drupal 8 if you can.