[PATCH/RFC] Make the largest pack the first one in the pack search queue

[PATCH/RFC] Make the largest pack the first one in the pack search queue

[Nguyễn Thái Ngọc Duy]

When git looks for an object in a pack, it has to go through all the
pack indexes. Pack order becomes important because if the pack is
found early, the search stops early. Git sorts packs by mostly by
mtime, favoring recent packs.

This strategy however puts the main pack at the bottom because the
main pack is usually created at clone time and occasional "repack -ad",
so likely the oldest. Though being the largest pack, this pack is
likely hit (even latest commits have unchanged parts, which is likely
in the main pack).

This patch changes pack order a little bit, putting the main pack on
top, the rest is ordered as usual. When we look for latest changes,
it'll likely miss the main pack. But after the first miss,
"last_found_pack" optimization kicks in, thus reduce the miss cost.

I modified find_pack_entry() to record pack misses, then do a few
commonly used commands like "git diff", "git diff --cached", "git diff
HEAD", "git status", "git branch -v", "git log"... Pack miss decreased
in all cases. So I think this might be a good heuristic. But this is
micro-optmization and probably does not give us any significant
performance gain.

A probably better way to improve too-many-packs situation is create
meta-index in memory for small packs.

An implementation note, packed_git->num_objects should be used to
determine the largest pack, but that field may not be available until
open_packed_git() is called. pack_size should be a good enough
approximation.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 sha1_file.c |   21 ++++++++++++++++++++-
 1 files changed, 20 insertions(+), 1 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 798cd46..05ece2d 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1072,6 +1072,24 @@ static int sort_pack(const void *a_, const void *b_)
 	return -1;
 }
 
+static int sort_pack_by_size(const void *a_, const void *b_)
+{
+	struct packed_git *a = *((struct packed_git **)a_);
+	struct packed_git *b = *((struct packed_git **)b_);
+	int st;
+
+	/*
+	 * Local packs tend to contain objects specific to our
+	 * variant of the project than remote ones.  In addition,
+	 * remote ones could be on a network mounted filesystem.
+	 * Favor local ones for these reasons.
+	 */
+	st = a->pack_local - b->pack_local;
+	if (st)
+		return -st;
+	return b->pack_size - a->pack_size;
+}
+
 static void rearrange_packed_git(void)
 {
 	struct packed_git **ary, *p;
@@ -1087,7 +1105,8 @@ static void rearrange_packed_git(void)
 	for (n = 0, p = packed_git; p; p = p->next)
 		ary[n++] = p;
 
-	qsort(ary, n, sizeof(struct packed_git *), sort_pack);
+	qsort(ary, n, sizeof(struct packed_git *), sort_pack_by_size);
+	qsort(ary + 1, n - 1, sizeof(struct packed_git *), sort_pack);
 
 	/* link them back again */
 	for (i = 0; i < n - 1; i++)
-- 
1.7.3.1.256.g2539c.dirty

Re: [PATCH/RFC] Make the largest pack the first one in the pack search queue

[Junio C Hamano]

As the expected pay off from this change seems to be only based on a
hunch, it is hard for anybody to give useful comments on a patch
like this without benchmarks. As the implementation is more or less
trivial, the only thing anybody could say is "if changing the search
order is proved to be useful, the patch seems sane," but the "if"
part poses a lot bigger question than the patch itself.

At this late in the cycle, I would rather see a contributor with
many in-flight topics to start sifting his own existing topics into
the ones to be polished for the next release and the others to be
postponed for the next cycle, instead of adding yet more topics with
untied loose ends at this point.

Thanks.