[PATCH 0/2] For improved pack locality

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

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 <redacted>
---
 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

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 <redacted>
---
 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

On Thu, Jul 7, 2011 at 17:24, Junio C Hamano [off-list ref] 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.

On Fri, Jul 8, 2011 at 02:24, Junio C Hamano [off-list ref] 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.

On Thu, Oct 27, 2011 at 23:01, Ævar Arnfjörð Bjarmason [off-list ref] 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

On Thu, Oct 27, 2011 at 23:49, Ævar Arnfjörð Bjarmason [off-list ref] 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

Ævar Arnfjörð Bjarmason [off-list ref] writes:

On Thu, Oct 27, 2011 at 23:49, Ævar Arnfjörð Bjarmason [off-list ref] wrote:

quoted

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