diff mbox series

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

Message ID 812257e197cfe30bd0d3c68ea6ec0d062631185f.1730775907.git.gitgitgadget@gmail.com (mailing list archive)
State New, archived
Headers show
Series pack-objects: Create an alternative name hash algorithm (recreated) | expand

Commit Message

Derrick Stolee Nov. 5, 2024, 3:05 a.m. UTC
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         |

This example demonstrates how there is some natural overhead coming from
the cloned copy because the server is hosting many forks and has not
optimized for exactly this set of reachable objects. But the full repack
has similar characteristics with and without --full-name-hash.

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(-)

Comments

Taylor Blau Nov. 21, 2024, 8:08 p.m. UTC | #1
On Tue, Nov 05, 2024 at 03:05:01AM +0000, Derrick Stolee via GitGitGadget wrote:
> 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);
> 	}

Hah. I like that the existing implementation is small enough to fit (in
its entirety!) into the commit message!

> 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

s/differntiate/differentiate ;-).

>    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.

I'm not sure I entirely agree with the suggestion that the existing hash
function is only about packing repositories with short pathnames. I
think an important part of the existing implementation is that tries to
group similar files together, regardless of whether or not they appear
in the same tree.

As you have shown, this can be a problem when the fact two files that
happen to end in "CHANGELOG.json" end up in vastly different trees and
*aren't* related. I don't think that nailing all of these details in the
commit message is necessary, but I do think it's worth adjusting what
the original commit message says in terms of what the existing algorithm
is optimized for.

> 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.

I think you hint at this in the series' cover letter, but I suspect that
this pseduorandom behavior hurts in some small number of cases and that
the full-name hash idea isn't a pure win, e.g., when we really do want
to delta two paths that both end in CHAGNELOG.json despite being in
different parts of the tree.

You have some tables here below that demonstrate a significant
improvement with the full-name hash in use, which I think is good worth
keeping in my own opinion. It may be worth updating those to include the
new examples you highlighted in your revised cover letter as well.

> 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,

Is this repository publicly available? If so, it may be worth mentioning
here.

> 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         |

Ahh. Here's a great example of it helping to a smaller extent. Thanks
for including this as part of demonstrating the full picture (both the
benefits and drawbacks).

> This example demonstrates how there is some natural overhead coming from
> the cloned copy because the server is hosting many forks and has not
> optimized for exactly this set of reachable objects. But the full repack
> has similar characteristics with and without --full-name-hash.

Good.

> 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.

Amazing!

> 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.

Agreed.

> 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>

OK, I see that --full-name-hash is now listed in the synopsis, but I
don't see a corresponding description of what the option does later on
in this file. I took a look through the remaining patches in this series
and couldn't find any further changes to git-pack-objects(1) either.

>  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;
> +	}
> +

Good, we determine this early on in the command, so we don't risk
computing different hash functions within the same process.

I wonder if it's worth guarding against mixing the hash functions within
the pack_name_hash() and pack_full_name_hash() functions themselves. I'm
thinking something like:

    static inline uint32_t pack_name_hash(const char *name)
    {
        if (use_full_name_hash)
            BUG("called pack_name_hash() with --full-name-hash")
        /* ... */
    }

and the inverse in pack_full_name_hash(). I don't think it's strictly
necessary, but it would be a nice guard against someone calling, e.g.,
pack_full_name_hash() directly instead of pack_name_hash_fn().

The other small thought I had here is that we should use the convenience
function die_for_incompatible_opt3() here, since it uses an existing
translation string for pairs of incompatible options.

(As an aside, though that function is actually implemented in the
_opt4() variant, and it knows how to handle a pair, trio, and quartet of
mutually incompatible options, there is no die_for_incompatible_opt2()
function. It may be worth adding one here since I'm sure there are other
spots which would benefit from such a function).

> diff --git a/builtin/repack.c b/builtin/repack.c
> index d6bb37e84ae..ab2a2e46b20 100644
> --- a/builtin/repack.c
> +++ b/builtin/repack.c

I'm surprised to see the new option plumbed into repack in this commit.
I would have thought that it'd appear in the subsequent commit instead.
The implementation below looks good, I just imagined it would be placed
in the next commit instead of this one.

The remaining parts of this change look good to me.

Thanks,
Taylor
Taylor Blau Nov. 21, 2024, 9:35 p.m. UTC | #2
On Thu, Nov 21, 2024 at 03:08:09PM -0500, Taylor Blau wrote:
> The remaining parts of this change look good to me.

