Стратегии кэширования ресурсов игры.

Загруженные ресурсы(текстуры, звуковые буфера, шейдеры, и тп) делятся на используемые и неиспользуемые, последние хранятся на всякий случай, вдруг снова понадобятся.

1) Идеальный случай.
Пусть "Ресурсы" хранятся только в оперативной памяти, мы также точно знаем, сколько ее осталось.

Тогда все тривиально. Когда для последующей загрузки ресурса не хватает места, выгружаем last used. На PC имхо такой вариант невозможен. Нельзя точно сказать, сколько у нас оперативной, видео, API могут зеркалировать ресурсы, при этом невозможно сказать, сколько на это они требуют места и где именно они лежат, и тп.

2) Выгружаем ресурс через две минуты неиспользования. Но почему не через три?

3)
Вообще не выгружаем. Есть риск нарваться на медленный своп и на что-то типа E_OUTOFMEMORY, другие глюки.

4)
Вот только что придумал, хочу обсудить.
.)Если ресурс не используется в течение такого же количества времени, каковым было его использование, то он выгружается. Как вам такая простая идея?

.)Если не хватает ресурсов при загрузке нового, проводим "генеральную уборку", выгрузив все неиспользуемые(тут тоже проблемы. Если не хватает места для текстур, зачем выгружать звуковые буфера, если они хранятся в памяти звуковой/видеоплаты? Но с другой стороны, API может разместить и то, и то, в системной памяти. Но такие проблемы уже лучше забить, ИМХО.).

*******************+++++++++++----------**************
                   1          2         3

1- загрузка ресурса    
2- все клиенты отказались от этого (разделяемого) ресурса
3- убиваем его.

Последующие сложности.
Изучаю D3D.
В отличие от DSound буферов, OpenGL VBO, и D3D текстур, D3d модели с общим форматом вершин хранятся в общем, непрерывном куске буфера вершин/индексов. Для загруки можно увеличивать размер буфера в 2 раза, что тоже мне кажется странным. Как их тут выгружать, вообще не понятно? А как же делает OpenGL?

Здравствуйте, _Winnie, Вы писали:

_W>Последующие сложности.
_W>Изучаю D3D.
_W>В отличие от DSound буферов, OpenGL VBO, и D3D текстур, D3d модели с общим форматом вершин хранятся в общем, непрерывном куске буфера вершин/индексов. Для загруки можно увеличивать размер буфера в 2 раза, что тоже мне кажется странным. Как их тут выгружать, вообще не понятно? А как же делает OpenGL?

Модераторам. Можно вот эту часть убрать, а то не соответсвует теме ветки. И это сообщение тоже удалить. на moderator@rsdn.ru уже послал, но я не знаю, на сколько это надежно.

Здравствуйте, _Winnie, Вы писали:

W> 4)
W> Вот только что придумал, хочу обсудить.
W> .)Если ресурс не используется в течение такого же количества времени,
W> каковым было его использование, то он выгружается. Как вам такая простая
W> идея?
W>
W> .)Если не хватает ресурсов при загрузке нового, проводим "генеральную
W> уборку", выгрузив все неиспользуемые(тут тоже проблемы. Если не хватает
W> места для текстур, зачем выгружать звуковые буфера, если они хранятся в
W> памяти звуковой/видеоплаты? Но с другой стороны, API может разместить и
W> то, и то, в системной памяти. Но такие проблемы уже лучше забить,
W> ИМХО.).

Тебе ведь нужны контраргументы, правильно? Так вот. Непонятно, какая может быть связь между _длительностью_ использования ресурса и _паузами_ между его повторным использованием. Можно нарваться на неприятности. Например, 2 часа пользователь играл в игру, находясь на 1-м уровне. После этого перешел на второй. Что, текстуры и уровни первого уровня будут в памяти висеть 2 часа? На мой взгляд, все-таки лучше выгружать по времени неиспользования. А насчет, почему 2 минуты, а не 3 — это да, в подобного рода алгоритмах от некоторой доли "волшебности" никуда не уйти.

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

Здравствуйте, Alex Alexandrov, Вы писали:

AA>Здравствуйте, _Winnie, Вы писали:
AA>Тебе ведь нужны контраргументы, правильно?
Aга. И еще какую нибудь простую гениальную идею. Я знаю, Кодт так может.

AA>Так вот. Непонятно, какая может быть связь между _длительностью_ использования ресурса и _паузами_ между его повторным использованием. Можно нарваться на неприятности. Например, 2 часа пользователь играл в игру, находясь на 1-м уровне. После этого перешел на второй.

Точно!
Вот.
Очередная идея.

