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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).