Re: Thoughts about memory requirements in traversals [Was: Re: [RFC] Submodules in GIT]

On Sunday 03 December 2006 03:46, Shawn Pearce wrote:

Josef Weidendorfer [off-list ref] wrote:

quoted

Thinking even one step further:
Would it make sense to define an encoding format for the content of
commit and tree objects inside of packs, where the SHA1 is replaced by the
offset of the object in this pack?
As exactly the SHA1 is the least compressable thing, this could promise
quite a benefit.

[...]

This means that when we start to write out a commit we need to know
the offset to the tree that commit references.  But git-pack-objects
sorts object by type: commit, tree, blob (I forget where tags go,
but they aren't important in this context).  So generally *all*
commits appear before the first tree.  So when we write out the first
commit we need to know exactly how many bytes every commit will need
(compressed mind you) in this pack so we can determine the position
of the first tree.  Now do this for every commit and every tree
that those commits use...  yes, its a lot of work to precompute
and store all offsets before you even write out the first byte.

Yes, it looks like a hen-and-egg problem, but IMHO you can
handle it nicely with another redirection, i.e. a table you build
up while repacking the file, and storing this table at the end.

You simply sequentially renumber any object SHA, starting from 0
in the order you see them. You can do two renumberings, one for
the objects contained in the original pack (1), and one for the
external ones (2). Put these new numbers (with a bit distinguishing
(1) and (2)) as replacement into commit/tree objects.
At the end, you have the new offsets for objects in (1). Put
redirection tables for (1) [new number -> new offset]
and (2) [other new number->SHA1 of external object] at the end
of the new pack.
This way, you effectivly have removed all incompressable SHAs from
the pack file aside from one entry in the redirection tables for
each external object.

The only problem I see is how to decode the objects, i.e. how to
get the original SHA1 from an offset: we can not recalculate the
SHA1 from the object content as we changed the content itself.
But there should be a way to store the SHA1 in front of the object
somehow, perhaps it is already given by the current format? 

Am I missing something here?