pack: use a doubly linked lru list for eviction
Instead of going over every possible position in the hash table, use a
list to keep track of lru base, so we already know which ones to prefer.
Go with what git does as well, and limit the cache to 256 elements
instead of using a memory size limit.
This does make it perform better, but only by a smaller margin that I
had hoped.
diff --git a/src/pack.c b/src/pack.c
index de038a4..e360529 100644
--- a/src/pack.c
+++ b/src/pack.c
@@ -50,17 +50,25 @@
* Delta base cache
********************/
-static git_pack_cache_entry *new_cache_object(git_rawobj *source)
+static git_pack_cache_entry *new_cache_object(git_rawobj *source, git_off_t offset)
{
git_pack_cache_entry *e = git__calloc(1, sizeof(git_pack_cache_entry));
if (!e)
return NULL;
memcpy(&e->raw, source, sizeof(git_rawobj));
+ e->next = e->prev = e;
+ e->offset = offset;
return e;
}
+static void remove_entry(git_pack_cache_entry *entry)
+{
+ entry->prev->next = entry->next;
+ entry->next->prev = entry->prev;
+}
+
static void free_cache_object(void *o)
{
git_pack_cache_entry *e = (git_pack_cache_entry *)o;
@@ -74,12 +82,16 @@
static void cache_free(git_pack_cache *cache)
{
- khiter_t k;
+ git_pack_cache_entry *entry, *next;
+ /* this works as a proxy for an initialized cache */
if (cache->entries) {
- for (k = kh_begin(cache->entries); k != kh_end(cache->entries); k++) {
- if (kh_exist(cache->entries, k))
- free_cache_object(kh_value(cache->entries, k));
+ entry = cache->sentinel.next;
+ while (entry != &cache->sentinel) {
+ next = entry->next;
+ remove_entry(entry);
+ free_cache_object(entry);
+ entry = next;
}
git_offmap_free(cache->entries);
@@ -107,9 +119,30 @@
return -1;
}
+ cache->sentinel.prev = &cache->sentinel;
+ cache->sentinel.next = &cache->sentinel;
+
return 0;
}
+/* call with the cache lock held */
+static void move_to_front(git_pack_cache *cache, git_pack_cache_entry *entry)
+{
+ git_pack_cache_entry *next = NULL, *latest = NULL;
+
+ /* remove the entry from the current position */
+ next = entry->next;
+ entry->prev->next = entry->next;
+ next->prev = entry->prev;
+
+ /* and put ourselves at the top of the list */
+ latest = cache->sentinel.prev;
+ entry->next = latest->next;
+ latest->next = entry;
+ entry->prev = latest;
+ entry->next->prev = entry;
+}
+
static git_pack_cache_entry *cache_get(git_pack_cache *cache, git_off_t offset)
{
khiter_t k;
@@ -122,7 +155,7 @@
if (k != kh_end(cache->entries)) { /* found it */
entry = kh_value(cache->entries, k);
git_atomic_inc(&entry->refcount);
- entry->last_usage = cache->use_ctr++;
+ move_to_front(cache, entry);
}
git_mutex_unlock(&cache->lock);
@@ -130,23 +163,27 @@
}
/* Run with the cache lock held */
-static void free_lowest_entry(git_pack_cache *cache)
+static int free_lowest_entry(git_pack_cache *cache)
{
git_pack_cache_entry *entry;
khiter_t k;
+ int error = 0;
- for (k = kh_begin(cache->entries); k != kh_end(cache->entries); k++) {
- if (!kh_exist(cache->entries, k))
- continue;
-
- entry = kh_value(cache->entries, k);
-
- if (entry && entry->refcount.val == 0) {
+ entry = cache->sentinel.next;
+ while (entry != &cache->sentinel) {
+ if (entry->refcount.val == 0) {
cache->memory_used -= entry->raw.len;
+ cache->nentries--;
+ k = kh_get(off, cache->entries, entry->offset);
kh_del(off, cache->entries, k);
+ remove_entry(entry);
free_cache_object(entry);
+ break;
}
+ entry = entry->next;
}
+
+ return error;
}
static int cache_add(git_pack_cache *cache, git_rawobj *base, git_off_t offset)
@@ -158,7 +195,7 @@
if (base->len > GIT_PACK_CACHE_SIZE_LIMIT)
return -1;
- entry = new_cache_object(base);
+ entry = new_cache_object(base, offset);
if (entry) {
if (git_mutex_lock(&cache->lock) < 0) {
giterr_set(GITERR_OS, "failed to lock cache");
@@ -167,13 +204,15 @@
/* Add it to the cache if nobody else has */
exists = kh_get(off, cache->entries, offset) != kh_end(cache->entries);
if (!exists) {
- while (cache->memory_used + base->len > cache->memory_limit)
+ while (cache->nentries > 256)
free_lowest_entry(cache);
k = kh_put(off, cache->entries, offset, &error);
assert(error != 0);
kh_value(cache->entries, k) = entry;
cache->memory_used += entry->raw.len;
+ cache->nentries++;
+ move_to_front(cache, entry);
}
git_mutex_unlock(&cache->lock);
/* Somebody beat us to adding it into the cache */
diff --git a/src/pack.h b/src/pack.h
index 58f81e2..2985c8e 100644
--- a/src/pack.h
+++ b/src/pack.h
@@ -55,8 +55,10 @@
};
typedef struct git_pack_cache_entry {
- size_t last_usage; /* enough? */
+ struct git_pack_cache_entry *prev;
+ struct git_pack_cache_entry *next;
git_atomic refcount;
+ git_off_t offset;
git_rawobj raw;
} git_pack_cache_entry;
@@ -71,9 +73,10 @@
typedef struct {
size_t memory_used;
size_t memory_limit;
- size_t use_ctr;
+ git_pack_cache_entry sentinel;
git_mutex lock;
git_offmap *entries;
+ size_t nentries;
} git_pack_cache;
struct git_pack_file {
