2.18.0 Regression: packing performance and effectiveness

I had a user report some poor behavior of 'git gc --aggressive' on a certain repo (which I sadly cannot share). Turns out that on this repo, this operation takes about 60% longer and produces a pack roughly twice the expected size.

Quoted 5 lines · Elijah Newren

I had a user report some poor behavior of 'git gc --aggressive' on a certain repo (which I sadly cannot share). Turns out that on this repo, this operation takes about 60% longer and produces a pack roughly twice the expected size.

The intention was to make life better for weaker machines but definitely should not slow down beefier ones, so yes this is definitely a regression.

Is it possible to share "verify-pack -v <pack file>" output of the pack produced by 2.17.0 and 2.18.0? The only sensitive info there is sha-1, which you can replace with just "SHA-1" if you want. I'm more interested in delta sizes and distribution.

Quoted 5 lines · Elijah Newren

I had a user report some poor behavior of 'git gc --aggressive' on a certain repo (which I sadly cannot share). Turns out that on this repo, this operation takes about 60% longer and produces a pack roughly twice the expected size.

The intention was to make life better for weaker machines but definitely should not slow down beefier ones, so yes this is definitely a regression.

Is it possible to share "verify-pack -v <pack file>" output of the pack produced by 2.17.0 and 2.18.0? The only sensitive info there is sha-1, which you can replace with just "SHA-1" if you want. I'm more interested in delta sizes and distribution.

Quoted 10 lines · Duy Nguyen

Quoted 5 lines · Elijah Newren

I had a user report some poor behavior of 'git gc --aggressive' on a certain repo (which I sadly cannot share). Turns out that on this repo, this operation takes about 60% longer and produces a pack roughly twice the expected size.

The intention was to make life better for weaker machines but definitely should not slow down beefier ones, so yes this is definitely a regression.

Not sure if it matters, but the original discovery was on a laptop. Probably 4 cores and 16 GB RAM. I duplicated on my workstation (8 cores, 24 GB RAM). However, since the original patch was memory related and I noticed the repacking using all available memory, I repeated the testcases while measuring memory but did it on a machine that wouldn't be memory limited.

Quoted 4 lines

Is it possible to share "verify-pack -v <pack file>" output of the pack produced by 2.17.0 and 2.18.0? The only sensitive info there is sha-1, which you can replace with just "SHA-1" if you want. I'm more interested in delta sizes and distribution.

For the deltas, assuming the size-in-pack field (4th column) is the relevant one

Number of objects in repo (lines of verify-pack output): 4460755 Number of deltas: 2831384
Number of deltas greater than 1MB: 72
Min: 14
Median: 47
Mean: 586
99.999 percentile: 11366280.6 (10.8 MB)
Max: 141664210 (135.1 MB)

If the size field (3rd column) is the relevant one, then the numbers change slightly to:

Number of deltas greater than 1MB: 101
Min: 4
Median: 33
Mean: 660
99.999 percentile: 12245551.7 (11.7 MB)

Max: 144658342 (138.0 MB)

I checked out the blob which had the biggest delta, as well as the blob it was a delta against. One was a 280 MB file, the other a 278 MB file.

I had a user report some poor behavior of 'git gc --aggressive' on a certain repo (which I sadly cannot share). Turns out that on this repo, this operation takes about 60% longer and produces a pack roughly twice the expected size.

Naturally, bisecting takes a while but it points to this commit:

To put some numbers behind this, I got on a very beefy box (40 cores, 160GB RAM) and ran some comparisons:

Version  Pack (MB)  MaxRSS(kB)  Time (s)
-------  ---------  ----------  --------
 2.17.0     5498     43513628    2494.85
 2.18.0    10531     40449596    4168.94
 fix-v1     5509     42509784    2480.74
 fiv-v2     5509     41644104    2468.25

where fix-v1 and fix-v2 are different patches on top of git-2.18.0 that I'll follow up to this email with. The patches are just meant as discussion starters. I'll add signoffs and proper commit messages if folks actually want those fixes, but I suspect they're just starting points for discussion.

Quoted 6 lines · Elijah Newren

I had a user report some poor behavior of 'git gc --aggressive' on a certain repo (which I sadly cannot share). Turns out that on this repo, this operation takes about 60% longer and produces a pack roughly twice the expected size.

Naturally, bisecting takes a while but it points to this commit:

Thanks for finding and bisecting.

Quoted 10 lines

To put some numbers behind this, I got on a very beefy box (40 cores, 160GB RAM) and ran some comparisons:

Version  Pack (MB)  MaxRSS(kB)  Time (s)
-------  ---------  ----------  --------
 2.17.0     5498     43513628    2494.85
 2.18.0    10531     40449596    4168.94
 fix-v1     5509     42509784    2480.74
 fiv-v2     5509     41644104    2468.25

Quoted 5 lines

where fix-v1 and fix-v2 are different patches on top of git-2.18.0 that I'll follow up to this email with. The patches are just meant as discussion starters. I'll add signoffs and proper commit messages if folks actually want those fixes, but I suspect they're just starting points for discussion.

Hmm. So what's the mechanism causing the issue here? Looking at the patch from 0aca34e826 (pack-objects: shrink delta_size field in struct object_entry, 2018-04-14), it should _mostly_ be about how we store data in memory, and should not impact the deltas we find.

But reading the patch and looking at your v2, it seems clear that this hunk is the culprit:

(quoted diff) +4 -0

@@ -2006,10 +2008,14 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
        delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
        if (!delta_buf)
                return 0;
+       if (delta_size >= (1U << OE_DELTA_SIZE_BITS)) {
+               free(delta_buf);
+               return 0;
+       }
 

So we're punting on large deltas, and presumably your test case has some files that are large but delta well (and we miss those opportunities, which wastes further time in the delta search and creates a lousy pack).

I'm not sure why we need this hunk, though. Eventually we'd hit SET_DELTA_SIZE(), and I thought the point is that it should handle large sizes with some kind of fallback (the commit message even mentions an "overflow bit"). Looking at oe_set_delta_size(), though, I don't think the fallback would really work here; we'd hid the BUG().

I thought 2M was generous but I was obviously wrong. I'd like to see the biggest delta size in this pack and whether it's still reasonable to increase OE_DELTA_SIZE_BITS. But if it's very close to 4GB limit then we could just store 64-bit delta size in a separate array.

Quoted 4 lines · Duy Nguyen

I thought 2M was generous but I was obviously wrong. I'd like to see the biggest delta size in this pack and whether it's still reasonable to increase OE_DELTA_SIZE_BITS. But if it's very close to 4GB limit then we could just store 64-bit delta size in a separate array.

I realize now that these two options don't have to be mutually exclusive and I should provide a good fallback in terms of performance anyway.

So Elijah, could you try this patch and see if performance and pack size go back to 1.7.0? I can write proper commit message and test support later if it proves a good improvement.

-- 8< --

builtin/pack-objects.c +0 -4

index ebc8cefb53..7f3546057d 100644
@@ -2023,10 +2023,6 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
        delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
        if (!delta_buf)
                return 0;
-       if (delta_size >= (1U << OE_DELTA_SIZE_BITS)) {
-               free(delta_buf);
-               return 0;
-       }
 
        if (DELTA(trg_entry)) {
                /* Prefer only shallower same-sized deltas. */

pack-objects.c +16 -0

index 92708522e7..191ed45faf 100644
@@ -160,6 +160,8 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,
 
                if (!pdata->in_pack_by_idx)
                        REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);
