История изменений
Исправление a--, (текущая версия) :
Но реальность такова, что принцип компенсации не работает, бедные люди бывают одновременно ещё и больными, глупыми и злыми. В нашем случае такой злой и больной бедняк - это структура данных типа список.
Да, так, если это современная RAM. Но ведь можно сделать гибрид списка и массива, чем-то похожий на B-tree:
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ ┌─
→│ │A│B│C│D│ │E│F│G│H│I│ │J│ │K│L│⇄│M│ │ │ │N│ │ │O│P│Q│R│ │S│ │T│U│⇄│V
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─
⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵
▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒
Здесь латинским буквами обозначены ненулевые указатели, ▒ это нагрузка (payload). Массив указателей имеет длину в кэшлинию (64 байта). И все это предназначено для реализации LRU.
Исходная версия a--, :
Но реальность такова, что принцип компенсации не работает, бедные люди бывают одновременно ещё и больными, глупыми и злыми. В нашем случае такой злой и больной бедняк - это структура данных типа список.
Да, так, если это современная RAM. Но ведь можно сделать гибрид списка и массива, чем-то похожий на б-дерево:
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ ┌─
→│ │A│B│C│D│ │E│F│G│H│I│ │J│ │K│L│⇄│M│ │ │ │N│ │ │O│P│Q│R│ │S│ │T│U│⇄│V
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─
⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵ ⇵
▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒
Здесь латинским буквами обозначены ненулевые указатели, ▒ это нагрузка (payload). Массив указателей имеет длину в кэшлинию (64 байта). И все это предназначено для реализации LRU.