While profiling got-read-pack, I noticed that a significant amount of
malloc/free originates in tree-entry parsing. We are calling malloc/free
once for each entry in each tree. This adds up to a lot of such calls
while crawling tree objects of a large repository.

With the patch below we parse tree entries into an array instead of a
path-list. The number of malloc/free calls is reduced because we can
now use a malloc call for a given number of tree entries, and freeing
entries requires just one free call per tree.

For now, I have chosen to grow the array in chunks of 16 entries.
Going forward, we could decide to tweak this number in order to
trade more unused memory for speed, should it be worth it.

It turns out that we depend on the ordering of entries provided by
got_pathlist_insert(). Otherwise, commands like 'got update' will
misbehave when they run diffs between trees and the fileindex.
This is why each freshly parsed array is sorted with mergesort().

ok?
 
diff af2c4eff8bee6f826f378d225850e0d5bcc07140 03b9d0df36858d5da13aea7881ef4e671426ef1a
blob - adbb8bb3e8521199cb1e1ee0ae5ad5dce3f3503d
blob + 79b6e83d9872c4ee03472131af53beb3186ab6be
--- lib/got_lib_object_parse.h
+++ lib/got_lib_object_parse.h
@@ -23,18 +23,14 @@ struct got_tree_entry *got_alloc_tree_entry_partial(vo
 const struct got_error *got_object_parse_commit(struct got_commit_object **,
     char *, size_t);
 
-/*
- * In a pathlist returned by got_object_parse_tree(), a pointer to the entry's
- * name is stored in the pathlist element's path, while the pathlist element's
- * data pointer points to a struct got_parsed_tree_entry.
- */
 struct got_parsed_tree_entry {
+	const char *name; /* Points to name in parsed buffer */
+	size_t namelen; /* strlen(name) */
 	mode_t mode; /* Mode parsed from tree buffer. */
 	uint8_t *id; /* Points to ID in parsed tree buffer. */
 };
-const struct got_error *got_object_parse_tree(struct got_pathlist_head *, int *,
-    uint8_t *, size_t);
-void got_object_parsed_tree_entries_free(struct got_pathlist_head *);
+const struct got_error *got_object_parse_tree(struct got_parsed_tree_entry **,
+    int *, uint8_t *, size_t);
 
 const struct got_error *got_object_parse_tag(struct got_tag_object **,
     uint8_t *, size_t);
blob - b310a5120a14c05adbe049177d4af040d61f1ab9
blob + c6937820f54e6d66c1cbf81056a6b916516c9c5d
--- lib/got_lib_privsep.h
+++ lib/got_lib_privsep.h
@@ -662,8 +662,9 @@ const struct got_error *got_privsep_recv_commit(struct
     struct imsgbuf *);
 const struct got_error *got_privsep_recv_tree(struct got_tree_object **,
     struct imsgbuf *);
+struct got_parsed_tree_entry;
 const struct got_error *got_privsep_send_tree(struct imsgbuf *,
-    struct got_pathlist_head *, int);
+    struct got_parsed_tree_entry *, int);
 const struct got_error *got_privsep_send_blob(struct imsgbuf *, size_t, size_t,
     const uint8_t *);
 const struct got_error *got_privsep_recv_blob(uint8_t **, size_t *, size_t *,
blob - 511053239b0a892dbb0de04e93ccd9ed8e69e7b8
blob + a1ba3cdeeb0dba6b547cdb3694a08768b78b9fcf
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -669,83 +669,81 @@ got_object_tree_close(struct got_tree_object *tree)
 }
 
 static const struct got_error *
