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

Re: Using bitmaps to accelerate fetch and clone

From
Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Date
Oct 1, 2012, 01:59 UTC
Message-ID
<CACsJy8D5AXSWAdK7tgtXnE4Ro_+okaYM=zf9JnQfObkcx=FCOw@mail.gmail.com>
In-Reply-To
<CAJo=hJsWczUqhvj6Kqsomeh9WxAAJO-Yc-=61k94jos6vVtEjQ@mail.gmail.com>
On Mon, Oct 1, 2012 at 8:07 AM, Shawn Pearce <spearce@spearce.org> wrote:
Show 7 quoted lines
>> You mentioned this before in your idea mail a while back. I wonder if
>> it's worth storing bitmaps for all packs, not just the self contained
>> ones.
>
> Colby and I started talking about this late last week too. It seems
> feasible, but does add a bit more complexity to the algorithm used
> when enumerating.

Yes. Though at server side, if it's too much trouble, the packer can just ignore open packs and use only closed ones.

Show 9 quoted lines
>> We could have one leaf bitmap per pack to mark all leaves where
>> we'll need to traverse outside the pack. Commit leaves are the best as
>> we can potentially reuse commit bitmaps from other packs. Tree leaves
>> will be followed in the normal/slow way.
>
> Yes, Colby proposed the same idea.
>
> We cannot make a "leaf bitmap per pack". The leaf SHA-1s are not in
> the pack and therefore cannot have a bit assigned to them.

We could mark all objects _in_ the pack that lead to an external object. That's what I meant by leaves. We need to parse the leaves to find out actual SHA-1s that are outside the pack. Or we could go with your approach below too.

> We could
> add a new section that listed the unique leaf SHA-1s in their own
> private table, and then assigned per bitmap a leaf bitmap that set to
> 1 for any leaf object that is outside of the pack.
Show 10 quoted lines
> One of the problems we have seen with these non-closed packs is they
> waste an incredible amount of disk. As an example, do a `git fetch`
> from Linus tree when you are more than a few weeks behind. You will
> get back more than 100 objects, so the thin pack will be saved and
> completed with additional base objects. That thin pack will go from a
> few MiBs to more than 40 MiB of data on disk, thanks to the redundant
> base objects being appended to the end of the pack. For most uses
> these packs are best eliminated and replaced with a new complete
> closure pack. The redundant base objects disappear, and Git stops
> wasting a huge amount of disk.

That's probably a different problem. I appreciate disk savings but I would not want to wait a few more minutes for repack on every git-fetch. But if this bitmap thing makes repack much faster than currently, repacking after every git-fetch may become practical.

-- 
Duy
Previous: Shawn PearceNext: Shawn Pearce
Message 17 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.