Да, цеплятся к времени жизни — пожалуй, глупая идея.
Почему нужно что-то не выгружать? Потому что оно долго грузится обратно.
Поэтому новая идея такая: привязаться не к времени жизни, а к времени загрузки. Глупо, скажем, держать ресурс, который грузится 6 часов (УТРИРОВАННО!) две минуты после последнего Release. То что грузится за две наносекунды (тоже утрированно), тоже глупо кешировать в течение двух минут.

Поэтому такой вариант: при загрузке засекаем время t, в течение которого оно грузится. После начала неиcпользования держим ресурс 13*t времени. Тут я тоже вижу проблемы.

Ой, бежать надо. Чуть позже распишу какие...

Здравствуйте, _Winnie, Вы писали:
_W>Ой, бежать надо. Чуть позже распишу какие...


Пусть имеется маленький легкий ключик и большой тяжелый.

Бросим их с башни.
Маленький падает медленнее, так как он легче. Большой ключ, соответственно быстрее, и раньше долетит до земли.
Теперь бросим их с башни в связке – связку ключей. Она будет падать быстрей или медленней тяжелого ключа?

1)Разумеется, она будет падать медленней, так как маленький ключ будет тормозить большой.
2) Разумеется, она будет падать быстрей, так как связка из большого и маленького ключа тяжелей, чем один большой ключ.

Это противоречие доказывает, что большой и маленький ключ должны падать с одинаковой скоростью, не зависящей от массы

Теперь рассмотрим мою новую стратегию кэширования, где время неиспользования до выгрузки равно 13*(время загрузки).

Объединим формально два одинаковых ресурса в один (чисто логически). Тогда время их загрузки будет ровно в два раза дольше. И соответственно, время неиспользования до выгрузки тоже в 2 раза больше. А теперь, давайте их логически разъединим. Получим, что их теперь нужно выгружать в два раза быстрей. Противоречие…
Подскажите простую, непротиворечивую, красивую систему.

Здравствуйте, _Winnie, Вы писали:

_W>Стратегии кэширования ресурсов игры.

_W>Загруженные ресурсы(текстуры, звуковые буфера, шейдеры, и тп) делятся на используемые и неиспользуемые, последние хранятся на всякий случай, вдруг снова понадобятся.

_W>1) Идеальный случай.
используй мемори мепинг для файлов/стримов из которых грузиш ресурсы...
проблему выгрзки за ненадобностью на себя возьмет винда.

Здравствуйте, _Winnie, Вы писали:

__W>Подскажите простую, непротиворечивую, красивую систему.

Общие соображения:

Все стратегии кэширования внешних данных одинаково плохи до тех пор, пока не соблюдается хотя бы одно из следующих условий:
1) Стратегия кэширования явным образом учитывает схему данных и правильно вычисленную _априорную_ частоту и длительность их использования. Обычно этот подход не используется, т.к. схема данных считается изначально неизвестной.
2) Данные кластеризованы таким образом, чтобы при текущей стратегии их кэширования хотя бы частично выполнялось первое условие. Этот подход используется чаще, хотя и дает худшие результаты.

Вывод:

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

Пример:

Никакая универсальная стратегия кэширования не сможет сама определить, что лучше использовать:
map<pair<X,Y>, Z> или map<pair<Y,X>, Z>.

Предложение:

Аналогично графу PVS, строишь граф потенциально загружаемых ресурсов. Его используешь в следующих целях:
1) Для определения приоритета каждого ресурса;
2) Для упреждающей загрузки реурсов мелкими порциями, чтобы игра "подвисала" не редко и надолго, а постоянно и как бы незаметно. Квоту для каждого ресурса можно установить отдельно и сохранить для последующего использования, либо просто использовать таймер для ограничения кол-ва предварительно загружаемых ресурсов.
3) С кажой вершиной этого графа еще на этапе компиляции ресурсов можно сопоставить "временную метку" — т.е. время их последнего использованияупорядочить в соответствии с логикой прохождения игры. Эти метки можно использовать для выгрузки однозначно неиспользуемых ресурсов.
4) Ресурсы обязательно должны быть кластеризованы, т.к. повторного кэширования их виндой избежать не удастся, а винда все обрабатывает блоками по 64 кило.

Здравствуйте, lextasy, Вы писали:

L>Здравствуйте, _Winnie, Вы писали:

__W>>Подскажите простую, непротиворечивую, красивую систему.

L>Вывод:

L>Чтобы стратегия кэширования была эффективной, она должна быть согласована с моделью кэшируемых данных и моделью использования этих данных в программе. Соответственно, MapViewOfFile и иже с ними не подходят, т.к. они ничего не знают о модели кэшируемых данных, а мы практически ничего не знаем о том, как они работают в каждой конкретной версии Windows.