-parse_tree_entry(struct got_parsed_tree_entry **pte, const char **name,
-    size_t *elen, char *buf,
+parse_tree_entry(struct got_parsed_tree_entry *pte, size_t *elen, char *buf,
     size_t maxlen)
 {
 	char *p, *space;
-	const struct got_error *err = NULL;
 
-	*name = NULL;
 	*elen = 0;
 
-	*pte = malloc(sizeof(**pte));
-	if (*pte == NULL)
-		return got_error_from_errno("malloc");
-
 	*elen = strnlen(buf, maxlen) + 1;
-	if (*elen > maxlen) {
-		free(*pte);
-		*pte = NULL;
+	if (*elen > maxlen)
 		return got_error(GOT_ERR_BAD_OBJ_DATA);
-	}
 
 	space = memchr(buf, ' ', *elen);
-	if (space == NULL || space <= buf) {
-		err = got_error(GOT_ERR_BAD_OBJ_DATA);
-		free(*pte);
-		*pte = NULL;
-		return err;
-	}
-	(*pte)->mode = 0;
+	if (space == NULL || space <= buf)
+		return got_error(GOT_ERR_BAD_OBJ_DATA);
+
+	pte->mode = 0;
 	p = buf;
 	while (p < space) {
-		if (*p < '0' && *p > '7') {
-			err = got_error(GOT_ERR_BAD_OBJ_DATA);
-			goto done;
-		}
-		(*pte)->mode <<= 3;
-		(*pte)->mode |= *p - '0';
+		if (*p < '0' && *p > '7')
+			return got_error(GOT_ERR_BAD_OBJ_DATA);
+		pte->mode <<= 3;
+		pte->mode |= *p - '0';
 		p++;
 	}
 
-	if (*elen > maxlen || maxlen - *elen < SHA1_DIGEST_LENGTH) {
-		err = got_error(GOT_ERR_BAD_OBJ_DATA);
-		goto done;
-	}
-	*name = space + 1;
+	if (*elen > maxlen || maxlen - *elen < SHA1_DIGEST_LENGTH)
+		return got_error(GOT_ERR_BAD_OBJ_DATA);
+
+	pte->name = space + 1;
+	pte->namelen = strlen(pte->name);
 	buf += *elen;
-	(*pte)->id = buf;
+	pte->id = buf;
 	*elen += SHA1_DIGEST_LENGTH;
-done:
-	if (err) {
-		free(*pte);
-		*pte = NULL;
-	}
-	return err;
+	return NULL;
 }
 
+static int
+pte_cmp(const void *pa, const void *pb)
+{
+	const struct got_parsed_tree_entry *a, *b;
+
+	a = (const struct got_parsed_tree_entry *)pa;
+	b = (const struct got_parsed_tree_entry *)pb;
+
+	return got_path_cmp(a->name, b->name, a->namelen, b->namelen);
+}
+
 const struct got_error *
-got_object_parse_tree(struct got_pathlist_head *entries, int *nentries,
+got_object_parse_tree(struct got_parsed_tree_entry **entries, int *nentries,
     uint8_t *buf, size_t len)
 {
 	const struct got_error *err = NULL;
-	size_t remain = len;
+	size_t remain = len, totalloc;
+	const size_t nalloc = 16;
+	struct got_pathlist_head entry_names;
 
 	*nentries = 0;
 	if (remain == 0)
 		return NULL; /* tree is empty */
 
+	*entries = calloc(nalloc, sizeof(**entries));
+	if (*entries == NULL)
+		return got_error_from_errno("calloc");
+	totalloc = nalloc;
+
+	TAILQ_INIT(&entry_names);
 	while (remain > 0) {
-		struct got_parsed_tree_entry *pte;
 		struct got_pathlist_entry *new = NULL;
-		const char *name;
+		struct got_parsed_tree_entry *pte = &(*entries)[*nentries];
 		size_t elen;
 
-		err = parse_tree_entry(&pte, &name, &elen, buf, remain);
+		err = parse_tree_entry(pte, &elen, buf, remain);
 		if (err)
 			goto done;
-		err = got_pathlist_insert(&new, entries, name, pte);
+		err = got_pathlist_insert(&new, &entry_names, pte->name, NULL);
 		if (err)
 			goto done;
 		if (new == NULL) {
@@ -755,33 +753,35 @@ got_object_parse_tree(struct got_pathlist_head *entrie
 		buf += elen;
 		remain -= elen;
 		(*nentries)++;
+		if (*nentries >= totalloc) {
+			pte = recallocarray(*entries, totalloc,
+			    totalloc + nalloc, sizeof(**entries));
+			if (pte == NULL) {
+				err = got_error_from_errno("recallocarray");
+				goto done;
+			}
+			*entries = pte;
+			totalloc += nalloc;
+		}
 	}
 
 	if (remain != 0) {
 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
 		goto done;
 	}
+
+	mergesort(*entries, *nentries, sizeof(**entries), pte_cmp);
 done:
+	got_pathlist_free(&entry_names);
 	if (err) {
-		got_object_parsed_tree_entries_free(entries);
+		free(*entries);
+		*entries = NULL;
 		*nentries = 0;
 	}
 	return err;
 }
 
 void
-got_object_parsed_tree_entries_free(struct got_pathlist_head *entries)
-{
-	struct got_pathlist_entry *pe;
-
-	TAILQ_FOREACH(pe, entries, entry) {
-		struct got_parsed_tree_entry *pte = pe->data;
-		free(pte);
-	}
-	got_pathlist_free(entries);
-}
-
-void
 got_object_tag_close(struct got_tag_object *tag)
 {
 	if (tag->refcnt > 0) {
blob - b8e60e5a73e4d935fbc621706294df4e664a14d3
blob + 68b705edf2b77ccceddb9530af078387a0937aa0
--- lib/privsep.c
+++ lib/privsep.c
@@ -1490,14 +1490,13 @@ got_privsep_recv_commit(struct got_commit_object **com
 }
 
 const struct got_error *
-got_privsep_send_tree(struct imsgbuf *ibuf, struct got_pathlist_head *entries,
-    int nentries)
+got_privsep_send_tree(struct imsgbuf *ibuf,
+    struct got_parsed_tree_entry *entries, int nentries)
 {
 	const struct got_error *err = NULL;
 	struct got_imsg_tree_object itree;
-	struct got_pathlist_entry *pe;
 	size_t totlen;
-	int nimsg; /* number of imsg queued in ibuf */
+	int i, nimsg; /* number of imsg queued in ibuf */
 
 	itree.nentries = nentries;
 	if (imsg_compose(ibuf, GOT_IMSG_TREE, 0, 0, -1, &itree, sizeof(itree))
@@ -1506,12 +1505,10 @@ got_privsep_send_tree(struct imsgbuf *ibuf, struct got
 
 	totlen = sizeof(itree);
 	nimsg = 1;
-	TAILQ_FOREACH(pe, entries, entry) {
-		const char *name = pe->path;
-		struct got_parsed_tree_entry *pte = pe->data;
+	for (i = 0; i < nentries; i++) {
+		struct got_parsed_tree_entry *pte = &entries[i];
 		struct ibuf *wbuf;
-		size_t namelen = strlen(name);
-		size_t len = sizeof(struct got_imsg_tree_entry) + namelen;
+		size_t len = sizeof(struct got_imsg_tree_entry) + pte->namelen;
 
 		if (len > MAX_IMSGSIZE)
 			return got_error(GOT_ERR_NO_SPACE);
@@ -1540,7 +1537,7 @@ got_privsep_send_tree(struct imsgbuf *ibuf, struct got
 			return err;
 		}
 
-		if (imsg_add(wbuf, name, namelen) == -1) {
+		if (imsg_add(wbuf, pte->name, pte->namelen) == -1) {
 			err = got_error_from_errno("imsg_add TREE_ENTRY");
 			ibuf_free(wbuf);
 			return err;
blob - 20a67c9701816c2474c4d9e546a0c6f4aeb8d0ae
blob + b6d3c895f92db84cc93320a4f869170172782abd
--- libexec/got-read-pack/got-read-pack.c
+++ libexec/got-read-pack/got-read-pack.c
@@ -177,7 +177,7 @@ done:
 }
 
 static const struct got_error *
-open_tree(uint8_t **buf, struct got_pathlist_head *entries, int *nentries,
+open_tree(uint8_t **buf, struct got_parsed_tree_entry **entries, int *nentries,
     struct got_pack *pack, struct got_packidx *packidx, int obj_idx,
     struct got_object_id *id, struct got_object_cache *objcache)
 {
@@ -220,14 +220,12 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 {
 	const struct got_error *err = NULL;
 	struct got_imsg_packed_object iobj;
-	struct got_pathlist_head entries;
+	struct got_parsed_tree_entry *entries = NULL;
 	int nentries = 0;
 	uint8_t *buf = NULL;
 	struct got_object_id id;
 	size_t datalen;
 
-	TAILQ_INIT(&entries);
-
 	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
 	if (datalen != sizeof(iobj))
 		return got_error(GOT_ERR_PRIVSEP_LEN);
@@ -239,8 +237,8 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, 
 	if (err)
 		return err;
 
-	err = got_privsep_send_tree(ibuf, &entries, nentries);
-	got_object_parsed_tree_entries_free(&entries);
+	err = got_privsep_send_tree(ibuf, entries, nentries);
+	free(entries);
 	free(buf);
 	if (err) {
 		if (err->code == GOT_ERR_PRIVSEP_PIPE)
@@ -427,28 +425,30 @@ done:
 }
 
 static struct got_parsed_tree_entry *
-find_entry_by_name(struct got_pathlist_head *entries, int nentries,
+find_entry_by_name(struct got_parsed_tree_entry *entries, int nentries,
     const char *name, size_t len)
 {
-	struct got_pathlist_entry *pe;
+	struct got_parsed_tree_entry *pte;
+	int cmp, i;
 
 	/* Note that tree entries are sorted in strncmp() order. */
-	TAILQ_FOREACH(pe, entries, entry) {
-		int cmp = strncmp(pe->path, name, len);
+	for (i = 0; i < nentries; i++) {
+		pte = &entries[i];
+		cmp = strncmp(pte->name, name, len);
 		if (cmp < 0)
 			continue;
 		if (cmp > 0)
 			break;
-		if (pe->path[len] == '\0')
-			return (struct got_parsed_tree_entry *)pe->data;
+		if (pte->name[len] == '\0')
+			return pte;
 	}
 	return NULL;
 }
 
 static const struct got_error *
 tree_path_changed(int *changed, uint8_t **buf1, uint8_t **buf2,
-    struct got_pathlist_head *entries1, int *nentries1,
-    struct got_pathlist_head *entries2, int *nentries2,
+    struct got_parsed_tree_entry **entries1, int *nentries1,
+    struct got_parsed_tree_entry **entries2, int *nentries2,
     const char *path, struct got_pack *pack, struct got_packidx *packidx,
     struct imsgbuf *ibuf, struct got_object_cache *objcache)
 {
@@ -476,13 +476,13 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				continue;
 		}
 
-		pte1 = find_entry_by_name(entries1, *nentries1, seg, seglen);
+		pte1 = find_entry_by_name(*entries1, *nentries1, 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(*entries2, *nentries2, seg, seglen);
 		if (pte2 == NULL) {
 			*changed = 1;
 			break;
@@ -516,7 +516,7 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				err = got_error_no_obj(&id1);
 				break;
 			}
-			got_object_parsed_tree_entries_free(entries1);
+			free(*entries1);
 			*nentries1 = 0;
 			free(*buf1);
 			*buf1 = NULL;
@@ -532,7 +532,7 @@ tree_path_changed(int *changed, uint8_t **buf1, uint8_
 				err = got_error_no_obj(&id2);
 				break;
 			}
-			got_object_parsed_tree_entries_free(entries2);
+			free(*entries2);
 			*nentries2 = 0;
 			free(*buf2);
 			*buf2 = NULL;
@@ -602,7 +602,7 @@ commit_traversal_request(struct imsg *imsg, struct ims
 	struct got_imsg_packed_object iobj;
 	struct got_object_qid *pid;
 	struct got_commit_object *commit = NULL, *pcommit = NULL;
-	struct got_pathlist_head entries, pentries;
+	struct got_parsed_tree_entry *entries = NULL, *pentries = NULL;
 	int nentries = 0, pnentries = 0;
 	struct got_object_id id;
 	size_t datalen, path_len;
@@ -611,9 +611,6 @@ commit_traversal_request(struct imsg *imsg, struct ims
 	int changed = 0, ncommits = 0, nallocated = 0;
 	struct got_object_id *commit_ids = NULL;
 
-	TAILQ_INIT(&entries);
-	TAILQ_INIT(&pentries);
-
 	datalen = imsg->hdr.len - IMSG_HEADER_SIZE;
 	if (datalen < sizeof(iobj))
 		return got_error(GOT_ERR_PRIVSEP_LEN);
@@ -731,10 +728,12 @@ commit_traversal_request(struct imsg *imsg, struct ims
 			    &entries, &nentries, &pentries, &pnentries, path,
 			    pack, packidx, ibuf, objcache);
 
-			got_object_parsed_tree_entries_free(&entries);
+			free(entries);
+			entries = NULL;
 			nentries = 0;
 			free(buf);
-			got_object_parsed_tree_entries_free(&pentries);
+			free(pentries);
+			pentries = NULL;
 			pnentries = 0;
 			free(pbuf);
 			if (err) {
@@ -771,10 +770,8 @@ done:
 		got_object_commit_close(commit);
 	if (pcommit)
 		got_object_commit_close(pcommit);
-	if (nentries != 0)
-		got_object_parsed_tree_entries_free(&entries);
-	if (pnentries != 0)
-		got_object_parsed_tree_entries_free(&pentries);
+	free(entries);
+	free(pentries);
 	if (err) {
 		if (err->code == GOT_ERR_PRIVSEP_PIPE)
 			err = NULL;
blob - 95e34c068c96ce1a4a00a1ea034531e243919dfd
blob + 225f928a01e58925e0d8bcb3e1ffb1a2cc09d631
--- libexec/got-read-tree/got-read-tree.c
+++ libexec/got-read-tree/got-read-tree.c
@@ -50,7 +50,7 @@ catch_sigint(int signo)
 }
 
 static const struct got_error *
-read_tree_object(struct got_pathlist_head *entries, int *nentries,
+read_tree_object(struct got_parsed_tree_entry **entries, int *nentries,
     uint8_t **p, FILE *f, struct got_object_id *expected_id)
 {
 	const struct got_error *err = NULL;
@@ -119,13 +119,11 @@ main(int argc, char *argv[])
 	for (;;) {
 		struct imsg imsg;
 		FILE *f = NULL;
-		struct got_pathlist_head entries;
+		struct got_parsed_tree_entry *entries = NULL;
 		int nentries = 0;
 		uint8_t *buf = NULL;
 		struct got_object_id expected_id;
 
-		TAILQ_INIT(&entries);
-
 		if (sigint_received) {
 			err = got_error(GOT_ERR_CANCELLED);
 			break;
@@ -170,9 +168,9 @@ main(int argc, char *argv[])
 		if (err)
 			goto done;
 
-		err = got_privsep_send_tree(&ibuf, &entries, nentries);
+		err = got_privsep_send_tree(&ibuf, entries, nentries);
 done:
-		got_object_parsed_tree_entries_free(&entries);
+		free(entries);
 		free(buf);
 		if (f) {
 			if (fclose(f) == EOF && err == NULL)