LRU Cache дизайн в C с ограниченным размером - PullRequest
Новая
       19

LRU Cache дизайн в C с ограниченным размером

2 голосов
/ 07 июля 2010

Сейчас я работаю над программным обеспечением на мобильной платформе, где памяти очень мало.В функции узкого места ввода / вывода мне нужно прочитать несколько байтов из img-файла с помощью операции поиска (можно предположить, что поиск примерно в 10 раз медленнее, чем чтение непосредственно из memmry).В моем тесте эта функция вызывается 7480325 раз и считывает байты от bytes_offset 6800 до 130000, поэтому каждый байт читается в среднем 100 раз (некоторые байты читаются 3-4 раза, некоторые более 1000 раз).

Ниже приведена моя статистика. 

bytes offset 6800 ~ 6900: 170884 times
bytes offset 6900 ~ 7000: 220944 times
bytes offset 7000 ~ 7100: 24216 times
bytes offset 7100 ~ 7200: 9576 times
bytes offset 7200 ~ 7300: 14813 times
bytes offset 7300 ~ 7400: 22109 times
bytes offset 7400 ~ 7500: 19748 times
bytes offset 7500 ~ 7600: 43110 times
bytes offset 7600 ~ 7700: 157976 times
...
bytes offset 121200 ~ 121300: 1514 times
bytes offset 121300 ~ 121400: 802 times
bytes offset 121400 ~ 121500: 606 times
bytes offset 121500 ~ 121600: 444 times
bytes offset 121600 ~ 121700: 398 times

max_bytes_offset 121703
min_bytes_offset 6848

Затем я хочу построить кеш, используя схему LRU, чтобы повысить производительность ввода-вывода.В вопросе некоторых других я нахожу хэш-таблицу + список с двумя связями - хороший способ.Но как сделать структуру, чтобы улучшить мою проблему наилучшим образом?Я планирую построить 1300 блоков, и у каждого блока будет двойной список с максимальным размером 10. Тогда общий объем памяти, который он занимает, составляет около 13 КБ.Это просто внедрить и поддерживать, но я думаю, что эффективность не самая лучшая.

В моей статистике интервал смещения некоторых байтов имеет большее число попаданий, в то время как у некоторого интервала меньше.Как я могу построить структуру, чтобы адаптировать мою статистику?

И когда я ищу ключ, мне нужен обход всего списка размером 10. Есть ли какой-нибудь другой метод с более высокой эффективностью поиска?

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

Кажется, что метод caf лучше.Использование большого двусвязного списка и больших ключей отображения хеш-таблиц для записей узлов имеет больше смысла и использует больше преимуществ LRU.Но разработка хеш-функции становится сложной проблемой.

Я жду вашего предложения, спасибо ~

1 Ответ

0 голосов
/ 07 июля 2010

Если у вас будет максимум 10 записей в каждом сегменте, то вам, скорее всего, лучше отказаться от двусвязного списка и просто сделать каждый сегмент круглым массивом (который состоит всего из 10 записей ииндекс "top of list").

Возможно, вам даже лучше отказаться от ассоциативного дизайна с 10 путями и использовать кэш с прямым отображением (где у вас есть большая хеш-таблица, где хранится каждый сегмент).только одна запись).Наборы ассоциативных конструкций хороши в аппаратном обеспечении, где вы можете использовать выделенное оборудование для параллельного сравнения n, но не столько в программном обеспечении (если у вас нет векторного модуля, который вы можете использовать для этого).

Один из способов адаптации к вашей статистике - спроектировать хэш-функцию так, чтобы она отображала разные диапазоны адресов для каждого сегмента, так чтобы каждый блок получал примерно равную частоту доступа.

Изменение размера хэшаТаблица является еще одним очевидным способом масштабирования размера кэша.

...