[PATCH 0/2] For improved pack locality

[PATCH 0/2] For improved pack locality

[Junio C Hamano]

Shawn kept bugging me about the locality of data in the packfiles
generated by C-git (see pack-heuristics.txt in Documentation/technical)
is often horrible, so here is my stab at it. The idea is to make sure
that the majority of pack accesses fall to nearby locations in the
mmapped packfile to reduce minor faults (which would help if you are
accessing the packfile over slow link like NFS, or starting from a cold
cache).

Junio C Hamano (2):
  core: log offset pack data accesses happened
  pack-objects: optimize "recency order"

 builtin/pack-objects.c |  138 +++++++++++++++++++++++++++++++++++++++++++++++-
 cache.h                |    3 +
 config.c               |    3 +
 environment.c          |    1 +
 sha1_file.c            |   21 +++++++
 5 files changed, 165 insertions(+), 1 deletions(-)

-- 
1.7.6.134.gcf13f6

[PATCH 1/2] core: log offset pack data accesses happened

[Junio C Hamano]

In a workload other than "git log" (without pathspec nor any option that
causes us to inspect trees and blobs), the recency pack order is said to
cause the access jump around quite a bit. Add a hook to allow us observe
how bad it is.

"git config core.logpackaccess /var/tmp/pal.txt" will give you the log in
the specified file, one line per access, the name of the packfile and the
offset of the accessed location in the packfile. This data can be massaged
to show how large a seek is involved in between each pair of adjacent
accesses to the same packfile.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 cache.h       |    3 +++
 config.c      |    3 +++
 environment.c |    1 +
 sha1_file.c   |   21 +++++++++++++++++++++
 4 files changed, 28 insertions(+), 0 deletions(-)

diff --git a/cache.h b/cache.h
index f4bb43e..16a8c7c 100644
--- a/cache.h
+++ b/cache.h
@@ -784,6 +784,9 @@ extern int force_object_loose(const unsigned char *sha1, time_t mtime);
 /* global flag to enable extra checks when accessing packed objects */
 extern int do_check_packed_object_crc;
 
+/* for development: log offset of pack access */
+extern const char *log_pack_access;
+
 extern int check_sha1_signature(const unsigned char *sha1, void *buf, unsigned long size, const char *type);
 
 extern int move_temp_to_file(const char *tmpfile, const char *filename);
