On Mon, Apr 17, 2023 at 01:36:12PM +0200, Stefan Sperling wrote:
> On Mon, Apr 17, 2023 at 01:07:33PM +0200, Stefan Sperling wrote:
> > The profiler breaks got_object_parse_tree_entry() run-time down as follows:
> > 
> >  80% commit_traversal_request
> >  70% open_tree
> 
> Looking at commit_traversal_request again, we should be able to speed
> it up by caching trees. Currently this function loops and opens two
> trees per iteration. One of those trees has likely already been parsed
> during the previous loop iteration but has since been discarded.
> And when tree_path_changed() traverses into subtrees there is no caching
> either, which means quite some effort might be spent parsing the same
> trees over and over again.

Below is a patch which implements caching of parsed trees in got-read-pack.
Unfortunately, this does not seem to help your case much, if at all.

The devel/ directory in the FreeBSD ports tree is very large, with over
7000 entries in recent commits, and with 115415 commits in its history.
By comparison, the devel/ directory in OpenBSD ports has about 1800 entries
in recent comits, and 27431 commits of history.
These are order of magnitude differences!

Logging a path is also slow but not unusable in the OpenBSD ports tree.
On my x250 it usally completes with a one minute or two for ports with
much history like devel/gmake. Not great, but not catastrophic either
given that people rarely go digging into the history of a specific path
during most workflows.

I guess we could use the patch below if it helps you a little bit. But in
my testing the difference is not significant. This kind of caching would
probably shine more with very deep directory hierarchies where a lot of
path space needs to be traversed for each commit. But the case we are
looking at, with just 2 levels of hierarchy, is relatively flat.
If this doesn't help you I would rather discard this patch since it introduces
higher memory usage as a trade-off.

I am afraid the only way I see to speed this up is to get rid of entry
sorting in the tree parser and then deal with the consequences of doing so.
Which isn't going to be pretty. Does anyone else have other ideas?

diff refs/heads/main refs/heads/parsed-tree-cache
commit - 2b70695630ead3274d31727f6b477f3544dc9c9a
commit + 0006909a00949d4940a16c1dc9f6f388f3845962
blob - ef9737b133c279be1e1781fc0b8145a641d1fc30
blob + 00be2decfaf40e5dd7d8621a2a90bbea6a929c0e
--- lib/got_lib_object_cache.h
+++ lib/got_lib_object_cache.h
@@ -20,6 +20,7 @@ enum got_object_cache_type {
 	GOT_OBJECT_CACHE_TYPE_COMMIT,
 	GOT_OBJECT_CACHE_TYPE_TAG,
 	GOT_OBJECT_CACHE_TYPE_RAW,
+	GOT_OBJECT_CACHE_TYPE_PARSED_TREE,
 };
 
 struct got_object_cache_entry {
@@ -30,6 +31,7 @@ struct got_object_cache_entry {
 		struct got_commit_object *commit;
 		struct got_tag_object *tag;
 		struct got_raw_object *raw;
+		struct got_parsed_tree *parsed_tree;
 	} data;
 };
 
blob - ff0be54ad39998cf5dffd4bd99a222298cd15e06
blob + e95077db5ad9175f9539c9b459daa053a975aeb8
--- lib/got_lib_object_parse.h
+++ lib/got_lib_object_parse.h
@@ -32,10 +32,20 @@ const struct got_error *got_object_parse_tree(struct g
 	mode_t mode; /* Mode parsed from tree buffer. */
 	uint8_t *id; /* Points to ID in parsed tree buffer. */
 };
+
+struct got_parsed_tree {
+	int refcnt;
+	uint8_t *buf;
+	size_t bufsize;
+	struct got_parsed_tree_entry *entries;
+	size_t nentries;
+};
+
 const struct got_error *got_object_parse_tree(struct got_parsed_tree_entry **,
     size_t *, size_t *, uint8_t *, size_t);
 const struct got_error *got_object_read_tree(struct got_parsed_tree_entry **,
     size_t *, size_t *, uint8_t **, int, struct got_object_id *);
