git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: performance on repack

From
Nicolas Pitre <nico@cam.org>
Date
Aug 15, 2007, 21:05 UTC
Message-ID
<alpine.LFD.0.999.0708151650270.5415@xanadu.home>
In-Reply-To
<9e4733910708150808x39241071j1a4012f16cd26ef8@mail.gmail.com>
On Wed, 15 Aug 2007, Jon Smirl wrote:
Show 21 quoted lines
> 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
Previous: Nicolas PitreNext: Nicolas Pitre
Message 25 of 30 in “performance on repack”
  1. Jon SmirlAug 11, 2007
  2. David KastrupAug 11, 2007
  3. Linus TorvaldsAug 11, 2007
  4. Jon SmirlAug 11, 2007
  5. Martin KoeglerAug 12, 2007
  6. Jon SmirlAug 12, 2007
  7. Shawn O. PearceAug 14, 2007
  8. Jon SmirlAug 14, 2007
  9. Shawn O. PearceAug 14, 2007
  10. Jon SmirlAug 14, 2007
  11. Nicolas PitreAug 14, 2007
  12. Nicolas PitreAug 14, 2007
  13. Jon SmirlAug 15, 2007
  14. Nicolas PitreAug 15, 2007
  15. Shawn O. PearceAug 15, 2007
  16. Jon SmirlAug 15, 2007
  17. Martin KoeglerAug 15, 2007
  18. Jon SmirlAug 15, 2007
  19. Nicolas PitreAug 15, 2007
  20. Jon SmirlAug 15, 2007
  21. David KastrupAug 16, 2007
  22. Nicolas PitreAug 16, 2007
  23. Jon SmirlAug 16, 2007
  24. Nicolas PitreAug 16, 2007
  25. Nicolas PitreAug 15, 2007
  26. Nicolas PitreAug 15, 2007
  27. Nicolas PitreAug 30, 2007
  28. Nicolas PitreAug 30, 2007
  29. Jon SmirlAug 30, 2007
  30. Jon SmirlSep 1, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.