Re: [PATCH 1/7] pack-objects: add --full-name-hash option

> From: Derrick Stolee <stolee@gmail.com>
>
> The pack_name_hash() method has not been materially changed since it was
> introduced in ce0bd64299a (pack-objects: improve path grouping
> heuristics., 2006-06-05). The intention here is to group objects by path
> name, but also attempt to group similar file types together by making
> the most-significant digits of the hash be focused on the final
> characters.
>
> Here's the crux of the implementation:
>
> 	/*
> 	 * This effectively just creates a sortable number from the
> 	 * last sixteen non-whitespace characters. Last characters
> 	 * count "most", so things that end in ".c" sort together.
> 	 */
> 	while ((c = *name++) != 0) {
> 		if (isspace(c))
> 			continue;
> 		hash = (hash >> 2) + (c << 24);
> 	}

> As the comment mentions, this only cares about the last sixteen
> non-whitespace characters. This cause some filenames to collide more
> than others. Here are some examples that I've seen while investigating
> repositories that are growing more than they should be:
>
>  * "/CHANGELOG.json" is 15 characters, and is created by the beachball
>    [1] tool. Only the final character of the parent directory can
>    differntiate different versions of this file, but also only the two

>    most-significant digits. If that character is a letter, then this is
>    always a collision. Similar issues occur with the similar
>    "/CHANGELOG.md" path, though there is more opportunity for
>    differences in the parent directory.
>
>  * Localization files frequently have common filenames but differentiate
>    via parent directories. In C#, the name "/strings.resx.lcl" is used
>    for these localization files and they will all collide in name-hash.
>
> [1] https://github.com/microsoft/beachball
>
> I've come across many other examples where some internal tool uses a
> common name across multiple directories and is causing Git to repack
> poorly due to name-hash collisions.
>
> It is clear that the existing name-hash algorithm is optimized for
> repositories with short path names, but also is optimized for packing a
> single snapshot of a repository, not a repository with many versions of
> the same file. In my testing, this has proven out where the name-hash
> algorithm does a good job of finding peer files as delta bases when
> unable to use a historical version of that exact file.

> However, for repositories that have many versions of most files and
> directories, it is more important that the objects that appear at the
> same path are grouped together.
>
> Create a new pack_full_name_hash() method and a new --full-name-hash
> option for 'git pack-objects' to call that method instead. Add a simple
> pass-through for 'git repack --full-name-hash' for additional testing in
> the context of a full repack, where I expect this will be most
> effective.
>
> The hash algorithm is as simple as possible to be reasonably effective:
> for each character of the path string, add a multiple of that character
> and a large prime number (chosen arbitrarily, but intended to be large
> relative to the size of a uint32_t). Then, shift the current hash value
> to the right by 5, with overlap. The addition and shift parameters are
> standard mechanisms for creating hard-to-predict behaviors in the bits
> of the resulting hash.
>
> This is not meant to be cryptographic at all, but uniformly distributed
> across the possible hash values. This creates a hash that appears
> pseudorandom. There is no ability to consider similar file types as
> being close to each other.

> In a later change, a test-tool will be added so the effectiveness of
> this hash can be demonstrated directly.
>
> For now, let's consider how effective this mechanism is when repacking a
> repository with and without the --full-name-hash option. Specifically,

> let's use 'git repack -adf [--full-name-hash]' as our test.
>
> On the Git repository, we do not expect much difference. All path names
> are short. This is backed by our results:
>
> | Stage                 | Pack Size | Repack Time |
> |-----------------------|-----------|-------------|
> | After clone           | 260 MB    | N/A         |
> | Standard Repack       | 127MB     | 106s        |
> | With --full-name-hash | 126 MB    | 99s         |

> However, we can test this in a repository that uses one of the
> problematic naming conventions above. The fluentui [2] repo uses
> beachball to generate CHANGELOG.json and CHANGELOG.md files, and these
> files have very poor delta characteristics when comparing against
> versions across parent directories.
>
> | Stage                 | Pack Size | Repack Time |
> |-----------------------|-----------|-------------|
> | After clone           | 694 MB    | N/A         |
> | Standard Repack       | 438 MB    | 728s        |
> | With --full-name-hash | 168 MB    | 142s        |
>
> [2] https://github.com/microsoft/fluentui
>
> In this example, we see significant gains in the compressed packfile
> size as well as the time taken to compute the packfile.