+void got_object_parsed_tree_close(struct got_parsed_tree *);
 
 const struct got_error *got_object_parse_tag(struct got_tag_object **,
     uint8_t *, size_t);
blob - 82f79f01406b91db661457f0b87bd9d528f1085d
blob + 3c7d62976f5bb49355d873fe978b7ee9756b94b4
--- lib/object_cache.c
+++ lib/object_cache.c
@@ -35,6 +35,7 @@
 #include "got_lib_object.h"
 #include "got_lib_object_idset.h"
 #include "got_lib_object_cache.h"
+#include "got_lib_object_parse.h"
 
 /*
  * XXX This should be reworked to track cache size and usage in bytes,
@@ -65,6 +66,7 @@ got_object_cache_init(struct got_object_cache *cache,
 		cache->size = GOT_OBJECT_CACHE_SIZE_OBJ;
 		break;
 	case GOT_OBJECT_CACHE_TYPE_TREE:
+	case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
 		cache->size = GOT_OBJECT_CACHE_SIZE_TREE;
 		break;
 	case GOT_OBJECT_CACHE_TYPE_COMMIT:
@@ -146,6 +148,16 @@ const struct got_error *
 	return sizeof(*raw);
 }
 
+static size_t
+get_size_parsed_tree(struct got_parsed_tree *tree)
+{
+	size_t size = sizeof(*tree);
+
+	size += sizeof(struct got_parsed_tree_entry) * tree->nentries;
+	size += tree->bufsize;
+	return size;
+}
+
 const struct got_error *
 got_object_cache_add(struct got_object_cache *cache, struct got_object_id *id,
     void *item)
@@ -171,6 +183,9 @@ got_object_cache_add(struct got_object_cache *cache, s
 	case GOT_OBJECT_CACHE_TYPE_RAW:
 		size = get_size_raw((struct got_raw_object *)item);
 		break;
+	case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+		size = get_size_parsed_tree((struct got_parsed_tree *)item);
+		break;
 	default:
 		return got_error(GOT_ERR_OBJ_TYPE);
 	}
@@ -197,6 +212,9 @@ got_object_cache_add(struct got_object_cache *cache, s
 		case GOT_OBJECT_CACHE_TYPE_RAW:
 			fprintf(stderr, "raw");
 			break;
+		case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+			fprintf(stderr, "parsed-tree");
+			break;
 		}
 		fprintf(stderr, " %s (%zd bytes; %zd MB)\n", id_str, size,
 		    size/1024/1024);
@@ -228,6 +246,9 @@ got_object_cache_add(struct got_object_cache *cache, s
 		case GOT_OBJECT_CACHE_TYPE_RAW:
 			got_object_raw_close(ce->data.raw);
 			break;
+		case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+			got_object_parsed_tree_close(ce->data.parsed_tree);
+			break;
 		}
 		memset(ce, 0, sizeof(*ce));
 		cache->cache_evict++;
@@ -254,6 +275,9 @@ got_object_cache_add(struct got_object_cache *cache, s
 	case GOT_OBJECT_CACHE_TYPE_RAW:
 		ce->data.raw = (struct got_raw_object *)item;
 		break;
+	case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+		ce->data.parsed_tree = (struct got_parsed_tree *)item;
+		break;
 	}
 
 	err = got_object_idset_add(cache->idset, id, ce);
@@ -284,6 +308,8 @@ got_object_cache_get(struct got_object_cache *cache, s
 			return ce->data.tag;
 		case GOT_OBJECT_CACHE_TYPE_RAW:
 			return ce->data.raw;
+		case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+			return ce->data.parsed_tree;
 		}
 	}
 
@@ -314,6 +340,7 @@ check_refcount(struct got_object_id *id, void *data, v
 	struct got_commit_object *commit;
 	struct got_tag_object *tag;
 	struct got_raw_object *raw;
+	struct got_parsed_tree *parsed_tree;
 	char *id_str;
 
 	if (got_object_id_str(&id_str, id) != NULL)
@@ -355,6 +382,13 @@ check_refcount(struct got_object_id *id, void *data, v
 		fprintf(stderr, "raw %s has %d unclaimed references\n",
 		    id_str, raw->refcnt - 1);
 		break;
+	case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+		parsed_tree = ce->data.parsed_tree;
+		if (parsed_tree->refcnt == 1)
+			break;
+		fprintf(stderr, "raw %s has %d unclaimed references\n",
+		    id_str, parsed_tree->refcnt - 1);
+		break;
 	}
 	free(id_str);
 	return NULL;
@@ -383,6 +417,9 @@ free_entry(struct got_object_id *id, void *data, void 
 	case GOT_OBJECT_CACHE_TYPE_RAW:
 		got_object_raw_close(ce->data.raw);
 		break;
+	case GOT_OBJECT_CACHE_TYPE_PARSED_TREE:
+		got_object_parsed_tree_close(ce->data.parsed_tree);
+		break;
 	}
 
 	free(ce);
blob - 28536b3cc7243ce070909cda1331a2b7750713e0
blob + f6f6fd5e685f8da5db052e7b6558eb2b898ac62c
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -867,6 +867,20 @@ const struct got_error *
 	return err;
 }
 
+void
+got_object_parsed_tree_close(struct got_parsed_tree *tree)
+{
+	if (tree->refcnt > 0) {
+		tree->refcnt--;
+		if (tree->refcnt > 0)
+			return;
+	}
+
+	free(tree->buf);
+	free(tree->entries);
+	free(tree);
+}
+
 const struct got_error *
 got_object_read_tree(struct got_parsed_tree_entry **entries, size_t *nentries,
     size_t *nentries_alloc, uint8_t **p, int fd,
blob - 1ff3707be9bef771b3d4084997853ada44c722ac
blob + c1187ff00e3e443911d707148be24ae25a436e33
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -185,15 +185,16 @@ open_tree(uint8_t **buf, struct got_parsed_tree_entry 
 }
 
 static const struct got_error *
-open_tree(uint8_t **buf, struct got_parsed_tree_entry **entries, size_t *nentries,
+open_tree(uint8_t **buf, size_t *len,
+    struct got_parsed_tree_entry **entries, size_t *nentries,
     size_t *nentries_alloc, struct got_pack *pack, struct got_packidx *packidx,
     int obj_idx, struct got_object_id *id, struct got_object_cache *objcache)
 {
 	const struct got_error *err = NULL;
 	struct got_object *obj = NULL;
-	size_t len;
 
 	*buf = NULL;
+	*len = 0;
 	*nentries = 0;
 
 	obj = got_object_cache_get(objcache, id);
@@ -206,24 +207,78 @@ open_tree(uint8_t **buf, struct got_parsed_tree_entry 
 			return err;
 	}
 
-	err = got_packfile_extract_object_to_mem(buf, &len, obj, pack);
+	err = got_packfile_extract_object_to_mem(buf, len, obj, pack);
 	if (err)
 		goto done;
 
-	obj->size = len;
+	obj->size = *len;
 
 	err = got_object_parse_tree(entries, nentries, nentries_alloc,
-	    *buf, len);
+	    *buf, *len);
 done:
 	got_object_close(obj);
 	if (err) {
 		free(*buf);
 		*buf = NULL;
+		*len = 0;
+		*nentries = 0;
 	}
 	return err;
 }
 
 static const struct got_error *
+cache_parsed_tree(struct got_parsed_tree **new,
+    struct got_object_id *id, struct got_pack *pack,
+    struct got_packidx *packidx, int idx, 
+    struct got_object_cache *objcache,
+    struct got_object_cache *treecache)
+{
+	const struct got_error *err;
+	uint8_t *buf = NULL;
+	size_t bufsize;
+	struct got_parsed_tree_entry *entries = NULL;
+	size_t nentries = 0, nentries_alloc = 0;
+	struct got_parsed_tree *tree;
+
+	if (new)
+		*new = NULL;
+	
+	err = open_tree(&buf, &bufsize, &entries, &nentries, &nentries_alloc,
+	    pack, packidx, idx, id, objcache);
+	if (err)
+		return err;
+
+	tree = calloc(1, sizeof(*tree));
+	if (tree == NULL) {
+		err = got_error_from_errno("calloc");
+		goto done;
+	}
+
+	tree->refcnt = 1;
+	tree->buf = buf;
+	buf = NULL;
+	tree->bufsize = bufsize;
+	tree->entries = entries;
+	entries = NULL;
+	tree->nentries = nentries;
+
+	err = got_object_cache_add(treecache, id, tree);
+	if (err)
+		goto done;
+done:
+	if (err) {
+		if (tree)
+			got_object_parsed_tree_close(tree);
+		free(buf);
+	} else {
+		tree->refcnt++;
+		if (new)
+			*new = tree;
+	}
+	return NULL;
+}
+
+static const struct got_error *
 tree_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack,
     struct got_packidx *packidx, struct got_object_cache *objcache,
     struct got_parsed_tree_entry **entries, size_t *nentries,
@@ -233,7 +288,7 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 	struct got_imsg_packed_object iobj;
 	uint8_t *buf = NULL;
 	struct got_object_id id;
-	size_t datalen;
+	size_t datalen, bufsize;
 
 	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
 	if (datalen != sizeof(iobj))
@@ -241,7 +296,7 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 	memcpy(&iobj, imsg->data, sizeof(iobj));
 	memcpy(&id, &iobj.id, sizeof(id));
 
-	err = open_tree(&buf, entries, nentries, nentries_alloc,
+	err = open_tree(&buf, &bufsize, entries, nentries, nentries_alloc,
 	    pack, packidx, iobj.idx, &id, objcache);
 	if (err)
 		return err;
@@ -454,13 +509,11 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 }
 
 static const struct got_error *
-tree_path_changed(int *changed, uint8_t **buf1, uint8_t **buf2,
-    struct got_parsed_tree_entry **entries1, size_t *nentries1,
-    size_t *nentries_alloc1,
-    struct got_parsed_tree_entry **entries2, size_t *nentries2,
-    size_t *nentries_alloc2,
+tree_path_changed(int *changed,
+    struct got_parsed_tree **tree1, struct got_parsed_tree **tree2,
     const char *path, struct got_pack *pack, struct got_packidx *packidx,
-    struct imsgbuf *ibuf, struct got_object_cache *objcache)
+    struct imsgbuf *ibuf, struct got_object_cache *objcache,
+    struct got_object_cache *treecache)
 {
 	const struct got_error *err = NULL;
 	struct got_parsed_tree_entry *pte1 = NULL, *pte2 = NULL;
@@ -469,7 +522,7 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 
 	*changed = 0;
 
-	/* We not do support comparing the root path. */
+	/* We do not support comparing the root path. */
 	if (got_path_is_root_dir(path))
 		return got_error_path(path, GOT_ERR_BAD_PATH);
 
