Re: [PATCH 04/14] packed-graph: add format document

From: Derrick Stolee <stolee@gmail.com>
Date: Jan 26, 2018, 13:22 UTC
Message-ID: <c6ccbd6f-ef97-3240-7cdc-6ef7a3f95cf6@gmail.com>
In-Reply-To: <xmqqmv118tde.fsf@gitster.mtv.corp.google.com>

On 1/25/2018 5:06 PM, Junio C Hamano wrote:

Show 35 quoted lines

> Derrick Stolee <stolee@gmail.com> writes:
>
>> Add document specifying the binary format for packed graphs. This
>> format allows for:
>>
>> * New versions.
>> * New hash functions and hash lengths.
>> * Optional extensions.
>>
>> Basic header information is followed by a binary table of contents
>> into "chunks" that include:
>>
>> * An ordered list of commit object IDs.
>> * A 256-entry fanout into that list of OIDs.
>> * A list of metadata for the commits.
>> * A list of "large edges" to enable octopus merges.
>>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>> ---
>>   Documentation/technical/graph-format.txt | 88 ++++++++++++++++++++++++++++++++
>>   1 file changed, 88 insertions(+)
>>   create mode 100644 Documentation/technical/graph-format.txt
>>
>> diff --git a/Documentation/technical/graph-format.txt b/Documentation/technical/graph-format.txt
>> new file mode 100644
>> index 0000000000..a15e1036d7
>> --- /dev/null
>> +++ b/Documentation/technical/graph-format.txt
>> @@ -0,0 +1,88 @@
>> +Git commit graph format
>> +=======================
> Good that this is not saying "graph format" but is explicit that it
> is about "commit".  Do the same for the previous steps.  Especially,
> builtin/graph.c that does not have much to do with graph.c is not a
> good way forward ;-)

:+1:

Show 9 quoted lines

> I do like the fact that later parents of octopus merges are moved
> out of way to make the majority of records fixed length, but I am
> not sure if the "up to two parents are recorded in line" is truly
> the best arrangement.  Aren't majority of commits single-parent,
> thereby wasting 4 bytes almost always?
>
> Will 32-bit stay to be enough for everybody?  Wouldn't it make sense
> to at least define them to be indices into arrays (i.e. scaled to
> element size), not "offsets", to recover a few lost bits?

I incorrectly used the word "offset" when I mean "array position" for the edge values.

> What's the point of storing object id length?  If you do not
> understand the object ID scheme, knowing only the length would not
> do you much good anyway, no?  And if you know the hashing scheme
> specified by Object ID version, you already know the length, no?

I'll go read the OID transition document to learn more, but I didn't know if there were plans for things like "Use SHA3 but with different hash lengths depending on user requirements". One side benefit is that we immediately know the width of our commit and tree references within the commit graph file without needing to consult a table of hash definitions.

On 1/25/2018 5:18 PM, Stefan Beller wrote:

Show 8 quoted lines

> git.git has ~37k non-merge commits and ~12k merge commits,
> (35 of them have 3 or more parents).
>
> So 75% would waste the 4 bytes of the second parent.
>
> However the first parent is still there, so any operation that only needs
> the first parent (git bisect --first-parent?) would still be fast.
> Not sure if that is common.

The current API boundary does not support this, as parse_commit_gently() is not aware of the --first-parent option. The benefits of injecting that information are probably not worth the complication.

On 1/25/2018 5:29 PM, Junio C Hamano wrote:

Show 9 quoted lines

> Stefan Beller <sbeller@google.com> writes:
>
>> The downside of just having one parent or pointer into the edge list
>> would be to penalize 25% of the commit lookups with an indirection
>> compared to ~0% (the 35 octopus'). I'd rather want to optimize for
>> speed than disk size? (4 bytes for 37k is 145kB for git.git, which I
>> find is not a lot).
> My comment is not about disk size but is about the size of working
> set (or "size of array element").

I do want to optimize for speed over space, at least for two-parent commits. Hopefully my clarification about offset/array position clarifies Junio's concerns here.

Thanks, -Stolee