+               if (pdata->delta_size)
+                       REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc);
        }
 
        new_entry = pdata->objects + pdata->nr_objects++;

@@ -177,3 +179,17 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,
 
        return new_entry;
 }
+
+void oe_prepare_delta_size_array(struct packing_data *pack)
+{
+       int i;
+
+       /*
+        * nr_alloc, not nr_objects to align with realloc() strategy in
+        * packlist_alloc()
+        */
+       ALLOC_ARRAY(pack->delta_size, pack->nr_alloc);
+
+       for (i = 0; i < pack->nr_objects; i++)
+               pack->delta_size[i] = pack->objects[i].delta_size_;
+}

pack-objects.h +15 -10

index edf74dabdd..978500e474 100644
@@ -14,7 +14,7 @@
  * above this limit. Don't lower it too much.
  */
 #define OE_SIZE_BITS           31
-#define OE_DELTA_SIZE_BITS     20
+#define OE_DELTA_SIZE_BITS     21
 
 /*
  * State flags for depth-first search used for analyzing delta cycles.

@@ -93,7 +93,6 @@ struct object_entry {
                                     * uses the same base as me
                                     */
        unsigned delta_size_:OE_DELTA_SIZE_BITS; /* delta data size (uncompressed) */
-       unsigned delta_size_valid:1;
        unsigned in_pack_idx:OE_IN_PACK_BITS;   /* already in pack */
        unsigned z_delta_size:OE_Z_DELTA_BITS;
        unsigned type_valid:1;

@@ -130,6 +129,7 @@ struct packing_data {
        uint32_t index_size;
 
        unsigned int *in_pack_pos;
+       unsigned long *delta_size;
 
        /*
         * Only one of these can be non-NULL and they have different

@@ -330,20 +330,27 @@ static inline void oe_set_size(struct packing_data *pack,
 static inline unsigned long oe_delta_size(struct packing_data *pack,
                                          const struct object_entry *e)
 {
-       if (e->delta_size_valid)
+       if (!pack->delta_size)
                return e->delta_size_;
-       return oe_size(pack, e);
+       return pack->delta_size[e - pack->objects];
 }
 
+void oe_prepare_delta_size_array(struct packing_data *pack);
 static inline void oe_set_delta_size(struct packing_data *pack,
                                     struct object_entry *e,
                                     unsigned long size)
 {
        e->delta_size_ = size;
-       e->delta_size_valid = e->delta_size_ == size;
-       if (!e->delta_size_valid && size != oe_size(pack, e))
-               BUG("this can only happen in check_object() "
-                   "where delta size is the same as entry size");
+       if (!pack->delta_size && e->delta_size_ == size)
+               return;
+       /*
+        * We have had at least one delta size exceeding OE_DELTA_SIZE_BITS
+        * limit. delta_size_ will not be used anymore. All delta sizes are now
+        * from the delta_size[] array.
+        */
+       if (!pack->delta_size)
+               oe_prepare_delta_size_array(pack);
+       pack->delta_size[e - pack->objects] = size;
 }
 
 #endif
-- 8< --
 
 
--

Duy

Thanks for the quick turnaround. Unfortunately, I have some bad news. With this patch, I get the following:

$ /usr/bin/time -f 'MaxRSS:%M Time:%e' git gc --aggressive
Enumerating objects: 4460703, done.
Counting objects: 100% (4460703/4460703), done.
Delta compression using up to 40 threads.
Compressing objects: 100% (3807140/3807140), done.
Writing objects: 100% (4460703/4460703), done.
Total 4460703 (delta 2831383), reused 1587071 (delta 0)
error: failed to unpack compressed delta at offset 183854150 from
.git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack
fatal: packed object 20ce811e53dabbb8ef9368c108cbbdfa65639c03 (stored
in .git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack)
is corrupt
error: failed to run prune
MaxRSS:40025196 Time:2531.52

Quoted 17 lines · Elijah Newren

Thanks for the quick turnaround. Unfortunately, I have some bad news. With this patch, I get the following:

$ /usr/bin/time -f 'MaxRSS:%M Time:%e' git gc --aggressive
Enumerating objects: 4460703, done.
Counting objects: 100% (4460703/4460703), done.
Delta compression using up to 40 threads.
Compressing objects: 100% (3807140/3807140), done.
Writing objects: 100% (4460703/4460703), done.
Total 4460703 (delta 2831383), reused 1587071 (delta 0)
error: failed to unpack compressed delta at offset 183854150 from
.git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack
fatal: packed object 20ce811e53dabbb8ef9368c108cbbdfa65639c03 (stored
in .git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack)
is corrupt
error: failed to run prune
MaxRSS:40025196 Time:2531.52

Looking at that output, my _guess_ is that we somehow end up with a bogus delta_size value and write out a truncated entry. But I couldn't reproduce the issue with smaller test cases.

Quoted 20 lines · Jeff King

Quoted 17 lines · Elijah Newren

Thanks for the quick turnaround. Unfortunately, I have some bad news. With this patch, I get the following:

$ /usr/bin/time -f 'MaxRSS:%M Time:%e' git gc --aggressive
Enumerating objects: 4460703, done.
Counting objects: 100% (4460703/4460703), done.
Delta compression using up to 40 threads.
Compressing objects: 100% (3807140/3807140), done.
Writing objects: 100% (4460703/4460703), done.
Total 4460703 (delta 2831383), reused 1587071 (delta 0)
error: failed to unpack compressed delta at offset 183854150 from
.git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack
fatal: packed object 20ce811e53dabbb8ef9368c108cbbdfa65639c03 (stored
in .git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack)
is corrupt
error: failed to run prune
MaxRSS:40025196 Time:2531.52

Quoted 3 lines

Looking at that output, my _guess_ is that we somehow end up with a bogus delta_size value and write out a truncated entry. But I couldn't reproduce the issue with smaller test cases.

Could it be a race condition?

Quoted 5 lines

Quoted 3 lines

Looking at that output, my _guess_ is that we somehow end up with a bogus delta_size value and write out a truncated entry. But I couldn't reproduce the issue with smaller test cases.

Could it be a race condition?

I'm convinced my code is racy (between two writes). I created a broken pack once with 32 threads. Elijah please try again with this new patch. It should fix this (I only tried repack a few times so far but will continue)

The race is this

1. Thread one sees a large delta size and NULL delta_size[] array, allocates the new array and in the middle of copying old delta sizes over.

2. Thread two wants to write a new (large) delta size. It sees that delta_size[] is already allocated, it writes the correct size there (and truncated one in object_entry->delta_size_)

3. Back to thread one, it now copies the truncated value in delta_size_ from step 2 to delta_size[] array, overwriting the good value that thread two wrote.

There is also a potential read/write race where a read from pack_size[] happens when the array is not ready. But I don't think it can happen with current try_delta() code. I protect it anyway to be safe.

Quoted 21 lines · Duy Nguyen

Quoted 20 lines · Jeff King

Quoted 17 lines · Elijah Newren

Thanks for the quick turnaround. Unfortunately, I have some bad news. With this patch, I get the following:

