Re: Is cogito really this inefficient

On Thu, Jul 14, 2005 at 10:08:31AM +0100, Catalin Marinas wrote:

Russell King [off-list ref] wrote:

quoted

it appears that cg-diff does a

	git-update-cache --refresh >/dev/null

each time it's run, which is taking the bulk of the time.  Also note
that curiously, it exits with status 1.

Does git-ls-files --unmerged show any files?

No, and it returns fairly quickly:

$ /usr/bin/time git-ls-files --unmerged
0.29user 0.03system 0:00.43elapsed 73%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+655minor)pagefaults 0swaps

Actually, I should've left the sh -x /usr/bin/cg-diff drivers/serial/8250.c
running a little longer.  It's not the git-update-cache command which
is taking the time, it's git-diff-cache.

Running the diff several times, both with and without changes to
drivers/serial/8250.c, it seems that sometimes it's faster.  I guess
it has to do with dentry invalidation...

However, the point is - I've only asked for _one_ file.  Why do we need
to look at _every_ file in the tree?

I could understand this behaviour if I'd asked for a diff across the
whole tree, but I didn't.

Internally, the sha1 of the unmodified drivers/serial/8250.c should be
known, so should be trivial to unpack that and generate a diff.  Given
the cache, this should be something which should be lightning fast
when the requested fileset to diff is already known.

-- 
Russell King

On Thu, 14 Jul 2005, Russell King wrote:

Actually, I should've left the sh -x /usr/bin/cg-diff drivers/serial/8250.c
running a little longer.  It's not the git-update-cache command which
is taking the time, it's git-diff-cache.

Ok. git-diff-cache actually ends up reading your HEAD tree, and that, in
turn, is 1000+ tree objects. So it can take a while for the whole tree,
especially in the nonpacked and uncached case.

git-diff-tree (comparing two trees) is smart enough to limit itself to 
just the sub-trees that have been named, and would have compared the two 
trees by looking up just eight objects (three subdirectories from each 
tree, and then the file itself from both trees). 

But git-diff-cache isn't - because it's comparing the tree against the
index file, and the index is inevitably the whole tree.

And I now think I know what makes it slow. Not only are you basically
opening 1100 files (the tree objects - there's really that many
subdirectories in the kernel. Scary), but because you have alternate
object directories, and almost all of the objects are in the alternate
(not your primary), you'll basically always end up _first_ looking in the
primary, failing, and then looking in the alternate.

Together with the hashing, you'll be looking all over the place, in other
words ;)

Which means that you'll be needing a fair amount of memory to keep all of
those negative dentries etc cached (and the directory tree too).

This is something the pack-files will just help enormously with, but it
was only recently that we turned git around to check the pack-files
_first_, and the object directories second, so you probably won't see it
(not to mention that you probably don't have big pack-files at all ;)

I'll look into making diff-cache be more efficient. I normally don't use
it myself, so I didn't bother (I use git-diff-files, which is way more
efficient, but doesn't show the difference against the _tree_, it shows
the difference against the index. Since cogito tries to hide the index
from you, cogito can't very well use that).

			Linus

On Thu, 14 Jul 2005, Linus Torvalds wrote:

I'll look into making diff-cache be more efficient. I normally don't use
it myself, so I didn't bother (I use git-diff-files, which is way more
efficient, but doesn't show the difference against the _tree_, it shows
the difference against the index. Since cogito tries to hide the index
from you, cogito can't very well use that).

Ok, done.

I made git-diff-cache _and_ git-diff-files limit the pathnames early, so
that they don't even bother expanding the tree objects that are
irrelevant, and don't bother even validating index objects that don't
match the pathnames given.

Junio - I think this makes gitcore-pathspec pretty pointless, but I didn't
actually remove it. I guess "git-diff-helper" still uses it.

		Linus

Linus Torvalds [off-list ref] writes:

On Thu, 14 Jul 2005, Linus Torvalds wrote:

quoted

I'll look into making diff-cache be more efficient. I normally don't use
it myself, so I didn't bother (I use git-diff-files, which is way more
efficient, but doesn't show the difference against the _tree_, it shows
the difference against the index. Since cogito tries to hide the index
from you, cogito can't very well use that).

Ok, done.

Wonderful.

Junio - I think this makes gitcore-pathspec pretty pointless, but I didn't
actually remove it. I guess "git-diff-helper" still uses it.

And probably it shouldn't; diff-helper should be raw-to-patch
converter, nothing more.

Usually I'd volunteer to clean up the remaining mess (which was
originally my mess anyway) myself, but since I'd already asked
smurf to help cleaning up the diff option parsing, and recently
I've suddenly got quite busy in the day job, so ...