On 1/25/2018 5:06 PM, Junio C Hamano wrote:
Derrick Stolee <stolee@xxxxxxxxx> 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@xxxxxxxxxxxxx>
---
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:
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 <sbeller@xxxxxxxxxx> 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
