информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsВсе любят медГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 HP закрыла 16-летнюю уязвимость... 
 Microsoft советует пользователям... 
 MS Edge обогнал FireFox 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
На самом деле примерно так :-)... 15.06.05 12:22  Число просмотров: 2963
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 15.06.05 14:27  Количество правок: 1
<"чистая" ссылка>
Построить оптимальный кэш невозможно, можно только не совсем плохой. При любой стратегии/тактики кэша можно найти способ, при котором от него не будет толку.

Поэтому, чтобы получить хорошую итоговую производительность нужно всегда задумываться как меньше «нагадить» в кэш, и иногда гонять данные «мимо» (поиск в кэше делается, но без замещения при неудаче).

---

Далее, при поиске элементов, которые необходимо «выкинуть», правильнее искать оптимум f(x,y) ~= занимаемый_размер / ресуры_для_восстановления. Другими словами учитывать отношение освобождаемой памяти и средств, необходимых для повторной загрузки вытесняемого элемента.

Это даёт особенный выигрыш, когда таким образом организуется глобальный кэш сопряженный с подсистемой выделения памяти. Вся память используется под кэширование, но кэш усекается при динамическом выделении.

---

Как уже говорилось, выбрасывание элементов по случайному закону часто не намного хуже (или вовсе не хуже) многих «навороченных» алгоритмов. Обычно еще одна небольшая эвристика улучшает ситуацию:
- используется генератор случайных чисел с неравномерным распределением. Например, вероятность генерации чисел-индексов увеличивается от минимума до максимума при «движении» от начала очереди (недавно использовавшихся элементов) к концу (старых элементов);
- элемент можно выкидывать не сразу, а когда он «выпал» несколько раз. Можно не выкидывать элементы, которые «жили» в кэше меньше определенного времени. Можно для разных «классов» элементов установить разное количество требуемых выпадений на ГСЧ;
- Можно менять этот порог срабатывания динамически и при желании построить кэш, который будет само-оптимизироваться под задачу на принципах генетических алгоритмов;

---

Неплохие результаты дает использование идей динамического кодирования по Наффману (Huffman) или LZW-сжатия. Каждому элементу (например строке в таблице БД) назначается уникальный ID. Пока элемент находится в кэше, codeword соответствующий его ID в схеме сжатия соответствует его позиции в кэше. Чем больше (длиннее) codeword, тем ближе элемент к концу очереди, и тем более он подходит в кандидаты для «вылета».
Это хорошо дополняется идеей «минимальной» жизни элемента и стохастической чисткой (выбросом по ГСЧ).

Но чтобы ранжирование на основе алгоритмов сжатия работало нормально, нужно использовать HANDLEs. HANDLE в данном случае управляющая структура, соответствующая каждому элементу кэша. Но "хендлов" в несколько раз (как минимум в два раза) больше чем живых элементов кэша. Это позволяет отслеживать обращение к элементам, которые уже были удалены из кэша, и учитывать это в дальнейшем. Другими словами кэш состоит из множества "хендлов", но не более половина из них соответствует присутствующим в ОЗУ элементам, остальные используются только для сбора статистики по кэш-промахам.

---

Если теоретизировать далее, и постараться сделать максимально оптимальный, или само-оптимизирующийся кэш, то нужно строить модель на основе скрытых Марковских процессов.

Можно сделать и попроще:

Вероятность повторного обращения к элементу можно представить как периодическую функцию от времени. Большие периоды (низкие частоты) нас мало интересуют, поэтому можно ограничиться рассмотрениям ограниченного периода. Время дискретизировать до «разов» обращения к данным через кэш.

Если используя «хендлы» собирать достаточно статистики, то можно опроксимировать эту функцию полиномом, или разложить в ряд (Фурье здесь видимо лучше чем Хартли, потому что важно фаза). Можно подумать и над wavelet преобразованием со своей материнской функцией (обратимость вроде-бы не нужна).

Как вариант, можно представить всё в виде Марковского процесса. При этом дополнительной характеристикой каждого состояния будет вероятность повторного обращения к элементу в течение какого-то определенного времени. В идеале это должен быть ряд Фурье/Хартли посчитанный по статистике.

Короче, фантазировать можно очень долго. Но самое главное «правило» в начале поста все равно останется в силе…
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach