From: Josef Wolf <jw@raven.inka.de>
To: git@vger.kernel.org
Subject: Re: Re-Transmission of blobs?
Date: Fri, 13 Sep 2013 12:09:35 +0200 [thread overview]
Message-ID: <20130913100934.GE14259@raven.wolf.lan> (raw)
In-Reply-To: <20130912194453.GD32069@sigill.intra.peff.net>
On Thu, Sep 12, 2013 at 03:44:53PM -0400, Jeff King wrote:
> On Thu, Sep 12, 2013 at 12:35:32PM +0200, Josef Wolf wrote:
>
> > I'm not sure I understand correctly. I see that bitmaps can be used to
> > implement set operations. But how comes that walking the graph requires a lot
> > of CPU? Isn't it O(n)?
>
> Yes and no. Your "n" there is the entirety of history.
Is this really true?
> (and each one needs to be pulled off of the disk,
> decompressed, and reconstructed from deltas).
While you need to unpack commits/trees to traverse further down, I can't see
any reason to unpack/reconstruct blobs just to see whether you need to send
it. The SHA is all you need to know, isn't it?
> Secondly, the graph traversal ends up seeing the same sha1s over and
> over again in tree entries (because most entries in the tree don't
> change from commit to commit).
Whenever you see an object (whether commit or tree) that you already have
seen, you can stop traversing further down this part of the graph/tree, as
everything you will see on this part has already be seen before.
Why would you see the same commits/trees over and over again? You'd stop
traversing on the boundary of the already-seen-territory, leaving the vast
majority of the "duplicated" structure under the carpet. Somehow I fail to see
the problem here.
--
Josef Wolf
jw@raven.inka.de
next prev parent reply other threads:[~2013-09-13 10:10 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-09-10 13:08 Re-Transmission of blobs? Josef Wolf
2013-09-10 17:51 ` Junio C Hamano
2013-09-11 11:27 ` Josef Wolf
2013-09-11 17:14 ` Junio C Hamano
2013-09-12 7:42 ` Josef Wolf
2013-09-12 9:23 ` Jeff King
2013-09-12 10:35 ` Josef Wolf
2013-09-12 19:44 ` Jeff King
2013-09-13 10:09 ` Josef Wolf [this message]
2013-09-16 21:55 ` Jeff King
2013-09-20 9:27 ` Josef Wolf
2013-09-24 7:36 ` Jeff King
2013-09-24 20:36 ` Josef Wolf
2013-09-12 12:45 ` Pyeron, Jason J CTR (US)
2013-09-12 19:56 ` Jeff King
2013-09-12 20:06 ` Pyeron, Jason J CTR (US)
2013-09-13 10:23 ` Josef Wolf
2013-09-13 11:51 ` Jason Pyeron
2013-09-13 12:16 ` Duy Nguyen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20130913100934.GE14259@raven.wolf.lan \
--to=jw@raven.inka.de \
--cc=git@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.