From: Artur Skawina <art.08.09@gmail.com>
To: Nicolas Pitre <nico@fluxnic.net>
Cc: Nguyen Thai Ngoc Duy <pclouds@gmail.com>,
Luke Kenneth Casson Leighton <luke.leighton@gmail.com>,
Ted Ts'o <tytso@mit.edu>, Junio C Hamano <gitster@pobox.com>,
git <git@vger.kernel.org>
Subject: Re: git pack/unpack over bittorrent - works!
Date: Sat, 04 Sep 2010 07:42:12 +0200 [thread overview]
Message-ID: <4C81DC34.2090800@gmail.com> (raw)
In-Reply-To: <alpine.LFD.2.00.1009032304560.19366@xanadu.home>
>> 2) Git doesn't use chained deltas. IOW given commits "A --d1-> B --d2-> C",
>> "C" can be represented as a delta against "A" or "B", but _not_ against "d1".
>> (Think of the case where "C" reverts /part of/ "B")
>
> Git does use chained deltas indeed. But deltas are used only at the
> object level within a pack file. Any blob object can be represented as
> a delta against any other blob in the pack, regardless of the commit(s)
> those blob objects belong to. Same thing for tree objects. So you can
> have deltas going in total random directions if you look them from a
> commit perspective. So "C" can have some of its objects being deltas
> against objects from "B", or "A", or any other commit for that matter,
> or even objects belonging to the same commit "C". And some other objects
> from "B" can delta against objects from "C" too. There is simply no
> restrictions at all on the actual delta direction. The only rule is
> that an object may only delta against another object of the same type.
>
> Of course we don't try to delta each object against all the other
> available objects as that would be a O(n^2) operation (imagine with n =
> 1.7 million objects). So we use many heuristics to make this delta
> packing efficient without taking an infinite amount of time.
>
> For example, if we have objects X and Y that need to be packed together
> and sent to a client over the net, and we find that Y is already a delta
> against X in one pack that exists locally, then we simply and literally
> copy the delta representation of Y from that local pack file and send it
> out without recomputing that delta.
What i meant by 'chained deltas' is a representation that takes delta#1 and
applies delta#2 to the first delta, and applies the result to the source of
delta#1. Which could be a more compact representation of eg. a partial revert.
IOW, if I have commits A..Y, ask (via git pull) for commits X and Z, then I'm
guaranteed to receive them either raw, or as a delta vs commits A..X, right?
What I'm really asking is, if a (modified) git-upload-pack skips transferring
commit X, and just sends me commit Z (possibly as delta vs 'X'), _and_ I
obtain commit 'X" in some other way, I will be able to reconstruct 'Z', correct?
TIA,
artur
next prev parent reply other threads:[~2010-09-04 5:42 UTC|newest]
Thread overview: 88+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-09-01 14:36 git pack/unpack over bittorrent - works! Luke Kenneth Casson Leighton
2010-09-01 22:04 ` Nguyen Thai Ngoc Duy
2010-09-02 13:37 ` Luke Kenneth Casson Leighton
2010-09-02 13:53 ` Luke Kenneth Casson Leighton
2010-09-02 14:08 ` Ævar Arnfjörð Bjarmason
2010-09-02 15:33 ` A Large Angry SCM
2010-09-02 15:42 ` Luke Kenneth Casson Leighton
2010-09-02 15:51 ` Luke Kenneth Casson Leighton
2010-09-02 17:06 ` A Large Angry SCM
2010-09-02 15:58 ` Jeff King
2010-09-02 16:41 ` Nicolas Pitre
2010-09-02 17:09 ` A Large Angry SCM
2010-09-02 17:31 ` Nicolas Pitre
2010-09-02 19:17 ` Luke Kenneth Casson Leighton
2010-09-02 19:29 ` Shawn O. Pearce
2010-09-02 19:51 ` Luke Kenneth Casson Leighton
2010-09-02 20:06 ` Luke Kenneth Casson Leighton
2010-09-03 0:36 ` Nicolas Pitre
2010-09-03 10:34 ` Luke Kenneth Casson Leighton
2010-09-03 17:03 ` Junio C Hamano
2010-09-02 20:28 ` Brandon Casey
2010-09-02 20:48 ` Luke Kenneth Casson Leighton
2010-09-02 20:45 ` Jakub Narebski
2010-09-02 21:10 ` Luke Kenneth Casson Leighton
2010-09-02 21:19 ` Luke Kenneth Casson Leighton
2010-09-03 0:29 ` Nicolas Pitre
2010-09-03 2:48 ` Nguyen Thai Ngoc Duy
2010-09-03 10:55 ` Luke Kenneth Casson Leighton
2010-09-03 10:23 ` Luke Kenneth Casson Leighton
2010-09-03 10:54 ` Luke Kenneth Casson Leighton
2010-09-02 18:07 ` Luke Kenneth Casson Leighton
2010-09-02 18:23 ` Casey Dahlin
2010-09-02 16:58 ` A Large Angry SCM
2010-09-02 17:21 ` Nicolas Pitre
2010-09-02 19:41 ` Luke Kenneth Casson Leighton
2010-09-02 19:52 ` A Large Angry SCM
2010-09-02 23:09 ` Nicolas Pitre
2010-09-03 10:37 ` Theodore Tso
2010-09-03 11:04 ` Luke Kenneth Casson Leighton
2010-09-03 17:12 ` Junio C Hamano
2010-09-03 18:31 ` Ted Ts'o
2010-09-03 19:41 ` Nicolas Pitre
2010-09-03 21:11 ` Luke Kenneth Casson Leighton
2010-09-04 0:24 ` Nguyen Thai Ngoc Duy
2010-09-04 0:57 ` Nguyen Thai Ngoc Duy
2010-09-04 1:52 ` Artur Skawina
2010-09-04 4:39 ` Nicolas Pitre
2010-09-04 5:42 ` Artur Skawina [this message]
2010-09-04 6:13 ` Nicolas Pitre
2010-09-04 11:58 ` Luke Kenneth Casson Leighton
2010-09-04 13:14 ` Luke Kenneth Casson Leighton
2010-09-05 2:16 ` Nicolas Pitre
2010-09-05 18:05 ` Luke Kenneth Casson Leighton
2010-09-05 23:52 ` Nicolas Pitre
2010-09-06 13:23 ` Luke Kenneth Casson Leighton
2010-09-06 16:51 ` Nicolas Pitre
2010-09-06 22:33 ` Luke Kenneth Casson Leighton
2010-09-06 23:34 ` Junio C Hamano
2010-09-06 23:57 ` Nicolas Pitre
2010-09-07 0:17 ` Luke Kenneth Casson Leighton
2010-09-07 0:29 ` Luke Kenneth Casson Leighton
2010-09-04 13:42 ` Artur Skawina
[not found] ` <20100904155638.GA17606@pcpool00.mathematik.uni-freiburg.de>
2010-09-04 17:23 ` Artur Skawina
2010-09-04 18:46 ` Artur Skawina
2010-09-04 1:57 ` Theodore Tso
2010-09-04 5:23 ` Kyle Moffett
2010-09-04 11:46 ` Theodore Tso
2010-09-04 14:06 ` Luke Kenneth Casson Leighton
2010-09-05 1:32 ` Nicolas Pitre
2010-09-05 17:16 ` Luke Kenneth Casson Leighton
2010-09-04 5:40 ` Nicolas Pitre
2010-09-04 12:00 ` Theodore Tso
2010-09-04 12:44 ` Luke Kenneth Casson Leighton
2010-09-04 14:50 ` Luke Kenneth Casson Leighton
2010-09-04 18:14 ` Ted Ts'o
2010-09-04 20:00 ` Luke Kenneth Casson Leighton
2010-09-04 22:41 ` Ted Ts'o
2010-09-05 17:22 ` Luke Kenneth Casson Leighton
2010-09-04 20:20 ` Jakub Narebski
2010-09-04 20:47 ` Luke Kenneth Casson Leighton
2010-09-04 21:16 ` Jakub Narebski
2010-09-04 21:24 ` Luke Kenneth Casson Leighton
2010-09-04 22:47 ` Ted Ts'o
2010-09-05 1:43 ` Tomas Carnecky
2010-09-05 1:18 ` Nicolas Pitre
2010-09-05 17:25 ` Luke Kenneth Casson Leighton
2010-09-06 0:05 ` Nicolas Pitre
2010-09-04 12:33 ` Luke Kenneth Casson Leighton
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=4C81DC34.2090800@gmail.com \
--to=art.08.09@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=luke.leighton@gmail.com \
--cc=nico@fluxnic.net \
--cc=pclouds@gmail.com \
--cc=tytso@mit.edu \
/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).