Re: [PATCH 01/14] graph: add packed graph design document

From: Duy Nguyen <pclouds@gmail.com>
Date: Jan 26, 2018, 14:13 UTC
Message-ID: <CACsJy8D8ofq+G8XrN-i2MTxGWESfE8_TZm6sAEJe9=mUjpipRg@mail.gmail.com>
In-Reply-To: <20180125140231.65604-2-dstolee@microsoft.com>

On Thu, Jan 25, 2018 at 9:02 PM, Derrick Stolee <stolee@gmail.com> wrote:

Show 23 quoted lines

> +Git walks the commit graph for many reasons, including:
> +
> +1. Listing and filtering commit history.
> +2. Computing merge bases.
> +
> +These operations can become slow as the commit count grows above 100K.
> +The merge base calculation shows up in many user-facing commands, such
> +as 'status' and 'fetch' and can take minutes to compute depending on
> +data shape. There are two main costs here:
> +
> +1. Decompressing and parsing commits.
> +2. Walking the entire graph to avoid topological order mistakes.
> +
> +The packed graph is a file that stores the commit graph structure along
> +with some extra metadata to speed up graph walks. This format allows a
> +consumer to load the following info for a commit:
> +
> +1. The commit OID.
> +2. The list of parents.
> +3. The commit date.
> +4. The root tree OID.
> +5. An integer ID for fast lookups in the graph.
> +6. The generation number (see definition below).

I didn't look closely to compare, but perhaps you should check out pack file format version 4 [1]. It tried to address the same thing but it never got to the point where we could replace our current pack format with it. At some point I wanted to push it even as a local optimization (pack transfer is still in old format) but I never had enough time or energy for it. How it stores commits though can probably be reused.

[1] https://github.com/pclouds/git/commit/23cb8ae5bdd968c1a290ff8d0fd7cb6b4d572a43

-- 
Duy