Skip to contentSkip to conversation

Modify git-rev-list ... [ resend to fix whitespace mangle ]

PATCH New [email protected] 2 participants 2 messages Jun 15, 2016 2 messages not in the archive Kbuild

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Modify git-rev-list ... [ resend to fix whitespace mangle ]

[PATCH] Modify git-rev-list to linearise the commit history in merge order.

This patch linearises the GIT commit history graph into merge order which is defined by invariants specified in Documentation/git-rev-list.txt.

The linearisation produced by this patch is superior in an objective sense to that produced by the existing git-rev-list implementation in that the linearisation produced is guaranteed to have the minimum number of discontinuities, where a discontinuity is defined as an adjacent pair of commits in the output list which are not related in a direct child-parent relationship.

A test script, t/t5000-rev-list.sh, includes a test which demonstrates that the linearisation produced by --merge-order has less discontinuities than the linearisation produced by git-rev-list without the --merge-order flag specified. To see this, do the following:

	cd t
	./t5000-rev-list.sh
	cd trash
	cat actual-default-order
	cat actual-merge-order

The existing behaviour of git-rev-list is preserved, by default. To obtain the modified behaviour, specify --merge-order or --merge-order --show-breaks on the command line.

This version of the patch has been tested on the git repository and also on the linux-2.6 repository and has reasonable performance on both.

For more details about this change, refer to Documentation/git-rev-list.txt and http://blackcubes.dyndns.org/epoch/.

---

Makefile +3 -2
@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)
 	$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)
 
 LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
-	 tag.o delta.o date.o index.o diff-delta.o patch-delta.o
+	 tag.o delta.o date.o index.o diff-delta.o patch-delta.o epoch.o
 LIB_FILE=libgit.a
-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h
+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h
 
 LIB_H += strbuf.h
 LIB_OBJS += strbuf.o
@@ -134,6 +134,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.
 diffcore-pickaxe.o : $(LIB_H) diffcore.h
 diffcore-break.o : $(LIB_H) diffcore.h
 diffcore-order.o : $(LIB_H) diffcore.h
+epoch.o: $(LIB_H)
 
 test: all
 	$(MAKE) -C t/ all
commit.c +23 -1
@@ -129,7 +129,7 @@ void free_commit_list(struct commit_list
 	}
 }
 
-static void insert_by_date(struct commit_list **list, struct commit *item)
+void insert_by_date(struct commit_list **list, struct commit *item)
 {
 	struct commit_list **pp = list;
 	struct commit_list *p;
@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const 
 	buf[offset] = '\0';
 	return offset;
 }
+
+struct commit *pop_commit(struct commit_list **stack)
+{
+	struct commit_list *top = *stack;
+	struct commit *item = top ? top->item : NULL;
+
+	if (top) {
+		*stack = top->next;
+		free(top);
+	}
+	return item;
+}
+
+int count_parents(struct commit * commit)
+{
+        int count = 0;
+        struct commit_list * parents = commit->parents;
+        for (count=0;parents; parents=parents->next,count++)
+          ;
+        return count;
+}
+
commit.h +5 -0
@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list
 
 void sort_by_date(struct commit_list **list);
 
+void insert_by_date(struct commit_list **list, struct commit *item);
+
 extern unsigned long pretty_print_commit(const char *msg, unsigned long len, char *buf, unsigned long space);
 
 
@@ -41,4 +43,7 @@ extern unsigned long pretty_print_commit
 struct commit *pop_most_recent_commit(struct commit_list **list, 
 				      unsigned int mark);
 
+struct commit *pop_commit(struct commit_list **stack);
+
+int count_parents(struct commit * commit);
 #endif /* COMMIT_H */
epoch.c new file +454 -0

454 lines not on this page · raw message

epoch.h new file +12 -0
new file mode 100644
@@ -0,0 +1,12 @@
+#ifndef EPOCH_H
+#define EPOCH_H
+
+typedef int (*emitter_func) (struct commit *);
+
+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);
+
+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)
+#define MERGE_ORDER_VISIT_FLAG (1u<<4)
+#define MERGE_ORDER_BREAK_FLAG (1u<<5)
+
+#endif				/* EPOCH_H */
object.h +1 -0
@@ -15,6 +15,7 @@ struct object {
 	const char *type;
 	struct object_list *refs;
 	struct object_list *attached_deltas;
+	void *util;
 };
 
 extern int nr_objs;
rev-list.c +76 -38

150 lines not on this page · raw message

t/t5000-rev-list.sh new file +85 -0

85 lines not on this page · raw message

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#3 lore raw

PATCH 1/1 Modify git-rev-list ... [ resend to fix whitespace mangle ]

Quoted 8 lines · Junio C Hamano

I only fast-forwarded over maths on your website about the epoch ordering, but what the patch tries to do sounds right to me.

One nitpick request I have is to name its test t6000 series, to match the naming convention Pasky came up with?

First digit tells the family:

Quoted 8 lines

0 - the absolute basics and global stuff
1 - the basic commands concerning database 2 - the basic commands concerning the working tree 3 - the other basic commands (e.g. ls-files) 4 - the diff commands
5 - the pull and exporting commands
6 - the revision tree commands (even e.g. merge-base)

Sure. I'll modify the patch and repost.

Quoted 2 lines

Also I wonder what the performance implication of this patch is.

It actually works quite well. I took some care to make sure the algorithm didn't have to scan the entire tree if you only want part of it and is roughly linear in the number of edges it actually processes. It does this by borrowing the original heuristic of a latest date first scan, and also by accumulating "work" to do prior to propagating it through the network. This means that most nodes are only visited (a small-multiple of) once.

One thing to be aware of is that it does have to scan to epoch boundaries which, in the Linux kernel, are spaced an average of 100 commits apart. The first time you run it on a cold-cache, the output pauses for a while after the first few commits. But run it again when the cache is warm and the performance is, IMO, quite ok.

Here are the cold-cache stats on the Linux-2.6 tree which has 1300 commits and quite a lot of merges and forks

$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err
real    0m32.283s
user    0m0.135s
sys     0m0.141s

And the warm cache stats:

$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err
real    0m0.181s
user    0m0.119s
sys     0m0.040s

Compared with the standard algorithm:

$ time git-rev-list HEAD > out 2>err
real    0m0.112s
user    0m0.065s
sys     0m0.032s

So, it is perhaps 50-100% slower on a warm-cache than the standard algorithm.

jon.
--
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/