commit bb7182a5b18165905163dc712f19974358abfe76
from: Stefan Sperling <stsp@stsp.name>
date: Sun Sep 16 14:12:58 2018 UTC

speed up object id cache by using multiple lists

commit - 59790a325126d5fa5d7b2a0af2b2db6357d55063
commit + bb7182a5b18165905163dc712f19974358abfe76
blob - c10be9b25f2c42ae51559018bee66d6d981c67f9
blob + 340cb9c6d027478c290e3e6453ed01ae32f4048d
--- lib/object_idcache.c
+++ 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;
+	int i;
 
-	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);
+	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 *cach
     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 *cach
 	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 
     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_idc
     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;
 }