[v2,1/8] pack-objects: create new name-hash function version

Commit Message

Jonathan Tan Dec. 2, 2024, 11:21 p.m. UTC

From: Jonathan Tan <[e-mail]>

As we will explore in later changes, the default name-hash function used
in 'git pack-objects' has a tendency to cause collisions and cause poor
delta selection. This change creates an alternative that avoids some
collisions while preserving some amount of hash locality.

The pack_name_hash() method has not been materially changed since it was
introduced in ce0bd64 (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. This collision is somewhat by design in order to promote hash
locality for files that have similar types (.c, .h, .json) or could be the
same file across a directory rename (a/foo.txt to b/foo.txt). This leads to
decent cross-path deltas in cases like shallow clones or packing a
repository with very few historical versions of files that share common data
with other similarly-named files.

However, when the name-hash instead leads to a large number of name-hash
collisions for otherwise unrelated files, this can lead to confusing the
delta calculation to prefer cross-path deltas over previous versions of the
same file.

The new pack_name_hash_v2() function attempts to fix this issue by
taking more of the directory path into account through its hash
function. Its naming implies that we will later wire up details for
choosing a name-hash function by version.

The first change is to be more careful about paths using non-ASCII
characters. With these characters in mind, reverse the bits in the byte
as the least-significant bits have the highest entropy and we want to
maximize their influence. This is done with some bit manipulation that
swaps the two halves, then the quarters within those halves, and then
the bits within those quarters.

The second change is to perform hash composition operations at every
level of the path. This is done by storing a 'base' hash value that
contains the hash of the parent directory. When reaching a directory
boundary, we XOR the current level's name-hash value with a downshift of
the previous level's hash. This perturbation intends to create low-bit
distinctions for paths with the same final 16 bytes but distinct parent
directory structures.

The collision rate and effectiveness of this hash function will be
explored in later changes as the function is integrated with 'git
pack-objects' and 'git repack'.

Signed-off-by: Jonathan Tan <[e-mail]>
Signed-off-by: Derrick Stolee <[e-mail]>
---
 pack-objects.h | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

Comments

Karthik Nayak Dec. 4, 2024, 8:06 p.m. UTC | #1

"Jonathan Tan via GitGitGadget" <[e-mail]> writes:

[snip]

> diff --git a/pack-objects.h b/pack-objects.h
> index b9898a4e64b..15be8368d21 100644
> --- a/pack-objects.h
> +++ b/pack-objects.h
> @@ -207,6 +207,34 @@ static inline uint32_t pack_name_hash(const char *name)
>  	return hash;
>  }
>
> +static inline uint32_t pack_name_hash_v2(const char *name)
> +{
> +	uint32_t hash = 0, base = 0, c;
> +
> +	if (!name)
> +		return 0;
> +
> +	while ((c = *name++)) {
> +		if (isspace(c))
> +			continue;
> +		if (c == '/') {
> +			base = (base >> 6) ^ hash;

Just two questions about the implementation for my own knowledge.
1. Why use '6' here? I couldn't understand the reasoning for the
specific value.
2. Generally in hashing algorithms the XOR is used to ensure that the
output distribution is uniform which reduces collisions. Here, as you
noted, we're more finding values for sorting rather than hashing in the
traditional sense. So why use an XOR?

> +			hash = 0;
> +		} else {
> +			/*
> +			 * 'c' is only a single byte. Reverse it and move
> +			 * it to the top of the hash, moving the rest to
> +			 * less-significant bits.
> +			 */
> +			c = (c & 0xF0) >> 4 | (c & 0x0F) << 4;
> +			c = (c & 0xCC) >> 2 | (c & 0x33) << 2;
> +			c = (c & 0xAA) >> 1 | (c & 0x55) << 1;
> +			hash = (hash >> 2) + (c << 24);
> +		}
> +	}
> +	return (base >> 6) ^ hash;
> +}
> +
>  static inline enum object_type oe_type(const struct object_entry *e)
>  {
>  	return e->type_valid ? e->type_ : OBJ_BAD;
> --
> gitgitgadget

Junio C Hamano Dec. 4, 2024, 9:05 p.m. UTC | #2

karthik nayak <[e-mail]> writes:

> 2. Generally in hashing algorithms the XOR is used to ensure that the
> output distribution is uniform which reduces collisions. Here, as you
> noted, we're more finding values for sorting rather than hashing in the
> traditional sense. So why use an XOR?

I am not Jonathan, but since the mixing-of-bits is done with XOR in
the original that Linus and I wrote, I think the question applies to
our version as well.  We prefer not to lose entropy from input
bytes, so we do not want to use OR or AND, which tend to paint
everything with 1 or 0 as you mix in bits from more bytes.

Anyway the question sounds like "generally when you take tests you
write with a pencil, but right now you are merely taking notes and
not taking any tests. why are you writing with a pencil?"  There are
multiple occasions that a pencil is a great fit as writing equipment.

Karthik Nayak Dec. 5, 2024, 9:46 a.m. UTC | #3

Junio C Hamano <[e-mail]> writes:

> karthik nayak <[e-mail]> writes:
>
>> 2. Generally in hashing algorithms the XOR is used to ensure that the
>> output distribution is uniform which reduces collisions. Here, as you
>> noted, we're more finding values for sorting rather than hashing in the
>> traditional sense. So why use an XOR?
>
> I am not Jonathan, but since the mixing-of-bits is done with XOR in
> the original that Linus and I wrote, I think the question applies to
> our version as well.  We prefer not to lose entropy from input
> bytes, so we do not want to use OR or AND, which tend to paint
> everything with 1 or 0 as you mix in bits from more bytes.
>

Thanks for the answering. My reasoning at the start was more of my
thoughts on why XOR could be used here and your explanation makes it
clearer.

> Anyway the question sounds like "generally when you take tests you
> write with a pencil, but right now you are merely taking notes and
> not taking any tests. why are you writing with a pencil?"  There are
> multiple occasions that a pencil is a great fit as writing equipment.

I'd say my questions was more of "I know a pencil is used when taking
tests because of XYZ reasons. On similar lines, why is a pencil used
here?" :)

Jonathan Tan Dec. 9, 2024, 11:15 p.m. UTC | #4

"Jonathan Tan via GitGitGadget" <[e-mail]> writes:
> diff --git a/pack-objects.h b/pack-objects.h
> index b9898a4e64b..15be8368d21 100644
> --- a/pack-objects.h
> +++ b/pack-objects.h
> @@ -207,6 +207,34 @@ static inline uint32_t pack_name_hash(const char *name)
>  	return hash;
>  }
>  
> +static inline uint32_t pack_name_hash_v2(const char *name)
> +{
> +	uint32_t hash = 0, base = 0, c;
> +
> +	if (!name)
> +		return 0;
> +
> +	while ((c = *name++)) {
> +		if (isspace(c))
> +			continue;
> +		if (c == '/') {
> +			base = (base >> 6) ^ hash;
> +			hash = 0;
> +		} else {
> +			/*
> +			 * 'c' is only a single byte. Reverse it and move
> +			 * it to the top of the hash, moving the rest to
> +			 * less-significant bits.
> +			 */
> +			c = (c & 0xF0) >> 4 | (c & 0x0F) << 4;
> +			c = (c & 0xCC) >> 2 | (c & 0x33) << 2;
> +			c = (c & 0xAA) >> 1 | (c & 0x55) << 1;
> +			hash = (hash >> 2) + (c << 24);
> +		}
> +	}
> +	return (base >> 6) ^ hash;
> +}

