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

Re: [RFC] Packing large repositories

From
Shawn O. Pearce <spearce@spearce.org>
Date
Apr 3, 2007, 05:39 UTC
Message-ID
<20070403053959.GH15922@spearce.org>
In-Reply-To
<64E16DEF-E572-4384-9E68-42EBBCE678B1@adacore.com>
Geert Bosch <bosch@adacore.com> wrote:
Show 9 quoted lines
> Actually, I had implemented this first, using two newton-raphson
> iterations and then binary search. With just one iteration is
> too little, and one iteration+binary search often is no win.
> Two iterations followed by binary search cuts the nr of steps in
> half for the Linux kernel. Two iterations followed by linear search
> is often worse, because of "unlucky" cases that end up doing many
> probes. Still, during the 5-8 probes in moderately large repositories
> (1M objects), each probe pretty much requires its own cache line:
> very cache unfriendly.

If Nico and I can ever find the time to get our ideas for pack v4 coded into something executable, I think you will find this is less of an issue than you think.

We're hoping to change enough of the commit and tree traversal code that the "tight" loops around chasing tree, parent, and blob pointers can be done using strictly pack offsets and completely avoid these SHA-1 lookups. Thus the only time we'd fall into the above-mentioned SHA-1 lookup path is on initial entry to a revision walk, or when spanning to another packfile. This would mean most workloads should only hit that code once per command line argument.

-- 
Shawn.
Previous: Geert BoschNext: Nicolas Pitre
Message 12 of 15 in “[RFC] Packing large repositories”
  1. Dana HowMar 28, 2007
  2. Linus TorvaldsMar 28, 2007
  3. Shawn O. PearceMar 30, 2007
  4. Nicolas PitreMar 30, 2007
  5. Geert BoschMar 31, 2007
  6. Linus TorvaldsMar 31, 2007
  7. Nicolas PitreMar 31, 2007
  8. Junio C HamanoMar 31, 2007
  9. Linus TorvaldsMar 31, 2007
  10. Linus TorvaldsMar 31, 2007
  11. Geert BoschApr 2, 2007
  12. Shawn O. PearceApr 3, 2007
  13. Nicolas PitreMar 31, 2007
  14. Dana HowApr 2, 2007
  15. Sam VilainApr 2, 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.