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

From: Junio C Hamano <gitster@pobox.com>
Date: Mar 13, 2015, 06:03 UTC
Message-ID: <xmqqwq2lzb6u.fsf@gitster.dls.corp.google.com>
In-Reply-To: <CACsJy8CMZbwyBayX-bbWmGwV=AWC000Yx6LfzOcB2irq2X6qHQ@mail.gmail.com>

Duy Nguyen <pclouds@gmail.com> writes:

Show 7 quoted lines

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

Show 7 quoted lines

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