Вопросы по созданию кэша (+)

>КАК МНЕ РАЗРУЛИТЬ ПРОБЛЕМУ ???

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

См., как в OCaml реализованы weak pointers. Оченно эффективно для всякого рода кэшей...

если нет дополнительных требований - длину элемента писать в память перед ним самим и писать/удалять по кругу

фрагментация быстро возникнет :-(.

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

читай у Кнута, помоему в первом томе

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

Дык, если данные совершенно нерегулярны, то, IMHO, нечего велосипед изобретать, делай обычное кэширование линейками (как в процессорах сделано), с обратной записью. Если памяти много, то подойдет самый примитивный direct-mapped cache.

2 Die-Hard
Сорри не совсем догнал как ты предлогаешь сделать
Чуть подробнее если можно.
Данные храняться иногда довольно долго днями
(ведется статсы по попаданиям и выкидываются
только наимение используемые элементы)
А скорость поиска элементов критична этож кэш
всеже он для этого и нужен....

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

2anonymous (*) (27.09.2004 14:20:04):

Просто, классические способы кэширования, "как в школе проходят". Набери в Гугле типа

direct mapped fully associative cache

Вот, навскидку:

http://courses.ece.uiuc.edu/ece411/lectures/LectureFall03/Lecture8.pdf http://courses.ece.uiuc.edu/ece411/lectures/LectureFall03/Lecture9.pdf

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

Ну, разумеется, идея требует творческой доработки...

2 Die-Hard
Спасибо все понял
В моем конкретном случае правда много проще
для заточки под скорость сделать оверхед по данным
и работать со элементами одного размера но идея в общемто
интересная и как-то в голову не приходила спасибо.

Наверное уже был об этом разговор, если что извините.
Можно разбить всю память на 2 неравные части (можно не разбивать)
в одной маленькой, все поля имеют один размер - там хранятся
указатели на сами данные;
в другой  хранятся сами данные большого и различного размера.
Сами эти большие данные можно разбить на страницы 
(блоки одинакового размера) и организовать их в список - наверное это
правильно.
Поиск, добавление и удаление ведется по списку (массиву) где хранятся
указатели. (хэш таблица) - ее можно сортировать и индексировать.