commit-slab: avoid large realloc

Instead of using a single "slab" and keep reallocating it as we find
that we need to deal with commits with larger values of commit->index,
make a "slab" an array of many "slab_piece"s. Each access may need
two levels of indirections, but we only need to reallocate the first
level array of pointers when we have to grow the table this way.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/commit.c b/commit.c
index 9365e3b34aba1c0d4f1ffe9e5e5eebcce886a42e..4c05b3966a7e6521b09057d5e7ae040d6606c795 100644 (file)
--- a/commit.c
+++ b/commit.c
@@ -501,34 +501,56 @@ struct commit *pop_commit(struct commit_list **stack)
        return item;
 }
 
+struct commit_slab_piece {
+       int buf;
+};
+
 struct commit_slab {
-       int *buf;
-       int alloc;
+       int piece_size;
+       int piece_count;
+       struct commit_slab_piece **piece;
 };
 
 static void slab_init(struct commit_slab *s)
 {
-       memset(s, 0, sizeof(*s));
+       /* allocate ~512kB at once, allowing for malloc overhead */
+       int size = (512*1024-32) / sizeof(struct commit_slab_piece);
+
+       s->piece_size = size;
+       s->piece_count = 0;
+       s->piece = NULL;
 }
 
 static void slab_clear(struct commit_slab *s)
 {
-       free(s->buf);
-       slab_init(s);
+       int i;
+
+       for (i = 0; i < s->piece_count; i++)
+               free(s->piece[i]);
+       s->piece_count = 0;
+       free(s->piece);
+       s->piece = NULL;
 }
 
-static inline int *slab_at(struct commit_slab *s, const struct commit *c)
+static inline struct commit_slab_piece *slab_at(struct commit_slab *s,
+                                               const struct commit *c)
 {
-       if (s->alloc <= c->index) {
-               int new_alloc = alloc_nr(s->alloc);
-               if (new_alloc <= c->index)
-                       new_alloc = c->index + 1;
-
-               s->buf = xrealloc(s->buf, new_alloc * sizeof(*s->buf));
-               memset(s->buf + s->alloc, 0, new_alloc - s->alloc);
-               s->alloc = new_alloc;
+       int nth_piece, nth_slot;
+
+       nth_piece = c->index / s->piece_size;
+       nth_slot = c->index % s->piece_size;
+
+       if (s->piece_count <= nth_piece) {
+               int i;
+
+               s->piece = xrealloc(s->piece, (nth_piece + 1) * sizeof(s->piece));
+               for (i = s->piece_count; i <= nth_piece; i++)
+                       s->piece[i] = NULL;
+               s->piece_count = nth_piece + 1;
        }
-       return s->buf + c->index;
+       if (!s->piece[nth_piece])
+               s->piece[nth_piece] = xcalloc(s->piece_size, sizeof(**s->piece));
+       return &s->piece[nth_piece][nth_slot];
 }
 
 /*
@@ -550,7 +572,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
        /* Mark them and clear the indegree */
        for (next = orig; next; next = next->next) {
                struct commit *commit = next->item;
-               *slab_at(&indegree, commit) = 1;
+               slab_at(&indegree, commit)->buf = 1;
        }
 
        /* update the indegree */
@@ -558,7 +580,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
                struct commit_list * parents = next->item->parents;
                while (parents) {
                        struct commit *parent = parents->item;
-                       int *pi = slab_at(&indegree, parent);
+                       int *pi = &slab_at(&indegree, parent)->buf;
 
                        if (*pi)
                                (*pi)++;
@@ -578,7 +600,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 (*slab_at(&indegree, commit) == 1)
+               if (slab_at(&indegree, commit)->buf == 1)
                        insert = &commit_list_insert(commit, insert)->next;
        }
 
@@ -599,7 +621,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
                commit = work_item->item;
                for (parents = commit->parents; parents ; parents = parents->next) {
                        struct commit *parent = parents->item;
-                       int *pi = slab_at(&indegree, parent);
+                       int *pi = &slab_at(&indegree, parent)->buf;
 
                        if (!*pi)
                                continue;
@@ -620,7 +642,7 @@ 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.
                 */
-               *slab_at(&indegree, commit) = 0;
+               slab_at(&indegree, commit)->buf = 0;
                *pptr = work_item;
                pptr = &work_item->next;
        }