> Using a collection of repositories that use the beachball tool, I was
> able to make similar comparisions with dramatic results. While the
> fluentui repo is public, the others are private so cannot be shared for
> reproduction. The results are so significant that I find it important to
> share here:
>
> | Repo     | Standard Repack | With --full-name-hash |
> |----------|-----------------|-----------------------|
> | fluentui |         438 MB  |               168 MB  |
> | Repo B   |       6,255 MB  |               829 MB  |
> | Repo C   |      37,737 MB  |             7,125 MB  |
> | Repo D   |     130,049 MB  |             6,190 MB  |
>
> Future changes could include making --full-name-hash implied by a config
> value or even implied by default during a full repack.
>
> It is important to point out that the name hash value is stored in the
> .bitmap file format, so we must disable the --full-name-hash option when
> bitmaps are being read or written. Later, the bitmap format could be
> updated to be aware of the name hash version so deltas can be quickly
> computed across the bitmapped/not-bitmapped boundary.

> Signed-off-by: Derrick Stolee <stolee@gmail.com>
> ---
>  Documentation/git-pack-objects.txt |  3 ++-
>  builtin/pack-objects.c             | 25 ++++++++++++++++++++-----
>  builtin/repack.c                   |  5 +++++
>  pack-objects.h                     | 21 +++++++++++++++++++++
>  t/t5300-pack-object.sh             | 15 +++++++++++++++
>  5 files changed, 63 insertions(+), 6 deletions(-)
>
> diff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt
> index e32404c6aae..93861d9f85b 100644
> --- a/Documentation/git-pack-objects.txt
> +++ b/Documentation/git-pack-objects.txt
> @@ -15,7 +15,8 @@ SYNOPSIS
>  	[--revs [--unpacked | --all]] [--keep-pack=<pack-name>]
>  	[--cruft] [--cruft-expiration=<time>]
>  	[--stdout [--filter=<filter-spec>] | <base-name>]
> -	[--shallow] [--keep-true-parents] [--[no-]sparse] < <object-list>
> +	[--shallow] [--keep-true-parents] [--[no-]sparse]
> +	[--full-name-hash] < <object-list>

>  DESCRIPTION
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index 08007142671..85595dfcd88 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -266,6 +266,14 @@ struct configured_exclusion {
>  static struct oidmap configured_exclusions;
>
>  static struct oidset excluded_by_config;
> +static int use_full_name_hash;
> +
> +static inline uint32_t pack_name_hash_fn(const char *name)
> +{
> +	if (use_full_name_hash)
> +		return pack_full_name_hash(name);
> +	return pack_name_hash(name);
> +}
>
>  /*
>   * stats
> @@ -1698,7 +1706,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type,
>  		return 0;
>  	}
>
> -	create_object_entry(oid, type, pack_name_hash(name),
> +	create_object_entry(oid, type, pack_name_hash_fn(name),
>  			    exclude, name && no_try_delta(name),
>  			    found_pack, found_offset);
>  	return 1;
> @@ -1912,7 +1920,7 @@ static void add_preferred_base_object(const char *name)
>  {
>  	struct pbase_tree *it;
>  	size_t cmplen;
> -	unsigned hash = pack_name_hash(name);
> +	unsigned hash = pack_name_hash_fn(name);
>
>  	if (!num_preferred_base || check_pbase_path(hash))
>  		return;
> @@ -3422,7 +3430,7 @@ static void show_object_pack_hint(struct object *object, const char *name,
>  	 * here using a now in order to perhaps improve the delta selection
>  	 * process.
>  	 */
> -	oe->hash = pack_name_hash(name);
> +	oe->hash = pack_name_hash_fn(name);
>  	oe->no_try_delta = name && no_try_delta(name);
>
>  	stdin_packs_hints_nr++;
> @@ -3572,7 +3580,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type
>  	entry = packlist_find(&to_pack, oid);
>  	if (entry) {
>  		if (name) {
> -			entry->hash = pack_name_hash(name);
> +			entry->hash = pack_name_hash_fn(name);
>  			entry->no_try_delta = no_try_delta(name);
>  		}
>  	} else {
> @@ -3595,7 +3603,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type
>  			return;
>  		}
>
> -		entry = create_object_entry(oid, type, pack_name_hash(name),
> +		entry = create_object_entry(oid, type, pack_name_hash_fn(name),
>  					    0, name && no_try_delta(name),
>  					    pack, offset);
>  	}
> @@ -4429,6 +4437,8 @@ int cmd_pack_objects(int argc,
>  		OPT_STRING_LIST(0, "uri-protocol", &uri_protocols,
>  				N_("protocol"),
>  				N_("exclude any configured uploadpack.blobpackfileuri with this protocol")),
> +		OPT_BOOL(0, "full-name-hash", &use_full_name_hash,
> +			 N_("optimize delta compression across identical path names over time")),
>  		OPT_END(),
>  	};
>
> @@ -4576,6 +4586,11 @@ int cmd_pack_objects(int argc,
>  	if (pack_to_stdout || !rev_list_all)
>  		write_bitmap_index = 0;
>
> +	if (write_bitmap_index && use_full_name_hash) {
> +		warning(_("currently, the --full-name-hash option is incompatible with --write-bitmap-index"));
> +		use_full_name_hash = 0;
> +	}
> +