LRU кеширует в C

Question

Мне нужно кэшировать большое (но переменное) количество мелких файлов (от 1 килобайта до 10 мегабайт) в памяти для приложения C (в среде * nix).Поскольку я не хочу использовать всю свою память, я бы хотел установить жесткий предел памяти (скажем, 64 мегабайта) и помещать файлы в хеш-таблицу с именем файла в качестве ключа и распоряжаться записями с наименьшим использованием.,Я считаю, что мне нужен кеш LRU.

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

Примечание: я понимаю, что это почти точно функция memcache, но это не вариант для меня.Я также взглянул на источник в надежде просветить себя в кэшировании LRU, но безуспешно.

Answer 1

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

Я просто догадываюсь здесь, но вы могли бы сделать что-то вроде этого (используя псевдо-C здесь, потому что я ленивый). Вот основные структуры данных:

struct File
{
    // hash key
    string Name;

    // doubly-linked list
    File* Previous;
    File* Next;

    // other file data...
}

struct Cache
{
    HashTable<string, File*> Table // some existing hashtable implementation
    File* First; // most recent
    File* Last;  // least recent
}

А вот как вы можете открыть и закрыть файл:

File* Open(Cache* cache, string name)
{
    if (look up name in cache->Table succeeds)
    {
        File* found = find it from the hash table lookup
        move it to the front of the list
    }
    else
    {
        File* newFile = open the file and create a new node for it

        insert it at the beginning of the list

        if (the cache is full now)
        {
            remove the last file from the list
            close it
            remove it from the hashtable too
        }
    }
}

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

Но я могу быть абсолютно неправ во всем этом.

Answer 2

Если вы используете Linux, я думаю, что ОС сделает все, что вам нужно, особенно если вы воспользуетесь системным вызовом fadvise, чтобы сообщить системе, какие файлы вы планируете использовать дальше .

Answer 3

Кажется, вы можете создать LRU-кэш в C с помощью uthash .

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

Answer 4

koders.com находит несколько;тот, который легче всего адаптировать и использовать повторно (если вы согласны с условиями лицензии), выглядит как , этот из проекта FreeType (потребуется некоторое время для его, хм, интереса препроцессорная работа).В худшем случае он должен показать вам один подход, при котором вы можете реализовать кэш LRU на языке C.

Большинство реализаций кэш-памяти LRU многократного использования (а их много в сети), конечно, используют более удобные языкиJava, C ++, C #, Python, ...), которые предлагают более сильные структуры данных и, как правило, управление памятью.

Answer 5

Мне неизвестны какие-либо общие библиотеки среды Unix в C, но это не должно быть сложно реализовать.

Для примеров кода я предлагаю взглянуть на любую из реализаций хэш-таблиц gazillion (oi). Независимо от того, использует ли таблица связанный список или древовидную структуру для фактической обработки, весьма часто используется некоторая форма кэширования (например, MRU), поэтому она может дать вам представление о том, как может выглядеть реализация. Некоторые простые сборщики мусора и различное программное обеспечение, нуждающееся в алгоритме замены страниц, также могут стоить посмотреть.

По сути, вы отмечаете вещи, когда к ним обращаются, и стареете ссылки. Если вы увеличиваете возраст вещей при доступе, а не у каждого равноправного элемента, к которому вы обращались, вы, очевидно, сохраняете цикл при доступе и переносите вес на операцию истечения срока действия. Вы захотите сделать небольшое профилирование, чтобы найти общее представление о том, насколько менее недавний достаточно! Достаточно недавний для вашей задачи. Когда вы доберетесь до этой точки, вы просто обновите кеш соответственно.