Re: pack-object's try_delta fast path for v2 trees?

From: Nicolas Pitre <nico@fluxnic.net>
Date: Oct 12, 2013, 14:52 UTC
Message-ID: <alpine.LFD.2.03.1310121042290.3023@syhkavp.arg>
In-Reply-To: <CACsJy8Behb7PW=pFjH=wpjfHjUiyCo8n_ER+KyzcBwCzpyG6pg@mail.gmail.com>

On Sat, 12 Oct 2013, Duy Nguyen wrote:

Show 10 quoted lines

> Hi,
> 
> 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.

Fortaking advantage of the sorted nature of tree objects, you need to actually parse those objects to determine tree entry boundaries. The delta diff code doesn't parse anything and simply do a search into a binary buffer which may or may not end up slicing that buffer on actual tree entry boundaries.

So this could help somewhat, however the need for pre-parsing those tree objects is probably going to counter-balance all the performance gain you might get.

I think the potential for improvements would be greater by moving to pack v4 (when the right algorithm is in place that is). Eventually the proper pack v4 tree delta diffing code could be made to serve the pack v2 case as well.

Nicolas