$ /usr/bin/time -f 'MaxRSS:%M Time:%e' git gc --aggressive
Enumerating objects: 4460703, done.
Counting objects: 100% (4460703/4460703), done.
Delta compression using up to 40 threads.
Compressing objects: 100% (3807140/3807140), done.
Writing objects: 100% (4460703/4460703), done.
Total 4460703 (delta 2831383), reused 1587071 (delta 0)
error: failed to unpack compressed delta at offset 183854150 from
.git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack
fatal: packed object 20ce811e53dabbb8ef9368c108cbbdfa65639c03 (stored
in .git/objects/pack/pack-30d4f0b0e5a03dc91a658a0586f4e74cdf4a94d6.pack)
is corrupt
error: failed to run prune
MaxRSS:40025196 Time:2531.52

Quoted 5 lines

Quoted 3 lines

Looking at that output, my _guess_ is that we somehow end up with a bogus delta_size value and write out a truncated entry. But I couldn't reproduce the issue with smaller test cases.

Could it be a race condition?

I'm convinced my code is racy (between two writes). I created a broken pack once with 32 threads. Elijah please try again with this new patch. It should fix this (I only tried repack a few times so far but will continue)

The race is this

1. Thread one sees a large delta size and NULL delta_size[] array, allocates the new array and in the middle of copying old delta sizes over.

2. Thread two wants to write a new (large) delta size. It sees that delta_size[] is already allocated, it writes the correct size there (and truncated one in object_entry->delta_size_)

3. Back to thread one, it now copies the truncated value in delta_size_ from step 2 to delta_size[] array, overwriting the good value that thread two wrote.

There is also a potential read/write race where a read from pack_size[] happens when the array is not ready. But I don't think it can happen with current try_delta() code. I protect it anyway to be safe.

Looking at the output from Peff's instrumentation elsewhere in this thread, I see a lot of lines like
mismatched get: 32889efd307c7be376da9e3d45a78305f14ba73a = (, 28)
Does that mean it was reading the array when it wasn't ready?

However, it's interesting to also look at the effect on packing linux.git (on the same beefy hardware):

Version  Pack (MB)  MaxRSS(kB)  Time (s)
-------  ---------  ----------  --------
 2.17.0     1279     11382932      632.24
 2.18.0     1279     10817568      621.97
 fiv-v4     1279     11484168     1193.67

