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

Re: [PATCH 4/6] introduce a commit metapack

From
Jeff King <peff@peff.net>
Date
Mar 18, 2013, 12:20 UTC
Message-ID
<20130318122011.GE14789@sigill.intra.peff.net>
In-Reply-To
<CACsJy8CPXFhUYz2f1wuxJvqwknJr5VFNFrs3b_4pS14cxf=3Wg@mail.gmail.com>
On Sun, Mar 17, 2013 at 08:21:13PM +0700, Nguyen Thai Ngoc Duy wrote:
Show 21 quoted lines
> On Thu, Jan 31, 2013 at 6:06 PM, Duy Nguyen <pclouds@gmail.com> wrote:
> > On Wed, Jan 30, 2013 at 09:16:29PM +0700, Duy Nguyen wrote:
> >> Perhaps we could store abbrev sha-1 instead of full sha-1. Nice
> >> space/time trade-off.
> >
> > Following the on-disk format experiment yesterday, I changed the
> > format to:
> >
> >  - a list a _short_ SHA-1 of cached commits
> > ..
> >
> > The length of SHA-1 is chosen to be able to unambiguously identify any
> > cached commits. Full SHA-1 check is done after to catch false
> > positives. For linux-2.6, SHA-1 length is 6 bytes, git and many
> > moderate-sized projects are 4 bytes.
> 
> And if we are going to create index v3, the same trick could be used
> for the sha-1 table in the index. We use the short sha-1 table for
> binary search and put the rest of sha-1 in a following table (just
> like file offset table). The advantage is a denser search space, about
> 1/4-1/3 the size of full sha-1 table.
You can make it even smaller at some (potential) run-time cost.

Keep in mind you are just repeating information that is in the full sha1 list in the index. So you could store a fixed-size offset into that list (e.g., 32-bit), and then instead of comparing sha1s during a binary search, you would dereference the offset to the real sha1s and compare those.

The run-time cost is not any worse in a big-O sense, but your cache locality is much worse (you hit a second random page for each sha1 comparison), which might be noticeable. You'd have to benchmark to see how big an impact.

-Peff
Previous: Duy NguyenNext: Jeff King
Message 34 of 43 in “commit caching”
  1. 0/6 commit cachingJeff King, Jan 29, 2013
  2. 1/6 csum-file: make sha1write const-correctJeff King, Jan 29, 2013
  3. 2/6 strbuf: add string-chomping functionsJeff King, Jan 29, 2013
  4. Michael HaggertyJan 29, 2013
  5. Jeff KingJan 29, 2013
  6. Michael HaggertyJan 30, 2013
  7. 3/6 introduce pack metadata cache filesJeff King, Jan 29, 2013
  8. Junio C HamanoJan 29, 2013
  9. Jeff KingJan 30, 2013
  10. Duy NguyenJan 30, 2013
  11. Jeff KingJan 30, 2013
  12. 4/6 introduce a commit metapackJeff King, Jan 29, 2013
  13. Michael HaggertyJan 29, 2013
  14. Jeff KingJan 29, 2013
  15. Junio C HamanoJan 29, 2013
  16. Junio C HamanoJan 29, 2013
  17. Jeff KingJan 30, 2013
  18. Junio C HamanoJan 30, 2013
  19. Jeff KingFeb 1, 2013
  20. Junio C HamanoJan 30, 2013
  21. Shawn PearceJan 31, 2013
  22. Jeff KingFeb 1, 2013
  23. Junio C HamanoFeb 2, 2013
  24. Jeff KingJan 30, 2013
  25. Duy NguyenJan 30, 2013
  26. Jeff KingJan 30, 2013
  27. Duy NguyenJan 30, 2013
  28. Duy NguyenJan 30, 2013
  29. Duy NguyenJan 31, 2013
  30. Jeff KingFeb 1, 2013
  31. Duy NguyenFeb 2, 2013
  32. Jeff KingFeb 1, 2013
  33. Duy NguyenMar 17, 2013
  34. Jeff KingMar 18, 2013
  35. Jeff KingFeb 1, 2013
  36. 5/6 add git-metapack commandJeff King, Jan 29, 2013
  37. 6/6 commit: look up commit info in metapackJeff King, Jan 29, 2013
  38. Duy NguyenJan 30, 2013
  39. Jeff KingJan 30, 2013
  40. Duy NguyenJan 30, 2013
  41. Shawn PearceJan 31, 2013
  42. Jeff KingFeb 1, 2013
  43. Shawn PearceFeb 2, 2013

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.