shagguboy дело говорит, если object caching (массив) не удовлетворяет, ибо значительный расход времени идет на калькуляции на уровне PHP, используется fragment caching - генерируете уже готовый html и храните в memcached его.
Если сайт/приложение использует авторизацию и данные отличаются для гостей и пользователей, или вовлечена другая логика, которая требует множества вариантов - используйте комбинацию. 1й уровень - object cache (для авторизованных), поверх полируем fragment cache для гостей. Или же, если есть возможность и готовы к хардкору, разбиваете само меню / другой объект на части, те которые можно кешировать целиком, и те которые должны оставаться динамическими.