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

Re: A look at some alternative PACK file encodings

From
Shawn Pearce <spearce@spearce.org>
Date
Sep 7, 2006, 05:34 UTC
Message-ID
<20060907053424.GB31580@spearce.org>
In-Reply-To
<44FF5C27.2040300@gmail.com>
A Large Angry SCM <gitzilla@gmail.com> wrote:
Show 5 quoted lines
> Just looking at the structures in non-BLOBS, I see a lot of potential
> for the use of a set dictionaries when deflating TREEs and another set
> of dictionaries when deflating COMMITs and TAGs. The low hanging fruit
> is to create dictionaries of the most referenced IDs across all TREE or
> COMMIT/TAG objects.

The most referenced IDs should be getting reused through deltas. That is IDs which are highly referenced are probably referenced in the same tree over many versions of that tree. Since the data isn't changing it should be getting copied by a delta copy command rather than appearing as a literal.

The Mozilla pack appears to have the bulk of its storage taken up by blobs (both bases and deltas). I suspect this is because the bases compress to approx. 50% of their original size but share a lot of common tokens. Those common tokens are being repeated in every private zlib dictionary. The same thing happens in a delta, except here we are probably copying a lot from the base so the average size is greatly reduced but we are still repeating tokens in the zlib dictionary for anything that is a literal in the delta (as it didn't appear in the base).

A large dictionary containing all tokens for the project should greatly reduce the size of each blob, base and delta alike. It also lends itself to creating an efficient full text index.

-- 
Shawn.
Previous: Shawn PearceNext: Nicolas Pitre
Message 12 of 24 in “A look at some alternative PACK file encodings”
  1. A Large Angry SCMSep 6, 2006
  2. Jon SmirlSep 6, 2006
  3. A Large Angry SCMSep 6, 2006
  4. Linus TorvaldsSep 6, 2006
  5. Jon SmirlSep 7, 2006
  6. David LangSep 7, 2006
  7. A Large Angry SCMSep 7, 2006
  8. Linus TorvaldsSep 7, 2006
  9. Nicolas PitreSep 7, 2006
  10. Jon SmirlSep 7, 2006
  11. Shawn PearceSep 7, 2006
  12. Shawn PearceSep 7, 2006
  13. Nicolas PitreSep 7, 2006
  14. Jon SmirlSep 7, 2006
  15. Nicolas PitreSep 7, 2006
  16. A Large Angry SCMSep 7, 2006
  17. Junio C HamanoSep 7, 2006
  18. Nicolas PitreSep 7, 2006
  19. Shawn PearceSep 7, 2006
  20. Junio C HamanoSep 7, 2006
  21. Shawn PearceSep 7, 2006
  22. Junio C HamanoSep 7, 2006
  23. Shawn PearceSep 7, 2006
  24. A Large Angry SCMSep 7, 2006

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.