@@ -486,13 +539,15 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				continue;
 		}
 
-		pte1 = find_entry_by_name(*entries1, *nentries1, seg, seglen);
+		pte1 = find_entry_by_name((*tree1)->entries,
+		    (*tree1)->nentries, seg, seglen);
 		if (pte1 == NULL) {
 			err = got_error(GOT_ERR_NO_OBJ);
 			break;
 		}
 
-		pte2 = find_entry_by_name(*entries2, *nentries2, seg, seglen);
+		pte2 = find_entry_by_name((*tree2)->entries,
+		    (*tree2)->nentries, seg, seglen);
 		if (pte2 == NULL) {
 			*changed = 1;
 			break;
@@ -526,15 +581,16 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				err = got_error_no_obj(&id1);
 				break;
 			}
-			*nentries1 = 0;
-			free(*buf1);
-			*buf1 = NULL;
-			err = open_tree(buf1, entries1, nentries1,
-			    nentries_alloc1, pack, packidx, idx, &id1,
-			    objcache);
+			got_object_parsed_tree_close(*tree1);
+			*tree1 = got_object_cache_get(treecache, &id1);
+			if (*tree1 == NULL) {
+				err = cache_parsed_tree(tree1, &id1,
+				    pack, packidx, idx, objcache, treecache);
+				if (err)
+					break;
+			} else
+				(*tree1)->refcnt++;
 			pte1 = NULL;