While the pack size is nice and small, the original memory savings added in 2.18.0 are gone and the performance is much worse. :-(

Quoted 4 lines · Elijah Newren

Looking at the output from Peff's instrumentation elsewhere in this thread, I see a lot of lines like
mismatched get: 32889efd307c7be376da9e3d45a78305f14ba73a = (, 28)
Does that mean it was reading the array when it wasn't ready?

Yes, it looks like we saw a "get" without a "set". Though this could also be due to threading. The tracing isn't atomic with respect to the actual get/set operation, so it's possible that the ordering of the trace output does not match the ordering of the actual operations.

Quoted 9 lines

However, it's interesting to also look at the effect on packing linux.git (on the same beefy hardware):

Version  Pack (MB)  MaxRSS(kB)  Time (s)
-------  ---------  ----------  --------
 2.17.0     1279     11382932      632.24
 2.18.0     1279     10817568      621.97
 fiv-v4     1279     11484168     1193.67

Quoted 2 lines

While the pack size is nice and small, the original memory savings added in 2.18.0 are gone and the performance is much worse. :-(

Interesting. I can't reproduce here. The fix-v4 case is only slightly slower than 2.18.0. Can you double check that your compiler flags, etc, were the same? Many times I've accidentally compared -O0 to -O0. :)

You might also try the patch below (on top of fix-v4), which moves the

locking to its own dedicated mutex. That should reduce lock contention,

and it fixes the remaining realloc where I think we're still racy. On my

repack of linux.git, it dropped the runtime from 6m3s to 5m41s, almost entirely in system CPU.

Quoted 4 lines · Elijah Newren

Looking at the output from Peff's instrumentation elsewhere in this thread, I see a lot of lines like
mismatched get: 32889efd307c7be376da9e3d45a78305f14ba73a = (, 28)
Does that mean it was reading the array when it wasn't ready?

Yes, it looks like we saw a "get" without a "set". Though this could also be due to threading. The tracing isn't atomic with respect to the actual get/set operation, so it's possible that the ordering of the trace output does not match the ordering of the actual operations.

Quoted 9 lines

However, it's interesting to also look at the effect on packing linux.git (on the same beefy hardware):

Version  Pack (MB)  MaxRSS(kB)  Time (s)
-------  ---------  ----------  --------
 2.17.0     1279     11382932      632.24
 2.18.0     1279     10817568      621.97
 fiv-v4     1279     11484168     1193.67

Quoted 2 lines

While the pack size is nice and small, the original memory savings added in 2.18.0 are gone and the performance is much worse. :-(

Interesting. I can't reproduce here. The fix-v4 case is only slightly slower than 2.18.0. Can you double check that your compiler flags, etc, were the same? Many times I've accidentally compared -O0 to -O0. :)

You might also try the patch below (on top of fix-v4), which moves the locking to its own dedicated mutex. That should reduce lock contention, and it fixes the remaining realloc where I think we're still racy. On my repack of linux.git, it dropped the runtime from 6m3s to 5m41s, almost entirely in system CPU.

I didn't measure my max rss. However, I'd caution slightly against drawing too much conclusion from it, for two reasons:

1. RSS includes mmap'd packfiles, which is subject to whatever pages the OS feels like keeping in RAM. So using more heap can sometimes go unnoticed in that count, since you're just trading heap pages for mmap pages. Although that implies some memory pressure, and it sounds like your machine is sufficiently beefy to avoid that.

2. Peak heap is going to depend on the threading. You have one thread per CPU working on a window of objects, each of which will be in memory at once. So I'd expect a fair bit of fluctuation in the peak just depending on how the threads line up with each other (some of it random, and some of it maybe impacted by what the code does, but in a way that just happens to fall out for this specific workload).

Which isn't to say measuring it is useless. The trends may override the noise from those two things. I've just run into problems in the past trying to get consistent measurements.

Here's the lock patch.

builtin/pack-objects.c +5 -5

index ba14a1bfbc..b76ce04cb9 100644
@@ -1926,12 +1926,12 @@ static unsigned long oe_delta_size(struct packing_data *pack,
 {
        unsigned long size;
 
-       read_lock();     /* to protect access to pack->delta_size[] */
+       pack_delta_lock(pack);
        if (pack->delta_size)
                size = pack->delta_size[e - pack->objects];
        else
                size = e->delta_size_;
-       read_unlock();
+       pack_delta_unlock(pack);
        return size;
 }
 

@@ -1939,10 +1939,10 @@ static void oe_set_delta_size(struct packing_data *pack,
                              struct object_entry *e,
                              unsigned long size)
 {
-       read_lock();     /* to protect access to pack->delta_size[] */
+       pack_delta_lock(pack);
        if (!pack->delta_size && size < pack->oe_delta_size_limit) {
                e->delta_size_ = size;
-               read_unlock();
+               pack_delta_unlock(pack);
                return;
        }
        /*

@@ -1963,7 +1963,7 @@ static void oe_set_delta_size(struct packing_data *pack,
                        pack->delta_size[i] = pack->objects[i].delta_size_;
        }
        pack->delta_size[e - pack->objects] = size;
-       read_unlock();
+       pack_delta_unlock(pack);
 }
 
 static int try_delta(struct unpacked *trg, struct unpacked *src,

pack-objects.c +6 -0

index e3c32bbfc2..8d9c2dfb82 100644
@@ -148,6 +148,10 @@ void prepare_packing_data(struct packing_data *pdata)
                                             1U << OE_SIZE_BITS);
        pdata->oe_delta_size_limit = git_env_ulong("GIT_TEST_OE_DELTA_SIZE",
                                                   1U << OE_DELTA_SIZE_BITS);
+
+#ifndef NO_PTHREADS
+       pthread_mutex_init(&pdata->delta_lock, NULL);
+#endif
 }
 
 struct object_entry *packlist_alloc(struct packing_data *pdata,

@@ -162,8 +166,10 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,
 
                if (!pdata->in_pack_by_idx)
                        REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);
+               pack_delta_lock(pdata);
                if (pdata->delta_size)
                        REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc);
+               pack_delta_unlock(pdata);
        }
 
        new_entry = pdata->objects + pdata->nr_objects++;

pack-objects.h +11 -0

index 730990c5d2..29b6006949 100644
@@ -130,6 +130,9 @@ struct packing_data {
 
        unsigned int *in_pack_pos;
        uint32_t *delta_size;
+#ifndef NO_PTHREADS
+       pthread_mutex_t delta_lock;
+#endif
 
        /*
         * Only one of these can be non-NULL and they have different

@@ -144,6 +147,14 @@ struct packing_data {
        uintmax_t oe_delta_size_limit;
 };
 
+#ifndef NO_PTHREADS
+#define pack_delta_lock(pdata) pthread_mutex_lock(&pdata->delta_lock)
+#define pack_delta_unlock(pdata) pthread_mutex_unlock(&pdata->delta_lock)
+#else
+#define pack_delta_lock(pdata)
+#define pack_delta_unlock(pdata)
+#endif
+
 void prepare_packing_data(struct packing_data *pdata);
 struct object_entry *packlist_alloc(struct packing_data *pdata,
                                    const unsigned char *sha1,

Quoted 4 lines · Duy Nguyen

I thought 2M was generous but I was obviously wrong. I'd like to see the biggest delta size in this pack and whether it's still reasonable to increase OE_DELTA_SIZE_BITS. But if it's very close to 4GB limit then we could just store 64-bit delta size in a separate array.

I realize now that these two options don't have to be mutually exclusive and I should provide a good fallback in terms of performance anyway.

pack-objects.h +4 -6

@@ -330,20 +330,27 @@ static inline void oe_set_size(struct packing_data *pack,
 static inline unsigned long oe_delta_size(struct packing_data *pack,
 					  const struct object_entry *e)
 {
-	if (e->delta_size_valid)
+	if (!pack->delta_size)
 		return e->delta_size_;
-	return oe_size(pack, e);
+	return pack->delta_size[e - pack->objects];
 }
 
+void oe_prepare_delta_size_array(struct packing_data *pack);
 static inline void oe_set_delta_size(struct packing_data *pack,
 				     struct object_entry *e,
 				     unsigned long size)
 {
 	e->delta_size_ = size;
-	e->delta_size_valid = e->delta_size_ == size;
-	if (!e->delta_size_valid && size != oe_size(pack, e))
-		BUG("this can only happen in check_object() "
-		    "where delta size is the same as entry size");
+	if (!pack->delta_size && e->delta_size_ == size)

Imagine that you create a delta and set its size (which happens to fit in the entry) and then create another whose size does not fit in the entry. How does oe_delta_size() know not to look at pack->delta_size[] and instead look at e->delta_size_ when it wants to know the delta for the first one? IOW, shouldn't there be a "backfill" procedure when oe_set_delta_size() notices that we now switch to pack->delta_size[] array?

Let's start with some background about oe_delta_size() and oe_set_delta_size(). If you already know, skip the next paragraph.

These two are added in 0aca34e826 (pack-objects: shrink delta_size field in struct object_entry - 2018-04-14) to help reduce 'struct object_entry' size. The delta size field in this struct is reduced to only contain max 2MB. So if any new delta is produced and larger than 2MB, it's dropped because we can't really save such a large size anywhere. Fallback is provided in case existingpackfiles already have large deltas, then we can retrieve it from the pack.

[...more commit message...]

With this, we do not have to drop deltas in try_delta() anymore. Of course the downside is we use slightly more memory, even compared to 2.17.0. But since this is considered an uncommon case, a bit more memory consumption should not be a problem.

A note about thread synchronization. Since this code can be run in parallel during delta searching phase, we need a mutex. The realloc part in packlist_alloc() is not protected because it only happens during the object counting phase, which is always single-threaded.

The locking in oe_delta_size() could also be dropped if we make sure the pack->delta_size pointer assignment in oe_set_delta_size() is atomic. But let's keep the lock for now to be on the safe side. Lock contention should not be that high for this lock.

[1] With a small tweak. 2.17.0 on 64-bit linux can hold 2^64 byte deltas, which is absolutely insane. But windows builds, even 64-bit version, only hold 2^32. So reducing it to 2^32 should be quite safe.

---
I'm optimistic that the slowness on linux repo is lock contention (because if it's not then I have no clue what is). So let's start doing proper patches.

If we want a quick fix for 2.18.1. I suggest bumping up OE_DELTA_SIZE_BITS like Elijah did in his second option. I don't think it's safe to fast track this patch.

pack-objects.h +0 -3

@@ -330,20 +353,37 @@ static inline void oe_set_size(struct packing_data *pack,
 static inline unsigned long oe_delta_size(struct packing_data *pack,
 					  const struct object_entry *e)
 {
-	if (e->delta_size_valid)
-		return e->delta_size_;
-	return oe_size(pack, e);

[...]

Quoted 10 lines · Nguyễn Thái Ngọc Duy

Let's start with some background about oe_delta_size() and oe_set_delta_size(). If you already know, skip the next paragraph.

These two are added in 0aca34e826 (pack-objects: shrink delta_size field in struct object_entry - 2018-04-14) to help reduce 'struct object_entry' size. The delta size field in this struct is reduced to only contain max 2MB. So if any new delta is produced and larger than 2MB, it's dropped because we can't really save such a large size anywhere. Fallback is provided in case existingpackfiles already have large deltas, then we can retrieve it from the pack.

Minor nit, but isn't this 1MB (it was 2MB after one of your patches, but I think v2.18.0 has 20 bits)?

Quoted 4 lines

With this, we do not have to drop deltas in try_delta() anymore. Of course the downside is we use slightly more memory, even compared to 2.17.0. But since this is considered an uncommon case, a bit more memory consumption should not be a problem.

I wondered how common this might be. The easiest way to see the largest delta sizes is:

  git cat-file --batch-all-objects \
               --batch-check='%(objectsize:disk) %(deltabase)' |
  grep -v 0000000000000000000000000000000000000000 |
  sort -rn | head

The biggest one in the kernel is ~300k. Which is about what I'd expect for a normal source code repo. Even some private repos I have with a lot of binary artifacts top out at about 3MB. So the new 32MB is probably

Quoted 4 lines

[1] With a small tweak. 2.17.0 on 64-bit linux can hold 2^64 byte deltas, which is absolutely insane. But windows builds, even 64-bit version, only hold 2^32. So reducing it to 2^32 should be quite safe.

I'm not sure I completely agree with this. While 4GB deltas should be pretty rare, the nice thing about 64-bit is that you never have to even think about whether the variable is large enough. I think the 2^32 limitations on Windows are something we should be fixing in the long term (though there it is even worse because it is not just deltas, but entire objects).

builtin/pack-objects.c static void init_threaded_search(void) · line 2280

Quoted 8 lines

builtin/pack-objects.c +2 -0

@@ -2278,6 +2274,8 @@ static void init_threaded_search(void)
      pthread_mutex_init(&cache_mutex, NULL);
      pthread_mutex_init(&progress_mutex, NULL);
      pthread_cond_init(&progress_cond, NULL);
+     pthread_mutex_init(&to_pack.lock, NULL);
+     to_pack.lock_initialized = 1;
      old_try_to_free_routine = set_try_to_free_routine(try_to_free_from_threads);
 }

This is new in this iteration. I guess this is to cover the case where we are built with pthread support, but --threads=1?

Given that we no longer have to touch this lock during the realloc, is it worth actually putting it into to_pack? Instead, we could keep it local to pack-objects, alongside all the other locks (and use the lock_mutex() helper which handles the single-thread case).

Your original patch had to copy the oe_* helpers into the file to handle that. But I think we're essentially just locking the whole functions:

Quoted 6 lines

I'm not sure I completely agree with this. While 4GB deltas should be pretty rare, the nice thing about 64-bit is that you never have to even think about whether the variable is large enough. I think the 2^32 limitations on Windows are something we should be fixing in the long term (though there it is even worse because it is not just deltas, but entire objects).

I guess that means we stick to uint64_t then? It does increase more memory on 32-bit architecture (and probably processing cost as well because 64-bit uses up 2 registers).

Quoted 2 lines

This is new in this iteration. I guess this is to cover the case where we are built with pthread support, but --threads=1?

If you mean the "lock_initialized" variable, not really. the other _lock() macros in builtin/ call pthread_mutex_lock() unconditionally, which is fine. But I feel a bit uncomfortable doing the same in pack-objects.h which technically is library code (but yes practically is a long arm of builtin/pack-objects.c), so lock_initialized is there to make sure we don't touch uninitialized locks if somebody forgets to init them first.

Quoted 2 lines

Your original patch had to copy the oe_* helpers into the file to handle that. But I think we're essentially just locking the whole functions:

I'll try to avoid this lock when deltas are small and see if it helps the linux.git case on Elijah's machine. So we may end up locking just a part of these functions.

Let's start with some background about oe_delta_size() and oe_set_delta_size(). If you already know, skip the next paragraph.

These two are added in 0aca34e826 (pack-objects: shrink delta_size field in struct object_entry - 2018-04-14) to help reduce 'struct object_entry' size. The delta size field in this struct is reduced to only contain max 2MB. So if any new delta is produced and larger than

2MB, it's dropped because we can't really save such a large size anywhere. Fallback is provided in case existingpackfiles already have

large deltas, then we can retrieve it from the pack.

While this should help small machines repacking large repos (i.e. less

memory pressure), dropping large deltas during the delta selection process could end up with worse pack files. And if existing packfiles already have >2MB delta and pack-objects is instructed to not reuse deltas, all of them will be dropped on the floor, and the resulting pack would be definitely bigger.

There is also a regression in terms of CPU/IO if we have large on-disk deltas because fallback code needs to parse the pack every time the delta size is needed and just access to the mmap'd pack data is enough for extra page faults when memory is under pressure.

Both of these issues were reported on the mailing list. Here's some numbers for comparison.

    Version  Pack (MB)  MaxRSS(kB)  Time (s)
    -------  ---------  ----------  --------
     2.17.0     5498     43513628    2494.85
     2.18.0    10531     40449596    4168.94

This patch provides a better fallback that is

- cheaper in terms of cpu and io because we won't have to read existing pack files as much

- better in terms of pack size because the pack heuristics is back to 2.17.0 time, we do not drop large deltas at all

If we encounter any delta (on-disk or created during try_delta phase) that is larger than the 2MB limit, we stop using delta_size_ field for this because it can't contain such size anyway. A new array of delta size is dynamically allocated and can hold all the deltas that 2.17.0 can [1]. All current delta sizes are migrated over.

With this, we do not have to drop deltas in try_delta() anymore. Of course the downside is we use slightly more memory, even compared to 2.17.0. But since this is considered an uncommon case, a bit more memory consumption should not be a problem.

Delta size limit is also raised from 2MB to 32 MB to better cover common case and avoid that extra memory consumption (99.999% deltas in this reported repo are under 12MB). Other fields are shuffled around to keep this struct packed tight. We don't use more memory in common case even with this limit update.

A note about thread synchronization. Since this code can be run in parallel during delta searching phase, we need a mutex. The realloc part in packlist_alloc() is not protected because it only happens during the object counting phase, which is always single-threaded.

The locking in oe_delta_size() could also be dropped if we make sure the pack->delta_size pointer assignment in oe_set_delta_size() is atomic. But let's keep the lock for now to be on the safe side. Lock contention should not be that high for this lock.

[1] With a small tweak. 2.17.0 on 64-bit linux can hold 2^64 byte deltas, which is absolutely insane. But windows builds, even 64-bit version, only hold 2^32. So reducing it to 2^32 should be quite safe.

Reported-by Elijah Newren <[email protected]>

Helped-by Elijah Newren <[email protected]>

Helped-by Jeff King <[email protected]>

Signed-off-by Nguyễn Thái Ngọc Duy <[email protected]>

---
I'm optimistic that the slowness on linux repo is lock contention (because if it's not then I have no clue what is). So let's start doing proper patches.

If we want a quick fix for 2.18.1. I suggest bumping up OE_DELTA_SIZE_BITS like Elijah did in his second option. I don't think it's safe to fast track this patch.

 builtin/pack-objects.c    |  6 ++--
 ci/run-build-and-tests.sh |  1 +
 pack-objects.c            | 21 ++++++++++++
 pack-objects.h            | 68 +++++++++++++++++++++++++++++++--------
 t/README                  |  4 +++
 5 files changed, 82 insertions(+), 18 deletions(-)

builtin/pack-objects.c +2 -4

index ebc8cefb53..3bc182b1b6 100644
@@ -2023,10 +2023,6 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
        delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size);
        if (!delta_buf)
                return 0;
-       if (delta_size >= (1U << OE_DELTA_SIZE_BITS)) {
-               free(delta_buf);
-               return 0;
-       }
 
        if (DELTA(trg_entry)) {
                /* Prefer only shallower same-sized deltas. */

@@ -2278,6 +2274,8 @@ static void init_threaded_search(void)
        pthread_mutex_init(&cache_mutex, NULL);
        pthread_mutex_init(&progress_mutex, NULL);
        pthread_cond_init(&progress_cond, NULL);
+       pthread_mutex_init(&to_pack.lock, NULL);
+       to_pack.lock_initialized = 1;
        old_try_to_free_routine = set_try_to_free_routine(try_to_free_from_threads);
 }
 

ci/run-build-and-tests.sh +1 -0

index 4b04c75b7f..2a5bff4a1c 100755
@@ -14,6 +14,7 @@ then
        export GIT_TEST_SPLIT_INDEX=yes
        export GIT_TEST_FULL_IN_PACK_ARRAY=true
        export GIT_TEST_OE_SIZE=10
+       export GIT_TEST_OE_DELTA_SIZE=5
        make --quiet test
 fi
 

pack-objects.c +17 -0

index 92708522e7..eef344b7c1 100644
@@ -88,6 +88,23 @@ struct object_entry *packlist_find(struct packing_data *pdata,
        return &pdata->objects[pdata->index[i] - 1];
 }
 
+uint32_t *new_delta_size_array(struct packing_data *pack)
+{
+       uint32_t *delta_size;
+       uint32_t i;
+
+       /*
+        * nr_alloc, not nr_objects to align with realloc() strategy in
+        * packlist_alloc()
+        */
+       ALLOC_ARRAY(delta_size, pack->nr_alloc);
+
+       for (i = 0; i < pack->nr_objects; i++)
+               delta_size[i] = pack->objects[i].delta_size_;
+
+       return delta_size;
+}
+
 static void prepare_in_pack_by_idx(struct packing_data *pdata)
 {
        struct packed_git **mapping, *p;

pack-objects.c +2 -0

 }
 
 struct object_entry *packlist_alloc(struct packing_data *pdata,

@@ -160,6 +179,8 @@ struct object_entry *packlist_alloc(struct packing_data *pdata,
 
                if (!pdata->in_pack_by_idx)
                        REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);
+               if (pdata->delta_size)
+                       REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc);
        }
 
        new_entry = pdata->objects + pdata->nr_objects++;

pack-objects.h +54 -14

index edf74dabdd..9f977ae800 100644
@@ -2,6 +2,7 @@
 #define PACK_OBJECTS_H
 
 #include "object-store.h"
+#include "thread-utils.h"
 
 #define DEFAULT_DELTA_CACHE_SIZE (256 * 1024 * 1024)
 

@@ -14,7 +15,7 @@
  * above this limit. Don't lower it too much.
  */
 #define OE_SIZE_BITS           31
-#define OE_DELTA_SIZE_BITS     20
+#define OE_DELTA_SIZE_BITS     24
 
 /*
  * State flags for depth-first search used for analyzing delta cycles.

@@ -93,12 +94,12 @@ struct object_entry {
                                     * uses the same base as me
                                     */
        unsigned delta_size_:OE_DELTA_SIZE_BITS; /* delta data size (uncompressed) */
-       unsigned delta_size_valid:1;
+       unsigned char in_pack_header_size;
        unsigned in_pack_idx:OE_IN_PACK_BITS;   /* already in pack */
        unsigned z_delta_size:OE_Z_DELTA_BITS;
        unsigned type_valid:1;
-       unsigned type_:TYPE_BITS;
        unsigned no_try_delta:1;
+       unsigned type_:TYPE_BITS;
        unsigned in_pack_type:TYPE_BITS; /* could be delta */
        unsigned preferred_base:1; /*
                                    * we do not pack this, but is available

@@ -108,17 +109,16 @@ struct object_entry {
        unsigned tagged:1; /* near the very tip of refs */
        unsigned filled:1; /* assigned write-order */
        unsigned dfs_state:OE_DFS_STATE_BITS;
-       unsigned char in_pack_header_size;
        unsigned depth:OE_DEPTH_BITS;
 
        /*
         * pahole results on 64-bit linux (gcc and clang)
         *
-        *   size: 80, bit_padding: 20 bits, holes: 8 bits
+        *   size: 80, bit_padding: 9 bits
         *
         * and on 32-bit (gcc)
         *
-        *   size: 76, bit_padding: 20 bits, holes: 8 bits
+        *   size: 76, bit_padding: 9 bits
         */
 };
 

