On Fri, Jul 20, 2018 at 8:39 AM, Nguyễn Thái Ngọc Duy <pclouds@xxxxxxxxx> wrote:
> 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
I think you mean 1MB?
$ git grep OE_DELTA_SIZE_BITS v2.18.0
v2.18.0:builtin/pack-objects.c: if (delta_size >= (1U << OE_DELTA_SIZE_BITS)) {
v2.18.0:pack-objects.h:#define OE_DELTA_SIZE_BITS 20
v2.18.0:pack-objects.h: unsigned delta_size_:OE_DELTA_SIZE_BITS; /*
delta data size (uncompressed) */
In https://public-inbox.org/git/20180719151640.GA24997@xxxxxxxxxxxxxx/,
you bumped this to 21, which may be where you got the 2MB figure?
Your 2MB figure also appears on the next line and a few other places
in the commit message.
> 2MB, it's dropped because we can't really save such a large size
> anywhere. Fallback is provided in case existingpackfiles already have
Missing space: s/existingpackfiles/existing packfiles/
> large deltas, then we can retrieve it from the pack.
>
> While this should help small machines repacking large repos (i.e. less
Maybe change "repacking large repos" to "repacking large repos without
large deltas"?
> 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.
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?
> 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 <newren@xxxxxxxxx>
> Helped-by: Elijah Newren <newren@xxxxxxxxx>
> Helped-by: Jeff King <peff@xxxxxxxx>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@xxxxxxxxx>
> ---
> 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...
>
> 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.
> 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(-)
>
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index ebc8cefb53..3bc182b1b6 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -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);
> }
>
> diff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh
> index 4b04c75b7f..2a5bff4a1c 100755
> --- a/ci/run-build-and-tests.sh
> +++ b/ci/run-build-and-tests.sh
> @@ -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
>
> diff --git a/pack-objects.c b/pack-objects.c
> index 92708522e7..eef344b7c1 100644
> --- a/pack-objects.c
> +++ b/pack-objects.c
> @@ -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;
> @@ -146,6 +163,8 @@ void prepare_packing_data(struct packing_data *pdata)
>
> pdata->oe_size_limit = git_env_ulong("GIT_TEST_OE_SIZE",
> 1U << OE_SIZE_BITS);
> + pdata->oe_delta_size_limit = git_env_ulong("GIT_TEST_OE_DELTA_SIZE",
> + 1U << OE_DELTA_SIZE_BITS);
Perhaps 1UL instead of 1U, in case the user specifies the value of 32?
I know that flag is meant for testing smaller values, but since 32
was the first value I tried for OE_DELTA_SIZE_BITS when debugging my
issue maybe it makes sense to allow it?
> }
>
> 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++;
> diff --git a/pack-objects.h b/pack-objects.h
> index edf74dabdd..9f977ae800 100644
> --- a/pack-objects.h
> +++ b/pack-objects.h
> @@ -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
> diff --git a/t/README b/t/README
> index 8373a27fea..9028b47d92 100644
> --- a/t/README
> +++ b/t/README
> @@ -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
Missing the 2.18.0 tag? ;-)
