From: Jakub Narebski <jnareb@gmail.com>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Jon Loeliger <jdl@freescale.com>,
Daniel Berlin <dberlin@dberlin.org>,
David Miller <davem@davemloft.net>,
Ismail Donmez <ismail@pardus.org.tr>,
gcc@gcc.gnu.org, git@vger.kernel.org
Subject: Re: Git and GCC
Date: Thu, 06 Dec 2007 16:29:56 -0800 (PST) [thread overview]
Message-ID: <m3y7c7tkbs.fsf@roke.D-201> (raw)
In-Reply-To: <alpine.LFD.0.9999.0712061118050.13796@woody.linux-foundation.org>
Linus Torvalds <torvalds@linux-foundation.org> writes:
> On Thu, 6 Dec 2007, Jon Loeliger wrote:
>> I guess one question I posit is, would it be more accurate
>> to think of this as a "delta net" in a weighted graph rather
>> than a "delta chain"?
>
> It's certainly not a simple chain, it's more of a set of acyclic directed
> graphs in the object list. And yes, it's weigted by the size of the delta
> between objects, and the optimization problem is kind of akin to finding
> the smallest spanning tree (well, forest - since you do *not* want to
> create one large graph, you also want to make the individual trees shallow
> enough that you don't have excessive delta depth).
>
> There are good algorithms for finding minimum spanning trees, but this one
> is complicated by the fact that the biggest cost (by far!) is the
> calculation of the weights itself. So rather than really worry about
> finding the minimal tree/forest, the code needs to worry about not having
> to even calculate all the weights!
>
> (That, btw, is a common theme. A lot of git is about traversing graphs,
> like the revision graph. And most of the trivial graph problems all assume
> that you have the whole graph, but since the "whole graph" is the whole
> history of the repository, those algorithms are totally worthless, since
> they are fundamentally much too expensive - if we have to generate the
> whole history, we're already screwed for a big project. So things like
> revision graph calculation, the main performance issue is to avoid having
> to even *look* at parts of the graph that we don't need to see!)
Hmmm...
I think that these two problems (find minimal spanning forest with
limited depth and traverse graph) with the additional constraint to
avoid calculating weights / avoid calculating whole graph would be
a good problem to present at CompSci course.
Just a thought...
--
Jakub Narebski
Poland
ShadeHawk on #git
next prev parent reply other threads:[~2007-12-07 0:30 UTC|newest]
Thread overview: 95+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <4aca3dc20712051108s216d3331t8061ef45b9aa324a@mail.gmail.com>
2007-12-06 2:28 ` Git and GCC David Miller
2007-12-06 2:41 ` Daniel Berlin
2007-12-06 2:52 ` David Miller
2007-12-06 3:47 ` Daniel Berlin
2007-12-06 4:20 ` David Miller
2007-12-06 4:28 ` Harvey Harrison
2007-12-06 4:32 ` Daniel Berlin
2007-12-06 4:48 ` David Miller
2007-12-06 5:11 ` Daniel Berlin
2007-12-06 5:15 ` Harvey Harrison
2007-12-06 5:17 ` Daniel Berlin
2007-12-06 6:47 ` Jon Smirl
2007-12-06 7:15 ` Jeff King
2007-12-06 14:18 ` Nicolas Pitre
2007-12-06 17:39 ` Jeff King
2007-12-06 18:02 ` Nicolas Pitre
2007-12-07 6:50 ` Jeff King
2007-12-07 7:27 ` Jeff King
2007-12-06 18:35 ` Linus Torvalds
2007-12-06 18:55 ` Jon Smirl
2007-12-06 19:08 ` Nicolas Pitre
2007-12-06 21:39 ` Jon Smirl
2007-12-06 22:08 ` Nicolas Pitre
2007-12-06 22:11 ` Jon Smirl
2007-12-06 22:22 ` Jon Smirl
2007-12-06 22:30 ` Nicolas Pitre
2007-12-06 22:44 ` Jon Smirl
2007-12-07 7:31 ` Jeff King
2007-12-08 0:47 ` Harvey Harrison
2007-12-10 9:54 ` Gabriel Paubert
2007-12-10 15:35 ` Nicolas Pitre
2007-12-07 3:31 ` David Miller
2007-12-07 6:38 ` Jeff King
2007-12-07 7:10 ` Jon Smirl
2007-12-07 12:53 ` David Miller
2007-12-07 17:23 ` Linus Torvalds
2007-12-07 20:26 ` Giovanni Bajo
2007-12-07 22:14 ` Jakub Narebski
2007-12-07 23:04 ` Luke Lu
2007-12-07 23:14 ` Giovanni Bajo
2007-12-07 23:33 ` Daniel Berlin
2007-12-08 12:00 ` Johannes Schindelin
2007-12-08 1:55 ` David Miller
2007-12-10 9:57 ` David Miller
2007-12-06 6:09 ` Linus Torvalds
2007-12-06 7:49 ` Harvey Harrison
2007-12-06 8:11 ` David Brown
2007-12-06 14:01 ` Nicolas Pitre
2007-12-06 12:03 ` [PATCH] gc --aggressive: make it really aggressive Johannes Schindelin
2007-12-06 13:42 ` Theodore Tso
2007-12-06 14:15 ` Nicolas Pitre
2007-12-06 14:22 ` Pierre Habouzit
2007-12-06 15:55 ` Johannes Schindelin
2007-12-06 17:05 ` David Kastrup
2007-12-06 15:30 ` Harvey Harrison
2007-12-06 15:56 ` Johannes Schindelin
2007-12-06 16:19 ` Linus Torvalds
2009-03-18 16:01 ` Johannes Schindelin
2009-03-18 16:27 ` Teemu Likonen
2009-03-18 18:02 ` Nicolas Pitre
2007-12-06 18:04 ` Git and GCC Daniel Berlin
2007-12-06 18:29 ` Linus Torvalds
2007-12-07 2:42 ` Harvey Harrison
2007-12-07 3:01 ` Linus Torvalds
2007-12-07 4:06 ` Jon Smirl
2007-12-07 4:21 ` Nicolas Pitre
2007-12-07 5:21 ` Linus Torvalds
2007-12-07 7:08 ` Jon Smirl
2007-12-07 19:36 ` Nicolas Pitre
2007-12-06 18:24 ` NightStrike
2007-12-06 18:45 ` Linus Torvalds
2007-12-07 5:36 ` NightStrike
2007-12-06 19:12 ` Jon Loeliger
2007-12-06 19:39 ` Linus Torvalds
2007-12-07 0:29 ` Jakub Narebski [this message]
2007-12-06 20:04 ` Junio C Hamano
2007-12-06 21:02 ` Junio C Hamano
2007-12-06 22:26 ` David Kastrup
2007-12-06 22:38 ` [OT] " Randy Dunlap
2007-12-06 4:25 ` Harvey Harrison
2007-12-06 4:54 ` Linus Torvalds
2007-12-06 5:04 ` Harvey Harrison
2007-12-06 11:57 ` Johannes Schindelin
2007-12-06 12:04 ` Ismail Dönmez
[not found] ` <2007-12-05-21-23-14+trackit+sam@rfc1149.net>
[not found] ` <1196891451.10408.54.camel@brick>
[not found] ` <jeeje0ogvk.fsf@sykes.suse.de>
[not found] ` <1196897840.10408.57.camel@brick>
[not found] ` <38a0d8450712130640p1b5d74d6nfa124ad0b0110d64@mail.gmail.com>
[not found] ` <1197572755.898.15.camel@brick>
2007-12-17 22:15 ` "Argument list too long" in git remote update (Was: Git and GCC) Geert Bosch
2007-12-17 22:59 ` Johannes Schindelin
2007-12-17 23:01 ` Linus Torvalds
2007-12-18 1:34 ` Derek Fawcus
2007-12-18 1:52 ` Shawn O. Pearce
2007-12-08 2:21 Git and GCC J.C. Pizarro
2007-12-08 12:24 ` Johannes Schindelin
2007-12-08 19:53 ` Joe Buck
2007-12-08 20:28 ` Marco Costalba
2007-12-09 1:51 ` Daniel Berlin
2007-12-15 0:18 ` Nix
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
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=m3y7c7tkbs.fsf@roke.D-201 \
--to=jnareb@gmail.com \
--cc=davem@davemloft.net \
--cc=dberlin@dberlin.org \
--cc=gcc@gcc.gnu.org \
--cc=git@vger.kernel.org \
--cc=ismail@pardus.org.tr \
--cc=jdl@freescale.com \
--cc=torvalds@linux-foundation.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.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
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 read-only IMAP folder(s) and NNTP newsgroup(s).