@@ -130,6 +130,7 @@ struct packing_data {
        uint32_t index_size;
 
        unsigned int *in_pack_pos;
+       uint32_t *delta_size;
 
        /*
         * Only one of these can be non-NULL and they have different

@@ -140,10 +141,32 @@ struct packing_data {
        struct packed_git **in_pack_by_idx;
        struct packed_git **in_pack;
 
+#ifndef NO_PTHREADS
+       int lock_initialized;
+       pthread_mutex_t lock;
+#endif
+
        uintmax_t oe_size_limit;
+       uintmax_t oe_delta_size_limit;
 };
 
 void prepare_packing_data(struct packing_data *pdata);
+
+static inline void packing_data_lock(struct packing_data *pdata)
+{
+#ifndef NO_PTHREADS
+       if (pdata->lock_initialized)
+               pthread_mutex_lock(&pdata->lock);
+#endif
+}
+static inline void packing_data_unlock(struct packing_data *pdata)
+{
+#ifndef NO_PTHREADS
+       if (pdata->lock_initialized)
+               pthread_mutex_unlock(&pdata->lock);
+#endif
+}
+
 struct object_entry *packlist_alloc(struct packing_data *pdata,
                                    const unsigned char *sha1,
                                    uint32_t index_pos);

@@ -330,20 +353,37 @@ static inline void oe_set_size(struct packing_data *pack,
 static inline unsigned long oe_delta_size(struct packing_data *pack,
                                          const struct object_entry *e)
 {
-       if (e->delta_size_valid)
-               return e->delta_size_;
-       return oe_size(pack, e);
+       unsigned long size;
+
+       packing_data_lock(pack);
+       if (pack->delta_size)
+               size = pack->delta_size[e - pack->objects];
+       else
+               size = e->delta_size_;
+       packing_data_unlock(pack);
+       return size;
 }
 
+uint32_t *new_delta_size_array(struct packing_data *pdata);
 static inline void oe_set_delta_size(struct packing_data *pack,
                                     struct object_entry *e,
                                     unsigned long size)
 {
-       e->delta_size_ = size;
-       e->delta_size_valid = e->delta_size_ == size;
-       if (!e->delta_size_valid && size != oe_size(pack, e))
-               BUG("this can only happen in check_object() "
-                   "where delta size is the same as entry size");
+       packing_data_lock(pack);
+       if (!pack->delta_size && size < pack->oe_delta_size_limit) {
+               packing_data_unlock(pack);
+               e->delta_size_ = size;
+               return;
+       }
+       /*
+        * We have had at least one delta size exceeding OE_DELTA_SIZE_BITS
+        * limit. delta_size_ will not be used anymore. All delta sizes are
+        * now from the delta_size[] array.
+        */
+       if (!pack->delta_size)
+               pack->delta_size = new_delta_size_array(pack);
+       pack->delta_size[e - pack->objects] = size;
+       packing_data_unlock(pack);
 }
 
 #endif

