Re: [PATCH 0/7] pack-objects: Create an alternative name hash algorithm (recreated)

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 22, 2024, 03:01 UTC
Message-ID: <xmqqiksgas54.fsf@gitster.g>
In-Reply-To: <20241121235014.2554033-1-jonathantanmy@google.com>

Jonathan Tan <jonathantanmy@google.com> writes:

Show 13 quoted lines

> +       while ((c = (uint8_t) *name++) != 0) {
> +               if (isspace(c))
> +                       continue;
> +               if (c == '/') {
> +                       base = (base >> 6) ^ hash;
> +                       hash = 0;
> +               } else {
> +                       uint8_t nybble_swapped = (c >> 4) + ((c & 15) << 4);
> +                       hash = (hash >> 2) + (nybble_swapped << 24);
> +               }
>         }
> +       return (base >> 6) ^ hash;
>  }

Nice. The diff relative to the --full-name-hash version is a bit hard to grok, but compared to the current hash function, there are two and a half changes that matter:

 (0) it is more careful with bytes with the MSB set (i.e. non-ASCII
     pathnames).

 (1) it hashes each path component separetely and rotates the whole
     thing only at a directory boundary.  I'd imagine that this
     would make a big difference for languages that force overly
     long filenames at each level.

 (2) it gives more weight to lower bits by swapping nybbles of each
     byte.

I wonder if we do even better if we reverse all 8 bits instead of swapping nybbles (if we were to do so, it might be more efficient to shift in from the right instead of left end of the base and hash accumulators in the loop and then swap the whole resulting word at the end).

Thanks for a fun read.