On Mon, 14 Oct 2013, Jeff King wrote: > On Sat, Oct 12, 2013 at 10:42:17AM +0700, Nguyen Thai Ngoc Duy wrote: > > > Just wondering if this has been considered and dropped before. > > Currently we use try_delta() for every object including trees. But > > trees are special. All tree entries must be unique and sorted. That > > helps simplify diff algorithm, as demonstrated by diff_tree() and > > pv4_encode_tree(). A quick and dirty test with test-delta shows that > > tree_diff only needs half the time of diff_delta(). As trees account > > for like half the objects in a repo, speeding up delta search might > > help performance, I think. > > No, as far as I know, it is a novel idea. When we were discussing commit > caching a while back, Shawn suggested slicing trees on boundaries and > store delta instructions that were pure "change this entry", "add this > entry", and "delete this entry" chunks. The deltas might end up a little > bigger, but if the reader knew the writer had sliced in this way, it > could get a packv4-style cheap tree-diff, while remaining backwards > compatible with implementations that just blindly reassemble the buffer > from delta instructions. > > I didn't get far enough to try it, but doing what you propose would be > the first step. Now that packv4 is more of a reality, it may not be > worth pursuing, though. The "easy" way to produce pack v2 tree objects from a pack v4 would be exactly that: take the pack v4 tree encoding and do a straight translation into delta encoding using the base from which the most entries are copied from. Nicolas -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html