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 <gits...@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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
