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

[Derrick Stolee]

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

On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee  wrote:

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 
---
  Documentation/technical/graph-format.txt | 88 

So this is different from Documentation/technical/packed-graph.txt,
which gives high level design and this gives the details on how
to set bits.


  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 00..a15e1036d7
--- /dev/null
+++ b/Documentation/technical/graph-format.txt
@@ -0,0 +1,88 @@
+Git commit graph format
+===
+
+The Git commit graph stores a list of commit OIDs and some associated
+metadata, including:
+
+- The generation number of the commit. Commits with no parents have
+  generation number 1; commits with parents have generation number
+  one more than the maximum generation number of its parents. We
+  reserve zero as special, and can be used to mark a generation
+  number invalid or as "not computed".
+
+- The root tree OID.
+
+- The commit date.
+
+- The parents of the commit, stored using positional references within
+  the graph file.
+
+== graph-*.graph files have the following format:
+
+In order to allow extensions that add extra data to the graph, we organize
+the body into "chunks" and provide a binary lookup table at the beginning
+of the body. The header includes certain values, such as number of chunks,
+hash lengths and types.
+
+All 4-byte numbers are in network order.
+
+HEADER:
+
+   4-byte signature:
+   The signature is: {'C', 'G', 'P', 'H'}
+
+   1-byte version number:
+   Currently, the only valid version is 1.
+
+   1-byte Object Id Version (1 = SHA-1)
+
+   1-byte Object Id Length (H)

   This is 20 or 40 for sha1 ? (binary or text representation?)


20 for binary.




+   1-byte number (C) of "chunks"
+
+CHUNK LOOKUP:
+
+   (C + 1) * 12 bytes listing the table of contents for the chunks:
+   First 4 bytes describe chunk id. Value 0 is a terminating label.
+   Other 8 bytes provide offset in current file for chunk to start.

... offset [in bytes/words/4k blocks?] in ...


bytes.




+   (Chunks are ordered contiguously in the file, so you can infer
+   the length using the next chunk position if necessary.)
+
+   The remaining data in the body is described one chunk at a time, and
+   these chunks may be given in any order. Chunks are required unless
+   otherwise specified.
+
+CHUNK DATA:
+
+   OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)
+   The ith entry, F[i], stores the number of OIDs with first
+   byte at most i. Thus F[255] stores the total
+   number of commits (N).

So F[0] > 0 for git.git for example.

Or another way: To lookup a 01xxx, I need to look at
entry(F[00] + 1 )...entry(F[01]).

Makes sense.


+
+   OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)
+   The OIDs for all commits in the graph.

... sorted ascending.



+   Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)
+   * The first H bytes are for the OID of the root tree.
+   * The next 8 bytes are for the int-ids of the first two parents of
+ the ith commit. Stores value 0x if no parent in that 
position.
+ If there are more than two parents, the second value has its most-
+ significant bit on and the other bits store an offset into the 
Large
+ Edge List chunk.

s/an offset into/position in/ ? (otherwise offset in bytes?)


+   * The next 8 bytes store the generation number of the commit and the
+ commit time in seconds since EPOCH. The generation number uses the
+ higher 30 bits of the first 4 bytes, while the commit time uses 
the
+ 32 bits of the second 4 bytes, along with the lowest 2 bits of the
+ lowest byte, storing the 33rd and 34th bit of the commit time.

This allows for a maximum generation number of
1.073.741.823 (2^30 -1) = 1 billion,
and a max time stamp of later than 2100.

Do you allow negative time stamps?



+
+   [Optional] Large Edge List (ID: {'E', 'D', 'G', 'E'})
+   This list of 4-byte values store the second through nth parents for
+   all octoput merges. The second parent value in the commit 

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

[Derrick Stolee]

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

Derrick Stolee  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 
---
  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 00..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:


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:

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:

Stefan Beller  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

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

[Junio C Hamano]

Stefan Beller  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").

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

[Stefan Beller]

On Thu, Jan 25, 2018 at 2:06 PM, Junio C Hamano  wrote:
> Derrick Stolee  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 
>> ---
>>  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 00..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 ;-)
>
> 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?

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 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).

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

[Stefan Beller]

On Thu, Jan 25, 2018 at 6:02 AM, Derrick Stolee  wrote:
> 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 
> ---
>  Documentation/technical/graph-format.txt | 88 
> 

So this is different from Documentation/technical/packed-graph.txt,
which gives high level design and this gives the details on how
to set bits.

>  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 00..a15e1036d7
> --- /dev/null
> +++ b/Documentation/technical/graph-format.txt
> @@ -0,0 +1,88 @@
> +Git commit graph format
> +===
> +
> +The Git commit graph stores a list of commit OIDs and some associated
> +metadata, including:
> +
> +- The generation number of the commit. Commits with no parents have
> +  generation number 1; commits with parents have generation number
> +  one more than the maximum generation number of its parents. We
> +  reserve zero as special, and can be used to mark a generation
> +  number invalid or as "not computed".
> +
> +- The root tree OID.
> +
> +- The commit date.
> +
> +- The parents of the commit, stored using positional references within
> +  the graph file.
> +
> +== graph-*.graph files have the following format:
> +
> +In order to allow extensions that add extra data to the graph, we organize
> +the body into "chunks" and provide a binary lookup table at the beginning
> +of the body. The header includes certain values, such as number of chunks,
> +hash lengths and types.
> +
> +All 4-byte numbers are in network order.
> +
> +HEADER:
> +
> +   4-byte signature:
> +   The signature is: {'C', 'G', 'P', 'H'}
> +
> +   1-byte version number:
> +   Currently, the only valid version is 1.
> +
> +   1-byte Object Id Version (1 = SHA-1)
> +
> +   1-byte Object Id Length (H)

  This is 20 or 40 for sha1 ? (binary or text representation?)

