[PATCH v2 0/3] fast-export: speed improvements

Hi,

Second try, dropped one fix, and address a few comments.

Parsing the marks of an import of the emacs repository moves fast-export to a
crawl. It takes 14 minutes in my setup, after these patches, it takes 1 second.

The important patches are #2 and #3, the rest are niceities.

Felipe Contreras (3):
  fast-{import,export}: use get_sha1_hex() directly
  fast-export: improve speed by skipping blobs
  fast-export: don't parse all the commits

 builtin/fast-export.c | 22 +++++++++++++++-------
 fast-import.c         | 10 +++++-----
 2 files changed, 20 insertions(+), 12 deletions(-)

-- 
1.8.3.rc0.401.g45bba44

It's wrong to call get_sha1() if they should be SHA-1s, plus
inefficient.

Signed-off-by: Felipe Contreras <redacted>
---
 builtin/fast-export.c |  2 +-
 fast-import.c         | 10 +++++-----
 2 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index d60d675..a4dee14 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c

@@ -621,7 +621,7 @@ static void import_marks(char *input_file)
 
 		mark = strtoumax(line + 1, &mark_end, 10);
 		if (!mark || mark_end == line + 1
-			|| *mark_end != ' ' || get_sha1(mark_end + 1, sha1))
+			|| *mark_end != ' ' || get_sha1_hex(mark_end + 1, sha1))
 			die("corrupt mark line: %s", line);
 
 		if (last_idnum < mark)

diff --git a/fast-import.c b/fast-import.c
index 5f539d7..e02f212 100644
--- a/fast-import.c
+++ b/fast-import.c

@@ -1822,7 +1822,7 @@ static void read_marks(void)
 		*end = 0;
 		mark = strtoumax(line + 1, &end, 10);
 		if (!mark || end == line + 1
-			|| *end != ' ' || get_sha1(end + 1, sha1))
+			|| *end != ' ' || get_sha1_hex(end + 1, sha1))
 			die("corrupt mark line: %s", line);
 		e = find_object(sha1);
 		if (!e) {

@@ -2490,7 +2490,7 @@ static void note_change_n(struct branch *b, unsigned char *old_fanout)
 		if (commit_oe->type != OBJ_COMMIT)
 			die("Mark :%" PRIuMAX " not a commit", commit_mark);
 		hashcpy(commit_sha1, commit_oe->idx.sha1);
-	} else if (!get_sha1(p, commit_sha1)) {
+	} else if (!get_sha1_hex(p, commit_sha1)) {
 		unsigned long size;
 		char *buf = read_object_with_reference(commit_sha1,
 			commit_type, &size, commit_sha1);

@@ -2604,7 +2604,7 @@ static int parse_from(struct branch *b)
 			free(buf);
 		} else
 			parse_from_existing(b);
-	} else if (!get_sha1(from, b->sha1))
+	} else if (!get_sha1_hex(from, b->sha1))
 		parse_from_existing(b);
 	else
 		die("Invalid ref name or SHA1 expression: %s", from);

@@ -2632,7 +2632,7 @@ static struct hash_list *parse_merge(unsigned int *count)
 			if (oe->type != OBJ_COMMIT)
 				die("Mark :%" PRIuMAX " not a commit", idnum);
 			hashcpy(n->sha1, oe->idx.sha1);
