Re: [PATCH 6/6] index-pack: make quantum of work smaller

[Jeff King]

On Wed, Oct 09, 2019 at 04:44:22PM -0700, Jonathan Tan wrote:

> Signed-off-by: Jonathan Tan 
> ---
>  builtin/index-pack.c | 267 ---
>  1 file changed, 127 insertions(+), 140 deletions(-)

I think this is a good direction to go in. I confess I didn't carefully
go over the implementation details, since you've marked this as RFC and
it sounds like you're mainly asking about direction. It looks pretty
reasonable from a high level, though.

-Peff

[PATCH 6/6] index-pack: make quantum of work smaller

[Jonathan Tan]

Signed-off-by: Jonathan Tan 
---
 builtin/index-pack.c | 267 ---
 1 file changed, 127 insertions(+), 140 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 3908cd3115..f6318037ca 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -38,15 +38,22 @@ struct base_data {
struct object_entry *obj;
int ref_first, ref_last;
int ofs_first, ofs_last;
+   int retain_data;
+   int children_remaining;
 
/* Not initialized by make_base(). */
+   struct list_head list;
void *data;
unsigned long size;
 };
 
+LIST_HEAD(work_head);
+LIST_HEAD(done_head);
+size_t base_cache_used;
+size_t base_cache_limit;
+
 struct thread_local {
pthread_t thread;
-   size_t base_cache_used;
int pack_fd;
 };
 
@@ -369,36 +376,38 @@ static void free_base_data(struct base_data *c)
 {
if (c->data) {
FREE_AND_NULL(c->data);
-   get_thread_data()->base_cache_used -= c->size;
+   base_cache_used -= c->size;
}
 }
 
-static void prune_base_data(struct base_data *youngest_child)
+static void prune_base_data(struct base_data *retain)
 {
-   struct base_data *b;
-   struct thread_local *data = get_thread_data();
-   struct base_data **ancestry = NULL;
-   int nr = 0, alloc = 0;
-   int i;
+   struct list_head *pos;
 
-   if (data->base_cache_used <= delta_base_cache_limit)
+   if (base_cache_used <= base_cache_limit)
return;
 
-   /*
-* Free all ancestors of youngest_child until we have enough space,
-* starting with the oldest. (We cannot free youngest_child itself.)
-*/
-   for (b = youngest_child->base; b != NULL; b = b->base) {
-   ALLOC_GROW(ancestry, nr + 1, alloc);
-   ancestry[nr++] = b;
+   list_for_each_prev(pos, &done_head) {
+   struct base_data *b = list_entry(pos, struct base_data, list);
+   if (b->retain_data || b == retain)
+   continue;
+   if (b->data) {
+   free_base_data(b);
+   if (base_cache_used <= base_cache_limit)
+   return;
+   }
}
-   for (i = nr - 1;
-i >= 0 && data->base_cache_used > delta_base_cache_limit;
-i--) {
-   if (ancestry[i]->data)
-   free_base_data(ancestry[i]);
+
+   list_for_each_prev(pos, &work_head) {
+   struct base_data *b = list_entry(pos, struct base_data, list);
+   if (b->retain_data || b == retain)
+   continue;
+   if (b->data) {
+   free_base_data(b);
+   if (base_cache_used <= base_cache_limit)
+   return;
+   }
}
-   free(ancestry);
 }
 
 static int is_delta_type(enum object_type type)
@@ -886,7 +895,7 @@ static void *get_base_data(struct base_data *c)
if (!delta_nr) {
c->data = get_data_from_pack(obj);
c->size = obj->size;
-   get_thread_data()->base_cache_used += c->size;
+   base_cache_used += c->size;
prune_base_data(c);
}
for (; delta_nr > 0; delta_nr--) {
@@ -902,7 +911,7 @@ static void *get_base_data(struct base_data *c)
free(raw);
if (!c->data)
bad_object(obj->idx.offset, _("failed to apply 
delta"));
-   get_thread_data()->base_cache_used += c->size;
+   base_cache_used += c->size;
prune_base_data(c);
}
free(delta);
@@ -920,6 +929,8 @@ static struct base_data *make_base(struct object_entry *obj,
&base->ref_first, &base->ref_last);
find_ofs_delta_children(obj->idx.offset,
&base->ofs_first, &base->ofs_last);
+   base->children_remaining = base->ref_last - base->ref_first +
+   base->ofs_last - base->ofs_first + 2;
return base;
 }
 
@@ -953,14 +964,8 @@ static struct base_data *resolve_delta(struct object_entry 
*delta_obj,
&delta_obj->idx.oid);
 
result = make_base(delta_obj, base);
-   if (result->ref_last == -1 && result->ofs_last == -1) {
-   free(result_data);
-   } else {
-   result->data = result_data;
-   result->size = result_size;
-   get_thread_data()->base_cache_used += result->size;
-   prune_base_data(result);
-   }
+   result->data = result_data;
+   result->size = result_size;
 
counter_lock();
nr_resolved_deltas++;
@@ -969,84 +974,6 @@ static struct base_data *re