Re: [PATCH v2 01/10] Define a structure for object IDs.

[Junio C Hamano <gitster@pobox.com>]

Duy Nguyen <pclouds@gmail.com> writes:

>> You mean "if it came in <pack, offset> format, convert it down to
>> <sha1> until the last second that it is needed (e.g. need to put
>> that in a tree object in order to compute the object name of the
>> containing tree object)"?
>
> I picked my words poorly. It should be <pack, the index in pack>
> instead of the _byte_ offset.

Thanks for a clarification, but I do not think it affects the main
point of the discussion very much.  If we use "union in struct",
where we can store either an SHA-1 hash or some other identifying
information for the object, but not both, then at some point you
would need to convert <pack, nth> to <sha-1> in a codepath that
needs the sha-1 hash value (e.g. if the object A, that is known to
you as <pack, nth>, is placed in a tree object B, you need the
object name of A in <sha-1> representation in order to compute the
object name of the tree object B.  You can choose to keep it in
<pack, nth> form in "struct object_id { union }" and look up the
<sha-1> from the pack index every time, or you can choose to give
up the <pack, nth> form and upgrade the "struct object_id" to store
<sha-1> at that point.

If you keep both <pack, nth> *and* <sha-1> in "struct object_id" at
the same time, you can choose whichever is convenient, but it would
bloat everything in core.  Not just it bloats "struct object" and
its subclasses, the in-core index entries, which is what I meant
by ...

>> Unless you fix that "union in struct" assumption, that is.

... this.

>> To me, <pack, offset> information smells to belong more to a "struct
>> object" (or its subclass) as an optional annotation---when a caller
>> is asked to parse_object(), you would bypass the sha1_read_file()
>> that goes and looks the object name up from the list of pack .idx
>> and instead go there straight using that annotation.
>
> For pack v4, commits and trees can be encoded this way.

Even if your in-pack representation of a commit object allowed to
store the tree pointer in <pack, nth> format, its object name must
be computed as if you have the commit object in the traditional
format and computed the hash of that (together with the standard
"<type> <size>\0" header), and at that point, you need the contained
object's name in <sha-1> format (imagine how you would implement the
commit-tree command).  Hence, I do not think the v4 encoding changes
the discussion very much.  I see the primary value of v4 encoding is
to shorten the length of various fields take on-disk and in-pack.
If it were <pack, offset>, it could be argued that it would also be
faster to get to the packed data in the packfile, and going from
<pack, nth> to the .idx file and then going to the location in the
data in the packfile would be faster than going from <sha-1> to a
particular pack and its in-pack offset, with the difference of cost
around log(n)*m where n is the number of objects in a pack and m is
the total number of packs in the repository.

It is true that <nth> format (force that the referred-to object
lives in the same pack as the referrer) can help speed up
interpretation of extended SHA-1 expression, e.g. "v1.0^0:t", which
can read v1.0 tag in v4 format, find the <nth> info for the commit
pointed by the tag and get to that data in the pack, find the <nth>
info for the top-tree recorded in that commit and directly get to
the data of that tree, and then find the entry for "t", which will
give the object name for that subtree again in <nth> format, and at
that point you can find the <sha-1> of that final object, without
having to know any object names of the intermediate objects
(i.e. you must start from <sha-1> of the tag you obtain from the
refs API, but you didn't use the object name of the commit and its
top-level tree).  So for such a codepath, I would say it would be
sufficient to use a "union in struct" people have been envisioning
and convert <pack, nth> to <sha-1> when the latter form becomes
necessary for the first time for the object.

Anyway, wouldn't this be all academic?  I do not see how you would
keep the object name in the <pack, nth> format in-core, as the
obj_hash[] is a hashtable keyed by <sha-1>, and even when we switch
to a different hash, I cannot see how such a table to ensure the
singleton-ness of in-core objects can be keyed sometimes by <hash>
and by <pack, nth> in some other time.