Oops, one thing I forgot (which reading Peff's message in [1] reminded
me of) is that I think we need to disable full-name hashing when we're
reusing existing packfiles as is the case with try_partial_reuse().

There we're always looking at classic name hash values, so mixing the
two would be a mistake. I think that amounts to:

--- 8< ---
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 762949e4c8..7e370bcfc9 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -4070,6 +4070,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
 	if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
 		return -1;

+	use_full_name_hash = 0;
+
 	if (pack_options_allow_reuse())
 		reuse_partial_packfile_from_bitmap(bitmap_git,
 						   &reuse_packfiles,
--- >8 ---

Thanks,
Taylor

[1]: https://lore.kernel.org/git/20241104172533.GA2985568@coredump.intra.peff.net/
Junio C Hamano Nov. 21, 2024, 11:32 p.m. UTC | #3
Taylor Blau <me@ttaylorr.com> writes:

> On Thu, Nov 21, 2024 at 03:08:09PM -0500, Taylor Blau wrote:
>> The remaining parts of this change look good to me.
>
> Oops, one thing I forgot (which reading Peff's message in [1] reminded
> me of) is that I think we need to disable full-name hashing when we're
> reusing existing packfiles as is the case with try_partial_reuse().
>
> There we're always looking at classic name hash values, so mixing the
> two would be a mistake. I think that amounts to:
>
> --- 8< ---
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index 762949e4c8..7e370bcfc9 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -4070,6 +4070,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
>  	if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
>  		return -1;
>
> +	use_full_name_hash = 0;

Hmph, is this early enough, or has some other code path already
computed the name hashes for the paths for the files to be packed?

    ... Goes and looks ...

This is called from get_object_list() which

 - is not called under --stdin-packs,
 - is not called in cruft mode,
 - is not called when reading object list from --stdin

so we are looking at the bog-standard "objects to be packed are
given in the form of rev-list command line options from our command
line".  And in the function, we walk the history near the end, which
makes show_object calls that adds object-entry with the name-hash.
So the call to get_object_list_from_bitmap() happens way before the
first use of the name-hash function, so this is probably safe.

And obviously get_object_list_from_bitmap() is the only place we
select objects to be packed from an existing pack and a bitmap file,
so even if we gain new callers in the future, it is very likely that
the new callers would benefit from this change.

OK.  Nicely done.

>  	if (pack_options_allow_reuse())
>  		reuse_partial_packfile_from_bitmap(bitmap_git,
>  						   &reuse_packfiles,
> --- >8 ---
>
> Thanks,
> Taylor
>
> [1]: https://lore.kernel.org/git/20241104172533.GA2985568@coredump.intra.peff.net/
Derrick Stolee Nov. 22, 2024, 11:46 a.m. UTC | #4
On 11/21/24 4:35 PM, Taylor Blau wrote:
> On Thu, Nov 21, 2024 at 03:08:09PM -0500, Taylor Blau wrote:
>> The remaining parts of this change look good to me.
> 
> Oops, one thing I forgot (which reading Peff's message in [1] reminded
> me of) is that I think we need to disable full-name hashing when we're
> reusing existing packfiles as is the case with try_partial_reuse().
> 
> There we're always looking at classic name hash values, so mixing the
> two would be a mistake. I think that amounts to:
> 
> --- 8< ---
> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index 762949e4c8..7e370bcfc9 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c
> @@ -4070,6 +4070,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
>   	if (!(bitmap_git = prepare_bitmap_walk(revs, 0)))
>   		return -1;
> 
> +	use_full_name_hash = 0;
> +
Thanks. I have applied this code change with a comment detailing
the context around the bitmap file storing only the default name-hash
(for now) but that it can change in the future.

Thanks,
-Stolee
Derrick Stolee Nov. 22, 2024, 11:59 a.m. UTC | #5
On 11/21/24 3:08 PM, Taylor Blau wrote:
> On Tue, Nov 05, 2024 at 03:05:01AM +0000, Derrick Stolee via GitGitGadget wrote:
>> From: Derrick Stolee <stolee@gmail.com>

>> 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.
> 
> I'm not sure I entirely agree with the suggestion that the existing hash
> function is only about packing repositories with short pathnames. I
> think an important part of the existing implementation is that tries to
> group similar files together, regardless of whether or not they appear
> in the same tree.

I'll be more explicit about the design for "hash locality" earlier in
the message, but also pointing out that the locality only makes sense as
a benefit when there are not enough versions of a file in history, since
it's nearly always better to choose a previous version of the same file
instead of a different path with a name-hash collision. Directory renames
are on place where this is a positive decision, but those are typically
rare compared to the full history of a large repo.

>> 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.
> 
> I think you hint at this in the series' cover letter, but I suspect that
> this pseduorandom behavior hurts in some small number of cases and that
> the full-name hash idea isn't a pure win, e.g., when we really do want
> to delta two paths that both end in CHAGNELOG.json despite being in
> different parts of the tree.

I mention that this doesn't work well in all cases when operating under
a 'git push' or in a shallow clone. Shallow clones are disabled in a later
commit and we don't have the necessary implementation to make this hash
function be selected within 'git push'.

> You have some tables here below that demonstrate a significant
> improvement with the full-name hash in use, which I think is good worth
> keeping in my own opinion. It may be worth updating those to include the
> new examples you highlighted in your revised cover letter as well.

I'll try to remember to move the newer examples to the cover letter.

>> 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,
> 
> Is this repository publicly available? If so, it may be worth mentioning
> here.

Here, by "when repacking a repository" I mean "we are going to test
repacking a number of example repositories, that will be listed in detail
in the coming tables".

>> 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  |

These repos B, C, and D are _not_ publicly available, though.

>> 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>
> 
> OK, I see that --full-name-hash is now listed in the synopsis, but I
> don't see a corresponding description of what the option does later on
> in this file. I took a look through the remaining patches in this series
> and couldn't find any further changes to git-pack-objects(1) either.

I'll fix that. Thanks. As well as moving the 'git repack' changes out
of this patch. I'll adjust the commit message to say "packing all objects'
instead of 'git repack' to be clear that this can be done with a direct
call to 'git pack-objects' instead of needing 'git repack'.

>> +	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;
>> +	}
>> +
> 
> Good, we determine this early on in the command, so we don't risk
> computing different hash functions within the same process.
> 
> I wonder if it's worth guarding against mixing the hash functions within
> the pack_name_hash() and pack_full_name_hash() functions themselves. I'm
> thinking something like:
> 
>      static inline uint32_t pack_name_hash(const char *name)
>      {
>          if (use_full_name_hash)
>              BUG("called pack_name_hash() with --full-name-hash")
>          /* ... */
>      }
> 
> and the inverse in pack_full_name_hash(). I don't think it's strictly
> necessary, but it would be a nice guard against someone calling, e.g.,
> pack_full_name_hash() directly instead of pack_name_hash_fn().

I think this is interesting defensive programming for future contributions.

We essentially want the methods to only be called by pack_name_hash_fn()
and don't have method privacy. We could extract it to its own header file
but then would need to modify the prototype to include the signal for
which hash type to use, but that would cause us to lose our ability to
check for a bug like this.

It may be even better to store a static value for the value of
use_full_name_hash when it first executes, so it can exit if it notices
a different value. (This is becoming large enough for its own patch.)

> The other small thought I had here is that we should use the convenience
> function die_for_incompatible_opt3() here, since it uses an existing
> translation string for pairs of incompatible options.
> 
> (As an aside, though that function is actually implemented in the
> _opt4() variant, and it knows how to handle a pair, trio, and quartet of
> mutually incompatible options, there is no die_for_incompatible_opt2()
> function. It may be worth adding one here since I'm sure there are other
> spots which would benefit from such a function).

Interesting. I've not considered these functions before.

>> diff --git a/builtin/repack.c b/builtin/repack.c
>> index d6bb37e84ae..ab2a2e46b20 100644
>> --- a/builtin/repack.c
>> +++ b/builtin/repack.c
> 
> I'm surprised to see the new option plumbed into repack in this commit.
> I would have thought that it'd appear in the subsequent commit instead.
> The implementation below looks good, I just imagined it would be placed
> in the next commit instead of this one.

Yes, I should delay that to patch 2.

Thanks,
-Stole
Patrick Steinhardt Nov. 26, 2024, 8:26 a.m. UTC | #6
On Tue, Nov 05, 2024 at 03:05:01AM +0000, Derrick Stolee via GitGitGadget wrote:
> 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.

I was wondering a bit about this: is there any reason why we cannot have
both, that is reap the benefits of "--full-name-hash" but end up writing
a bitmap with the old name hash so that we can continue to generate
bitmaps?

Forgive me if this question is naive, I'm more at home in the refs
subsystem :)