t/README +4 -1

index 8373a27fea..9028b47d92 100644
@@ -315,6 +315,10 @@ packs on demand. This normally only happens when the object size is
 over 2GB. This variable forces the code path on any object larger than
 <n> bytes.
 
+GIT_TEST_OE_DELTA_SIZE=<n> exercises the uncomon pack-objects code
+path where deltas larger than this limit require extra memory
+allocation for bookkeeping.
+
 Naming Tests
 ------------
 
--

2.18.0.rc2.476.g39500d3211

Quoted 14 lines · Nguyễn Thái Ngọc Duy

This patch provides a better fallback that is

- cheaper in terms of cpu and io because we won't have to read existing pack files as much

- better in terms of pack size because the pack heuristics is back to 2.17.0 time, we do not drop large deltas at all

If we encounter any delta (on-disk or created during try_delta phase) that is larger than the 2MB limit, we stop using delta_size_ field for this because it can't contain such size anyway. A new array of delta size is dynamically allocated and can hold all the deltas that 2.17.0 can [1]. All current delta sizes are migrated over.

Quoted 4 lines

With this, we do not have to drop deltas in try_delta() anymore. Of course the downside is we use slightly more memory, even compared to 2.17.0. But since this is considered an uncommon case, a bit more memory consumption should not be a problem.