> +   1-byte number (C) of "chunks"
> +
> +CHUNK LOOKUP:
> +
> +   (C + 1) * 12 bytes listing the table of contents for the chunks:
> +   First 4 bytes describe chunk id. Value 0 is a terminating label.
> +   Other 8 bytes provide offset in current file for chunk to start.

... offset [in bytes/words/4k blocks?] in ...


> +   (Chunks are ordered contiguously in the file, so you can infer
> +   the length using the next chunk position if necessary.)
> +
> +   The remaining data in the body is described one chunk at a time, and
> +   these chunks may be given in any order. Chunks are required unless
> +   otherwise specified.

> +
> +CHUNK DATA:
> +
> +   OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)
> +   The ith entry, F[i], stores the number of OIDs with first
> +   byte at most i. Thus F[255] stores the total
> +   number of commits (N).

So F[0] > 0 for git.git for example.

Or another way: To lookup a 01xxx, I need to look at
entry(F[00] + 1 )...entry(F[01]).

Makes sense.

> +
> +   OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)
> +   The OIDs for all commits in the graph.

... sorted ascending.


> +   Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)
> +   * The first H bytes are for the OID of the root tree.
> +   * The next 8 bytes are for the int-ids of the first two parents of
> + the ith commit. Stores value 0x if no parent in that 
> position.
> + If there are more than two parents, the second value has its 
> most-
> + significant bit on and the other bits store an offset into the 
> Large
> + Edge List chunk.

s/an offset into/position in/ ? (otherwise offset in bytes?)

> +   * The next 8 bytes store the generation number of the commit and 
> the
> + commit time in seconds since EPOCH. The generation number uses 
> the
> + higher 30 bits of the first 4 bytes, while the commit time uses 
> the
> + 32 bits of the second 4 bytes, along with the lowest 2 bits of 
> the
> + lowest byte, storing the 33rd and 34th bit of the commit time.

This allows for a maximum generation number of
1.073.741.823 (2^30 -1) = 1 billion,
and a max time stamp of later than 2100.

Do you allow negative time stamps?


> +
> +   [Optional] Large Edge List (ID: {'E', 'D', 'G', 'E'})
> +  

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

[Junio C Hamano]

Derrick Stolee  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 
> ---
>  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 00..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 ;-)

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?

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?

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

[Derrick Stolee]

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 
---
 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 00..a15e1036d7
--- /dev/null
+++ b/Documentation/technical/graph-format.txt
@@ -0,0 +1,88 @@
+Git commit graph format
+===
+
+The Git commit graph stores a list of commit OIDs and some associated
+metadata, including:
+
+- The generation number of the commit. Commits with no parents have
+  generation number 1; commits with parents have generation number
+  one more than the maximum generation number of its parents. We
+  reserve zero as special, and can be used to mark a generation
+  number invalid or as "not computed".
+
+- The root tree OID.
+
+- The commit date.
+
+- The parents of the commit, stored using positional references within
+  the graph file.
+
+== graph-*.graph files have the following format:
+
+In order to allow extensions that add extra data to the graph, we organize
+the body into "chunks" and provide a binary lookup table at the beginning
+of the body. The header includes certain values, such as number of chunks,
+hash lengths and types.
+
+All 4-byte numbers are in network order.
+
+HEADER:
+
+   4-byte signature:
+   The signature is: {'C', 'G', 'P', 'H'}
+
+   1-byte version number:
+   Currently, the only valid version is 1.
+
+   1-byte Object Id Version (1 = SHA-1)
+
+   1-byte Object Id Length (H)
+
+   1-byte number (C) of "chunks"
+
+CHUNK LOOKUP:
+
+   (C + 1) * 12 bytes listing the table of contents for the chunks:
+   First 4 bytes describe chunk id. Value 0 is a terminating label.
+   Other 8 bytes provide offset in current file for chunk to start.
+   (Chunks are ordered contiguously in the file, so you can infer
+   the length using the next chunk position if necessary.)
+
+   The remaining data in the body is described one chunk at a time, and
+   these chunks may be given in any order. Chunks are required unless
+   otherwise specified.
+
+CHUNK DATA:
+
+   OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes)
+   The ith entry, F[i], stores the number of OIDs with first
+   byte at most i. Thus F[255] stores the total
+   number of commits (N).
+
+   OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes)
+   The OIDs for all commits in the graph.
+
+   Commit Data (ID: {'C', 'G', 'E', 'T' }) (N * (H + 16) bytes)
+   * The first H bytes are for the OID of the root tree.
+   * The next 8 bytes are for the int-ids of the first two parents of
+ the ith commit. Stores value 0x if no parent in that 
position.
+ If there are more than two parents, the second value has its most-
+ significant bit on and the other bits store an offset into the 
Large
+ Edge List chunk.
+   * The next 8 bytes store the generation number of the commit and the
+ commit time in seconds since EPOCH. The generation number uses the
+ higher 30 bits of the first 4 bytes, while the commit time uses 
the
+ 32 bits of the second 4 bytes, along with the lowest 2 bits of the
+ lowest byte, storing the 33rd and 34th bit of the commit time.
+
+   [Optional] Large Edge List (ID: {'E', 'D', 'G', 'E'})
+   This list of 4-byte values store the second through nth parents for
+   all octoput merges. The second parent value in the commit data is a
+   negative number pointing into this list. Then iterate through this
+   list starting at that position until reaching a value with the most-
+   significant bit on. The other bits correspond to the int-id of the
+   last parent.
+
+TRAILER:
+
+   H-byte HASH-checksum of all of the above.
-- 
2.16.0