I think the pack v4 format and compatibility code is pretty stable now, 
and probably as optimal as it can reasonably be.

@Junio: might be a good idea to refresh your pu branch again.

Now the biggest problem to solve is the actual tree 
"deltification".  I don't have the time to spend on this otherwise very 
interesting problem (IMHO at least) so I'm sending this request for help 
in the hope that more people would be keen to contribute their computing 
skills to solve this challenge.

I'll make a quick description of the pv4 tree encoding first and explain 
the problem to solve afterwards.

A pv4 tree is comprised of two types of records: immediate tree entry 
and tree sequence copy.

1) Immediate Tree Entry

This is made of the following tuple:

        <path component index>,{SHA1 reference index>

The path component index refers to the path dictionary table where path 
strings and file modes are uniquely stored.  The SHA1 index refers to 
the sorted SHA1 table as previously found in the pack index but which is 
now part of the pack file itself.  So on average a single tree entry may 
take between 1 to 2 bytes for the path component index and 1 to 3 bytes 
for the SHA1 index.

2) Tree Sequence Copy

This is used to literally copy a contiguous list of tree entries from 
another tree object.  This goes as follows:

        <tree entry where to start>,<number of entries to copy>
        [,<SHA1 index of the object to copy from>]

So instead of having arbitrary copying of data like in delta objects, we 
refer directly to tree entries in another object.  The big advantage 
here is that the tree walker may directly jump to the copied object 
without having to do any delta patching and caching. The SHA1 index is 
optional if it refers to the same copied object as the previous tree 
sequence copy record in this tree object.  And another possible 
optimization for the tree walker when enumerating objects is to skip the 
copy entry entirely if the object being copied from has already been 

The size of this entry is more variable and is typically between 1 to 2 
bytes for the start index, 1 to 2 bytes for the copy size, and 0 to 3 
bytes for the SHA1 index.

So... what to do with this?

Currently the "deltification" is achieved using a pretty dumb heuristic 
which is to simply take each tree object in a pack v2 with their 
corresponding base delta object and perform a straight conversion into 
pack v4 tree format i.e. use copy records whenever possible as long as 
they represent a space saving over the corresponding immediate tree 
entries (which is normally the case).

However this is rather sub-optimal for two reasons:

1) This doesn't benefit from the ability to use multiple base objects to 
   copy from and is potentially missing on additional opportunities for 
   copy sequences which are not possible in the selected base object 
   from the pack v2 delta base selection. Pack v4 is already quite 
   smaller than pack v2 yet it might possibly be smaller still.

2) This makes deep delta chains very inefficient at runtime when the 
   pack is subsequently accessed.

Let's consider this example to fully illustrate #2.

        Tree A:
        entry 0:        "foo.txt"
        entry 1-3:      copy from tree B: start=2 count=3

        Tree B:
        entry 0-5:      copy from tree C: start=2 count=5
        entry 6:        "bar.txt"

        Tree C:
        entry 0:        "file_a"
        entry 1:        "file_b"
        entry 2:        "file_c"
        entry 3:        "file_D"
        entry 4:        "file_E"
        entry 5:        "file_F"
        entry 6:        "file_G"

This is a good example of what typically happens when the above heuristic 
is applied.  And it is not uncommon to see a long indirection chain of 
"copy those 2 entries from that other object" sometimes reaching 50 
levels deep where the same 2 (or more) entries require up to 50 object 
hops before they can be obtained.

Obviously here the encoding should be optimized to reduce the chaining 
effect simply by referring to the final object directly.  Hence tree A 
could be encoded as follows:

        Tree A:
        entry 0:        "foo.txt"
        entry 1-3:      copy from tree C: start=4 count=3

The on-disk encoding is likely to be the same size but the runtime 
access is greatly optimized.

Now... instead of trying to do reference simplification by factoring out 
the chain effect, I think a whole new approach to tree delta compression 
for pack v4 should be developed which would also address issue #1 above.

For example, we may try to make each canonical tree objects into 
sequences of hashed tree entries in memory where each tree entry would 
be reduced down to a single CRC32 value (or even Adler32 for speed).  
Each tree object would then be represented by some kind of 32-bit 
character "string".  Then it is just a matter of applying substring 
matching algorithms to find the best copy sequences without creating 
reference cycles, weighted by the number of indirections involved when 
a referred object already has a copy sequence covering part or all of 
the matched string. Etc.

Or that can be something else entirely.  Certainly there are similar 
problems already solved in the literature somewhere.

And it has to be _fast_.

So if someone is on the lookout for a nice algorithmic and coding 
challenge then here's your opportunity!


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

Reply via email to