> diff --git a/pack-objects.h b/pack-objects.h
> index b9898a4e64b..88360aa3e8e 100644
> --- a/pack-objects.h
> +++ b/pack-objects.h
> @@ -207,6 +207,27 @@ static inline uint32_t pack_name_hash(const char *name)
>  	return hash;
>  }
>  
> +static inline uint32_t pack_full_name_hash(const char *name)
> +{
> +	const uint32_t bigp = 1234572167U;
> +	uint32_t c, hash = bigp;

It would be nice to have a comment here detailing how you came up with
that number, and what its requirements are. You briefly mention it in
the comment further down, but I think this could be expanded a bit.

Patrick
diff mbox series

Patch

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;
+	}
+
 	if (use_delta_islands)
 		strvec_push(&rp, "--topo-order");
 
diff --git a/builtin/repack.c b/builtin/repack.c
index d6bb37e84ae..ab2a2e46b20 100644
--- a/builtin/repack.c
+++ b/builtin/repack.c
@@ -58,6 +58,7 @@  struct pack_objects_args {
 	int no_reuse_object;
 	int quiet;
 	int local;
+	int full_name_hash;
 	struct list_objects_filter_options filter_options;
 };
 
@@ -306,6 +307,8 @@  static void prepare_pack_objects(struct child_process *cmd,
 		strvec_pushf(&cmd->args, "--no-reuse-delta");
 	if (args->no_reuse_object)
 		strvec_pushf(&cmd->args, "--no-reuse-object");
+	if (args->full_name_hash)
+		strvec_pushf(&cmd->args, "--full-name-hash");
 	if (args->local)
 		strvec_push(&cmd->args,  "--local");
 	if (args->quiet)
@@ -1203,6 +1206,8 @@  int cmd_repack(int argc,
 				N_("pass --no-reuse-delta to git-pack-objects")),
 		OPT_BOOL('F', NULL, &po_args.no_reuse_object,
 				N_("pass --no-reuse-object to git-pack-objects")),
+		OPT_BOOL(0, "full-name-hash", &po_args.full_name_hash,
+				N_("pass --full-name-hash to git-pack-objects")),
 		OPT_NEGBIT('n', NULL, &run_update_server_info,
 				N_("do not run git-update-server-info"), 1),
 		OPT__QUIET(&po_args.quiet, N_("be quiet")),
diff --git a/pack-objects.h b/pack-objects.h
index b9898a4e64b..88360aa3e8e 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -207,6 +207,27 @@  static inline uint32_t pack_name_hash(const char *name)
 	return hash;
 }
 
