Re: [PATCH] basic threaded delta search

From: Nicolas Pitre <nico@cam.org>
Date: Sep 6, 2007, 14:48 UTC
Message-ID: <alpine.LFD.0.9999.0709061014280.21186@xanadu.home>
In-Reply-To: <7vwsv4cm6b.fsf@gitster.siamese.dyndns.org>

On Thu, 6 Sep 2007, Junio C Hamano wrote:

Show 16 quoted lines

> Nicolas Pitre <nico@cam.org> writes:
> 
> > this is still rough, hence it is disabled by default.  You need to compile
> > with "make THREADED_DELTA_SEARCH=1 ..." at the moment.
> >
> > Threading is done on different portions of the object list to be
> > deltified. This is currently done by spliting the list into n parts and
> > then a thread is spawned for each of them.  A better method would consist
> > of spliting the list into more smaller parts and have the n threads
> > pick the next part available.
> 
> Hmmm.  I wonder how the result is affected by such a partition;
> aren't you going to have many objects that could have used
> somebody else as a delta but gets stored as base because they
> happen to be a very early part of their partition (and lacking
> delta base candidates in the window)?

Yes. On a largish repo that shouldn't be significant though, not worse than repacking multiple packs into one without -f.

> You cannot solve it with
> overlapping partitions without busting the depth limit easily
> either, I suspect.

My plan is to call find_deltas() again over partition boundaries after adjacent partitions have been processed. If delta_child is properly maintained in all cases (trivial) then this should just work.

> Also how would this interact with the LRU
> delta base window we discussed a week or two ago?

This is completely orthogonal.

Show 5 quoted lines

> Separating the list into different object types would not have
> any adverse impact coming from the "horizon" of delta base
> candidates window (because we do not deltify across types), but
> that is not very useful because we cannot gain much parallerism
> from such a partition.

Indeed. Even with a straight split with equal number of objects, some threads currently complete much faster than others. This is why a more sophisticated distribution of work is still needed to keep the desired amount of threads busy all the time.

Nicolas