diff --git a/config.c b/config.c
index e0b3b80..5ef3f39 100644
--- a/config.c
+++ b/config.c
@@ -569,6 +569,9 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.logpackaccess"))
+		return git_config_string(&log_pack_access, var, value);
+
 	if (!strcmp(var, "core.autocrlf")) {
 		if (value && !strcasecmp(value, "input")) {
 			if (core_eol == EOL_CRLF)
diff --git a/environment.c b/environment.c
index 94d58fd..1935102 100644
--- a/environment.c
+++ b/environment.c
@@ -36,6 +36,7 @@ size_t packed_git_window_size = DEFAULT_PACKED_GIT_WINDOW_SIZE;
 size_t packed_git_limit = DEFAULT_PACKED_GIT_LIMIT;
 size_t delta_base_cache_limit = 16 * 1024 * 1024;
 unsigned long big_file_threshold = 512 * 1024 * 1024;
+const char *log_pack_access;
 const char *pager_program;
 int pager_use_color = 1;
 const char *editor_program;
diff --git a/sha1_file.c b/sha1_file.c
index 064a330..baf5da1 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1839,6 +1839,24 @@ static void *unpack_delta_entry(struct packed_git *p,
 	return result;
 }
 
+static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
+{
+	static FILE *log_file;
+
+	if (!log_file) {
+		log_file = fopen(log_pack_access, "w");
+		if (!log_file) {
+			error("cannot open pack access log '%s' for writing: %s",
+			      log_pack_access, strerror(errno));
+			log_pack_access = NULL;
+			return;
+		}
+	}
+	fprintf(log_file, "%s %"PRIuMAX"\n",
+		p->pack_name, (uintmax_t)obj_offset);
+	fflush(log_file);
+}
+
 int do_check_packed_object_crc;
 
 void *unpack_entry(struct packed_git *p, off_t obj_offset,
@@ -1848,6 +1866,9 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,
 	off_t curpos = obj_offset;
 	void *data;
 
+	if (log_pack_access)
+		write_pack_access_log(p, obj_offset);
+
 	if (do_check_packed_object_crc && p->index_version > 1) {
 		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
 		unsigned long len = revidx[1].offset - obj_offset;
-- 
1.7.6.134.gcf13f6

[PATCH 2/2] pack-objects: optimize "recency order"

[Junio C Hamano]

This optimizes the "recency order" (see pack-heuristics.txt in
Documentation/technical/ directory) used to order objects within a
packfile in three ways:

 - Commits at the tip of tags are written together, in the hope that
   revision traversal done in incremental fetch (which starts by
   putting them in a revision queue marked as UNINTERESTING) will see a
   better locality of these objects;

 - In the original recency order, trees and blobs are intermixed. Write
   trees together before blobs, in the hope that this will improve
   locality when running pathspec-limited revision traversal, i.e.
   "git log paths...";

 - When writing blob objects out, write the whole family of blobs that use
   the same delta base object together, by starting from the root of the
   delta chain, and writing its immediate children in a width-first
   manner, in the hope that this will again improve locality when reading
   blobs that belong to the same path, which are likely to be deltified
   against each other.

I tried various workloads in the Linux kernel repositories (HEAD at
v3.0-rc6-71-g4dd1b49) packed with v1.7.6 and with this patch, counting how
large seeks are needed between adjacent accesses to objects in the pack,
and the result looks promising.  The history has 2072052 objects, weighing
some 490MiB.

 * Simple commit-only log.

   $ git log >/dev/null

   There are 254656 commits in total.

                                  v1.7.6  with patch
   Total number of access :      258,031     258,032
	  0.0% percentile :           12          12
	 10.0% percentile :          259         259
	 20.0% percentile :          294         294
	 30.0% percentile :          326         326
	 40.0% percentile :          363         363
	 50.0% percentile :          415         415
	 60.0% percentile :          513         513
	 70.0% percentile :          857         858
	 80.0% percentile :       10,434      10,441
	 90.0% percentile :       91,985      91,996
	 95.0% percentile :      260,852     260,885
	 99.0% percentile :    1,150,680   1,152,811
	 99.9% percentile :    3,148,435   3,148,435
       Less than 2MiB seek:       99.70%      99.69%

   95% of the pack accesses look at data that is no further than 260kB
   from the previous location we accessed. The patch does not change the
   order of commit objects very much, and the result is very similar.

 * Pathspec-limited log.

   $ git log drivers/net >/dev/null

   The path is touched by 26551 commits and merges (among 254656 total).

                                  v1.7.6  with patch
   Total number of access :      559,511     558,663
	  0.0% percentile :            0           0
	 10.0% percentile :          182         167
	 20.0% percentile :          259         233
	 30.0% percentile :          357         304
	 40.0% percentile :          714         485
	 50.0% percentile :        5,046       3,976
	 60.0% percentile :      688,671     443,578
	 70.0% percentile :  319,574,732 110,370,100
	 80.0% percentile :  361,647,599 123,707,229
	 90.0% percentile :  393,195,669 128,947,636
	 95.0% percentile :  405,496,875 131,609,321
	 99.0% percentile :  412,942,470 133,078,115
	 99.5% percentile :  413,172,266 133,163,349
	 99.9% percentile :  413,354,356 133,240,445
       Less than 2MiB seek:       61.71%      62.87%

   With the current pack heuristics, more than 30% of accesses have to
   seek further than 300MB; the updated pack heuristics ensures that less
   than 0.1% of accesses have to seek further than 135MB. This is largely
   due to the fact that the updated heuristics does not mix blobs and
   trees together.

 * Blame.

   $ git blame drivers/net/ne.c >/dev/null

   The path is touched by 34 commits and merges.

                                  v1.7.6  with patch
   Total number of access :      178,147     178,166
	  0.0% percentile :            0           0
	 10.0% percentile :          142         139
	 20.0% percentile :          222         194
	 30.0% percentile :          373         300
	 40.0% percentile :        1,168         837
	 50.0% percentile :       11,248       7,334
	 60.0% percentile :  305,121,284 106,850,130
	 70.0% percentile :  361,427,854 123,709,715
	 80.0% percentile :  388,127,343 128,171,047
	 90.0% percentile :  399,987,762 130,200,707
	 95.0% percentile :  408,230,673 132,174,308
	 99.0% percentile :  412,947,017 133,181,160
	 99.5% percentile :  413,312,798 133,220,425
	 99.9% percentile :  413,352,366 133,269,051
       Less than 2MiB seek:       56.47%      56.83%

   The result is very similar to the pathspec-limited log above, which
   only looks at the tree objects.

 * Packing recent history.

   $ (git for-each-ref --format='^%(refname)' refs/tags; echo HEAD) |
     git pack-objects --revs --stdout >/dev/null

   This should pack data worth 71 commits.

                                  v1.7.6  with patch
   Total number of access :       11,511      11,514
	  0.0% percentile :            0           0
	 10.0% percentile :           48          47
	 20.0% percentile :          134          98
	 30.0% percentile :          332         178
	 40.0% percentile :        1,386         293
	 50.0% percentile :        8,030         478
	 60.0% percentile :       33,676       1,195
	 70.0% percentile :      147,268      26,216
	 80.0% percentile :    9,178,662     464,598
	 90.0% percentile :   67,922,665     965,782
	 95.0% percentile :   87,773,251   1,226,102
	 99.0% percentile :   98,011,763   1,932,377
	 99.5% percentile :  100,074,427  33,642,128
	 99.9% percentile :  105,336,398 275,772,650
       Less than 2MiB seek:       77.09%      99.04%

    The long-tail part of the result looks worse with the patch, but
    the change helps majority of the access. 99.04% of the accesses
    need less than 2MiB of seeking, compared to 77.09% with the current
    packing heuristics.

 * Index pack.

   $ git index-pack -v .git/objects/pack/pack*.pack

                                  v1.7.6  with patch
   Total number of access :    2,791,228   2,788,802
	  0.0% percentile :            9           9
	 10.0% percentile :          140          89
	 20.0% percentile :          233         167
	 30.0% percentile :          322         235
	 40.0% percentile :          464         310
	 50.0% percentile :          862         423
	 60.0% percentile :        2,566         686
	 70.0% percentile :       25,827       1,498
	 80.0% percentile :    1,317,862       4,971
	 90.0% percentile :   11,926,385     119,398
	 95.0% percentile :   41,304,149     952,519
	 99.0% percentile :  227,613,070   6,709,650
	 99.5% percentile :  321,265,121  11,734,871
	 99.9% percentile :  382,919,785  33,155,191
       Less than 2MiB seek:       81.73%      96.92%

   As the index-pack command already walks objects in the delta chain
   order, writing the blobs out in the delta chain order seems to
   drastically improve the locality of access.

Note that a half-a-gigabyte packfile comfortably fits in the buffer cache,
and you would unlikely to see much performance difference on a modern and
reasonably beefy machine with enough memory and local disks. Benchmarking
with cold cache (or over NFS) would be interesting.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/pack-objects.c |  138 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 137 insertions(+), 1 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index f402a84..27132bb 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -51,6 +51,8 @@ struct object_entry {
 				       * objects against.
 				       */
 	unsigned char no_try_delta;
+	unsigned char tagged; /* near the very tip of refs */
+	unsigned char filled; /* assigned write-order */
 };
 
 /*
@@ -95,6 +97,7 @@ static unsigned long window_memory_limit = 0;
  */
 static int *object_ix;
 static int object_ix_hashsz;
+static struct object_entry *locate_object_entry(const unsigned char *sha1);
 
 /*
  * stats
@@ -199,6 +202,7 @@ static void copy_pack_data(struct sha1file *f,
 	}
 }
 
+/* Return 0 if we will bust the pack-size limit */
 static unsigned long write_object(struct sha1file *f,
 				  struct object_entry *entry,
 				  off_t write_offset)
@@ -433,6 +437,134 @@ static int write_one(struct sha1file *f,
 	return 1;
 }
 
+static int mark_tagged(const char *path, const unsigned char *sha1, int flag,
+		       void *cb_data)
+{
+	unsigned char peeled[20];
+	struct object_entry *entry = locate_object_entry(sha1);
+
+	if (entry)
+		entry->tagged = 1;
+	if (!peel_ref(path, peeled)) {
+		entry = locate_object_entry(peeled);
+		if (entry)
+			entry->tagged = 1;
+	}
+	return 0;
+}
+
+static void add_to_write_order(struct object_entry **wo,
+			       int *endp,
+			       struct object_entry *e)
+{
+	if (e->filled)
+		return;
+	wo[(*endp)++] = e;
+	e->filled = 1;
+}
+
+static void add_descendants_to_write_order(struct object_entry **wo,
+					   int *endp,
+					   struct object_entry *e)
+{
+	struct object_entry *child;
+
+	for (child = e->delta_child; child; child = child->delta_sibling)
+		add_to_write_order(wo, endp, child);
+	for (child = e->delta_child; child; child = child->delta_sibling)
+		add_descendants_to_write_order(wo, endp, child);
+}
+
+static void add_family_to_write_order(struct object_entry **wo,
+				      int *endp,
+				      struct object_entry *e)
+{
+	struct object_entry *root;
+
+	for (root = e; root->delta; root = root->delta)
+		; /* nothing */
+	add_to_write_order(wo, endp, root);
+	add_descendants_to_write_order(wo, endp, root);
+}
+
+static struct object_entry **compute_write_order(void)
+{
+	int i, wo_end;
+
+	struct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));
+
+	for (i = 0; i < nr_objects; i++) {
+		objects[i].tagged = 0;
+		objects[i].filled = 0;
+		objects[i].delta_child = NULL;
+		objects[i].delta_sibling = NULL;
+	}
+
+	/*
+	 * Fully connect delta_child/delta_sibling network.
+	 * Make sure delta_sibling is sorted in the original
+	 * recency order.
+	 */
+	for (i = nr_objects - 1; 0 <= i; i--) {
+		struct object_entry *e = &objects[i];
+		if (!e->delta)
+			continue;
+		/* Mark me as the first child */
+		e->delta_sibling = e->delta->delta_child;
+		e->delta->delta_child = e;
+	}
+
+	/*
+	 * Mark objects that are at the tip of tags.
+	 */
+	for_each_tag_ref(mark_tagged, NULL);
+
+	/*
+	 * Give the commits in the original recency order until
+	 * we see a tagged tip.
+	 */
+	for (i = wo_end = 0; i < nr_objects; i++) {
+		if (objects[i].tagged)
+			break;
+		add_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	/*
+	 * Then fill all the tagged tips.
+	 */
+	for (; i < nr_objects; i++) {
+		if (objects[i].tagged)
+			add_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	/*
+	 * And then all remaining commits and tags.
+	 */
+	for (i = 0; i < nr_objects; i++) {
+		if (objects[i].type != OBJ_COMMIT &&
+		    objects[i].type != OBJ_TAG)
+			continue;
+		add_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	/*
+	 * And then all the trees.
+	 */
+	for (i = 0; i < nr_objects; i++) {
+		if (objects[i].type != OBJ_TREE)
+			continue;
+		add_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	/*
+	 * Finally all the rest in really tight order
+	 */
+	for (i = 0; i < nr_objects; i++)
+		add_family_to_write_order(wo, &wo_end, &objects[i]);
+
+	return wo;
+}
+
 static void write_pack_file(void)
 {
 	uint32_t i = 0, j;
@@ -441,10 +573,12 @@ static void write_pack_file(void)
 	struct pack_header hdr;
 	uint32_t nr_remaining = nr_result;
 	time_t last_mtime = 0;
+	struct object_entry **write_order;
 
 	if (progress > pack_to_stdout)
 		progress_state = start_progress("Writing objects", nr_result);
 	written_list = xmalloc(nr_objects * sizeof(*written_list));
+	write_order = compute_write_order();
 
 	do {
 		unsigned char sha1[20];
@@ -468,7 +602,8 @@ static void write_pack_file(void)
 		offset = sizeof(hdr);
 		nr_written = 0;
 		for (; i < nr_objects; i++) {
-			if (!write_one(f, objects + i, &offset))
+			struct object_entry *e = write_order[i];
+			if (!write_one(f, e, &offset))
 				break;
 			display_progress(progress_state, written);
 		}
@@ -545,6 +680,7 @@ static void write_pack_file(void)
 	} while (nr_remaining && i < nr_objects);
 
 	free(written_list);
+	free(write_order);
 	stop_progress(&progress_state);
 	if (written != nr_result)
 		die("wrote %"PRIu32" objects while expecting %"PRIu32,
-- 
1.7.6.134.gcf13f6

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Shawn Pearce]

On Thu, Jul 7, 2011 at 17:24, Junio C Hamano <gitster@pobox.com> wrote:
> This optimizes the "recency order" (see pack-heuristics.txt in
> Documentation/technical/ directory) used to order objects within a
> packfile in three ways:

Yay!

>  - Commits at the tip of tags are written together, in the hope that
>   revision traversal done in incremental fetch (which starts by
>   putting them in a revision queue marked as UNINTERESTING) will see a
>   better locality of these objects;

Putting these together after the first tagged commit is an interesting
approach. Currently JGit drops these after 1024 recent commits have
been produced, the alternative here parks them around the most recent
release. I wonder which is really the better approach for the
upload-pack workload. I chose 1024 because linux-2.6 seemed to be
getting several thousand commits per MB of pack data, so 1024 would
park the tagged commits within the first MB (making a cold-cache
upload-pack slightly faster), but doesn't harm `git log` going through
the pager too badly because this block is 1024 commits back.

Have you tried putting commits in parse order rather than recency order?

By this I mean the revision traversal code needs to parse the parents
of a commit in order to get their commit date and enqueue them into
the priority queue at the right position. The order the commits get
parsed in is different from the order they are popped in, especially
when a commit is created on an older revision and there is much
concurrent activity on a different branch between the commit and its
ancestor. This pattern is very typical in repositories that pull from
others to merge changes in... aka linux, git.git, etc.

My intuition says emulating the priority queue in pack-objects and
using that to influence the order commits are written out (so its the
order commits enter the queue, rather than leave it) will further
reduce minor page faults during the `git log >/dev/null` test, and
possibly also help the other log based workloads. Its certainly a lot
more work to code than this patch, but I wonder if it produces better
ordering.

>  - In the original recency order, trees and blobs are intermixed. Write
>   trees together before blobs, in the hope that this will improve
>   locality when running pathspec-limited revision traversal, i.e.
>   "git log paths...";

FWIW JGit has been doing "commits-then-trees-then-blobs" for a long
time now and we have generally found the same results as you did here,
segregating by object type helps page faults.

>  - When writing blob objects out, write the whole family of blobs that use
>   the same delta base object together, by starting from the root of the
>   delta chain, and writing its immediate children in a width-first
>   manner, in the hope that this will again improve locality when reading
>   blobs that belong to the same path, which are likely to be deltified
>   against each other.

This is an interesting approach, and one I had not considered before.

>  * Simple commit-only log.
>
>   $ git log >/dev/null
...
>   95% of the pack accesses look at data that is no further than 260kB
>   from the previous location we accessed. The patch does not change the
>   order of commit objects very much, and the result is very similar.

I think a more interesting thing to examine is how often do we have to
"skip back" to an earlier part of the file. Consider the case that the
~190MBish of commits does not fully fit into kernel buffer cache, but
we do have read-ahead support in the kernel. Forward references are
relatively free, because read-ahead should populate that page before
we need it. Backward references are horribly expensive, because they
may have been evicted to make room for more read-ahead. From what I
could tell of similar traces in JGit, the recency commit ordering
causes a lot more backwards references than the parse ordering.

>  * Pathspec-limited log.
>
>   $ git log drivers/net >/dev/null
>
>   The path is touched by 26551 commits and merges (among 254656 total).
>
>                                  v1.7.6  with patch
>   Total number of access :      559,511     558,663
...
>         70.0% percentile :  319,574,732 110,370,100
>         80.0% percentile :  361,647,599 123,707,229
>         90.0% percentile :  393,195,669 128,947,636
>         95.0% percentile :  405,496,875 131,609,321
...

Does this result suggest that we needed less of the pack in-memory in
order to produce the result? That is, on a cold cache we should be
touching fewer pages of the pack when this patch was used to create
it, and fewer page references would allow the command to complete more
quickly on a cold cache.

> Note that a half-a-gigabyte packfile comfortably fits in the buffer cache,
> and you would unlikely to see much performance difference on a modern and
> reasonably beefy machine with enough memory and local disks. Benchmarking
> with cold cache (or over NFS) would be interesting.

It would also be easy to test these cases by setting the pack window
size to something small (e.g. 1 MB) and the pack limit to something
equally small (e.g. 25 MB), and stuffing a delay of 20 ms into the
code path that xmmaps a new window when its not already opened.

I'm glad you started working on this, it looks like it may lead to a
better pack ordering.

-- 
Shawn.

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Junio C Hamano]

I <gitster@pobox.com> wrote:

>  - In the original recency order, trees and blobs are intermixed. Write
>    trees together before blobs, in the hope that this will improve
>    locality when running pathspec-limited revision traversal, i.e.
>    "git log paths...";
>
>  - When writing blob objects out, write the whole family of blobs that use
>    the same delta base object together, by starting from the root of the
>    delta chain, and writing its immediate children in a width-first
>    manner, in the hope that this will again improve locality when reading
>    blobs that belong to the same path, which are likely to be deltified
>    against each other.

An interesting tangent.

With a single-liner change to apply the same "write the entire family as a
group" logic also to tree objects, we get a superb improvement to the
"index-pack" workload, while "log pathspec" becomes measurably worse.

>  * Pathspec-limited log.
>    $ git log drivers/net >/dev/null
>                                   v1.7.6  with patch
> 	 60.0% percentile :        688,671     443,578
> 	 70.0% percentile :    319,574,732 110,370,100
> 	 99.0% percentile :    412,942,470 133,078,115
> 	 99.5% percentile :    413,172,266 133,163,349
> 	 99.9% percentile :    413,354,356 133,240,445
>        Less than 2MiB seek:       61.71%      62.87%

     60.00% percentile :    2,240,841
     70.00% percentile :  115,729,538
     99.00% percentile :  132,912,877
     99.90% percentile :  133,129,574
   Less than 2MiB seek :       59.77%

This of course is because trees tend to delta well against each other and
writing out everything in the same family tends to coalesce ancient and
recent trees close together, while the history traversal wants to see the
trees at the same path in adjacent commits, and the process to jump over
to the "next tree" in the same commit need to seek a lot more.

>  * Blame.
>    $ git blame drivers/net/ne.c >/dev/null
>                                   v1.7.6  with patch
> 	 50.0% percentile :         11,248       7,334
> 	 95.0% percentile :    408,230,673 132,174,308
>        Less than 2MiB seek:       56.47%      56.83%

     50.00% percentile :       79,182
     95.00% percentile :  132,547,959
   Less than 2MiB seek :       56.16%

This also is harmed by trees in adjacent commits being further apart, but
blame needs to read a lot of blobs as well, so the effect is not as grave
as tree-only "log pathspec" case. 

>  * Index pack.
>    $ git index-pack -v .git/objects/pack/pack*.pack
>                                   v1.7.6  with patch
> 	 80.0% percentile :      1,317,862       4,971
> 	 90.0% percentile :     11,926,385     119,398
> 	 99.9% percentile :    382,919,785  33,155,191
>        Less than 2MiB seek:       81.73%      96.92%

     80.00% percentile :      745
     90.00% percentile :    1,891
     99.90% percentile :   80,001
   Less than 2MiB seek :  100.00%

It is so obvious that the in pack object ordering with "the whole family
at once" tweak is extremely tuned for this workload that the result is not
even funny.

The moral of the story is that index-pack is not a workload to optimize
for ;-) and the following is a wrong patch to apply. In general, we have
to be extremely careful not to tune for a particular workload while
unknowingly sacrificing other workloads.

I wonder if we would get a better locality for "blame" by not writing the
whole family at once for blobs, but only a smaller subset.

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 27132bb..adcb509 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -553,7 +553,7 @@ static struct object_entry **compute_write_order(void)
 	for (i = 0; i < nr_objects; i++) {
 		if (objects[i].type != OBJ_TREE)
 			continue;
-		add_to_write_order(wo, &wo_end, &objects[i]);
+		add_family_to_write_order(wo, &wo_end, &objects[i]);
 	}
 
 	/*

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Nicolas Pitre]

On Fri, 8 Jul 2011, Junio C Hamano wrote:

> The moral of the story is that index-pack is not a workload to optimize
> for ;-) and the following is a wrong patch to apply.

Right.  And if it was possible to slow down index-pack while speeding up 
the other workloads then this would actually be worthwhile because 
index-pack is not used as often and people are not expecting it to be 
fast either.


Nicolas

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Junio C Hamano]

This updates the codepath to write commit objects so that when a commit is
emitted, its parents are scheduled to be output next (but this does not go
recursively), in the hope that it may help a typical "rev-list" traversal.

I've tried various workloads from the previous message; while this patch
does not regress any of them significantly, it does not seem to improve
them significantly, either.



 builtin/pack-objects.c |   96 ++++++++++++++++++++++++++++++++++-------------
 1 files changed, 69 insertions(+), 27 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 27132bb..46ae610 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -487,6 +487,74 @@ static void add_family_to_write_order(struct object_entry **wo,
 	add_descendants_to_write_order(wo, endp, root);
 }
 
+static void add_commit_to_write_order(struct object_entry **wo,
+				      int *endp,
+				      struct object_entry *e)
+{
+	/*
+	 * A typical rev-list traversal looks at the parent of a
+	 * commit before deciding to emit the commit; if it ends up
+	 * emitting this commit, it is likely that it needs an early
+	 * access of its parents.
+	 */
+	struct commit *commit;
+	struct commit_list *parents;
+
+	if (e->filled)
+		return;
+	add_to_write_order(wo, endp, e);
+	commit = lookup_commit(e->idx.sha1);
+	if (!commit ||
+	    (!commit->object.parsed && parse_commit(commit)))
+		die("BUG: calling add_commit with a non-commit???");
+	for (parents = commit->parents; parents; parents = parents->next) {
+		struct object_entry *pe;
+		struct commit *parent = parents->item;
+		pe = locate_object_entry(parent->object.sha1);
+		if (pe)
+			add_to_write_order(wo, endp, pe);
+	}
+}
+
+static int add_commits_to_write_order(struct object_entry **wo)
+{
+	int i, wo_end;
+
+	/*
+	 * Give the commits in the original recency order until
+	 * we see a tagged tip.
+	 */
+	for (i = wo_end = 0; i < nr_objects; i++) {
+		if (objects[i].type != OBJ_COMMIT)
+			continue;
+		if (objects[i].tagged)
+			break;
+		add_commit_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	/*
+	 * Then fill all the tagged tips.
+	 */
+	for (i = 0; i < nr_objects; i++) {
+		if (objects[i].type != OBJ_COMMIT)
+			continue;
+		if (objects[i].tagged)
+			add_commit_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	/*
+	 * And then all remaining commits and tags.
+	 */
+	for (i = 0; i < nr_objects; i++) {
+		if (objects[i].type == OBJ_COMMIT)
+			add_commit_to_write_order(wo, &wo_end, &objects[i]);
+		else if (objects[i].type != OBJ_TAG)
+			add_to_write_order(wo, &wo_end, &objects[i]);
+	}
+
+	return wo_end;
+}
+
 static struct object_entry **compute_write_order(void)
 {
 	int i, wo_end;
@@ -519,33 +587,7 @@ static struct object_entry **compute_write_order(void)
 	 */
 	for_each_tag_ref(mark_tagged, NULL);
 
-	/*
-	 * Give the commits in the original recency order until
-	 * we see a tagged tip.
-	 */
-	for (i = wo_end = 0; i < nr_objects; i++) {
-		if (objects[i].tagged)
-			break;
-		add_to_write_order(wo, &wo_end, &objects[i]);
-	}
-
-	/*
-	 * Then fill all the tagged tips.
-	 */
-	for (; i < nr_objects; i++) {
-		if (objects[i].tagged)
-			add_to_write_order(wo, &wo_end, &objects[i]);
-	}
-
-	/*
-	 * And then all remaining commits and tags.
-	 */
-	for (i = 0; i < nr_objects; i++) {
-		if (objects[i].type != OBJ_COMMIT &&
-		    objects[i].type != OBJ_TAG)
-			continue;
-		add_to_write_order(wo, &wo_end, &objects[i]);
-	}
+	wo_end = add_commits_to_write_order(wo);
 
 	/*
 	 * And then all the trees.

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Shawn Pearce]

On Fri, Jul 8, 2011 at 15:47, Junio C Hamano <gitster@pobox.com> wrote:
> This updates the codepath to write commit objects so that when a commit is
> emitted, its parents are scheduled to be output next (but this does not go
> recursively), in the hope that it may help a typical "rev-list" traversal.
>
> I've tried various workloads from the previous message; while this patch
> does not regress any of them significantly, it does not seem to improve
> them significantly, either.

I'll have to do some more testing then... I feel like this improves
things when the underlying storage has higher latency than 0 (aka cold
cache, or NFS). But its good to hear this didn't make the workloads
worse. :-)

-- 
Shawn.

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Ævar Arnfjörð Bjarmason]

On Fri, Jul 8, 2011 at 02:24, Junio C Hamano <gitster@pobox.com> wrote:

>  - Commits at the tip of tags are written together, in the hope that
>   revision traversal done in incremental fetch (which starts by
>   putting them in a revision queue marked as UNINTERESTING) will see a
>   better locality of these objects;

We recently upgraded to 1.7.7 and I've traced a very large slowdown in
packing down to this commit.

On our repository packing used to take around 30 seconds, it now takes
about 4 minutes. Which means that cloning the repository went from
being slightly slow to pretty intolerable.

I haven't dug into why this is but I'm pretty sure it's because this
patch makes Git behave pathologically on repositories with a large
amount of tags. git.git itself has ~27k revs / and ~450 tags, or a tag
every ~60 revisions.

Try it on e.g. a repository with a couple of hundred thousand revs and
a tag every 10-20 revisions.

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Ævar Arnfjörð Bjarmason]

On Thu, Oct 27, 2011 at 23:01, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

> I haven't dug into why this is but I'm pretty sure it's because this
> patch makes Git behave pathologically on repositories with a large
> amount of tags. git.git itself has ~27k revs / and ~450 tags, or a tag
> every ~60 revisions.
>
> Try it on e.g. a repository with a couple of hundred thousand revs and
> a tag every 10-20 revisions.

Actually it just seems slow in general, not just on repositories with
a lot of tags, on linux-2.6.git with this patch:

    $ time ~/g/git/git-pack-objects --keep-true-parents
--honor-pack-keep --non-empty --all --reflog
--delta-base-offs</dev/null
/home/avar/g/linux-2.6/.git/objects/pack/.tmp-pack
    Counting objects: 2184059, done.
    Delta compression using up to 8 threads.
    Compressing objects: 100% (338780/338780), done.
    130605d5b82492a38452b9bc7bddfb4a6ef0e942
    Writing objects: 100% (2184059/2184059), done.
    Total 2184059 (delta 1825129), reused 2184059 (delta 1825129)

    real    1m28.426s
    user    1m19.661s
    sys     0m3.008s

With it reverted:

    $ time ~/g/git/git-pack-objects --keep-true-parents
--honor-pack-keep --non-empty --all --reflog --delta-base-offset
</dev/null /home/avar/g/linux-2.6/.git/objects/pack/.tmp-pack
    Counting objects: 2184059, done.
    Delta compression using up to 8 threads.
    Compressing objects: 100% (338780/338780), done.
    130605d5b82492a38452b9bc7bddfb4a6ef0e942
    Writing objects: 100% (2184059/2184059), done.
    Total 2184059 (delta 1825129), reused 2184059 (delta 1825129)

    real    0m50.152s
    user    0m45.367s
    sys     0m2.920s

And if you create a lot of tags:

    git log --pretty=%h | perl -lne 'chomp(my $sha = <>); print $sha
if $i++ % 10 == 0' | parallel "git tag test-tag-{} {}"

Resulting in:

    $ git rev-list HEAD | wc -l
    269514
    $ git tag -l | wc -l
    13733

This'll be the time with this patch reverted, i.e. almost exactly the
same as with just ~250 tags:

    real    0m52.860s
    user    0m44.907s
    sys     0m3.172s

And with it applied, i.e. almost exactly the same as with just ~250
tags:

    real    1m29.080s
    user    1m21.825s
    sys     0m3.096s

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Ævar Arnfjörð Bjarmason]

On Thu, Oct 27, 2011 at 23:49, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

> Actually it just seems slow in general, not just on repositories with
> a lot of tags, on linux-2.6.git with this patch:

Here's profiling with gprof for everything with >1% of execution time
with the patch applied:

    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total
     time   seconds   seconds    calls   s/call   s/call  name
     21.07     15.99    15.99  2184059     0.00     0.00
add_descendants_to_write_order
     20.25     31.35    15.37 1146371554     0.00     0.00  add_to_write_order
     11.94     40.41     9.06 142180385     0.00     0.00  hashcmp
      5.55     44.62     4.21 90592818     0.00     0.00  lookup_object
      4.64     48.14     3.52 72804470     0.00     0.00  hashcmp
      3.87     51.08     2.94 90007452     0.00     0.00  get_mode
      3.31     53.59     2.51 90007452     0.00     0.00  decode_tree_entry
      1.90     55.03     1.44  2184059     0.00     0.00
add_family_to_write_order
      1.79     56.39     1.36 43247856     0.00     0.00  hashcmp
      1.29     57.37     0.98                             pack_offset_sort
      1.27     58.33     0.96 90007452     0.00     0.00  update_tree_entry
      1.27     59.29     0.96 90592817     0.00     0.00  hashtable_index
      1.20     60.20     0.91  4009188     0.00     0.00  find_pack_revindex
      1.19     61.10     0.90  5899321     0.00     0.00  find_pack_entry_one
      1.12     61.95     0.85   269514     0.00     0.00
commit_list_insert_by_date
      1.08     62.77     0.82  5387773     0.00     0.00  patch_delta

And without:

    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total
     time   seconds   seconds    calls   s/call   s/call  name
     21.29      9.13     9.13 142180385     0.00     0.00  hashcmp
     10.59     13.67     4.54 90592818     0.00     0.00  lookup_object
      8.48     17.31     3.64 72638478     0.00     0.00  hashcmp
      6.60     20.14     2.83 90007452     0.00     0.00  decode_tree_entry
      6.15     22.77     2.64 90007452     0.00     0.00  get_mode
      2.99     24.05     1.28 43247182     0.00     0.00  hashcmp
      2.96     25.32     1.27 90592817     0.00     0.00  hashtable_index
      2.47     26.38     1.06 90007452     0.00     0.00  update_tree_entry
      2.26     27.35     0.97  4009188     0.00     0.00  find_pack_revindex
      2.05     28.23     0.88   269245     0.00     0.00  process_tree
      1.96     29.07     0.84   269514     0.00     0.00
commit_list_insert_by_date
      1.94     29.90     0.83                             pack_offset_sort
      1.73     30.64     0.74  5389900     0.00     0.00  patch_delta
      1.70     31.37     0.73  5885588     0.00     0.00  find_pack_entry_one
      1.38     31.96     0.59  8692967     0.00     0.00  hashcmp
      1.24     32.49     0.53  8175096     0.00     0.00
unpack_object_header_buffer
      1.14     32.98     0.49        1     0.49     0.59  write_idx_file
      1.12     33.46     0.48  5885588     0.00     0.00
nth_packed_object_offset
      1.12     33.94     0.48  6051632     0.00     0.00
locate_object_entry_hash

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Jakub Narebski]

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

> On Thu, Oct 27, 2011 at 23:49, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> 
> > Actually it just seems slow in general, not just on repositories with
> > a lot of tags, on linux-2.6.git with this patch:
> 
> Here's profiling with gprof for everything with >1% of execution time
> with the patch applied:
> 
>     Each sample counts as 0.01 seconds.
>       %   cumulative   self              self     total
>      time   seconds   seconds    calls   s/call   s/call  name
>      21.07     15.99    15.99  2184059     0.00     0.00  add_descendants_to_write_order
>      20.25     31.35    15.37 1146371554     0.00     0.00  add_to_write_order
[...]
> 
> And without:
> 
>     Each sample counts as 0.01 seconds.
>       %   cumulative   self              self     total
>      time   seconds   seconds    calls   s/call   s/call  name
>      21.29      9.13     9.13 142180385     0.00     0.00  hashcmp
>      10.59     13.67     4.54 90592818     0.00     0.00  lookup_object
[...]

Errr... do or do not gprof results include time spend in libraries?
Though that might not matter for this case.

Can you repeat profiling using "perf events" or something using it
(e.g. via PAPI library like HPCToolkit)?

-- 
Jakub Narębski

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Junio C Hamano]

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

> We recently upgraded to 1.7.7 and I've traced a very large slowdown in
> packing down to this commit.

Does Dan McGee's series leading to 38d4deb (pack-objects: don't traverse
objects unnecessarily, 2011-10-18) help?

Re: [PATCH 2/2] pack-objects: optimize "recency order"

[Ævar Arnfjörð Bjarmason]

On Fri, Oct 28, 2011 at 00:05, Junio C Hamano <gitster@pobox.com> wrote:
> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:
>
>> We recently upgraded to 1.7.7 and I've traced a very large slowdown in
>> packing down to this commit.
>
> Does Dan McGee's series leading to 38d4deb (pack-objects: don't traverse
> objects unnecessarily, 2011-10-18) help?

Yes it does!

When I do:

    git cherry-pick 703f05ad5835cff92b12c29aecf8d724c8c847e2..38d4deb

Here's the time on the linux-2.6.git repack with that series:

    real    0m53.969s
    user    0m47.063s
    sys     0m3.020s

On the repository I was having troubles with this was the result on
master:

    Total 911023 (delta 687744), reused 905500 (delta 683064)

    real    6m0.487s
    user    4m1.751s
    sys     1m56.331s

And with the cherry-pick:

    Total 911023 (delta 687744), reused 911023 (delta 687744)

    real    1m44.192s
    user    0m32.169s
    sys     0m4.383s

And with 1b4bb16b9ec331c91e28d2e3e7dee5070534b6a2 reverted:

    Total 911023 (delta 687744), reused 911023 (delta 687744)

    real    1m23.796s
    user    0m31.931s
    sys     0m3.549s

So it's still slower, but not intolerably slower. I'd be interested to
find out why we have that 20% difference that doesn't show up on
linux-2.6.git though, the repository is mostly source code but there
are some binary blobs in it as well, although not very large, the
overall size of the entire repository is <500MB.