commit 950de2cd7ce881d3596a41afa88c20f21387c1e3
from: Stefan Sperling <stsp@stsp.name>
date: Wed Mar 18 16:13:43 2020 UTC

avoid unnecessary memmove calls during the first indexing pass

commit - 55fdd2574a8da106021dd4857d3727185bda6c99
commit + 950de2cd7ce881d3596a41afa88c20f21387c1e3
blob - fc35ff4dc3aa95542ad3f9141e8fdf2970b229e6
blob + 3d5f3fce1a9671ed367ea1dc222cda6d19e7c3c0
--- libexec/got-index-pack/got-index-pack.c
+++ libexec/got-index-pack/got-index-pack.c
@@ -385,24 +385,10 @@ print_packidx(struct got_packidx *packidx)
 #endif
 
 static void
-update_packidx(struct got_packidx *packidx, int nobj,
+add_indexed_object(struct got_packidx *packidx, uint32_t idx,
     struct got_indexed_object *obj)
 {
-	int i, n, idx;
-	uint32_t nindexed = betoh32(packidx->hdr.fanout_table[0xff]);
-
-	idx = find_object_idx(packidx, obj->id.sha1);
-	if (idx == -1) {
-		char hex[SHA1_DIGEST_STRING_LENGTH];
-		got_sha1_digest_to_str(obj->id.sha1, hex, sizeof(hex));
-		return; /* object already indexed */
-	}
-
-	memmove(&packidx->hdr.sorted_ids[idx + 1],
-	    &packidx->hdr.sorted_ids[idx],
-	    sizeof(struct got_packidx_object_id) * (nindexed - idx));
-	memmove(&packidx->hdr.offsets[idx + 1], &packidx->hdr.offsets[idx],
-	    sizeof(uint32_t) * (nindexed - idx));
+	int i;
 
 	memcpy(packidx->hdr.sorted_ids[idx].sha1, obj->id.sha1,
 	    SHA1_DIGEST_LENGTH);
@@ -417,7 +403,7 @@ update_packidx(struct got_packidx *packidx, int nobj,
 	}
 
 	for (i = obj->id.sha1[0]; i <= 0xff; i++) {
-		n = be32toh(packidx->hdr.fanout_table[i]);
+		uint32_t n = be32toh(packidx->hdr.fanout_table[i]);
 		packidx->hdr.fanout_table[i] = htobe32(n + 1);
 	}
 }
@@ -432,6 +418,48 @@ indexed_obj_cmp(const void *pa, const void *pb)
 	return got_object_id_cmp(&a->id, &b->id);
 }
 
+static void
+make_initial_packidx(struct got_packidx *packidx, int nobj,
+    struct got_indexed_object **objects)
+{
+	struct got_indexed_object *obj;
+	int i;
+	uint32_t idx = 0;
+
+	mergesort(objects, nobj, sizeof(struct got_indexed_object *),
+	    indexed_obj_cmp);
+
+	for (i = 0; i < nobj; i++) {
+		obj = objects[i];
+		if (!obj->valid)
+			continue;
+		add_indexed_object(packidx, idx++, obj);
+	}
+}
+
+static void
+update_packidx(struct got_packidx *packidx, int nobj,
+    struct got_indexed_object *obj)
+{
+	uint32_t idx;
+	uint32_t nindexed = betoh32(packidx->hdr.fanout_table[0xff]);
+
+	idx = find_object_idx(packidx, obj->id.sha1);
+	if (idx == -1) {
+		char hex[SHA1_DIGEST_STRING_LENGTH];
+		got_sha1_digest_to_str(obj->id.sha1, hex, sizeof(hex));
+		return; /* object already indexed */
+	}
+
+	memmove(&packidx->hdr.sorted_ids[idx + 1],
+	    &packidx->hdr.sorted_ids[idx],
+	    sizeof(struct got_packidx_object_id) * (nindexed - idx));
+	memmove(&packidx->hdr.offsets[idx + 1], &packidx->hdr.offsets[idx],
+	    sizeof(uint32_t) * (nindexed - idx));
+
+	add_indexed_object(packidx, idx, obj);
+}
+
 static const struct got_error *
 index_pack(struct got_pack *pack, int idxfd, uint8_t *pack_hash,
     struct imsgbuf *ibuf)
@@ -562,11 +590,12 @@ index_pack(struct got_pack *pack, int idxfd, uint8_t *
 		    obj->type == GOT_OBJ_TYPE_TAG) {
 			objects[i]->valid = 1;
 			nloose++;
-			update_packidx(&packidx, nobj, obj);
 		}
 	}
 	nvalid = nloose;
 
+	make_initial_packidx(&packidx, nobj, objects);
+
 	/*
 	 * Second pass: We can now resolve deltas to compute the IDs of
 	 * objects which appear in deltified form. Because deltas can be