This works because `c` is masked before any arithmetic is performed on
it, but the cast from potentially signed char to uint32_t still makes
me nervous - if char is signed, it behaves as if it was first cast to
int32_t and only then to uint32_t, as you can see from running the code
below:

    #include <stdio.h>
    int main() {
        signed char c = 128;
        unsigned int u = c;
        printf("hello %u\n", u);
        return 0;
    }

I would declare `c` as uint8_t or unsigned char.

Junio C Hamano Dec. 10, 2024, 12:01 a.m. UTC | #5

Jonathan Tan <[e-mail]> writes:

> "Jonathan Tan via GitGitGadget" <[e-mail]> writes:
>> diff --git a/pack-objects.h b/pack-objects.h
>> index b9898a4e64b..15be8368d21 100644
>> --- a/pack-objects.h
>> +++ b/pack-objects.h
>> @@ -207,6 +207,34 @@ static inline uint32_t pack_name_hash(const char *name)
>>  	return hash;
>>  }
>>  
>> +static inline uint32_t pack_name_hash_v2(const char *name)
>> +{
>> +	uint32_t hash = 0, base = 0, c;
>> + ...
>> +	while ((c = *name++)) {
>> + ...
>> +			/*
>> +			 * 'c' is only a single byte. Reverse it and move
>> +			 * it to the top of the hash, moving the rest to
>> +			 * less-significant bits.
>> +			 */
>> +			c = (c & 0xF0) >> 4 | (c & 0x0F) << 4;
>> + ...
> This works because `c` is masked before any arithmetic is performed on
> it, but the cast from potentially signed char to uint32_t still makes
> me nervous - if char is signed, it behaves as if it was first cast to
> int32_t and only then to uint32_t, ...
> I would declare `c` as uint8_t or unsigned char.

I think you meant the type of "name", and your worry is that *name
may pick up a negative integer from there when the platform char is
signed?  Here we are dealing with a pathname that has often UTF-8
encoded non-ASCII letters with 8th bit set, and I agree with you
that being explicitly unsigned would certainly help reduce the
cognitive load.

Thanks.

Patch

diff --git a/pack-objects.h b/pack-objects.h
index b9898a4e64b..15be8368d21 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -207,6 +207,34 @@  static inline uint32_t pack_name_hash(const char *name)
 	return hash;
 }
 
+static inline uint32_t pack_name_hash_v2(const char *name)
+{
+	uint32_t hash = 0, base = 0, c;
+
+	if (!name)
+		return 0;
+
+	while ((c = *name++)) {
+		if (isspace(c))
+			continue;
+		if (c == '/') {
+			base = (base >> 6) ^ hash;
+			hash = 0;
+		} else {
+			/*
+			 * 'c' is only a single byte. Reverse it and move
+			 * it to the top of the hash, moving the rest to
+			 * less-significant bits.
+			 */
+			c = (c & 0xF0) >> 4 | (c & 0x0F) << 4;
+			c = (c & 0xCC) >> 2 | (c & 0x33) << 2;
+			c = (c & 0xAA) >> 1 | (c & 0x55) << 1;
+			hash = (hash >> 2) + (c << 24);
+		}
+	}
+	return (base >> 6) ^ hash;
+}
+
 static inline enum object_type oe_type(const struct object_entry *e)
 {
 	return e->type_valid ? e->type_ : OBJ_BAD;