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