-		} else if (!get_sha1(from, n->sha1)) {
+		} else if (!get_sha1_hex(from, n->sha1)) {
 			unsigned long size;
 			char *buf = read_object_with_reference(n->sha1,
 				commit_type, &size, n->sha1);

@@ -2792,7 +2792,7 @@ static void parse_new_tag(void)
 		oe = find_mark(from_mark);
 		type = oe->type;
 		hashcpy(sha1, oe->idx.sha1);
-	} else if (!get_sha1(from, sha1)) {
+	} else if (!get_sha1_hex(from, sha1)) {
 		struct object_entry *oe = find_object(sha1);
 		if (!oe) {
 			type = sha1_object_info(sha1, NULL);

-- 
1.8.3.rc0.401.g45bba44

We don't care about blobs, or any object other than commits, but in
order to find the type of object, we are parsing the whole thing, which
is slow, specially in big repositories with lots of big files.

There's no need for that, we can query the object information with
sha1_object_info();

Before this, loading the objects of a fresh emacs import, with 260598
blobs took 14 minutes, after this patch, it takes 3 seconds.

This is the way fast-import does it. Also die if the object is not
found (like fast-import).

Signed-off-by: Felipe Contreras <redacted>
---
 builtin/fast-export.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index a4dee14..a5b8da8 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c

@@ -613,6 +613,7 @@ static void import_marks(char *input_file)
 		char *line_end, *mark_end;
 		unsigned char sha1[20];
 		struct object *object;
+		enum object_type type;
 
 		line_end = strchr(line, '\n');
 		if (line[0] != ':' || !line_end)

@@ -627,17 +628,19 @@ static void import_marks(char *input_file)
 		if (last_idnum < mark)
 			last_idnum = mark;
 
-		object = parse_object(sha1);
-		if (!object)
+		type = sha1_object_info(sha1, NULL);
+		if (type < 0)
+			die("object not found: %s", sha1_to_hex(sha1));
+
+		if (type != OBJ_COMMIT)
+			/* only commits */
 			continue;
 
+		object = parse_object(sha1);
+
 		if (object->flags & SHOWN)
 			error("Object %s already has a mark", sha1_to_hex(sha1));
 
-		if (object->type != OBJ_COMMIT)
-			/* only commits */
-			continue;
-
 		mark_object(object, mark);
 
 		object->flags |= SHOWN;

-- 
1.8.3.rc0.401.g45bba44

We don't need the parsed objects at this point, merely the information
that they have marks.

Seems to be three times faster in my setup with lots of objects.

Signed-off-by: Felipe Contreras <redacted>
---
 builtin/fast-export.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index a5b8da8..d1d68e9 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c

@@ -613,6 +613,7 @@ static void import_marks(char *input_file)
 		char *line_end, *mark_end;
 		unsigned char sha1[20];
 		struct object *object;
+		struct commit *commit;
 		enum object_type type;
 
 		line_end = strchr(line, '\n');

@@ -636,7 +637,11 @@ static void import_marks(char *input_file)
 			/* only commits */
 			continue;
 
-		object = parse_object(sha1);
+		commit = lookup_commit(sha1);
+		if (!commit)
+			die("not a commit? can't happen: %s", sha1_to_hex(sha1));
+
+		object = &commit->object;
 
 		if (object->flags & SHOWN)
 			error("Object %s already has a mark", sha1_to_hex(sha1));

-- 
1.8.3.rc0.401.g45bba44

On Sun, May 05, 2013 at 05:38:53PM -0500, Felipe Contreras wrote:

We don't care about blobs, or any object other than commits, but in
order to find the type of object, we are parsing the whole thing, which
is slow, specially in big repositories with lots of big files.

I did a double-take on reading this subject line and first paragraph,
thinking "surely fast-export needs to actually output blobs?".

Reading the patch, I see that this is only about not bothering to load
blob marks from --import-marks. It might be nice to mention that in the
commit message, which is otherwise quite confusing.

I'm also not sure why your claim "we don't care about blobs" is true,
because naively we would want future runs of fast-export to avoid having
to write out the whole blob content when mentioning the blob again. I
think one argument could be "if we write a mark for blob X, we will also
have written a mark for commit Y which contains it; on subsequent runs,
we will just show the mark for Y in the first place, and not even care
about showing X (as a part of Y) either way. We would only refer to the
mark for X if it appears as part of a different commit, but that is a
rare case not worth worrying about."

Does that match your reasoning?

Before this, loading the objects of a fresh emacs import, with 260598
blobs took 14 minutes, after this patch, it takes 3 seconds.

Presumably most of that speed improvement comes from not parsing the
blob objects. I wonder if you could get similar speedups by applying the
"do not bother parsing" rule from your patch 3. You would still incur
some cost to create a "struct blob", but it may or may not be
measurable.  That would mean we get the "case not worth worrying about"
from above for free. I doubt it would make that big a difference,
though, given the rarity of it. So I am OK with it either way.

-Peff

On Mon, May 6, 2013 at 7:31 AM, Jeff King [off-list ref] wrote:

On Sun, May 05, 2013 at 05:38:53PM -0500, Felipe Contreras wrote:

quoted

We don't care about blobs, or any object other than commits, but in
order to find the type of object, we are parsing the whole thing, which
is slow, specially in big repositories with lots of big files.

I did a double-take on reading this subject line and first paragraph,
thinking "surely fast-export needs to actually output blobs?".

If you think that, then you are not familiar with the code.

--export-marks=<file>::
	Dumps the internal marks table to <file> when complete.
	Marks are written one per line as `:markid SHA-1`. Only marks
	for revisions are dumped; marks for blobs are ignored.

		if (deco->base && deco->base->type == 1) {
			mark = ptr_to_mark(deco->decoration);
			if (fprintf(f, ":%"PRIu32" %s\n", mark,
				sha1_to_hex(deco->base->sha1)) < 0) {
			    e = 1;
			    break;
			}
		}

Reading the patch, I see that this is only about not bothering to load
blob marks from --import-marks. It might be nice to mention that in the
commit message, which is otherwise quite confusing.

The commit message says it exactly like it is: we don't care about blobs.

If an object is not a commit, we *already* skip it. But as the commit
message already says, we do so by parsing the whole thing.

I'm also not sure why your claim "we don't care about blobs" is true,
because naively we would want future runs of fast-export to avoid having
to write out the whole blob content when mentioning the blob again.

Because it's pointless to have hundreds and thousands of blob marks
that are *never* going to be used, only for an extremely tiny minority
that would.

Does that match your reasoning?

It doesn't matter, it has been that way since --export-marks was introduced.

quoted

Before this, loading the objects of a fresh emacs import, with 260598
blobs took 14 minutes, after this patch, it takes 3 seconds.

Presumably most of that speed improvement comes from not parsing the
blob objects. I wonder if you could get similar speedups by applying the
"do not bother parsing" rule from your patch 3. You would still incur
some cost to create a "struct blob", but it may or may not be
measurable.  That would mean we get the "case not worth worrying about"
from above for free. I doubt it would make that big a difference,
though, given the rarity of it. So I am OK with it either way.

How would I know if it's a blob or a commit, if not by the code this
patch introduces?

-- 
Felipe Contreras

On Mon, May 06, 2013 at 02:02:13PM -0500, Felipe Contreras wrote:

quoted

I did a double-take on reading this subject line and first paragraph,
thinking "surely fast-export needs to actually output blobs?".

If you think that, then you are not familiar with the code.

--export-marks=<file>::
[...]

My point was that nothing in the subject line nor that first paragraph
(nor, for that matter, the entire commit message) says that we are
talking about marks here.

quoted

Reading the patch, I see that this is only about not bothering to load
blob marks from --import-marks. It might be nice to mention that in the
commit message, which is otherwise quite confusing.

The commit message says it exactly like it is: we don't care about blobs.

If you guess that "we" means the marks code and not all of fast-export,
then yes. But I do not have any desire to get into another debate trying
to convince you that there is value to having a clear commit message.
Junio has already proposed a much more readable one.

-Peff

On Mon, May 6, 2013 at 2:11 PM, Jeff King [off-list ref] wrote:

On Mon, May 06, 2013 at 02:02:13PM -0500, Felipe Contreras wrote:

quoted

quoted

I did a double-take on reading this subject line and first paragraph,
thinking "surely fast-export needs to actually output blobs?".

If you think that, then you are not familiar with the code.

--export-marks=<file>::
[...]

My point was that nothing in the subject line nor that first paragraph
(nor, for that matter, the entire commit message) says that we are
talking about marks here.

s/$/ while loading marks/. Fixed.

-- 
Felipe Contreras

Felipe Contreras [off-list ref] writes:

It's wrong to call get_sha1() if they should be SHA-1s, plus
inefficient.

Signed-off-by: Felipe Contreras <redacted>
---

It appears that "they should be SHA-1s" assumption does not hold;
this patch breaks at least 3303, 9020, and 9300.

Also assuming these are always 40-hex goes directly against what is
documented in Documentation/git-fast-import.txt (look for "Here
committish is any of the following").  My bad while reviewing the
earlier round.

I've redone 'pu' (which was failing the test last night) after
dropping this and keeping only patches 2 and 3 from the series.

On Tue, May 7, 2013 at 9:38 AM, Junio C Hamano [off-list ref] wrote:

Felipe Contreras [off-list ref] writes:

quoted

It's wrong to call get_sha1() if they should be SHA-1s, plus
inefficient.

Signed-off-by: Felipe Contreras <redacted>
---

It appears that "they should be SHA-1s" assumption does not hold;
this patch breaks at least 3303, 9020, and 9300.

Also assuming these are always 40-hex goes directly against what is
documented in Documentation/git-fast-import.txt (look for "Here
committish is any of the following").  My bad while reviewing the
earlier round.

I've redone 'pu' (which was failing the test last night) after
dropping this and keeping only patches 2 and 3 from the series.

Turns out most of the get_sha1() calls were correct; this does the trick:

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index 18fdfb3..d1d68e9 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c

@@ -623,7 +623,7 @@ static void import_marks(char *input_file)

                mark = strtoumax(line + 1, &mark_end, 10);
                if (!mark || mark_end == line + 1
-                       || *mark_end != ' ' || get_sha1(mark_end + 1, sha1))
+                       || *mark_end != ' ' || get_sha1_hex(mark_end + 1, sha1))
                        die("corrupt mark line: %s", line);

                if (last_idnum < mark)

diff --git a/fast-import.c b/fast-import.c
index 5f539d7..3f32149 100644
--- a/fast-import.c
+++ b/fast-import.c

@@ -1822,7 +1822,7 @@ static void read_marks(void)
                *end = 0;
                mark = strtoumax(line + 1, &end, 10);
                if (!mark || end == line + 1
-                       || *end != ' ' || get_sha1(end + 1, sha1))
+                       || *end != ' ' || get_sha1_hex(end + 1, sha1))
                        die("corrupt mark line: %s", line);
                e = find_object(sha1);
                if (!e) {

-- 
Felipe Contreras