согласен на все 100%, но в большенстве случаев этого тебе должно хвататиь. и ресурсы можно реорганизовать так чтобы они хорошо вписывались в модель винды... но никто не запрещает тебе делать что-то свое... просто нейтив поддержка в основном намного лучше, чем писанная собственно-ручно... и нейтив модель от винды хорошо оттесчина и может использовань внутренее знание OS и MemoryManagment'a

L>Пример:

L>Никакая универсальная стратегия кэширования не сможет сама определить, что лучше использовать:
L>map<pair<X,Y>, Z> или map<pair<Y,X>, Z>.

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

Здравствуйте, alku, Вы писали:

A>согласен на все 100%, но в большенстве случаев этого тебе должно хвататиь. и ресурсы можно реорганизовать так чтобы они хорошо вписывались в модель винды... но никто не запрещает тебе делать что-то свое... просто нейтив поддержка в основном намного лучше, чем писанная собственно-ручно... и нейтив модель от винды хорошо оттесчина и может использовань внутренее знание OS и MemoryManagment'a

В большинстве случаев хватает и производительности файлмэппинга, и его практический предел в 1.5 Gb не особо ограничивает полет фантазии... только это не касается компьютерных игр. Для игрушки 1.5 Gb — это фонарь. А что касается производительности, то ребята из микрософта тут как раз и не блещут. Например, они полюбляют отображенные участки файла прогонять через файловый кэш, который в случае нехватки памяти не сбрасывают, а зачем-то пихают в файл подкачки — можешь себе представить, какие начинаются тормозняки. Кроме того, винда всегда откладывает своппинг до самого последнего момента, пока практически вся физическая память не исчерпается. В результате, когда она все-таки начинает свопить, ее колбасит по страшной силе, т.к. уже не остается у нее никакого "пространства для маневра", и она срывается в рекурсивный своппинг. Я достаточно обильно наэкспериментировался с этим API, и утверждаю, что MapViewOfFile работает эффективно только в том случае, если размер отображаемого участка памяти не превышает общий объем установленной на компьютер физической памяти.
Если же нужно отображать более 1 Gb, то все равно придется писать свой менеджер кэша, чтобы не переполнилось виртуальное адресное пространство (оно, между прочим, не резиновое).

_W>Пусть имеется маленький легкий ключик и большой тяжелый.

_W>Бросим их с башни.
_W>Маленький падает медленнее, так как он легче. Большой ключ, соответственно быстрее,
оффтопик
с какой это вдруг, на скорость падения стала влиять масса предмета?

А если просто?

Иметь список "приоритетности ресурса":
1) При открытии ресурса добалять выталкивать его на верхушку списка, если есть, и добавлять ново-созданный в верхушку, если нет
2) При нехватке "ресурсов системы" закрывать ресурсы с хвоста списка (самые редкоиспользуемые), по мере необходимости

* Размер "списка приоритетности" в идеале должен быть неограничен

Здравствуйте, Chez, Вы писали:

C>2) При нехватке "ресурсов системы" закрывать ресурсы с хвоста списка (самые редкоиспользуемые), по мере необходимости
Не понятно, что значит "При нехватке". API начнут выталкивать текстуры из видеопамяти в системную, оттуда в СВОП. А своп у меня на гигабайт. Правда, E_OUTOFMEMORY я навереное получу раньше. Невозможно точно сказать, сколько у меня свободной памяти и где что лежит.

Ну пока я сделал абсолютно ТРИВИАЛЬНО. убиваем сразу, как только никому не нужен. Пока нормально работает и так, дальше посмотрим.

Здравствуйте, DEMON HOOD, Вы писали:
DH>с какой это вдруг, на скорость падения стала влиять масса предмета?
Прочитай на две строчки ниже

Здравствуйте, _Winnie, Вы писали:

_W>Ну пока я сделал абсолютно ТРИВИАЛЬНО. убиваем сразу, как только никому не нужен. Пока нормально работает и так, дальше посмотрим.

Правильно. Теперь осталось только вместо того, чтобы убивать — отправлять в пул _фиксированного_ размера. Элементы пула следует прошить двухсвязным списком. Вставлять в голову списка, удалять из хвоста. Размер пула зависит от игры, ОС и объема ОЗУ, и может быть вычислен экспериментальным путем.
Если же файловый кэш эффективно работает как пул, то все это может не потребоваться.

Здравствуйте, _Winnie, Вы писали:

_W>Здравствуйте, DEMON HOOD, Вы писали:
DH>>с какой это вдруг, на скорость падения стала влиять масса предмета?
_W>Прочитай на две строчки ниже
подскажи, что именно прочитать? а то я не понял