* [PATCH 0/2] For improved pack locality
@ 2011-07-08 0:24 Junio C Hamano
2011-07-08 0:24 ` [PATCH 1/2] core: log offset pack data accesses happened Junio C Hamano
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
0 siblings, 2 replies; 14+ messages in thread
From: Junio C Hamano @ 2011-07-08 0:24 UTC (permalink / raw)
To: git; +Cc: Shawn O. Pearce
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
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 1/2] core: log offset pack data accesses happened
2011-07-08 0:24 [PATCH 0/2] For improved pack locality Junio C Hamano
@ 2011-07-08 0:24 ` Junio C Hamano
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
1 sibling, 0 replies; 14+ messages in thread
From: Junio C Hamano @ 2011-07-08 0:24 UTC (permalink / raw)
To: git; +Cc: Shawn O. Pearce
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
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 0:24 [PATCH 0/2] For improved pack locality Junio C Hamano
2011-07-08 0:24 ` [PATCH 1/2] core: log offset pack data accesses happened Junio C Hamano
@ 2011-07-08 0:24 ` Junio C Hamano
2011-07-08 2:08 ` Shawn Pearce
` (3 more replies)
1 sibling, 4 replies; 14+ messages in thread
From: Junio C Hamano @ 2011-07-08 0:24 UTC (permalink / raw)
To: git; +Cc: Shawn O. Pearce
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
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
@ 2011-07-08 2:08 ` Shawn Pearce
2011-07-08 17:45 ` Junio C Hamano
` (2 subsequent siblings)
3 siblings, 0 replies; 14+ messages in thread
From: Shawn Pearce @ 2011-07-08 2:08 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
2011-07-08 2:08 ` Shawn Pearce
@ 2011-07-08 17:45 ` Junio C Hamano
2011-07-11 22:49 ` Nicolas Pitre
2011-07-08 22:47 ` Junio C Hamano
2011-10-27 21:01 ` Ævar Arnfjörð Bjarmason
3 siblings, 1 reply; 14+ messages in thread
From: Junio C Hamano @ 2011-07-08 17:45 UTC (permalink / raw)
To: Shawn O. Pearce; +Cc: git
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]);
}
/*
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
2011-07-08 2:08 ` Shawn Pearce
2011-07-08 17:45 ` Junio C Hamano
@ 2011-07-08 22:47 ` Junio C Hamano
2011-07-09 0:42 ` Shawn Pearce
2011-10-27 21:01 ` Ævar Arnfjörð Bjarmason
3 siblings, 1 reply; 14+ messages in thread
From: Junio C Hamano @ 2011-07-08 22:47 UTC (permalink / raw)
To: Shawn O. Pearce; +Cc: git
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.
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 22:47 ` Junio C Hamano
@ 2011-07-09 0:42 ` Shawn Pearce
0 siblings, 0 replies; 14+ messages in thread
From: Shawn Pearce @ 2011-07-09 0:42 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 17:45 ` Junio C Hamano
@ 2011-07-11 22:49 ` Nicolas Pitre
0 siblings, 0 replies; 14+ messages in thread
From: Nicolas Pitre @ 2011-07-11 22:49 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Shawn O. Pearce, git
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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
` (2 preceding siblings ...)
2011-07-08 22:47 ` Junio C Hamano
@ 2011-10-27 21:01 ` Ævar Arnfjörð Bjarmason
2011-10-27 21:49 ` Ævar Arnfjörð Bjarmason
2011-10-27 22:05 ` Junio C Hamano
3 siblings, 2 replies; 14+ messages in thread
From: Ævar Arnfjörð Bjarmason @ 2011-10-27 21:01 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Shawn O. Pearce
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-10-27 21:01 ` Ævar Arnfjörð Bjarmason
@ 2011-10-27 21:49 ` Ævar Arnfjörð Bjarmason
2011-10-27 22:02 ` Ævar Arnfjörð Bjarmason
2011-10-27 22:05 ` Junio C Hamano
1 sibling, 1 reply; 14+ messages in thread
From: Ævar Arnfjörð Bjarmason @ 2011-10-27 21:49 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Shawn O. Pearce
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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-10-27 21:49 ` Ævar Arnfjörð Bjarmason
@ 2011-10-27 22:02 ` Ævar Arnfjörð Bjarmason
2011-10-27 22:32 ` Jakub Narebski
0 siblings, 1 reply; 14+ messages in thread
From: Ævar Arnfjörð Bjarmason @ 2011-10-27 22:02 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Shawn O. Pearce
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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-10-27 21:01 ` Ævar Arnfjörð Bjarmason
2011-10-27 21:49 ` Ævar Arnfjörð Bjarmason
@ 2011-10-27 22:05 ` Junio C Hamano
2011-10-28 9:17 ` Ævar Arnfjörð Bjarmason
1 sibling, 1 reply; 14+ messages in thread
From: Junio C Hamano @ 2011-10-27 22:05 UTC (permalink / raw)
To: Ævar Arnfjörð Bjarmason; +Cc: git, Shawn O. Pearce
Æ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?
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-10-27 22:02 ` Ævar Arnfjörð Bjarmason
@ 2011-10-27 22:32 ` Jakub Narebski
0 siblings, 0 replies; 14+ messages in thread
From: Jakub Narebski @ 2011-10-27 22:32 UTC (permalink / raw)
To: Ævar Arnfjörð Bjarmason
Cc: Junio C Hamano, git, Shawn O. Pearce
Æ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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 2/2] pack-objects: optimize "recency order"
2011-10-27 22:05 ` Junio C Hamano
@ 2011-10-28 9:17 ` Ævar Arnfjörð Bjarmason
0 siblings, 0 replies; 14+ messages in thread
From: Ævar Arnfjörð Bjarmason @ 2011-10-28 9:17 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, Shawn O. Pearce, Dan McGee
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2011-10-28 9:18 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-07-08 0:24 [PATCH 0/2] For improved pack locality Junio C Hamano
2011-07-08 0:24 ` [PATCH 1/2] core: log offset pack data accesses happened Junio C Hamano
2011-07-08 0:24 ` [PATCH 2/2] pack-objects: optimize "recency order" Junio C Hamano
2011-07-08 2:08 ` Shawn Pearce
2011-07-08 17:45 ` Junio C Hamano
2011-07-11 22:49 ` Nicolas Pitre
2011-07-08 22:47 ` Junio C Hamano
2011-07-09 0:42 ` Shawn Pearce
2011-10-27 21:01 ` Ævar Arnfjörð Bjarmason
2011-10-27 21:49 ` Ævar Arnfjörð Bjarmason
2011-10-27 22:02 ` Ævar Arnfjörð Bjarmason
2011-10-27 22:32 ` Jakub Narebski
2011-10-27 22:05 ` Junio C Hamano
2011-10-28 9:17 ` Ævar Arnfjörð Bjarmason
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.