-			if (err)
-				break;
 
 			memcpy(id2.sha1, pte2->id, SHA1_DIGEST_LENGTH);
 			idx = got_packidx_get_object_idx(packidx, &id2);
@@ -542,15 +598,16 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				err = got_error_no_obj(&id2);
 				break;
 			}
-			*nentries2 = 0;
-			free(*buf2);
-			*buf2 = NULL;
-			err = open_tree(buf2, entries2, nentries2,
-			    nentries_alloc2, pack, packidx, idx, &id2,
-			    objcache);
+			got_object_parsed_tree_close(*tree2);
+			*tree2 = got_object_cache_get(treecache, &id2);
+			if (*tree2 == NULL) {
+				err = cache_parsed_tree(tree2, &id2,
+				    pack, packidx, idx, objcache, treecache);
+				if (err)
+					break;
+			} else
+				(*tree2)->refcnt++;
 			pte2 = NULL;
-			if (err)
-				break;
 		}
 	}
 
@@ -600,21 +657,20 @@ commit_traversal_request(struct imsg *imsg, struct ims
 static const struct got_error *
 commit_traversal_request(struct imsg *imsg, struct imsgbuf *ibuf,
     struct got_pack *pack, struct got_packidx *packidx,
-    struct got_object_cache *objcache)
+    struct got_object_cache *objcache,
+    struct got_object_cache *treecache)
 {
 	const struct got_error *err = NULL;
 	struct got_imsg_commit_traversal_request ctreq;
 	struct got_object_qid *pid;
 	struct got_commit_object *commit = NULL, *pcommit = NULL;
-	struct got_parsed_tree_entry *entries = NULL, *pentries = NULL;
-	size_t nentries = 0, nentries_alloc = 0;
-	size_t pnentries = 0, pnentries_alloc = 0;
 	struct got_object_id id;
 	size_t datalen;
 	char *path = NULL;
 	const int min_alloc = 64;
 	int changed = 0, ncommits = 0, nallocated = 0;
 	struct got_object_id *commit_ids = NULL;
+	struct got_parsed_tree *tree, *ptree;
 
 	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
 	if (datalen < sizeof(ctreq))
@@ -706,7 +762,6 @@ commit_traversal_request(struct imsg *imsg, struct ims
 			}
 		} else {
 			int pidx;
-			uint8_t *buf = NULL, *pbuf = NULL;
 
 			idx = got_packidx_get_object_idx(packidx,
 			    commit->tree_id);
@@ -717,28 +772,35 @@ commit_traversal_request(struct imsg *imsg, struct ims
 			if (pidx == -1)
 				break;
 
-			err = open_tree(&buf, &entries, &nentries,
-			    &nentries_alloc, pack, packidx, idx,
-			    commit->tree_id, objcache);
-			if (err)
-				goto done;
-			err = open_tree(&pbuf, &pentries, &pnentries,
-			    &pnentries_alloc, pack, packidx, pidx,
-			    pcommit->tree_id, objcache);
-			if (err) {
-				free(buf);
-				goto done;
-			}
+			tree = got_object_cache_get(treecache,
+			    commit->tree_id);
+			if (tree == NULL) {
+				err = cache_parsed_tree(&tree,
+				    commit->tree_id, pack, packidx, idx,
+				    objcache, treecache);
+				if (err)
+					goto done;
+			} else
+				tree->refcnt++;
 
-			err = tree_path_changed(&changed, &buf, &pbuf,
-			    &entries, &nentries, &nentries_alloc,
-			    &pentries, &pnentries, &pnentries_alloc,
-			    path, pack, packidx, ibuf, objcache);
+			ptree = got_object_cache_get(treecache,
+			    pcommit->tree_id);
+			if (ptree == NULL) {
+				err = cache_parsed_tree(&ptree,
+				    pcommit->tree_id, pack, packidx, pidx,
+				    objcache, treecache);
+				if (err)
+					goto done;
+			} else
+				ptree->refcnt++;
+	
+			err = tree_path_changed(&changed, &tree, &ptree,
+			    path, pack, packidx, ibuf, objcache, treecache);
 
-			nentries = 0;
-			free(buf);
-			pnentries = 0;
-			free(pbuf);
+			got_object_parsed_tree_close(tree);
+			tree = NULL;
+			got_object_parsed_tree_close(ptree);
+			ptree = NULL;
 			if (err) {
 				if (err->code != GOT_ERR_NO_OBJ)
 					goto done;
@@ -774,8 +836,6 @@ done:
 		got_object_commit_close(commit);
 	if (pcommit)
 		got_object_commit_close(pcommit);
-	free(entries);
-	free(pentries);
 	if (err) {
 		if (err->code == GOT_ERR_PRIVSEP_PIPE)
 			err = NULL;
@@ -1188,6 +1248,7 @@ enumerate_tree(int *have_all_entries, struct imsgbuf *
 	struct got_parsed_tree_entry *entries = NULL;
 	size_t nentries = 0, nentries_alloc = 0, i;
 	struct enumerated_tree *tree;
+	size_t bufsize;
 
 	*ntrees = 0;
 	*have_all_entries = 1;
@@ -1225,8 +1286,8 @@ enumerate_tree(int *have_all_entries, struct imsgbuf *
 			break;
 		}
 
-		err = open_tree(&buf, &entries, &nentries, &nentries_alloc,
-		    pack, packidx, idx, &qid->id, objcache);
+		err = open_tree(&buf, &bufsize, &entries, &nentries,
+		    &nentries_alloc, pack, packidx, idx, &qid->id, objcache);
 		if (err) {
 			if (err->code != GOT_ERR_NO_OBJ)
 				goto done;
@@ -1908,6 +1969,7 @@ main(int argc, char *argv[])
 	struct got_packidx *packidx = NULL;
 	struct got_pack *pack = NULL;
 	struct got_object_cache objcache;
+	struct got_object_cache treecache;
 	FILE *basefile = NULL, *accumfile = NULL, *delta_outfile = NULL;
 	struct got_object_idset *keep = NULL, *drop = NULL, *skip = NULL;
 	struct got_parsed_tree_entry *entries = NULL;
@@ -1927,6 +1989,13 @@ main(int argc, char *argv[])
 		return 1;
 	}
 
+	err = got_object_cache_init(&treecache,
+	    GOT_OBJECT_CACHE_TYPE_PARSED_TREE);
+	if (err) {
+		err = got_error_from_errno("got_object_cache_init");
+		got_privsep_send_error(&ibuf, err);
+		return 1;
+	}
 #ifndef PROFILE
 	/* revoke access to most system calls */
 	if (pledge("stdio recvfd", NULL) == -1) {
@@ -2030,7 +2099,7 @@ main(int argc, char *argv[])
 			break;
 		case GOT_IMSG_COMMIT_TRAVERSAL_REQUEST:
 			err = commit_traversal_request(&imsg, &ibuf, pack,
-			    packidx, &objcache);
+			    packidx, &objcache, &treecache);
 			break;
 		case GOT_IMSG_OBJECT_ENUMERATION_REQUEST:
 			err = enumeration_request(&imsg, &ibuf, pack,
@@ -2070,6 +2139,7 @@ main(int argc, char *argv[])
 	if (pack)
 		got_pack_close(pack);
 	got_object_cache_close(&objcache);
+	got_object_cache_close(&treecache);
 	imsg_clear(&ibuf);
 	if (basefile && fclose(basefile) == EOF && err == NULL)
 		err = got_error_from_errno("fclose");