Commit bb7182a5b18165905163dc712f19974358abfe76
2018-09-16T16:12:58
speed up object id cache by using multiple lists
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 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
diff --git a/lib/object_idcache.c b/lib/object_idcache.c
index c10be9b..340cb9c 100644
--- a/lib/object_idcache.c
+++ b/lib/object_idcache.c
@@ -45,8 +45,14 @@ struct got_object_idcache_element {
TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
struct got_object_idcache {
- struct got_object_idcache_head entries;
- int nelem;
+ /*
+ * The cache is implemented as a collection of 256 lists.
+ * The value of the first byte of an object ID determines
+ * which of these lists an object ID is stored in.
+ */
+ struct got_object_idcache_head entries[0xff + 1];
+ int nelem[0xff + 1];
+ int totelem;
int maxelem;
};
@@ -54,12 +60,14 @@ struct got_object_idcache *
got_object_idcache_alloc(int maxelem)
{
struct got_object_idcache *cache;
+ int i;
cache = calloc(1, sizeof(*cache));
if (cache == NULL)
return NULL;
- TAILQ_INIT(&cache->entries);
+ for (i = 0; i < nitems(cache->entries); i++)
+ TAILQ_INIT(&cache->entries[i]);
cache->maxelem = maxelem;
return cache;
}
@@ -68,12 +76,15 @@ void
got_object_idcache_free(struct got_object_idcache *cache)
{
struct got_object_idcache_element *entry;
-
- while (!TAILQ_EMPTY(&cache->entries)) {
- entry = TAILQ_FIRST(&cache->entries);
- TAILQ_REMOVE(&cache->entries, entry, entry);
- /* User data should be freed by caller. */
- free(entry);
+ int i;
+
+ for (i = 0; i < nitems(cache->entries); i++) {
+ while (!TAILQ_EMPTY(&cache->entries[i])) {
+ entry = TAILQ_FIRST(&cache->entries[i]);
+ TAILQ_REMOVE(&cache->entries[i], entry, entry);
+ /* User data should be freed by caller. */
+ free(entry);
+ }
}
free(cache);
}
@@ -83,8 +94,9 @@ got_object_idcache_add(struct got_object_idcache *cache,
struct got_object_id *id, void *data)
{
struct got_object_idcache_element *entry;
+ uint8_t i = id->sha1[0];
- if (cache->nelem >= cache->maxelem)
+ if (cache->totelem >= cache->maxelem)
return got_error(GOT_ERR_NO_SPACE);
entry = calloc(1, sizeof(*entry));
@@ -94,8 +106,9 @@ got_object_idcache_add(struct got_object_idcache *cache,
memcpy(&entry->id, id, sizeof(entry->id));
entry->data = data;
- TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
- cache->nelem++;
+ TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
+ cache->nelem[i]++;
+ cache->totelem++;
return NULL;
}
@@ -103,13 +116,14 @@ void *
got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
{
struct got_object_idcache_element *entry;
+ uint8_t i = id->sha1[0];
- TAILQ_FOREACH(entry, &cache->entries, entry) {
+ TAILQ_FOREACH(entry, &cache->entries[i], entry) {
if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0)
continue;
- if (entry != TAILQ_FIRST(&cache->entries)) {
- TAILQ_REMOVE(&cache->entries, entry, entry);
- TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
+ if (entry != TAILQ_FIRST(&cache->entries[i])) {
+ TAILQ_REMOVE(&cache->entries[i], entry, entry);
+ TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
}
return entry->data;
}
@@ -121,19 +135,28 @@ const struct got_error *
got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
{
struct got_object_idcache_element *entry;
+ int i, idx = 0, maxelem = cache->nelem[0];
if (data)
*data = NULL;
- if (cache->nelem == 0)
+ if (cache->totelem == 0)
return got_error(GOT_ERR_NO_OBJ);
- entry = TAILQ_LAST(&cache->entries, got_object_idcache_head);
- TAILQ_REMOVE(&cache->entries, entry, entry);
+ /* Remove least used element from longest list. */
+ for (i = 0; i < nitems(cache->entries); i++) {
+ if (maxelem < cache->nelem[i]) {
+ idx = i;
+ maxelem = cache->nelem[i];
+ }
+ }
+ entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head);
+ TAILQ_REMOVE(&cache->entries[idx], entry, entry);
if (data)
*data = entry->data;
free(entry);
- cache->nelem--;
+ cache->nelem[idx]--;
+ cache->totelem--;
return NULL;
}
@@ -142,8 +165,9 @@ got_object_idcache_contains(struct got_object_idcache *cache,
struct got_object_id *id)
{
struct got_object_idcache_element *entry;
+ uint8_t i = id->sha1[0];
- TAILQ_FOREACH(entry, &cache->entries, entry) {
+ TAILQ_FOREACH(entry, &cache->entries[i], entry) {
if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0)
return 1;
}
@@ -155,13 +179,16 @@ void got_object_idcache_for_each(struct got_object_idcache *cache,
void (*cb)(struct got_object_id *, void *, void *), void *arg)
{
struct got_object_idcache_element *entry;
+ int i;
- TAILQ_FOREACH(entry, &cache->entries, entry)
- cb(&entry->id, entry->data, arg);
+ for (i = 0; i < nitems(cache->entries); i++) {
+ TAILQ_FOREACH(entry, &cache->entries[i], entry)
+ cb(&entry->id, entry->data, arg);
+ }
}
int
-got_object_idcache_num_elements(struct got_object_idcache *set)
+got_object_idcache_num_elements(struct got_object_idcache *cache)
{
- return set->nelem;
+ return cache->totelem;
}