Почему строгая реализация O(1) LRU не используется в производственном программном и аппаратном обеспечении?

Подробнее:

Читая о реализации LRU или наименее недавно используемого кэша, я наткнулся на решение O(1), в котором используется unordered_map (c++) и двусвязный список. Что очень эффективно, так как доступ к элементу из этой карты по существу O (1) (из-за очень хорошего внутреннего хеширования), а затем перемещение или удаление из этого двусвязного списка также O (1).

Подробное объяснение здесь

Но затем, в ходе дополнительных исследований, я обнаружил Как кэш LRU реализовано в процессоре?

Для большей ассоциативности число состояний резко возрастает: факториал числа путей. Таким образом, 4-канальный кеш будет иметь 24 состояния, требующих 5 бит на набор, а 8-канальный кеш будет иметь 40 320 состояний, требующих 16 бит на набор. В дополнение к накладным расходам на хранение, есть также большие накладные расходы при обновлении значения.

и это

Теперь мне трудно понять, почему решение O (1) не решит большинство проблем с сохранением состояний для каждого набора и возрастных битов для отслеживания LRU?

Я предполагаю, что с помощью хэш-карты невозможно сохранить ассоциативность, но тогда каждая запись может быть отдельной записью, и поскольку доступ равен O (1), это не должно иметь значения, верно? Единственное, о чем я сейчас думаю, это о размере этой хеш-карты, но до сих пор не могу понять, почему?

Любая помощь приветствуется, спасибо!


c++ caching cpu-cache lru
person boparai    schedule 12.04.2021    source источник
comment
Это не настоящий ответ, но стоит знать, что реальная производительность часто не очень хорошо отображается в нотации с большим O. Наибольший вклад в производительность вносят локальность кэша, конвейерная обработка инструкций, спекулятивное выполнение и предсказание ветвления. . Такие вещи, как unordered_map, часто ужасны для локальности кеша, поскольку записи теперь находятся в разных сегментах (распределения кучи), размещенных в разных областях памяти, и при поиске возникают промахи кеша. Точно так же связанные списки очень плохи из-за того, что доступ к ним осуществляется не непрерывно.   -  person Human-Compiler    schedule 12.04.2021
comment
O (1) - это обозначение асимптотического времени выполнения, поэтому вы заботитесь о времени выполнения, когда длина вашего ввода стремится к бесконечности. Он ничего не говорит о том, насколько он быстр. Это может быть 1 нс или 1 мс.   -  person Unlikus    schedule 12.04.2021
comment
Связанный список, хотя и хорош с алгоритмической точки зрения, является одной из худших структур данных для использования на практике. Каждый обход узла — это промах кеша, поэтому вы работаете со скоростью оперативной памяти, чтобы пройти. std::unorded_map, так же реализован со списком понравившихся под капотом, из-за определенной сложности гарантирует стандартные мандаты.   -  person NathanOliver    schedule 12.04.2021
comment
Хеш-карта + список LRU используется в программном обеспечении. Почему вы думаете, что это не так?   -  person eerorika    schedule 13.04.2021
comment
Хотя сложность LRU hasmap + связанный список может быть постоянной по отношению к количеству элементов в кеше, неясно, как, по вашему мнению, это помогает снизить сложность при увеличении ассоциативности множества.   -  person eerorika    schedule 13.04.2021
comment
Аппаратное обеспечение имеет другие ограничения, чем программное обеспечение. Это O (1), поскольку для доступа к кешу процессора требуется постоянное количество тактовых циклов. Связанный список не имеет смысла в схемах, хотя это самый популярный подход в программном обеспечении.   -  person Ben Manes    schedule 13.04.2021