Quoted 4 lines

---
I'm optimistic that the slowness on linux repo is lock contention (because if it's not then I have no clue what is). So let's start doing proper patches.

I'll be testing this shortly...

Quoted 3 lines

If we want a quick fix for 2.18.1. I suggest bumping up OE_DELTA_SIZE_BITS like Elijah did in his second option. I don't think it's safe to fast track this patch.

Okay, I'll submit that with a proper commit message then. Since you also bump OE_DELTA_SIZE_BITS in your patch (though to a different value), it'll require a conflict resolution when merging maint into master, but at least the change won't silently leak through.

Quoted 16 lines · Elijah Newren

Quoted 14 lines · Nguyễn Thái Ngọc Duy

This patch provides a better fallback that is

- cheaper in terms of cpu and io because we won't have to read existing pack files as much

- better in terms of pack size because the pack heuristics is back to 2.17.0 time, we do not drop large deltas at all

If we encounter any delta (on-disk or created during try_delta phase) that is larger than the 2MB limit, we stop using delta_size_ field for this because it can't contain such size anyway. A new array of delta size is dynamically allocated and can hold all the deltas that 2.17.0 can [1]. All current delta sizes are migrated over.

Quoted 4 lines

Quoted 4 lines

With this, we do not have to drop deltas in try_delta() anymore. Of course the downside is we use slightly more memory, even compared to 2.17.0. But since this is considered an uncommon case, a bit more memory consumption should not be a problem.

Is the increased memory only supposed to affect the uncommon case? I was able to verify that 2.18.0 used less memory than 2.17.0 (for either my repo or linux.git), but I don't see nearly the same memory reduction relative to 2.17.0 for linux.git with your new patches.

Quoted 6 lines

Quoted 4 lines

---
I'm optimistic that the slowness on linux repo is lock contention (because if it's not then I have no clue what is). So let's start doing proper patches.

I'll be testing this shortly...

Using these definitions for versions:

fix-v5: https://public-inbox.org/git/[email protected]/
(plus what it depends on)
fix-v6: The patch I'm responding to
fix-v2: https://public-inbox.org/git/[email protected]/

and inspired by
https://public-inbox.org/git/[email protected]/, I ran

   /usr/bin/time -f 'MaxRSS:%M Time:%e' git gc --aggressive

three times on a beefy box (40 cores, 160GB ram, otherwise quiet system). If I take the lowest MaxRSS, and the lowest time reported (regardless of whether from the same run), then the results are as follows for linux.git (all cases repacked down to 1279 MB, so removing that from the table):

Version  MaxRSS(kB)  Time (s)
-------  ----------  --------
 2.17.0   11413236    621.36
 2.18.0   10987152    621.80
 fix-v5   11105564    836.29
 fix-v6   11357304    831.73
 fix-v2   10873348    619.96

The runtime could swing up to 10 seconds between runs. The memory use also had some variability, but all runs of fix-v2 had lower MaxRSS than any runs of 2.18.0 (which surprised me); all runs of 2.18.0 used less memory than any run of fix-v6, and all runs of fix-v6 used less memory than any run of 2.17.0. fix-v5 had the most variabiilty in MaxRSS, ranging from as low as some 2.18.0 runs up to higher than any 2.17.0 runs.

...but maybe that'd change with more than 3 runs of each?

Anyway, this is a lot better than the 1193.67 seconds I saw with fix-v4 (https://public-inbox.org/git/[email protected]/,
which Peff fixed up into fix-v5), suggesting it is lock contention, but we're still about 33% slower than 2.17.0 and we've lost almost all of the memory savings. Somewhat surprisingly, the highly simplistic fix-v2 does a lot better on both measures.

However, I'm just concentrating on a beefy machine; it may be that v6 drastically outperforms v2 on weaker hardware? Can others measure a lower memory usage for v6 than v2?

Also, for the original repo with the huge deltas that started it all, the numbers are (only run once since it takes so long):

Version  Pack (MB)  MaxRSS(kB)  Time (s)
-------  ---------  ----------  --------
 2.17.0     5498     43513628    2494.85
 2.18.0    10531     40449596    4168.94
 fix-v5     5500     42805716    2577.50
 fiv-v6     5509     42814836    2605.36
 fix-v2     5509     41644104    2468.25

Quoted 4 lines

Quoted 3 lines

If we want a quick fix for 2.18.1. I suggest bumping up OE_DELTA_SIZE_BITS like Elijah did in his second option. I don't think it's safe to fast track this patch.

Quoted 4 lines

Okay, I'll submit that with a proper commit message then. Since you also bump OE_DELTA_SIZE_BITS in your patch (though to a different value), it'll require a conflict resolution when merging maint into master, but at least the change won't silently leak through.

...except now I'm wondering if the commit message should mention that it's just a stopgap fix for 2.18.1, or whether it's actually the fix that we just want to use going forward as well.

Quoted 3 lines

However, I'm just concentrating on a beefy machine; it may be that v6 drastically outperforms v2 on weaker hardware? Can others measure a lower memory usage for v6 than v2?

I'll try it with massif on linux.git, but this is a very weak laptop (4GB) so it'll take a while....

Quoted 14 lines

This patch provides a better fallback that is

- cheaper in terms of cpu and io because we won't have to read existing pack files as much

- better in terms of pack size because the pack heuristics is back to 2.17.0 time, we do not drop large deltas at all

If we encounter any delta (on-disk or created during try_delta phase) that is larger than the 2MB limit, we stop using delta_size_ field for this because it can't contain such size anyway. A new array of delta size is dynamically allocated and can hold all the deltas that 2.17.0 can [1]. All current delta sizes are migrated over.

Quoted 4 lines

With this, we do not have to drop deltas in try_delta() anymore. Of course the downside is we use slightly more memory, even compared to 2.17.0. But since this is considered an uncommon case, a bit more memory consumption should not be a problem.

Out of curiosity, would it be possible to use the delta_size_ field for deltas that are small enough, and only use an external data structure (perhaps a hash rather than an array) for the few deltas that are large?

Quoted 2 lines

--
2.18.0.rc2.476.g39500d3211

Missing the 2.18.0 tag? ;-)

Quoted 4 lines · Elijah Newren

Out of curiosity, would it be possible to use the delta_size_ field for deltas that are small enough, and only use an external data structure (perhaps a hash rather than an array) for the few deltas that are large?

We could. And because repack time is still a bit higher in your linux.git case. Let's try this. No locking in common case and very small locked region when we hit large deltas

-- 8< --

pack-objects.h +0 -0

index 9f977ae800..11890e7217 100644
@@ -15,7 +15,7 @@

pack-objects.h +0 -2