+static inline uint32_t pack_full_name_hash(const char *name)
+{
+	const uint32_t bigp = 1234572167U;
+	uint32_t c, hash = bigp;
+
+	if (!name)
+		return 0;
+
+	/*
+	 * Do the simplest thing that will resemble pseudo-randomness: add
+	 * random multiples of a large prime number with a binary shift.
+	 * The goal is not to be cryptographic, but to be generally
+	 * uniformly distributed.
+	 */
+	while ((c = *name++) != 0) {
+		hash += c * bigp;
+		hash = (hash >> 5) | (hash << 27);
+	}
+	return hash;
+}
+
 static inline enum object_type oe_type(const struct object_entry *e)
 {
 	return e->type_valid ? e->type_ : OBJ_BAD;
diff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh
index 3b9dae331a5..7585cac6595 100755
--- a/t/t5300-pack-object.sh
+++ b/t/t5300-pack-object.sh
@@ -674,4 +674,19 @@  do
 	'
 done
 
+# The following test is not necessarily a permanent choice, but since we do not
+# have a "name hash version" bit in the .bitmap file format, we cannot write the
+# full-name hash values into the .bitmap file without risking breakage later.
+#
+# TODO: Make these compatible in the future and replace this test with the
+# expected behavior when both are specified.
+test_expect_success '--full-name-hash and --write-bitmap-index are incompatible' '
+	git pack-objects base --all --full-name-hash --write-bitmap-index 2>err &&
+	test_grep incompatible err &&
+
+	# --stdout option silently removes --write-bitmap-index
+	git pack-objects --stdout --all --full-name-hash --write-bitmap-index >out 2>err &&
+	! test_grep incompatible err
+'
+
 test_done