Commit 335d6c998041f7c44dce48d3bb087c52136d970f
2011-05-17T01:46:07
cache: Drop cuckoo hashing Now we use a simple closed-addressing cache. Cuckoo hashing was creating too many issues with race conditions. Fuck that. Let's see what happens performance wise, we may have to roll back or come up with another way to implement an efficient multi-threaded cache.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
diff --git a/src/cache.c b/src/cache.c
index 6e4ad4c..433fc3d 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -29,9 +29,6 @@
#include "thread-utils.h"
#include "cache.h"
-#define GIT_CACHE_OPENADR 3
-
-
int git_cache_init(git_cache *cache, size_t size, git_cached_obj_freeptr free_ptr)
{
size_t i;
@@ -58,7 +55,6 @@ int git_cache_init(git_cache *cache, size_t size, git_cached_obj_freeptr free_pt
for (i = 0; i < (size + 1); ++i) {
git_mutex_init(&cache->nodes[i].lock);
cache->nodes[i].ptr = NULL;
- cache->nodes[i].lru = 0;
}
return GIT_SUCCESS;
@@ -81,93 +77,53 @@ void git_cache_free(git_cache *cache)
void *git_cache_get(git_cache *cache, const git_oid *oid)
{
const uint32_t *hash;
- size_t i, pos, found = 0;
cache_node *node = NULL;
+ void *result = NULL;
hash = (const uint32_t *)oid->id;
+ node = &cache->nodes[hash[0] & cache->size_mask];
- for (i = 0; !found && i < GIT_CACHE_OPENADR; ++i) {
- pos = hash[i] & cache->size_mask;
- node = &cache->nodes[pos];
-
- git_mutex_lock(&node->lock);
- {
- if (node->ptr && git_cached_obj_compare(node->ptr, oid) == 0) {
- git_cached_obj_incref(node->ptr);
- node->lru = ++cache->lru_count;
- found = 1;
- }
+ git_mutex_lock(&node->lock);
+ {
+ if (node->ptr && git_cached_obj_compare(node->ptr, oid) == 0) {
+ git_cached_obj_incref(node->ptr);
+ result = node->ptr;
}
- git_mutex_unlock(&node->lock);
}
+ git_mutex_unlock(&node->lock);
-
- return found ? node->ptr : NULL;
+ return result;
}
void *git_cache_try_store(git_cache *cache, void *entry)
{
- cache_node *nodes[GIT_CACHE_OPENADR], *lru_node;
const uint32_t *hash;
const git_oid *oid;
- size_t i, j, node_count;
+ cache_node *node = NULL;
oid = &((git_cached_obj*)entry)->oid;
hash = (const uint32_t *)oid->id;
+ node = &cache->nodes[hash[0] & cache->size_mask];
/* increase the refcount on this object, because
* the cache now owns it */
git_cached_obj_incref(entry);
-
- node_count = 0;
- for (i = 0; i < GIT_CACHE_OPENADR; ++i) {
- size_t pos = hash[i] & cache->size_mask;
- cache_node *node = &cache->nodes[pos];
-
- for (j = 0; j < node_count; ++j)
- if (nodes[j] == node)
- break;
-
- if (j == node_count) {
- nodes[node_count++] = node;
- git_mutex_lock(node);
- }
- }
-
- lru_node = nodes[0];
-
- for (i = 0; i < node_count; ++i) {
-
- if (nodes[i]->ptr == NULL) {
- nodes[i]->ptr = entry;
- nodes[i]->lru = ++cache->lru_count;
- break;
- } else if (git_cached_obj_compare(nodes[i]->ptr, oid) == 0) {
- git_cached_obj_decref(entry, cache->free_obj);
- entry = nodes[i]->ptr;
- nodes[i]->lru = ++cache->lru_count;
- break;
- }
-
- if (nodes[i]->lru < lru_node->lru)
- lru_node = nodes[i];
- }
-
- if (i == node_count) {
- void *old_entry = lru_node->ptr;
- assert(old_entry);
-
- git_cached_obj_decref(old_entry, cache->free_obj);
- lru_node->ptr = entry;
- lru_node->lru = ++cache->lru_count;
+ git_mutex_lock(&node->lock);
+
+ if (node->ptr == NULL) {
+ node->ptr = entry;
+ } else if (git_cached_obj_compare(node->ptr, oid) == 0) {
+ git_cached_obj_decref(entry, cache->free_obj);
+ entry = node->ptr;
+ } else {
+ git_cached_obj_decref(node->ptr, cache->free_obj);
+ node->ptr = entry;
}
/* increase the refcount again, because we are
* returning it to the user */
git_cached_obj_incref(entry);
-
- for (i = 0; i < node_count; ++i)
- git_mutex_unlock(&nodes[i]->lock);
+ git_mutex_unlock(&node->lock);
return entry;
}
diff --git a/src/cache.h b/src/cache.h
index 2d9bb51..4794dea 100644
--- a/src/cache.h
+++ b/src/cache.h
@@ -19,7 +19,6 @@ typedef struct {
typedef struct {
git_cached_obj *ptr;
git_mutex lock;
- unsigned int lru;
} cache_node;
typedef struct {