@@ -353,37 +354,26 @@ static inline void oe_set_size(struct packing_data *pack,
 static inline unsigned long oe_delta_size(struct packing_data *pack,
                                          const struct object_entry *e)
 {
-       unsigned long size;
-

pack-objects.h +8 -14

 }
 
-uint32_t *new_delta_size_array(struct packing_data *pdata);
 static inline void oe_set_delta_size(struct packing_data *pack,
                                     struct object_entry *e,
                                     unsigned long size)
 {
-       packing_data_lock(pack);
-       if (!pack->delta_size && size < pack->oe_delta_size_limit) {
-               packing_data_unlock(pack);
+       if (size < pack->oe_delta_size_limit) {
                e->delta_size_ = size;
-               return;
+               e->delta_size_valid = 1;
+       } else {
+               packing_data_lock(pack);
+               if (!pack->delta_size)
+                       ALLOC_ARRAY(pack->delta_size, pack->nr_alloc);
+               packing_data_unlock(pack);
+               pack->delta_size[e - pack->objects] = size;
        }
-       /*
-        * We have had at least one delta size exceeding OE_DELTA_SIZE_BITS
-        * limit. delta_size_ will not be used anymore. All delta sizes are
-        * now from the delta_size[] array.
-        */
-       if (!pack->delta_size)
-               pack->delta_size = new_delta_size_array(pack);
-       pack->delta_size[e - pack->objects] = size;
-       packing_data_unlock(pack);
 }
 
 #endif

Quoted 1 line

-- 8< --

...

Quoted 5 lines

pack-objects.h +0 -0

index 9f977ae800..11890e7217 100644
@@ -15,7 +15,7 @@

...

Quoted 11 lines

pack-objects.h +2 -5

@@ -353,37 +354,26 @@ static inline void oe_set_size(struct packing_data *pack,
 static inline unsigned long oe_delta_size(struct packing_data *pack,
                                          const struct object_entry *e)
 {
-       unsigned long size;
-
-       packing_data_lock(pack);
-       if (pack->delta_size)
-               size = pack->delta_size[e - pack->objects];
+       if (e->delta_size_valid)
+               return e->delta_size_;

pack-objects.h static inline void oe_set_size(struct packing_data *pack, · line 360

Quoted 5 lines

pack-objects.h +1 -3

        else
-               size = e->delta_size_;
-       packing_data_unlock(pack);
-       return size;
+               return pack->delta_size[e - pack->objects];

Should this last line be wrapped with packing_data_lock/unlock calls? (And similarly in oe_set_delta_size when writing to this array?)

Quoted 4 lines · Elijah Newren

Out of curiosity, would it be possible to use the delta_size_ field for deltas that are small enough, and only use an external data structure (perhaps a hash rather than an array) for the few deltas that are large?

We could. And because repack time is still a bit higher in your linux.git case. Let's try this. No locking in common case and very small locked region when we hit large deltas

Quoted 9 lines · Duy Nguyen

Quoted 4 lines · Elijah Newren

Out of curiosity, would it be possible to use the delta_size_ field for deltas that are small enough, and only use an external data structure (perhaps a hash rather than an array) for the few deltas that are large?

We could. And because repack time is still a bit higher in your linux.git case. Let's try this. No locking in common case and very small locked region when we hit large deltas

This one looks like a winner. Labelling this as fix-v7, this rounds out the table to:

Version Time (s)
------- --------

 2.17.0   621.36
 2.18.0   621.80
 fix-v5   836.29
 fix-v6   831.73
 fix-v2   619.96
 fix-v7   622.88

So the runtime is basically within the noise of different runs of the timing for 2.17.0 or 2.18.0 or -v2, and is much faster than -v5 or -v6.

Quoted 3 lines · Nguyễn Thái Ngọc Duy

If we want a quick fix for 2.18.1. I suggest bumping up OE_DELTA_SIZE_BITS like Elijah did in his second option. I don't think it's safe to fast track this patch.

Okay, I'll submit that with a proper commit message then. Since you also bump OE_DELTA_SIZE_BITS in your patch (though to a different value), it'll require a conflict resolution when merging maint into master, but at least the change won't silently leak through.

This patch provides a stop-gap improvement for maint that increases the delta size back up to 32 bits (still an improvement over the 64 bit size of the original).

I think Duy's comment that I'm responding to suggests he Acks this patch for maint, but there is that little 'if' he put in his statement.

Access to e->delta_size_ (and by extension pack->delta_size[e - pack->objects]) is unprotected as before, the thread scheduler in pack-objects must make sure "e" is never updated by two different threads.

pack-objects.h +1 -0

@@ -130,6 +131,7 @@ struct packing_data {
 	uint32_t index_size;
 
 	unsigned int *in_pack_pos;
+	unsigned long *delta_size;
 
 	/*
 	 * Only one of these can be non-NULL and they have different

pack-objects.h +22 -6

@@ -332,18 +353,34 @@ static inline unsigned long oe_delta_size(struct packing_data *pack,
 {
 	if (e->delta_size_valid)
 		return e->delta_size_;
-	return oe_size(pack, e);
+
+	/*
+	 * pack->detla_size[] can't be NULL because oe_set_delta_size()
+	 * must have been called when a new delta is saved with
+	 * oe_set_delta().
+	 * If oe_delta() returns NULL (i.e. default state, which means
+	 * delta_size_valid is also false), then the caller must never
+	 * call oe_delta_size().
+	 */
+	return pack->delta_size[e - pack->objects];
 }
 
 static inline void oe_set_delta_size(struct packing_data *pack,
 				     struct object_entry *e,
 				     unsigned long size)
 {
-	e->delta_size_ = size;
-	e->delta_size_valid = e->delta_size_ == size;
-	if (!e->delta_size_valid && size != oe_size(pack, e))
-		BUG("this can only happen in check_object() "
-		    "where delta size is the same as entry size");
+	if (size < pack->oe_delta_size_limit) {
+		e->delta_size_ = size;
+		e->delta_size_valid = 1;
+	} else {
+		packing_data_lock(pack);
+		if (!pack->delta_size)
+			ALLOC_ARRAY(pack->delta_size, pack->nr_alloc);
+		packing_data_unlock(pack);
+
+		pack->delta_size[e - pack->objects] = size;
+		e->delta_size_valid = 0;
+	}
 }

Quoted 4 lines · Nguyễn Thái Ngọc Duy

Access to e->delta_size_ (and by extension pack->delta_size[e - pack->objects]) is unprotected as before, the thread scheduler in pack-objects must make sure "e" is never updated by two different threads.

OK. Do we need to worry about "e" (e.g. "e->delta_size_valid") being accessed while/before it is set by another thread?

I will have to study the thread dispatch code more to have a better answer, unfortunately.

Quoted 2 lines · Duy Nguyen

I will have to study the thread dispatch code more to have a better answer, unfortunately.

Well.. I thought I would need this weekend for this, but a quick look and ll_find_deltas() suggests that what we're doing is safe. At least you and Jeff are way to familiar with the delta window concept in pack-objects. So in multithread mode, we have a big list of all objects, then the list is cut in N sublists and each is owned entirely by one thread. Each thread then can slide a window over this sublist to search for the best delta.

Because of this partitioning, if trg_entry is being processed now, it will not be accessed by any other thread. It's owned by this thread and will be accessed again as src_entry when the next entry becomes the delta target in the same thread. As long as we don't access objects of another thread (and my v1 violates this) we should be ok.