Re: performance on repack

[Nicolas Pitre <nico@cam.org>]

On Wed, 15 Aug 2007, Jon Smirl wrote:

> You can avoid making all the low level calls thread safe by using the
> main thread to get everything into RAM before starting to search for
> the deltas. The worker threads would only deal with things completely
> in memory. You may need to ref count these in-memory objects if they
> are shared between worker threads. For simplicity the in-memory input
> objects should be read only by the threads. The worker threads create
> new structures to hand their results back to the main thread for
> writing to disk.
> 
> A typical solution is to use a queue protected by locks. Main thread
> faults in all the needed objects to cache. Main thread builds a queue
> entry and increments reference count on all referenced objects. Main
> thread uses locks to add entry to queue, while queue is locked it
> removes any finished jobs. Main thread writes finished results to
> disks, decrements ref counts. Cache logic can then take over about
> when objects are actually deleted.
> 
> Worker threads wait on the queue. When something is placed in the
> queue a waiting worker thread removes it, processes it, puts the
> results in RAM, and places the object back on the finished queue. Then
> waits for another object. It doesn't call into the main body of code.

Way too complex and rather unpractical with the current algorithms.

Currently, information on objects is gathered (the "Counting objects" 
phase) and that hardly can be paralleled.

Once objects are known then a sorted list is created so deltification of 
object x might be optimally attempted on objects x-1 through to x-10.  
Creating that list cannot be paralleled either, but it is quick 
anyway.

Then comes the actual deltification phase where the huge cost is. The 
problem simply has to be partitioned into a few threads, where thread 1 
deals with object 1 to 100000 from that sorted list, thread 2 has 
objects 100001 to 200000, etc. etc.  This is now a partitioning problem 
where the thread synchronization is dealt with from a higher and non 
performance critical level.


Nicolas