[PATCH 1/3] commit: shrink "indegree" field

[Junio C Hamano <gitster@pobox.com>]

The "indegree" field in the commit object is used only while a
commit list is sorted using the topo_order sorting.  The idea is to
initially store the number of direct parents and the commit itself
there, and start emitting the commits with indegree 1 (i.e. leaves
that do not have any commit as the parent), and every time a commit
is emitted, decrement its own count (to drop it to 0 to clear the
field) and the count in its parents (so eventually a commit whose
children are all emitted will see its count dropped to 1, becoming
eligible to be emitted) by one.

We used to allocate a full integer for this, but in real life, a
commit with thousands of direct children are rare. Shrink it to an
unsigned char to represent a commit with 254 children or less
without any extra overhead, and spilling the overflow to a separate
decoration hash.

This does not save any bytes from the commit object structure due to
alignment, but would give us 3 or 7 bytes to store other information.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 commit.c | 46 +++++++++++++++++++++++++++++++++++++++-------
 commit.h |  2 +-
 2 files changed, 40 insertions(+), 8 deletions(-)

diff --git a/commit.c b/commit.c
index 516a4ff..9d7e81b 100644
--- a/commit.c
+++ b/commit.c
@@ -506,6 +506,30 @@ struct commit *pop_commit(struct commit_list **stack)
 	return item;
 }
 
+#define QUICK_INDEGREE_LIMIT 255
+
+static inline void set_indegree(struct decoration *indegree,
+				struct commit *commit, intptr_t value)
+{
+	if (QUICK_INDEGREE_LIMIT <= value) {
+		commit->indegree = QUICK_INDEGREE_LIMIT;
+		add_decoration(indegree, &commit->object, (void *)value);
+	} else {
+		commit->indegree = value;
+	}
+}
+
+static inline intptr_t get_indegree(struct decoration *indegree,
+				    struct commit *commit)
+{
+	if (commit->indegree < QUICK_INDEGREE_LIMIT)
+		return commit->indegree;
+	else {
+		void *count = lookup_decoration(indegree, &commit->object);
+		return (int) count;
+	}
+}
+
 /*
  * Performs an in-place topological sort on the list supplied.
  */
@@ -514,15 +538,18 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	struct commit_list *next, *orig = *list;
 	struct commit_list *work, **insert;
 	struct commit_list **pptr;
+	struct decoration id_overflow;
+	intptr_t count;
 
 	if (!orig)
 		return;
 	*list = NULL;
 
 	/* Mark them and clear the indegree */
+	memset(&id_overflow, 0, sizeof(id_overflow));
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
-		commit->indegree = 1;
+		set_indegree(&id_overflow, commit, 1);
 	}
 
 	/* update the indegree */
@@ -531,8 +558,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		while (parents) {
 			struct commit *parent = parents->item;
 
-			if (parent->indegree)
-				parent->indegree++;
+			count = get_indegree(&id_overflow, parent);
+			if (count)
+				set_indegree(&id_overflow, parent, count + 1);
 			parents = parents->next;
 		}
 	}
@@ -549,7 +577,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
 
-		if (commit->indegree == 1)
+		if (get_indegree(&id_overflow, commit) == 1)
 			insert = &commit_list_insert(commit, insert)->next;
 	}
 
@@ -571,7 +599,8 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		for (parents = commit->parents; parents ; parents = parents->next) {
 			struct commit *parent = parents->item;
 
-			if (!parent->indegree)
+			count = get_indegree(&id_overflow, parent);
+			if (!count)
 				continue;
 
 			/*
@@ -579,7 +608,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 			 * when all their children have been emitted thereby
 			 * guaranteeing topological order.
 			 */
-			if (--parent->indegree == 1) {
+			count--;
+			set_indegree(&id_overflow, parent, count);
+			if (count == 1) {
 				if (!lifo)
 					commit_list_insert_by_date(parent, &work);
 				else
@@ -590,10 +621,11 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		 * work_item is a commit all of whose children
 		 * have already been emitted. we can emit it now.
 		 */
-		commit->indegree = 0;
+		set_indegree(&id_overflow, commit, 0);
 		*pptr = work_item;
 		pptr = &work_item->next;
 	}
+	clear_decoration(&id_overflow, NULL);
 }
 
 /* merge-base stuff */
diff --git a/commit.h b/commit.h
index 87b4b6c..771eeae 100644
--- a/commit.h
+++ b/commit.h
@@ -15,7 +15,7 @@ struct commit_list {
 struct commit {
 	struct object object;
 	void *util;
-	unsigned int indegree;
+	unsigned int indegree:8; /* see QUICK_INDEGREE_LIMIT in commit.c */
 	unsigned long date;
 	struct commit_list *parents;
 	struct tree *tree;
-- 
1.8.2.1-450-gd047976