* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-11 23:36 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Daniel Berlin, Git Mailing List
In-Reply-To: <7vprxcdhis.fsf@gitster.siamese.dyndns.org>
On Tue, 11 Dec 2007, Junio C Hamano wrote:
>
> Instead, how about discarding after we are done with each origin, like
> this?
Sure, looks fine to me. With either of these patches, all of the cost is
in the diffing routines:
samples % image name app name symbol name
191317 31.4074 git git xdl_hash_record
120060 19.7096 git git xdl_recmatch
99286 16.2992 git git xdl_prepare_ctx
56370 9.2539 libc-2.7.so libc-2.7.so memcpy
23315 3.8275 git git xdl_prepare_env
..
and while I suspect xdiff could be optimized a bit more for the cases
where we have no changes at the end, that's beyond my skills.
Linus
^ permalink raw reply
* Re: [PATCH] builtin-clone: Implement git clone as a builtin command.
From: Kristian Høgsberg @ 2007-12-11 23:38 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: git
In-Reply-To: <Pine.LNX.4.64.0712111549490.5349@iabervon.org>
On Tue, 2007-12-11 at 15:59 -0500, Daniel Barkalow wrote:
> On Tue, 11 Dec 2007, Kristian Høgsberg wrote:
>
> > Ok, don't flame me, I know this isn't appropriate at the moment with
> > stabilization for 1.5.4 going on, but I just wanted to post a heads up
> > on this work to avoid duplicate effort. It's one big patch at this point
> > and I haven't even run the test suite yet, but that will change.
>
> Is that why you misspelled Junio's email address? :)
Hehe, yeah, do not mess with maintainers in release mode :)
> Also as a heads-up, I've got a builtin-checkout that I've got passing all
> the tests (plus a few to test stuff I originally hadn't implemented). This
> mostly involved correcting the "interesting" states that unpack_trees()
> can leave the index in memory when it returns and figuring out how the
> merge code works. I can send it off for review and testing to people who
> are interested and don't have other things they should be doing instead.
Thanks, that's useful, I was already considering what to do next. I
wouldn't mind having a look, but maybe it's better to not discuss new
features on the list at this point. I appreciate the heads up though.
cheers,
Kristian
^ permalink raw reply
* Re: git annotate runs out of memory
From: Matthieu Moy @ 2007-12-11 23:37 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Berlin, git
In-Reply-To: <alpine.LFD.0.9999.0712111119310.25032@woody.linux-foundation.org>
Linus Torvalds <torvalds@linux-foundation.org> writes:
> On Tue, 11 Dec 2007, Matthieu Moy wrote:
>>
>> I've seen you pointing this kind of examples many times, but is that
>> really different from what even SVN does? "svn log drivers/char" will
>> also list atomic commits, and give me a filtered view of the global
>> log.
>
> Ok, BK and CVS both got this horribly wrong, which is why I care. Maybe
> this is one of the things SVN gets right.
>
> I seriously doubt it, though. Do you get *history* right, or do you just
> get a random list of commits?
Well, you don't get merge commit right with SVN, but that's a
different issue (svn 1.5 is supposed to have something about merge
history, I don't know how it's done ...). So, if by "history", you
mean how branches interferred together, obviously, SVN is bad at this.
But it's equally bad at "svn log dir/" and plain "svn log".
But to simplify, if you take a linear history (no merge commits),
"svn log dir/" give you the list of commits which changed something
inside "dir/". As pointed out in other messages, the way it's done is
really different from what git does. SVN does know a lot about
directories, and records a lot about them at commit time, while git
just considers them as file containers.
Year, CVS got this terribly wrong. IIRC, it just took the log for
individual messages, and mix them together, so a commit touching
multiple files would appear several times.
I've taken SVN as an extreme example, but at least bzr and mercurial
have an approach very similar to git.
So, to me, this particular point is something git obviously got right,
but not a point where git is so different from the others.
--
Matthieu
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-11 23:48 UTC (permalink / raw)
To: Matthieu Moy; +Cc: Daniel Berlin, git
In-Reply-To: <vpq63z49511.fsf@bauges.imag.fr>
On Wed, 12 Dec 2007, Matthieu Moy wrote:
>
> > I seriously doubt it, though. Do you get *history* right, or do you just
> > get a random list of commits?
>
> Well, you don't get merge commit right with SVN, but that's a
> different issue (svn 1.5 is supposed to have something about merge
> history, I don't know how it's done ...). So, if by "history", you
> mean how branches interferred together, obviously, SVN is bad at this.
> But it's equally bad at "svn log dir/" and plain "svn log".
Yeah, git just has higher goals.
The time history really matters (or rather, what I call the "shape" of
history) is when you are trying to merge, and you get a merge conflict.
That's when you want to do
gitk master merge ^merge-base -- files-that-are-unmerged
and in fact this is such an important thing for me that there is a
shorthand argument to do exactly that, ie:
gitk --merge
which shows the commits that touched the unmerged files graphically *with*
the history being correct (ie you don't just get a random log of "these
changes happened", you get the real history of the two branches as it
pertains to the files you care about!)
> But to simplify, if you take a linear history (no merge commits),
> "svn log dir/" give you the list of commits which changed something
> inside "dir/"
Sure, linear history is trivial. But it's also almost totally
uninteresting.
Linus
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-12 0:02 UTC (permalink / raw)
To: Junio C Hamano, Davide Libenzi; +Cc: Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111523210.25032@woody.linux-foundation.org>
On Tue, 11 Dec 2007, Linus Torvalds wrote:
>
> and while I suspect xdiff could be optimized a bit more for the cases
> where we have no changes at the end, that's beyond my skills.
Ok, I lied.
Nothing is beyond my skills. My mad k0der skillz are unbeatable.
This speeds up git-blame on ChangeLog-style files by a big amount, by just
ignoring the common end that we don't care about, since we don't want any
context anyway at that point. So I now get:
[torvalds@woody gcc]$ time git blame gcc/ChangeLog > /dev/null
real 0m7.031s
user 0m6.852s
sys 0m0.180s
which seems quite reasonable, and is about three times faster than trying
to diff those big files.
Davide: this really _does_ make a huge difference. Maybe xdiff itself
should do this optimization on its own, rather than have the caller hack
around the fact that xdiff doesn't handle this common case all that well?
The same thing obviously works for the beginning-of-file too, but then you
have to play games with line numbers being affected etc, so the end is the
rather much easier case and is the case that a ChangeLog-style file cares
about.
Daniel, this is obviously on top of the patches that fix the memory leak.
Linus
---
diff --git a/builtin-blame.c b/builtin-blame.c
index c158d31..677188c 100644
--- a/builtin-blame.c
+++ b/builtin-blame.c
@@ -543,6 +551,20 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,
return state.ret;
}
+#define BLOCK 1024
+
+static void truncate_common_data(mmfile_t *a, mmfile_t *b)
+{
+ long l1 = a->size, l2 = b->size;
+
+ while ((l1 -= BLOCK) > 0 && (l2 -= BLOCK) > 0) {
+ if (memcmp(a->ptr + l1, b->ptr + l2, BLOCK))
+ break;
+ a->size = l1;
+ b->size = l2;
+ }
+}
+
/*
* Run diff between two origins and grab the patch output, so that
* we can pass blame for lines origin is currently suspected for
@@ -557,6 +579,7 @@ static struct patch *get_patch(struct origin *parent, struct origin *origin)
fill_origin_blob(origin, &file_o);
if (!file_p.ptr || !file_o.ptr)
return NULL;
+ truncate_common_data(&file_p, &file_o);
patch = compare_buffer(&file_p, &file_o, 0);
num_get_patch++;
return patch;
^ permalink raw reply related
* Re: [ANNOUNCE] ugit: a pyqt-based git gui // was: Re: If you would write git from scratch now, what would you change?
From: Jakub Narebski @ 2007-12-12 0:11 UTC (permalink / raw)
To: David; +Cc: Andy Parkins, git
In-Reply-To: <402731c90712110548k67f28b64w5afa93ee908ce73b@mail.gmail.com>
David <davvid@gmail.com> writes:
> For whatever it's worth, I've written a PyQt4-based git gui. For lack
> of a better name I call it ugit, as in "I git, you git, we all git
> with ugit" (or something silly like that).
I have added it to http://git.or.cz/gitwiki/InterfacesFrontendsAndTools
Funny that both (h)gct and Qct, which are commit tools too (although
multi-SCM) are also written in PyQt...
--
Jakub Narebski
Poland
ShadeHawk on #git
^ permalink raw reply
* Re: git annotate runs out of memory
From: Davide Libenzi @ 2007-12-12 0:22 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111548200.25032@woody.linux-foundation.org>
On Tue, 11 Dec 2007, Linus Torvalds wrote:
> On Tue, 11 Dec 2007, Linus Torvalds wrote:
> >
> > and while I suspect xdiff could be optimized a bit more for the cases
> > where we have no changes at the end, that's beyond my skills.
>
> Ok, I lied.
>
> Nothing is beyond my skills. My mad k0der skillz are unbeatable.
>
> This speeds up git-blame on ChangeLog-style files by a big amount, by just
> ignoring the common end that we don't care about, since we don't want any
> context anyway at that point. So I now get:
>
> [torvalds@woody gcc]$ time git blame gcc/ChangeLog > /dev/null
>
> real 0m7.031s
> user 0m6.852s
> sys 0m0.180s
>
> which seems quite reasonable, and is about three times faster than trying
> to diff those big files.
>
> Davide: this really _does_ make a huge difference. Maybe xdiff itself
> should do this optimization on its own, rather than have the caller hack
> around the fact that xdiff doesn't handle this common case all that well?
I didn't follow the thread, but I can guess from the subject that this is
about memory, isn't it?
Libxdiff already has a xdl_trim_ends() that strips all the common
beginning and ending records, but at that point files are already loaded.
Since libxdiff works with memory files in order to keep any sort of
system dependency out of the window, so the optimization would be
useless on libxdiff side. This because the user would have to have
already the file loaded in memory, to pass it to libxdiff.
If this is really about memory, this better be kept on the libxdiff caller
side, so that it can avoid loading the terminal file sections altogether.
About your code, you may want to have an extend-till-next-eol code after
the trimming part, since the last line may be used for context in the
diffs.
- Davide
^ permalink raw reply
* Re: Using git with Eclipse
From: Robin Rosenberg @ 2007-12-12 0:29 UTC (permalink / raw)
To: Wink Saville; +Cc: Shawn O. Pearce, git
In-Reply-To: <475E265D.5090106@saville.com>
tisdag 11 december 2007 skrev Wink Saville:
> Shawn O. Pearce wrote:
> > Wink Saville <wink@saville.com> wrote:
> >
> >> I'm trying to use git on an Eclipse workspace and the .metadata
> >> directory is chock full of files and was wondering what, if anything,
> >> should be ignored. At the moment .history looks like a candidate for
> >> ignoring there are probably others.
> >>
> >
> > Ignore all of .metadata; its Eclipse private state that you don't
> > want to version. I'd add it to .git/info/exclude so its ignored only
> > in the repository that is using Eclipse, rather than in .gitignore
> > (which is published).
> >
> >
> Shawn,
>
> I added .metadata to exclude then used git rm to remove
> .metadata from the repository. I then cloned that
> repository to see how Eclipse would work. (As part of my
> workflow I use git as a backup so I wanted to see what would
> happen when I "restored".)
>
> As I'm sure you know with the metadata gone my existing projects
> in the Ui were gone and they have to be recreated as well as
> some Eclipse and plugin specific configuration.
> I understand you and others are working on an Eclipse plugin
> for git, will it also ignore . metadata?
I don't put my projects into the workspace directory so I don't have
that problem. I think mixing projects and workspaces is a bad idea
(from experience, especially when testing different Eclipse versions
on the same projects.
As for settings you can configure project specific settings,
rather than workspace settings for most interesting settings. You can
also export/import settings. Getting projects into a new workspace
is best done using import. Point import to a directory and it will scan
for all projects and let you import them all in one go.
Egit doesn't ignore .metadata by default, I think. Probably should. For now
you can tell egit to ignore it via the workspace settings, which egit honors.
Eventually it will honor .git/info/exclude etc, but currently it doesn't.
>
> Do you need any testing done or is it too early? I'd be glad to
> test if you feel its solid enough that I won't lose data or if it
> uses a separate different repo then I could use both.
Sure testing is needed. It's solid enough to be usable, but probably not
bug free and isn't feature complete. So if we can root out some bugs and not
just introduce new buggy features that helps. Not that development is very
fast nowadays, but having real users spurs development and hopefully gets
more contributors.
The likelyhood of loosing data is probably very low as few operations are
dangerous. Of course, there is no warranty etc. etc. and we haven't done
very much monkey testing (unless using the plugin on windows counts).
I use egit and git on the same work dir in parallel, sometimes using egit,
sometimes git-gui and sometimes plain git depending on which does the
work better.
-- robin
^ permalink raw reply
* [(not so) random thoughts] using git as its own caching tool
From: Pierre Habouzit @ 2007-12-12 0:38 UTC (permalink / raw)
To: Git ML
[-- Attachment #1: Type: text/plain, Size: 3819 bytes --]
That's an idea I have for quite some time, and I wonder why it's not
used in git tools as a general rule.
This idea is simple, git objects database has two (for this
discussion) very interesting features: its delta compressed cached that
is _very_ efficient, and the reflog.
I wonder if that would be possible to write some git porcelains (and
builtin API too) that would be more "map" oriented. I mean, we could use
a reference as a pointer to a given tree that would be the map (where
keys have a path form, which is nice). When I say that, I'm thinking
about git-svn, that even with the recent improvements of its .rev_db's
still eats a lot of space with the unhandled.log _and_ the indexes it
stores for _each_ svn branch/tag. This way, instead of many:
foo/index
foo/.rev_map.6ef976f9-4de5-0310-a40d-91cae572ec18
foo/unhandled.log
we would just have a special refs/db/git-svn/foo reference that would be
a tree with three blobs in it: index, rev_map.xxxx, unhandled.log. (or
probably index would even be a tree but that's another matter). This
way, all the unhandled.log that share a lot of common content would be
nicely compressed by the delta-compression algorithms, with a negligible
overhead (git-svn is _very_ slow because of svn anyways, we don't really
care if it needs to get a blob contents instead opening a flat file).
Another nifty usage we could have is memoization databases that don't
require a specific tool to expire them, but use the reflog expiration
for that. I remember that we discussed quite some time ago, the idea of
annotating objects. We could use such annotations to link some objects
to memoized datas under different namespaces for each caching scheme
involved, and with one reference per namespace that will have in its
reflog each of the linked objects created over time for caching. Good
candidates to use that are the rr-cache, or git-annotate/blame caching.
Of course that would need to write a tool that removes weak annotations
that point to objects that don't exist anymore. We could also cache the
rename/copies/… detection results, and make those really really cheap to
use[0].
I know that some will say something about hammers, problems and nails,
though it would allow to develop quite efficient tools with a generic
and easy to use API, that could directly benefit from already existing
infrastructure in git. I mean it's silly to write yet-another cache
expirer when you have the reflog. Or to speak about git-svn again, it
could even version its state per branch the way I propose, it'll end up
using less disk that what it does now, with the immediate gain that it
would be fully clone-able[1] (which would be a _really_ nice feature).
So am I having crazy thoughts and should I throw my crack-pipe away ?
Or does parts of this mumbling makes any sense to someone ?
PS: It's late, and I'm tired, hence my english is probably very clumsy,
and I hope I'm understandable enough. I'd be glad to rephrase parts
that needs it.
[0] and if the copy/rename/… detection algorithm gets smarter, we just
need to change its memoization namespace to throw the old cache
away at once.
[1] and the really nice part here is that even if you don't create one
new step per svn revision you import but do macro-steps with
hundreds of svn revisions at a time, the merge of two differnt
git-svn states of two clones of the _same_ svn repository will
have a trivial exact merge: the one that knows the biggest svn
revision is the new state to use.
--
·O· Pierre Habouzit
··O madcoder@debian.org
OOO http://www.madism.org
[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: git blame with valgrind massif
From: André Goddard Rosa @ 2007-12-12 0:50 UTC (permalink / raw)
To: Jon Smirl; +Cc: Pierre Habouzit, Git Mailing List
In-Reply-To: <9e4733910712111345i23d86a85jfedb4f37f20a5b0@mail.gmail.com>
On Dec 11, 2007 7:45 PM, Jon Smirl <jonsmirl@gmail.com> wrote:
> On 12/11/07, Pierre Habouzit <madcoder@debian.org> wrote:
> > On Tue, Dec 11, 2007 at 08:57:24PM +0000, Jon Smirl wrote:
> > > I ran:
> > > valgrind --tool=massif --heap=yes git blame gcc/ChangeLog
> > > it used about 2.25GB
> > >
> > > How do you interpret the massif output?
A bit unrelated, but there's a new valgrind release:
http://www.valgrind.org/docs/manual/dist.news.html
"The main excitement in 3.3.0 is new and improved tools. Helgrind
works again, Massif has been completely overhauled and much improved,
Cachegrind now does branch-misprediction profiling, and a new category
of experimental tools has been created, containing two new tools:
Omega and DRD. There are many other smaller improvements."
Best regards,
--
[]s,
André Goddard
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-12 0:50 UTC (permalink / raw)
To: Davide Libenzi; +Cc: Junio C Hamano, Daniel Berlin, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0712111611570.1671@alien.or.mcafeemobile.com>
On Tue, 11 Dec 2007, Davide Libenzi wrote:
>
> I didn't follow the thread, but I can guess from the subject that this is
> about memory, isn't it?
No, it started out that way, but now it's about performance.
> Libxdiff already has a xdl_trim_ends() that strips all the common
> beginning and ending records, but at that point files are already loaded.
That's not the problem. The problem with xdl_trim_ends() is that it
happens *after* you have done all the hashing, so as an optimization it's
fairly useless, because it still leaves the real cost (the per-line
hashing) on the table.
So doing the trimming of the ends before you do even that, allows you to
just do the trivial "let's see if the ends are identical" with a plain
memcmp, which is much faster.
Linus
^ permalink raw reply
* Re: git annotate runs out of memory
From: Junio C Hamano @ 2007-12-12 0:56 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Davide Libenzi, Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111548200.25032@woody.linux-foundation.org>
Linus Torvalds <torvalds@linux-foundation.org> writes:
> On Tue, 11 Dec 2007, Linus Torvalds wrote:
>>
>> and while I suspect xdiff could be optimized a bit more for the cases
>> where we have no changes at the end, that's beyond my skills.
>
> Ok, I lied.
>
> Nothing is beyond my skills. My mad k0der skillz are unbeatable.
>
> This speeds up git-blame on ChangeLog-style files by a big amount, by just
> ignoring the common end that we don't care about, since we don't want any
> context anyway at that point. So I now get:
>
> [torvalds@woody gcc]$ time git blame gcc/ChangeLog > /dev/null
>
> real 0m7.031s
> user 0m6.852s
> sys 0m0.180s
>
> which seems quite reasonable, and is about three times faster than trying
> to diff those big files.
Funny. I did not understand what you were talking about "no changes at
the end" when I read it ('cause I am at work and do not have the data
you are looking at handy), but now I see what you meant. It is a cute
hack that optimizes for a very special case of "prepend only" files (aka
"ChangeLog").
I suspect that this optimization has an interesting corner case, though.
What happens if you chomp at the middle of the last line that is
different between the two files? xdiff will report the line number but
wouldn't its (now artificial) "No newline at the end of the file" affect
the blame logic?
Besides, "prepend only" (or "append only") files would be good
candidates for the original -S"pickaxe" search, I would imagine, and
unless you are looking at that ChangeLog-2000 consolidated log, isn't
blame way overkill?
^ permalink raw reply
* Re: git annotate runs out of memory
From: Davide Libenzi @ 2007-12-12 1:12 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111648180.25032@woody.linux-foundation.org>
On Tue, 11 Dec 2007, Linus Torvalds wrote:
> > Libxdiff already has a xdl_trim_ends() that strips all the common
> > beginning and ending records, but at that point files are already loaded.
>
> That's not the problem. The problem with xdl_trim_ends() is that it
> happens *after* you have done all the hashing, so as an optimization it's
> fairly useless, because it still leaves the real cost (the per-line
> hashing) on the table.
Careful. The real cost of diffing, is not the O(1) pass of the prepare
phase. It's the potentially O(N*M) worst case of the cross-record compare.
So that optimization is far from useless. That optimization is indeed
mainly targeted to avoid such worst case.
> So doing the trimming of the ends before you do even that, allows you to
> just do the trivial "let's see if the ends are identical" with a plain
> memcmp, which is much faster.
Yes, tail trimming done on a block-basis is faster and does not consume
memory. The code for libxdiff would have to be a bit more complex though,
since memory files can be composed by many sections, of different sizes
(so you cannot just assume it's a single block you're trimming the end).
Also, you'd need some code at the end that hands you back at least the N
lines you want for context.
- Davide
^ permalink raw reply
* Re: 'git fast-export' is crashing on the gcc repo
From: Alex Riesen @ 2007-12-12 1:38 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: git
In-Reply-To: <alpine.LFD.0.99999.0712111703380.555@xanadu.home>
Nicolas Pitre, Tue, Dec 11, 2007 23:06:42 +0100:
>
> Well, ignore the above. It seems that most of stdio doesn't set errno
> so the above is crap.
>
Well, it had no reason to in this case. It's not an error.
It does not even have to do a syscall.
> diff --git a/builtin-fast-export.c b/builtin-fast-export.c
> index 2136aad..c32a124 100755
> --- a/builtin-fast-export.c
> +++ b/builtin-fast-export.c
> @@ -103,7 +103,7 @@ static void handle_object(const unsigned char *sha1)
> mark_object(object);
>
> printf("blob\nmark :%d\ndata %lu\n", last_idnum, size);
> - if (fwrite(buf, size, 1, stdout) != 1)
> + if (fwrite(buf, 1, size, stdout) != size)
That's a probable syscall which could be spared
^ permalink raw reply
* Re: 'git fast-export' is crashing on the gcc repo
From: Nicolas Pitre @ 2007-12-12 1:45 UTC (permalink / raw)
To: Alex Riesen; +Cc: git
In-Reply-To: <20071212013828.GC19857@steel.home>
On Wed, 12 Dec 2007, Alex Riesen wrote:
> Nicolas Pitre, Tue, Dec 11, 2007 23:06:42 +0100:
> >
> > Well, ignore the above. It seems that most of stdio doesn't set errno
> > so the above is crap.
> >
>
> Well, it had no reason to in this case. It's not an error.
> It does not even have to do a syscall.
Which is why I later agreed with your patch.
Nicolas
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-12 2:10 UTC (permalink / raw)
To: Davide Libenzi; +Cc: Junio C Hamano, Daniel Berlin, Git Mailing List
In-Reply-To: <Pine.LNX.4.64.0712111653520.1671@alien.or.mcafeemobile.com>
On Tue, 11 Dec 2007, Davide Libenzi wrote:
>
> > That's not the problem. The problem with xdl_trim_ends() is that it
> > happens *after* you have done all the hashing, so as an optimization it's
> > fairly useless, because it still leaves the real cost (the per-line
> > hashing) on the table.
>
> Careful. The real cost of diffing, is not the O(1) pass of the prepare
> phase. It's the potentially O(N*M) worst case of the cross-record compare.
> So that optimization is far from useless. That optimization is indeed
> mainly targeted to avoid such worst case.
I'm not saying it's useless. I'm saying it's ineffective.
My simple patch that you saw, speeded up a real-life case by A FACTOR OF
THREE. We're not talking small potatoes here.
> Also, you'd need some code at the end that hands you back at least the N
> lines you want for context.
Sure. The special case I added it to specifically wanted a context of zero
in the caller, so I could just ignore that.
But doing this in general and handing back the context is a simple matter
of
while (size < orig && context_lines) {
if (src->buffer[size++] == '\n')
context_lines--;
}
which will usually hit in a really short time (ie three lines by default,
just a few tens of bytes).
Linus
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-12 2:20 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Davide Libenzi, Daniel Berlin, Git Mailing List
In-Reply-To: <7vwsrkbuje.fsf@gitster.siamese.dyndns.org>
On Tue, 11 Dec 2007, Junio C Hamano wrote:
>
> I suspect that this optimization has an interesting corner case, though.
> What happens if you chomp at the middle of the last line that is
> different between the two files? xdiff will report the line number but
> wouldn't its (now artificial) "No newline at the end of the file" affect
> the blame logic?
It shouldn't. I thought about it, but there doesn't seem to be any reason
why blame could possibly care - the message can come at the end of a
_real_ file, of course, so if the extra message confuses the blame logic,
there's already a bug there.
But no, I didn't create a test-case.
> Besides, "prepend only" (or "append only") files would be good
> candidates for the original -S"pickaxe" search, I would imagine, and
> unless you are looking at that ChangeLog-2000 consolidated log, isn't
> blame way overkill?
Actually, I suspect that this makes a difference for totally normal files
too. I bet it cuts the size of the files to be tested for the common case
(ie just a few small changes) down by 30-50% even on average. The fact
that it cuts it down by 99.9% on ChangeLog files is just an added bonus.
As Davide mentioned, xdiff actually does something like that hack for the
beginning and end of files internally _anyway_, the problem with that is
that it does it so late that it's already done a fairly expensive hash for
the file (and allocated space for it based on guesses that are in turn
based on the original size) that it doesn't actually get the full effect
of the optimization.
Linus
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-12 2:39 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Davide Libenzi, Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111816220.25032@woody.linux-foundation.org>
On Tue, 11 Dec 2007, Linus Torvalds wrote:
>
> But no, I didn't create a test-case.
This *should* trigger the special case:
mkdir test-dir
cd test-dir
git init
(echo -n a ; yes '' | dd count=2) > file
git add file
git commit -m "'a' + 1k newlines"
(echo -n b ; yes '' | dd count=2) > file
git add file
git commit -m "'b' + 1k newlines"
and it all seems to work fine.
But I didn't actually check that it really triggered, this is just
creating a 1025-byte file that has a single character and then 1024
newlines. So when the logic removes the shared tail (all the newlines), it
leaves a single-character newlineless buffer for diff, and no, git-blame
didn't care, and got the right answer.
Linus
^ permalink raw reply
* Re: [PATCH] builtin-clone: Implement git clone as a builtin command.
From: Junio C Hamano @ 2007-12-12 3:12 UTC (permalink / raw)
To: Kristian Høgsberg; +Cc: Daniel Barkalow, git
In-Reply-To: <1197416286.7552.4.camel@hinata.boston.redhat.com>
Kristian Høgsberg <krh@redhat.com> writes:
> On Tue, 2007-12-11 at 15:59 -0500, Daniel Barkalow wrote:
>> On Tue, 11 Dec 2007, Kristian Høgsberg wrote:
>>
>> > Ok, don't flame me, I know this isn't appropriate at the moment with
>> > stabilization for 1.5.4 going on, but I just wanted to post a heads up
>> > on this work to avoid duplicate effort. It's one big patch at this point
>> > and I haven't even run the test suite yet, but that will change.
>>
>> Is that why you misspelled Junio's email address? :)
>
> Hehe, yeah, do not mess with maintainers in release mode :)
Actually this is a bit unfortunate, regardless of everybody being in
release and bugfix only mode.
I was hoping that the evolution path for clone would be to first make it
a very thin wrapper around:
git init
git remote add -f
git checkout
sequence. Currently, the "origin" repository is not quite equal to
other remotes added with "git remote add", but if we enhance "git remote
add" a bit, we should be able to make this happen. This would hopefully
lose a lot of code from git-clone. And then after we are done with
that, rewrite the remaining thin wrapper in C.
There are a handful issues in that approach with the current git-remote,
and that was why I also thought recent "git remote in C" by Dscho a bit
unfortunate, as enhancements and interface fixes (both user and machine)
tend to be much easier in scripted version.
What the current "git clone" does that are not naturally expressed by
the above sequence are:
* HEAD discovery
The code can be lifted from the scripted version and transplanted to
git-remote. And to make "origin" and other remotes added by "git
remote add", this logic needs to be moved to "git remote".
However, before rewriting the "git remote" to C, it would be really
nice if we can update the native protocol so that we can reliably
find out which branch HEAD points at. The current code guesses, only
because the native protocol does not carry that information [*1*].
Worse yet, even though the current code _knows_ this information when
going over dumb protocols, it discards it to use the same guessing
logic as used by the native protocol.
* --shared optimization
This is a very easy addition to "git remote add". You make sure that
the added remote repository is on a local machine, and set up
alternates to point at its object store.
* --reference optimization
This is a bit more involved than --shared. Half the power of this
optimization is coming from setting up alternates to point at another
local repository, which allows you not to have to _store_ duplicated
objects yourself, but the other half is coming from being able to lie
to the repository being cloned from that you have branches and tags
that reference repository has, even though they are not your branches
and tags, which allows you not to have to _download_ the objects to
begin with.
I think this can be added to "git remote add" by making --reference
also imply -f. Then while "git remote add" sets up the new remote,
it can stash the borrowed refs somewhere, just like git-clone does,
run the git-fetch, and then remove the borrowed refs once done.
* local optimization (the "cpio" thing)
I think this part needs to stay in git-clone even after we move the
above to "git remote add".
[Footnote]
*1* Here is a demonstration of the necessary protocol extension.
-- >8 --
Implement show-symref protocol extension.
This updates the git native "upload-pack" protocol to carry extra
information to show which branch HEAD symref points at. As is the other
protocol extension, this is enabled only when both ends of the exchange
supports it.
The receiving end currently does not do anything, and the logic needs to
go to peek-remote more than it needs to go to fetch-pack, but one has to
start from somewhere.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
builtin-fetch-pack.c | 86 +++++++++++++++++++++++++++++++++----------------
upload-pack.c | 25 +++++++++++++-
2 files changed, 81 insertions(+), 30 deletions(-)
diff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c
index 807fa93..e9f86d6 100644
--- a/builtin-fetch-pack.c
+++ b/builtin-fetch-pack.c
@@ -32,7 +32,7 @@ static const char fetch_pack_usage[] =
#define MAX_IN_VAIN 256
static struct commit_list *rev_list;
-static int non_common_revs, multi_ack, use_sideband;
+static int non_common_revs, multi_ack, use_sideband, show_symref;
static void rev_list_push(struct commit *commit, int mark)
{
@@ -141,6 +141,51 @@ static const unsigned char* get_rev(void)
return commit->object.sha1;
}
+static void handle_shallow(int fd[2])
+{
+ char line[1024];
+ unsigned char sha1[20];
+ int len;
+
+ while ((len = packet_read_line(fd[0], line, sizeof(line)))) {
+ if (!prefixcmp(line, "shallow ")) {
+ if (get_sha1_hex(line + 8, sha1))
+ die("invalid shallow line: %s", line);
+ register_shallow(sha1);
+ continue;
+ }
+ if (!prefixcmp(line, "unshallow ")) {
+ if (get_sha1_hex(line + 10, sha1))
+ die("invalid unshallow line: %s", line);
+ if (!lookup_object(sha1))
+ die("object not found: %s", line);
+ /* make sure that it is parsed as shallow */
+ parse_object(sha1);
+ if (unregister_shallow(sha1))
+ die("no shallow found: %s", line);
+ continue;
+ }
+ die("expected shallow/unshallow, got %s", line);
+ }
+}
+
+static void handle_symref(int fd[2], struct ref *refs)
+{
+ char line[1024];
+ int len;
+
+ while ((len = packet_read_line(fd[0], line, sizeof(line)))) {
+ if (!prefixcmp(line, "symref ")) {
+ /*
+ * Here you would remember what symbolic ref
+ * pointed at what real ref to use that
+ * information later.
+ */
+ fputs(line, stderr);
+ }
+ }
+}
+
static int find_common(int fd[2], unsigned char *result_sha1,
struct ref *refs)
{
@@ -173,8 +218,9 @@ static int find_common(int fd[2], unsigned char *result_sha1,
}
if (!fetching)
- packet_write(fd[1], "want %s%s%s%s%s%s%s\n",
+ packet_write(fd[1], "want %s%s%s%s%s%s%s%s\n",
sha1_to_hex(remote),
+ (show_symref ? " show-symref" : ""),
(multi_ack ? " multi_ack" : ""),
(use_sideband == 2 ? " side-band-64k" : ""),
(use_sideband == 1 ? " side-band" : ""),
@@ -193,32 +239,11 @@ static int find_common(int fd[2], unsigned char *result_sha1,
if (!fetching)
return 1;
- if (args.depth > 0) {
- char line[1024];
- unsigned char sha1[20];
- int len;
-
- while ((len = packet_read_line(fd[0], line, sizeof(line)))) {
- if (!prefixcmp(line, "shallow ")) {
- if (get_sha1_hex(line + 8, sha1))
- die("invalid shallow line: %s", line);
- register_shallow(sha1);
- continue;
- }
- if (!prefixcmp(line, "unshallow ")) {
- if (get_sha1_hex(line + 10, sha1))
- die("invalid unshallow line: %s", line);
- if (!lookup_object(sha1))
- die("object not found: %s", line);
- /* make sure that it is parsed as shallow */
- parse_object(sha1);
- if (unregister_shallow(sha1))
- die("no shallow found: %s", line);
- continue;
- }
- die("expected shallow/unshallow, got %s", line);
- }
- }
+ if (args.depth > 0)
+ handle_shallow(fd);
+
+ if (show_symref)
+ handle_symref(fd, refs);
flushes = 0;
retval = -1;
@@ -558,6 +583,11 @@ static struct ref *do_fetch_pack(int fd[2],
get_remote_heads(fd[0], &ref, 0, NULL, 0);
if (is_repository_shallow() && !server_supports("shallow"))
die("Server does not support shallow clients");
+ if (server_supports("show-symref")) {
+ if (args.verbose)
+ fprintf(stderr, "Server supports show-symref\n");
+ show_symref = 1;
+ }
if (server_supports("multi_ack")) {
if (args.verbose)
fprintf(stderr, "Server supports multi_ack\n");
diff --git a/upload-pack.c b/upload-pack.c
index 7e04311..351d501 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -27,7 +27,7 @@ static const char upload_pack_usage[] = "git-upload-pack [--strict] [--timeout=n
static unsigned long oldest_have;
static int multi_ack, nr_our_refs;
-static int use_thin_pack, use_ofs_delta, no_progress;
+static int use_thin_pack, use_ofs_delta, no_progress, show_symref;
static struct object_array have_obj;
static struct object_array want_obj;
static unsigned int timeout;
@@ -477,6 +477,10 @@ static void receive_needs(void)
get_sha1_hex(line+5, sha1_buf))
die("git-upload-pack: protocol error, "
"expected to get sha, not '%s'", line);
+
+ /* Protocol extensions */
+ if (strstr(line+45, "show-symref"))
+ show_symref = 1;
if (strstr(line+45, "multi_ack"))
multi_ack = 1;
if (strstr(line+45, "thin-pack"))
@@ -557,7 +561,7 @@ static void receive_needs(void)
static int send_ref(const char *refname, const unsigned char *sha1, int flag, void *cb_data)
{
static const char *capabilities = "multi_ack thin-pack side-band"
- " side-band-64k ofs-delta shallow no-progress";
+ " side-band-64k ofs-delta shallow no-progress show-symref";
struct object *o = parse_object(sha1);
if (!o)
@@ -580,6 +584,18 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo
return 0;
}
+static int send_symref(const char *refname, const unsigned char *sha1, int flag, void *cb_data)
+{
+ unsigned char object_name[20];
+ const char *symref;
+ int what;
+
+ symref = resolve_ref(refname, object_name, 1, &what);
+ if (symref && (what & REF_ISSYMREF))
+ packet_write(1, "symref %s %s\n", refname, symref);
+ return 0;
+}
+
static void upload_pack(void)
{
reset_timeout();
@@ -587,6 +603,11 @@ static void upload_pack(void)
for_each_ref(send_ref, NULL);
packet_flush(1);
receive_needs();
+ if (show_symref) {
+ send_symref("HEAD", NULL, 0, NULL);
+ for_each_ref(send_symref, NULL);
+ packet_flush(1);
+ }
if (want_obj.nr) {
get_common_commits();
create_pack_file();
--
1.5.3.7-1157-gbf82a
^ permalink raw reply related
* Re: [PATCH] builtin-clone: Implement git clone as a builtin command.
From: Junio C Hamano @ 2007-12-12 3:20 UTC (permalink / raw)
To: Kristian Høgsberg; +Cc: Daniel Barkalow, git
In-Reply-To: <7vejdsbo7d.fsf@gitster.siamese.dyndns.org>
Junio C Hamano <gitster@pobox.com> writes:
> What the current "git clone" does that are not naturally expressed by
> the above sequence are:
>
> * HEAD discovery
>
> The code can be lifted from the scripted version and transplanted to
> git-remote. And to make "origin" and other remotes added by "git
> remote add", this logic needs to be moved to "git remote".
s/remote add", this/remote add" more equal, this/;
^ permalink raw reply
* Re: git annotate runs out of memory
From: Linus Torvalds @ 2007-12-12 3:35 UTC (permalink / raw)
To: Davide Libenzi; +Cc: Junio C Hamano, Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111806320.25032@woody.linux-foundation.org>
On Tue, 11 Dec 2007, Linus Torvalds wrote:
>
> I'm not saying it's useless. I'm saying it's ineffective.
Sorry, I _did_ call it "fairly useless".
The rest of the comment stands. I'm sure the trimming that xdiff does is
good at avoiding some common O(n*m) cases, it's just not as good as it
could be, and leaves a big constant factor of the O(n) case on the table.
Linus
^ permalink raw reply
* Re: git annotate runs out of memory
From: Shawn O. Pearce @ 2007-12-12 3:57 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Berlin, Git Mailing List
In-Reply-To: <alpine.LFD.0.9999.0712111122400.25032@woody.linux-foundation.org>
Linus Torvalds <torvalds@linux-foundation.org> wrote:
...
> is virtually useless because it's too expensive, but try doing
>
> git gui blame gcc ChangeLog
>
> instead, and doesn't that just seem nicer? (*)
>
> The difference is that the GUI one does it incrementally, and doesn't have
> to get _all_ the results before it can start reporting blame.
>
> Not that I claim that the gui blame is perfect either (I dunno why it
> delays the nice coloring so long ...
git-gui waits to color until after it gets the move/copy annotations
back from the -C -C -w second pass it does. This way the coloring
is based on the original source location, not on the move/copy that
caused it to be placed where it is now.
I played around with this for a while and finally made it work the
way it does as I assumed most users would want to see where something
originally came from more than how it got moved to where it is now.
IOW the (very expensive) -C -C -w pass is usually much more
interesting than the default (fast) pass, so that is the line
annotation data we color with. But it takes longer to get and
is run second, so yea, coloring takes a while.
--
Shawn.
^ permalink raw reply
* Re: [ANNOUNCE] ugit: a pyqt-based git gui // was: Re: If you would write git from scratch now, what would you change?
From: Shawn O. Pearce @ 2007-12-12 4:10 UTC (permalink / raw)
To: Jason Sewall; +Cc: David, Marco Costalba, Andy Parkins, git
In-Reply-To: <31e9dd080712111329j2c8b22ebs38ab727a5fbe85fb@mail.gmail.com>
Jason Sewall <jasonsewall@gmail.com> wrote:
> Anyway, ugit is very good for a first draft; its text display beats
> whats in git-gui in a big way (and I would *hope* qt4 would beat
> Tcl/Tk at that at least).
Are you just using the wrong fonts under git-gui? I mean both
Tk and qt4 are drawing text through your windowing system, from
the same pool of font files... if qt4 can draw nice text then
so can Tk, right?
--
Shawn.
^ permalink raw reply
* Re: git annotate runs out of memory
From: Junio C Hamano @ 2007-12-12 4:48 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Berlin, Git Mailing List
In-Reply-To: <7vprxcdhis.fsf@gitster.siamese.dyndns.org>
Junio C Hamano <gitster@pobox.com> writes:
> While this should be safe (because the user of blob lazily re-fetches),
> it feels a bit too aggressive, especially when -C or other "retry and
> try harder to assign blame elsewhere" option is used.
>
> Instead, how about discarding after we are done with each origin, like
> this?
It's been a while for me to look at the blame engine, and it hit me that
it would be interesting to run assign_blame() loop on multi-core machine
in parallel threads.
^ permalink raw reply
* Re: Something is broken in repack
From: Nicolas Pitre @ 2007-12-12 5:12 UTC (permalink / raw)
To: Jon Smirl; +Cc: Junio C Hamano, gcc, Git Mailing List
In-Reply-To: <9e4733910712110821o7748802ag75d9df4be8b2c123@mail.gmail.com>
On Tue, 11 Dec 2007, Jon Smirl wrote:
> On 12/11/07, Nicolas Pitre <nico@cam.org> wrote:
> > On Tue, 11 Dec 2007, Nicolas Pitre wrote:
> >
> > > OK, here's something else for you to try:
> > >
> > > core.deltabasecachelimit=0
> > > pack.threads=2
> > > pack.deltacachesize=1
> > >
> > > With that I'm able to repack the small gcc pack on my machine with 1GB
> > > of ram using:
> > >
> > > git repack -a -f -d --window=250 --depth=250
> > >
> > > and top reports a ~700m virt and ~500m res without hitting swap at all.
> > > It is only at 25% so far, but I was unable to get that far before.
> >
> > Well, around 55% memory usage skyrocketed to 1.6GB and the system went
> > deep into swap. So I restarted it with no threads.
> >
> > Nicolas (even more puzzled)
>
> On the plus side you are seeing what I see, so it proves I am not imagining it.
Well... This is weird.
It seems that memory fragmentation is really really killing us here.
The fact that the Google allocator did manage to waste quite less memory
is a good indicator already.
I did modify the progress display to show accounted memory that was
allocated vs memory that was freed but still not released to the system.
At least that gives you an idea of memory allocation and fragmentation
with glibc in real time:
diff --git a/progress.c b/progress.c
index d19f80c..46ac9ef 100644
--- a/progress.c
+++ b/progress.c
@@ -8,6 +8,7 @@
* published by the Free Software Foundation.
*/
+#include <malloc.h>
#include "git-compat-util.h"
#include "progress.h"
@@ -94,10 +95,12 @@ static int display(struct progress *progress, unsigned n, const char *done)
if (progress->total) {
unsigned percent = n * 100 / progress->total;
if (percent != progress->last_percent || progress_update) {
+ struct mallinfo m = mallinfo();
progress->last_percent = percent;
- fprintf(stderr, "%s: %3u%% (%u/%u)%s%s",
- progress->title, percent, n,
- progress->total, tp, eol);
+ fprintf(stderr, "%s: %3u%% (%u/%u) %u/%uMB%s%s",
+ progress->title, percent, n, progress->total,
+ m.uordblks >> 18, m.fordblks >> 18,
+ tp, eol);
fflush(stderr);
progress_update = 0;
return 1;
This shows that at some point the repack goes into a big memory surge.
I don't have enough RAM to see how fragmented memory gets though, since
it starts swapping around 50% done with 2 threads.
With only 1 thread, memory usage grows significantly at around 11% with
a pretty noticeable slowdown in the progress rate.
So I think the theory goes like this:
There is a block of big objects together in the list somewhere.
Initially, all those big objects are assigned to thread #1 out of 4.
Because those objects are big, they get really slow to delta compress,
and storing them all in a window with 250 slots takes significant
memory.
Threads 2, 3, and 4 have "easy" work loads, so they complete fairly
quicly compared to thread #1. But since the progress display is global
then you won't notice that one thread is actually crawling slowly.
To keep all threads busy until the end, those threads that are done with
their work load will steal some work from another thread, choosing the
one with the largest remaining work. That is most likely thread #1. So
as threads 2, 3, and 4 complete, they will steal from thread 1 and
populate their own window with those big objects too, and get slow too.
And because all threads gets to work on those big objects towards the
end, the progress display will then show a significant slowdown, and
memory usage will almost quadruple.
Add memory fragmentation to that and you have a clogged system.
Solution:
pack.deltacachesize=1
pack.windowmemory=16M
Limiting the window memory to 16MB will automatically shrink the window
size when big objects are encountered, therefore keeping much fewer of
those objects at the same time in memory, which in turn means they will
be processed much more quickly. And somehow that must help with memory
fragmentation as well.
Setting pack.deltacachesize to 1 is simply to disable the caching of
delta results entirely which will only slow down the writing phase, but
I wanted to keep it out of the picture for now.
With the above settings, I'm currently repacking the gcc repo with 2
threads, and memory allocation never exceeded 700m virt and 400m res,
while the mallinfo shows about 350MB, and progress has reached 90% which
has never occurred on this machine with the 300MB source pack so far.
Nicolas
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox