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

> This series creates a mechanism to select alternative name hashes using a
> new --name-hash-version=<n> option. The versions are:
>
>  1. Version 1 is the default name hash that already exists. This option
>     focuses on the final bytes of the path to maximize locality for
>     cross-path deltas.
>
>  2. Version 2 is the new path-component hash function suggested by Jonathan
>     Tan in the previous version (with some modifications). This hash
>     function essentially computes the v1 name hash of each path component
>     and then overlays those hashes with a shift to make the parent
>     directories contribute less to the final hash, but enough to break many
>     collisions that exist in v1.
>
>  3. Version 3 is the hash function that I submitted under the
>     --full-name-hash feature in the previous versions. This uses a
>     pseudorandom hash procedure to minimize collisions but at the expense of
>     losing on locality. This version is implemented in the final patch of
>     the series mostly for comparison purposes, as it is unlikely to be
>     selected as a valuable hash function over v2. The final patch could be
>     omitted from the merged version.
>
> See the patches themselves for detailed results in the p5313-pack-objects.sh
> performance test and the p5314-name-hash.sh test that demonstrates how many
> collisions occur with each hash function.

> In general, the v2 name hash function gets very close to the compression
> results of v3 in the full repack case, even in the repositories that feature
> many name hash collisions. These benefits come as well without downsides to
> other kinds of packfiles, including small pushed packs, larger incremental
> fetch packs, and shallow clones.

> As we can see, v2 nearly reaches the effectiveness of v3 (and outperforms it
> once!) but there is still a significant change between the
> --name-hash-version feature and the --path-walk feature.
>
> The main reason we are considering this --name-hash-version feature is that
> it has the least amount of stretch required in order for it to be integrated
> with reachability bitmaps, required for server environments. In fact, the
> change in this version to use a numerical version makes it more obvious how
> to connect the version number to a value in the .bitmap file format. Tests
> are added to guarantee that the hash functions preserve their behavior over
> time, since data files depend on that.