On Mon, Aug 13, 2012 at 2:49 AM, Junio C Hamano <gits...@pobox.com> wrote:
> For example, the reachability bitmap would want to say something
> like "Traversing from commit A, these objects in this pack are
> reachable." The bitmap for one commit A would logically consist of
> N bits for a packfile that stores N objects (the resulting bitmap
> needs to be compressed before going to disk, perhaps with RLE or
> something). With the single "sorted by SHA-1" table, we can use the
> index in that single table to enumerate all reachable objects of any
> type in one go. With four separate tables, on the other hand, we
> would need four bitmaps per commit.
No we still need one per commit. The n-th bit is in the order of the
object in the pack, not the index. How sha-1 is sorted does not
> Either way is _possible_, but I think the former is simpler, and the
> latter makes it harder to introduce new types of objects in the
> future, which I do not think we have examined possible use cases
> well enough to make that decision to say "four types is enough
New types can be put in one of those four tables, depending on its
purpose. The reason I split because I care particularly about commits
and trees. If the new type serves the same purpose as tree, for
example, then it's better put in tree table...
> In either way, we would have such bitmap (or a set of four bitmaps
> in your case) for more than one commit (it is not necessary or
> desirable to add the reachability bitmap to all commits), and such a
> "reachability extension" would need to store a sequence of "the
> commit object name the bitmap (or a set of four bitmaps) is about,
> and the bitmap (or set of four bitmaps)". That object name does not
> have to be 20-byte but would be a varint representation of the
> offset into the "sorted by SHA-1" table.
How do you reach the bitmap, given its commit sha-1?
> That varint representation
> would be smaller by about 3.5 bits if you have a separate "commit
> only, sorted by SHA-1" table (as the number of all objects tend to
> be 10x larger than the number of all commits that need them). For
> the particular case of "we want to only annotate the commits, never
> other kinds of objects" use case, it would be a win. But without
> knowing what other use cases we will want to use the "object
> annotation in the pack index file" mechanism for, it feels like a
> premature optimization to me to have four tables to shave 3.5 bits
> per object.
caching trees for faster traversal in general case (sort of pack v4
but it comes as a cache instead of replacing the real pack).
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html