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

Re: Using bitmaps to accelerate fetch and clone

From
Jeff King <peff@peff.net>
Date
Sep 27, 2012, 18:52 UTC
Message-ID
<20120927185229.GD2519@sigill.intra.peff.net>
In-Reply-To
<CAJo=hJs4NXatb2vsZWWCamLGLmi+FoWkTaf3Ky-nereXkHEptA@mail.gmail.com>
On Thu, Sep 27, 2012 at 11:36:19AM -0700, Shawn O. Pearce wrote:
Show 9 quoted lines
> > Interesting. I would have assumed it depended on order in the index.
> 
> No. We tried that. Assigning bits by order in index (aka order of
> SHA-1s sorted) results in horrible compression of the bitmap itself
> because of the uniform distribution of SHA-1. Encoding instead by pack
> order gets us really good bitmap compression, because object graph
> traversal order tends to take reachability into account. So we see
> long contiguous runs of 1s and get good compression. Sorting by SHA-1
> just makes the space into swiss cheese.
Right, that makes a lot of sense.
Show 12 quoted lines
> > I think you are still OK, though, because
> > the filename comes from the sha1 over the index file, which in turn
> > includes the sha1 over the packfile. Thus any change in the packfile
> > would give you a new pack and index name.
> 
> No. The pack file name is composed from the SHA-1 of the sorted SHA-1s
> in the pack. Any change in compression settings or delta windows or
> even just random scheduling variations when repacking can cause
> offsets to slide, even if the set of objects being repacked has not
> differed. The resulting pack and index will have the same file names
> (as its the same set of objects), but the offset information and
> ordering is now different.

Are you sure? The trailer is computed over the sha1 of the actual pack data (ordering, delta choices, and all), and is computed and written to the packfile via sha1close (see pack-objects.c, ll. 753-763). That trailer sha1 is fed into finish_tmp_packfile (l. 793). That function feeds it to write_idx_file, which starts a new sha1 computation that includes the sorted sha1 list and other index info. But before we sha1close that computation, we write the _original_ trailer sha1, adding it to the new sha1 calculation. See pack-write.c, ll. 178-180.

And then that sha1 gets returned to finish_tmp_packfile, which uses it to name the resulting files.

Am I reading the code wrong?
-Peff
Previous: Shawn PearceNext: Jeff King
Message 9 of 20 in “Using bitmaps to accelerate fetch and clone”
  1. Shawn PearceSep 27, 2012
  2. Nguyen Thai Ngoc DuySep 27, 2012
  3. Shawn PearceSep 27, 2012
  4. Nguyen Thai Ngoc DuySep 28, 2012
  5. Jeff KingSep 27, 2012
  6. Shawn PearceSep 27, 2012
  7. Jeff KingSep 27, 2012
  8. Shawn PearceSep 27, 2012
  9. Jeff KingSep 27, 2012
  10. Jeff KingSep 27, 2012
  11. Junio C HamanoSep 27, 2012
  12. Jeff KingSep 27, 2012
  13. David Michael BarrSep 27, 2012
  14. Nguyen Thai Ngoc DuySep 28, 2012
  15. Nguyen Thai Ngoc DuySep 28, 2012
  16. Shawn PearceOct 1, 2012
  17. Nguyen Thai Ngoc DuyOct 1, 2012
  18. Shawn PearceOct 1, 2012
  19. Nguyen Thai Ngoc DuyOct 1, 2012
  20. Shawn PearceOct 2, 2012

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.