From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
Hi,
When I run 'git branch' in the linux-2.6 repo I think it takes
too long to finish (with cold cache):
[mafra@Pilar:linux-2.6]$ time git branch
27-stable
28-stable
29-stable
30-stable
dev-private
* master
option
sparse
stern
0.00user 0.05system 0:05.73elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (209major+1380minor)pagefaults 0swaps
This is with git 1.6.4.rc1.10.g2a67 and the kernel is 2.6.31-rc3+. The
machine is a 64bit Vaio laptop which is 1+ year old (so it is not "slow").
Repeating the command a second time takes basically zero seconds, but
this is more or less what I would expect in the first time too.
I use git to track linux-2.6 for 2 years now, and I remember that
'git branch' is slow for quite some time, so it is not a regression
or something. It is just now that I took the courage to report this
small issue.
I did a 'strace' and this is where it spent most of the time:
1248301060.654911 open(".git/refs/heads/sparse", O_RDONLY) = 6
1248301060.654985 read(6, "60afdf6a4065a170ad829b4d79a86ec0"..., 255) = 41
1248301060.655056 read(6, "", 214) = 0
1248301060.655116 close(6) = 0
1248301060.680754 lstat(".git/refs/heads/stern", 0x7fff80bfa8d0) = -1 ENOENT (No such file or directory)
1248301064.018491 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
1248301064.018641 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f409ffa7000
1248301064.018722 write(1, " 27-stable\33[m\n", 15) = 15
I don't know why .git/refs/heads/stern does not exist and why it takes
so long with it. That branch is functional ('git checkout stern' succeeds),
as well as all the others. But strangely .git/refs/heads/ contains only
[mafra@Pilar:linux-2.6]$ ls .git/refs/heads/
dev-private master sparse
which, apart from "master", are the last branches that I created.
I occasionally run 'git gc --aggressive --prune" to optimize the repo,
but other than that I don't do anything fancy, just 'pull' almost
every day and 'bisect' (which is becoming a rare event now :-)
So I would like to ask what should I do to recover the missing files
in .git/refs/heads/ (which apparently is the cause for my issue) and
how I can avoid losing them in the first place.
Also, is there a way to "fix" the 4-secs pause in that lstat() in
case the files in .git/refs/heads/ get lost again?
Thanks in advance,
Carlos
When I run 'git branch' in the linux-2.6 repo I think it takes
too long to finish (with cold cache):
[mafra@Pilar:linux-2.6]$ time git branch
27-stable
28-stable
29-stable
30-stable
dev-private
* master
option
sparse
stern
0.00user 0.05system 0:05.73elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (209major+1380minor)pagefaults 0swaps
This is with git 1.6.4.rc1.10.g2a67 and the kernel is 2.6.31-rc3+. The
machine is a 64bit Vaio laptop which is 1+ year old (so it is not "slow").
When have you last repacked the repository?
What you're descibing is basically IO overhead, and if you don't have
packed references, it's going to read a lot of small files.
I use git to track linux-2.6 for 2 years now, and I remember that
'git branch' is slow for quite some time, so it is not a regression
or something. It is just now that I took the courage to report this
small issue.
I did a 'strace' and this is where it spent most of the time:
1248301060.654911 open(".git/refs/heads/sparse", O_RDONLY) = 6
1248301060.654985 read(6, "60afdf6a4065a170ad829b4d79a86ec0"..., 255) = 41
1248301060.655056 read(6, "", 214) = 0
1248301060.655116 close(6) = 0
1248301060.680754 lstat(".git/refs/heads/stern", 0x7fff80bfa8d0) = -1 ENOENT (No such file or directory)
1248301064.018491 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
1248301064.018641 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f409ffa7000
1248301064.018722 write(1, " 27-stable\33[m\n", 15) = 15
I don't know why .git/refs/heads/stern does not exist and why it takes
so long with it. That branch is functional ('git checkout stern' succeeds),
as well as all the others. But strangely .git/refs/heads/ contains only
[mafra@Pilar:linux-2.6]$ ls .git/refs/heads/
dev-private master sparse
which, apart from "master", are the last branches that I created.
Ok, this actually means that you _have_ repacked the repo, and the rest of
the branches are all nicely packed in .git/packed-refs.
But that four _second_ lstat() is really disgusting.
Let me guess: if you do a "ls -ld .git/refs/heads" you get a very big
directory, despite it only having three entries in it. And your filesystem
doesn't have name hashing enabled, so searching for a non-existent file
involves looking through _all_ of the empty slots.
Try this:
git pack-refs --all
rmdir .git/refs/heads
rmdir .git/refs/tags
mkdir .git/refs/heads
mkdir .git/refs/tags
and see if it magically speeds up.
Linus
From: SZEDER Gábor <hidden> Date: 2016-06-15 22:47:05
Hi,
On Thu, Jul 23, 2009 at 01:59:14AM +0200, Carlos R. Mafra wrote:
I don't know why .git/refs/heads/stern does not exist and why it takes
so long with it. That branch is functional ('git checkout stern' succeeds),
as well as all the others. But strangely .git/refs/heads/ contains only
[mafra@Pilar:linux-2.6]$ ls .git/refs/heads/
dev-private master sparse
which, apart from "master", are the last branches that I created.
I occasionally run 'git gc --aggressive --prune" to optimize the repo,
but other than that I don't do anything fancy, just 'pull' almost
every day and 'bisect' (which is becoming a rare event now :-)
So I would like to ask what should I do to recover the missing files
in .git/refs/heads/ (which apparently is the cause for my issue) and
how I can avoid losing them in the first place.
have a look at .git/packed-refs and 'git pack-refs'.
Best,
Gábor
Try this:
git pack-refs --all
rmdir .git/refs/heads
rmdir .git/refs/tags
mkdir .git/refs/heads
mkdir .git/refs/tags
and see if it magically speeds up.
In fact, you could also just try
mv .git/refs .git/temp-refs &&
cp -a .git/temp-refs .git/refs &&
rm -rf .git/temp-refs
which will re-create other subdirectories too (like .git/refs/remotes
etc).
Of course, depending on your particular filesystem, a better fix might be
to enable filename hashing, which gets rid of the whole "look through all
the old empty stale directory entries to see if there's a filename there"
issue. That won't fix 'readdir()' performance, but it should fix your
insane 4-second lstat() thing.
If you have ext3, you'd do something like
tune2fs -O dir_index /dev/<node-of-your-filesystem-goes-here>
but as mentioned, even with directory indexing it can actually make sense
to recreate directories that at some point _used_ to be large, but got
shrunk down to something much smaller. It's a generic directory problem
(not just ext3, not just unix, it's a common issue across filesystems.
It's not _universal_ - some smarter filesystems really do shrink their
directories - but it's certainly not unusual).
Linus
If you have ext3, you'd do something like
tune2fs -O dir_index /dev/<node-of-your-filesystem-goes-here>
One last email note on this subject. Really. Promise.
If you do that "tune2fs -O dir_index" thing, it will only take effect for
_newly_ created directories. So you'll still need to do that whole
"mv+cp+rm" dance, just to make sure that the refs directories are all new.
I think you can also force all directories to be indexed by using fsck,
but I forget the details. I'm sure man-pages will have it. Or google.
Linus
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
On Wed 22.Jul'09 at 17:21:48 -0700, Linus Torvalds wrote:
When have you last repacked the repository?
Last week or so, with 'git repack -d -a'
quoted
[mafra@Pilar:linux-2.6]$ ls .git/refs/heads/
dev-private master sparse
which, apart from "master", are the last branches that I created.
Ok, this actually means that you _have_ repacked the repo, and the rest of
the branches are all nicely packed in .git/packed-refs.
Yes, now I saw the other branches inside packed-refs.
But that four _second_ lstat() is really disgusting.
Let me guess: if you do a "ls -ld .git/refs/heads" you get a very big
directory, despite it only having three entries in it.
And your filesystem
doesn't have name hashing enabled, so searching for a non-existent file
involves looking through _all_ of the empty slots.
I use ext3 without changing any defaults that I know of (I simply compile
and boot the kernel of the day), and I have no idea if name hashing
is enabled here.
Try this:
git pack-refs --all
rmdir .git/refs/heads
rmdir .git/refs/tags
mkdir .git/refs/heads
mkdir .git/refs/tags
and see if it magically speeds up.
It didn't change things, unfortunately.
After 'echo 3 > /proc/sys/vm/drop_caches' it still takes too long,
1248310449.693085 munmap(0x7f50bcd11000, 164) = 0
1248310449.693187 lstat(".git/refs/heads/sparse", 0x7fff618c0960) = -1 ENOENT (No such file or directory)
1248310449.719112 lstat(".git/refs/heads/stern", 0x7fff618c0960) = -1 ENOENT (No such file or directory)
1248310453.014041 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 3), ...}) = 0
1248310453.014183 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f50bcd11000
Perhaps I should delete the "stern" branch, but I would like to learn why
it is slowing things, because it also happened before (in fact it is always
like this, afaicr)
Do you have another theory? (now .git/refs/heads is empty)
Thanks,
Carlos
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
On Wed 22.Jul'09 at 17:55:51 -0700, Linus Torvalds wrote:
On Wed, 22 Jul 2009, Linus Torvalds wrote:
quoted
If you have ext3, you'd do something like
tune2fs -O dir_index /dev/<node-of-your-filesystem-goes-here>
One last email note on this subject. Really. Promise.
If you do that "tune2fs -O dir_index" thing, it will only take effect for
_newly_ created directories. So you'll still need to do that whole
"mv+cp+rm" dance, just to make sure that the refs directories are all new.
Ok, now I also did the "dir_index" thing followed by the mv+cp+rm instructions.
It doesn't change the 3.5 secs delay in that single line,
1248313742.355195 lstat(".git/refs/heads/sparse", 0x7fff0c663ab0) = -1 ENOENT (No such file or directory)
1248313742.381178 lstat(".git/refs/heads/stern", 0x7fff0c663ab0) = -1 ENOENT (No such file or directory)
1248313745.804637 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
Just to double check,
[root@Pilar linux-2.6]# tune2fs -l /dev/sda5 |grep dir_index
Filesystem features: has_journal ext_attr resize_inode dir_index filetype needs_recovery sparse_super large_file
(and I did the mv+cp+rm after setting "dir_index")
Is there another way to check what is going on with that anomalous lstat()?
[ perhaps I will try 'perf' after I read how to use it ]
Thanks,
Carlos
Hmm. That's just a single block.
Then I really don't see why the lstat takes so long.
After 'echo 3 > /proc/sys/vm/drop_caches' it still takes too long,
1248310449.693085 munmap(0x7f50bcd11000, 164) = 0
1248310449.693187 lstat(".git/refs/heads/sparse", 0x7fff618c0960) = -1 ENOENT (No such file or directory)
1248310449.719112 lstat(".git/refs/heads/stern", 0x7fff618c0960) = -1 ENOENT (No such file or directory)
1248310453.014041 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 3), ...}) = 0
1248310453.014183 mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f50bcd11000
Use 'strace -T', which shows how long the actual system calls take, rather
than '-tt' which just shows when they started.
Maybe the four seconds is something else than the lstat - page faults on
the pack-file in between the lstat and the fstat, for example.
Perhaps I should delete the "stern" branch, but I would like to learn why
it is slowing things, because it also happened before (in fact it is always
like this, afaicr)
Absolutely. Don't delete it until we figure out what takes so long there.
Do you have another theory? (now .git/refs/heads is empty)
Clearly it's IO, but if that 'lstat()' was just a red herring, then I
suspect it's IO on the pack-file. If so, I'd further guess that your VAIO
has some pitiful 4200rpm harddisk that is slow as hell and has horrible
seek latencies, and the CPU is way overpowered compared to the cruddy
disk.
It probably does the object lookup. You can see some debug output if you
do
GIT_DEBUG_LOOKUP=1 git branch
and that will show you the patterns. It won't be very pretty, especially
if you have several pack-files, but maybe we can figure out what's up.
Hmm. I wonder.. I suspect 'git branch' looks up _all_ refs, and then
afterwards it filters them. So even though it only prints out a few
branches, maybe it will look at all the tags etc of the whole repository.
Ooh yes. That would do it. It's going to peel and look up every single ref
it finds, so it's going to look up _hundreds_ of objects (all the tags,
all the commits they point to, etc etc). Even if it then only shows a
couple of branches.
Junio, any ideas?
Linus
Ooh yes. That would do it. It's going to peel and look up every single ref
it finds, so it's going to look up _hundreds_ of objects (all the tags,
all the commits they point to, etc etc). Even if it then only shows a
couple of branches.
Junio, any ideas?
I had one of my own.
Does this fix it?
It uses the "raw" version of 'for_each_ref()' (which doesn't verify that
the ref is valid), and then does the "type verification" before it starts
doing any gentle commit lookup.
That should hopefully mean that it no longer does tons of object lookups
on refs that it's not actually interested in.
Linus
---
builtin-branch.c | 10 +++++-----
1 files changed, 5 insertions(+), 5 deletions(-)
@@ -240,6 +240,10 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,if(ARRAY_SIZE(ref_kind)<=i)return0;+/* Don't add types the caller doesn't want */+if((kind&ref_list->kinds)==0)+return0;+commit=lookup_commit_reference_gently(sha1,1);if(!commit)returnerror("branch '%s' does not point at a commit",refname);
@@ -248,10 +252,6 @@ static int append_ref(const char *refname, const unsigned char *sha1, int flags,if(!is_descendant_of(commit,ref_list->with_commit))return0;-/* Don't add types the caller doesn't want */-if((kind&ref_list->kinds)==0)-return0;-if(merge_filter!=NO_FILTER)add_pending_object(&ref_list->revs,(structobject*)commit,refname);
@@ -426,7 +426,7 @@ static void print_ref_list(int kinds, int detached, int verbose, int abbrev, strref_list.with_commit=with_commit;if(merge_filter!=NO_FILTER)init_revisions(&ref_list.revs,NULL);-for_each_ref(append_ref,&ref_list);+for_each_rawref(append_ref,&ref_list);if(merge_filter!=NO_FILTER){structcommit*filter;filter=lookup_commit_reference_gently(merge_filter_ref,0);
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
Hi,
On Wed 22.Jul'09 at 19:23:23 -0500, SZEDER Gábor wrote:
quoted
So I would like to ask what should I do to recover the missing files
in .git/refs/heads/ (which apparently is the cause for my issue) and
how I can avoid losing them in the first place.
have a look at .git/packed-refs and 'git pack-refs'.
Yes, now I learned that the files were not really missing
as in "there is something wrong".
I will also start to use 'git pack-refs --prune' from time to time
now, in adition to 'git gc --prune' and 'git repack -d -a'.
But the takes-too-long 'git branch' issue is apparently caused
by something else.
Thanks Gábor,
Carlos
Is there another way to check what is going on with that anomalous lstat()?
I really don't think it's the lstat any more. Your directories look small
and simple, and clearly the indexing made no difference.
See earlier email about using "strace -T" instead of "-tt". Also, I sent
you a patch to try out just a minute ago, I think that may be it.
[ perhaps I will try 'perf' after I read how to use it ]
I really like 'perf' (it does what oprofile did for me, but without the
headaches), but it doesn't help with IO profiling.
I've actually often wanted to have a 'strace' that shows page faults as
special system calls, but it's sadly nontrivial ;(
Linus
It uses the "raw" version of 'for_each_ref()' (which doesn't verify that
the ref is valid), and then does the "type verification" before it starts
doing any gentle commit lookup.
That should hopefully mean that it no longer does tons of object lookups
on refs that it's not actually interested in.
Hmm. On my kernel repo, doing
GIT_DEBUG_LOOKUP=1 git branch | wc -l
I get
- before: 2121
- after: 39
(where two of the lines are the actual 'git branch' output). So yeah, this
should make a big difference. It now looks up just two objects (one of
them duplicated because it checks "HEAD" - but the duplicate lookup won't
result in any extra IO, so it's only two _uncached_ accesses).
The GIT_DEBUG_LOOKUP debug output probably does match the number of
cold-cache IO's fairly well for something like this (at least to a first
approximation), so I really hope my patch will fix your problem.
Linus
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
First of all:
* yes, my VAIO has a slow 4200 rpm disc :-(
* strace -T indeed showed that lstat() was not guilty
* GIT_DEBUG_LOOKUP=1 git branch produced ugly 2200+ lines
Now to the patch,
On Wed 22.Jul'09 at 19:23:39 -0700, Linus Torvalds wrote:
quoted
Ooh yes. That would do it. It's going to peel and look up every single ref
it finds, so it's going to look up _hundreds_ of objects (all the tags,
all the commits they point to, etc etc). Even if it then only shows a
couple of branches.
Junio, any ideas?
I had one of my own.
Does this fix it?
Yes!
[mafra@Pilar:linux-2.6]$ time git branch
27-stable
28-stable
29-stable
30-stable
dev-private
* master
option
sparse
stern
0.00user 0.01system 0:01.50elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (42major+757minor)pagefaults 0swaps
01.50 is not that good, but it doesn't "feel" terrible as 4 seconds.
[ It is incredible how 4 secs feels really bad while 2 is acceptable... ]
So thank you very much, Linus! A 50% improvement here!
And I am happy to have finally reported it, after quietly suffering for so long
thinking that "git is as fast as possible, so it is probably my fault".
PS: Out of curiosity, how many femtoseconds does it take in your
state-of-the-art machine? :-)
The GIT_DEBUG_LOOKUP debug output probably does match the number of
cold-cache IO's fairly well for something like this (at least to a first
approximation), so I really hope my patch will fix your problem.
Side note: the object lookup binary search we do is simple and reasonably
efficient, but it is _not_ very cache-friendly (where "cache-friendly"
also in this case means IO caches).
There are more cache-friendly ways of searching, although the really
clever ones would require us to switch the format of the pack-file index
around. Which would be a fairly big pain (in addition to making the lookup
a lot more complex).
The _simpler_ cache-friendly alternative is likely to try the "guess
location by assuming the SHA1's are evenly spread out" thing doesn't jump
back-and-forth like a binary search does.
We tried it a few years ago, but didn't do cold-cache numbers. And
repositories were smaller too.
With something like the kernel repo, with 1.2+ million objects, a binary
search needs about 21 comparisons for each object we look up. The index
has a first-level fan-out of 256, so that takes away 8 of them, but we're
still talking about 13 comparisons. With bad locality except for the very
last ones.
Assuming a 4kB page-size, and about 170 index entries per page (~7 binary
search levels), that's 6 pages we have to page-fault in for each search.
And we probably won't start seeing lots of cache reuse until we hit
hundreds or thousands of objects searched for.
With soemthing like "three iterations of newton-raphson + linear search",
we might end up with more index entries looked at, but we'd quite possibly
get much better locality.
I suspect the old newton-raphson patches we had (Discussions and patches
back in April 2007 on this list) could be resurrected pretty easily.
Linus
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
On Thu 23.Jul'09 at 5:18:44 +0200, Carlos R. Mafra wrote:
0.00user 0.01system 0:01.50elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (42major+757minor)pagefaults 0swaps
01.50 is not that good, but it doesn't "feel" terrible as 4 seconds.
[ It is incredible how 4 secs feels really bad while 2 is acceptable... ]
I need to sleep, as the number 4 seconds got stuck in my head. In my original
report it was much worse
0.00user 0.05system 0:05.73elapsed
So now it was a 75% improvement!
PS: Out of curiosity, how many femtoseconds does it take in your
state-of-the-art machine? :-)
Cold cache? 0.15s before the patch. 0.03s after.
So we're not talking femto-seconds, but I've got Intel SSD's that do
random reads in well under a millisecond. Your pitiful 4200rpm drive
probably takes 20ms for each seek. You don't really need that many IO's
for it to take a second or two. Or four.
The kernel will do IO in bigger chunks than a single page, and there is
_some_ locality to it all, so you won't see IO for each lookup. But with
2000+ lines of GIT_DEBUG_LOOKUP, you probably do end up having a
noticeable fraction of them being IO-causing, and another fraction causing
seeks.
But I'll see if I can dig up my non-binary-search patch and see if I can
make it go faster. My machine is fast, but not so fast that I can't
measure it ;)
Linus
But I'll see if I can dig up my non-binary-search patch and see if I can
make it go faster. My machine is fast, but not so fast that I can't
measure it ;)
Oh. We actually merged a fixed version of it. I'd completely forgotten.
Enabled with 'GIT_USE_LOOKUP'. But it seems to give worse performance,
despite giving me fewer searches: I get 2121 probes with binary searching,
but only 1325 with the newton-raphson method (for the non-fixed 'git
branch' case).
Using GIT_USE_LOOKUP actually results in fewer pagefaults (1391 vs 1473),
but it's still slower. Interesting. Carlos, try it on your machine (just
do
export GIT_USE_LOOKUP=1
time git branch
to try it, and 'unset GIT_USE_LOOKUP' to disable it.
(And note that the "=1" part isn't important - the only thing that matters
is whether the environment variable is set or not - setting it to '0' will
_not_ disable it, you need to 'unset' it).
With my fix to 'git branch', it doesn't matter. I get the same
performance, and same number of page faults (676) regardless. So my patch
makes the GIT_USE_LOOKUP=1 thing irrelevant.
Linus
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
On Wed 22.Jul'09 at 21:10:49 -0700, Linus Torvalds wrote:
Enabled with 'GIT_USE_LOOKUP'. But it seems to give worse performance,
despite giving me fewer searches: I get 2121 probes with binary searching,
but only 1325 with the newton-raphson method (for the non-fixed 'git
branch' case).
Using GIT_USE_LOOKUP actually results in fewer pagefaults (1391 vs 1473),
but it's still slower. Interesting. Carlos, try it on your machine (just
do
export GIT_USE_LOOKUP=1
time git branch
to try it, and 'unset GIT_USE_LOOKUP' to disable it.
GIT_USE_LOOKUP=1 makes is a bit slower overall.
Without your patch, I get fewer pagefaults (1254 vs 1404) when
it is set, but it takes ~0.5s longer (it varies a bit).
With my fix to 'git branch', it doesn't matter. I get the same
performance, and same number of page faults (676) regardless. So my patch
makes the GIT_USE_LOOKUP=1 thing irrelevant.
With your patch and GIT_USE_LOOKUP=1 I get 751 pagefaults, versus 775
if GIT_USE_LOOKUP is unset, but it is faster when unset.
So your patch without GIT_USE_LOOKUP=1 is the fastest option.
From: Jakub Narebski <hidden> Date: 2016-06-15 22:47:05
Linus Torvalds [off-list ref] writes:
On Thu, 23 Jul 2009, Carlos R. Mafra wrote:
quoted
Is there another way to check what is going on with that anomalous lstat()?
I really don't think it's the lstat any more. Your directories look small
and simple, and clearly the indexing made no difference.
See earlier email about using "strace -T" instead of "-tt". Also, I sent
you a patch to try out just a minute ago, I think that may be it.
quoted
[ perhaps I will try 'perf' after I read how to use it ]
I really like 'perf' (it does what oprofile did for me, but without the
headaches), but it doesn't help with IO profiling.
I've actually often wanted to have a 'strace' that shows page faults as
special system calls, but it's sadly nontrivial ;(
BTW. Would SystemTap help there? Among contributed scripts there is
iotimes, so perhaps it would be possible to have iotrace...
--
Jakub Narebski
Poland
ShadeHawk on #git
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
On Thu 23.Jul'09 at 5:42:03 -0700, Jakub Narebski wrote:
Linus Torvalds [off-list ref] writes:
quoted
On Thu, 23 Jul 2009, Carlos R. Mafra wrote:
quoted
Is there another way to check what is going on with that anomalous lstat()?
I really don't think it's the lstat any more. Your directories look small
and simple, and clearly the indexing made no difference.
See earlier email about using "strace -T" instead of "-tt". Also, I sent
you a patch to try out just a minute ago, I think that may be it.
quoted
[ perhaps I will try 'perf' after I read how to use it ]
I really like 'perf' (it does what oprofile did for me, but without the
headaches), but it doesn't help with IO profiling.
I've actually often wanted to have a 'strace' that shows page faults as
special system calls, but it's sadly nontrivial ;(
BTW. Would SystemTap help there? Among contributed scripts there is
iotimes, so perhaps it would be possible to have iotrace...
I played a bit with 'blktrace' and 'btrace' and had two terminals
open side by side, one with 'strace git branch' and the other with
'blktrace'.
It was pretty obvious that exactly at the point where 'git branch'
was stalling (without Linus' patch) -- which I thought had to do
with lstat() -- there was a flurry of activity going on in 'btrace'
output.
It would be nice if 'btrace' could be somehow unified with 'strace',
if that makes any sense.
Here are some numbers from my tests with blktrace (blkparse and btrace):
[root@Pilar mafra]# grep git blkparse-patch.txt |wc -l
811
[root@Pilar mafra]# grep git blkparse-nopatch.txt |wc -l
3479
where those lines with 'git' are something like
8,5 0 677 1.787350654 18591 I R 204488479 + 40 [git]
8,0 0 678 1.787370489 18591 A R 204488783 + 96 <- (8,5) 137529800
8,5 0 679 1.787371886 18591 Q R 204488783 + 96 [git]
8,5 0 680 1.787375378 18591 G R 204488783 + 96 [git]
8,5 0 681 1.787377613 18591 I R 204488783 + 96 [git]
And the summary lines also indicate that the non-patched git makes
the disc work much harder:
*************** Without Linus' patch ******************************************
Total (8,5):
Reads Queued: 764, 20,008KiB Writes Queued: 0, 0KiB
Read Dispatches: 764, 20,008KiB Write Dispatches: 0, 0KiB
Reads Requeued: 0 Writes Requeued: 0
Reads Completed: 764, 20,008KiB Writes Completed: 0, 0KiB
Read Merges: 0, 0KiB Write Merges: 0, 0KiB
IO unplugs: 299 Timer unplugs: 2
Throughput (R/W): 4,003KiB/s / 0KiB/s
Events (8,5): 5,266 entries
Skips: 0 forward (0 - 0.0%)
************** With Linus' patch **********************************************
Total (sda5):
Reads Queued: 171, 3,128KiB Writes Queued: 6, 24KiB
Read Dispatches: 171, 3,128KiB Write Dispatches: 2, 24KiB
Reads Requeued: 0 Writes Requeued: 0
Reads Completed: 171, 3,128KiB Writes Completed: 2, 24KiB
Read Merges: 0, 0KiB Write Merges: 4, 16KiB
IO unplugs: 80 Timer unplugs: 0
Throughput (R/W): 1,632KiB/s / 12KiB/s
Events (sda5): 1,226 entries
Skips: 0 forward (0 - 0.0%)
BTW. Would SystemTap help there? Among contributed scripts there is
iotimes, so perhaps it would be possible to have iotrace...
The problem I've had with all iotracers is that it's easy enough to get an
IO trace, but it's basically almost impossible to integrate it with what
actually _caused_ the IO.
Using 'strace -T' shows very clearly what operations are taking a long
time. It's very useful for seeing what you should not do for good
performance - including IO - and where it comes from. It's just that page
faults are invisible to it.
Linus
From: Anders Kaseorg <hidden> Date: 2016-06-15 22:47:05
On Wed, 22 Jul 2009, Linus Torvalds wrote:
It uses the "raw" version of 'for_each_ref()' (which doesn't verify that
the ref is valid), and then does the "type verification" before it starts
doing any gentle commit lookup.
I submitted essentially the same patch in May:
http://article.gmane.org/gmane.comp.version-control.git/120097
with the additional optimization that we don’t need to lookup commits at
all unless we’re using -v, --merged, --no-merged, or --contains. In my
tests, it makes `git branch` 5 times faster on an uncached linux-2.6
repository.
Anders
From: Tony Finch <dot@dotat.at> Date: 2016-06-15 22:47:05
On Wed, 22 Jul 2009, Linus Torvalds wrote:
I suspect the old newton-raphson patches we had (Discussions and patches
back in April 2007 on this list) could be resurrected pretty easily.
That sounds interesting, but I can't find the thread you are referring to.
Do you have a URL or a subject I can feed to Google?
Tony.
--
f.anthony.n.finch [off-list ref] http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.
I suspect the old newton-raphson patches we had (Discussions and patches
back in April 2007 on this list) could be resurrected pretty easily.
That sounds interesting, but I can't find the thread you are referring to.
Do you have a URL or a subject I can feed to Google?
Some googling found this:
http://marc.info/?l=git&m=117537594112450&w=2
but what got merged (half a year later) was a much fancier thing by Junio.
See sha1-lookup.c.
That original "single iteration of newton-raphson" patch was buggy, but
it's perhaps interesting as a concept patch.
Linus
From: Carlos R. Mafra <hidden> Date: 2016-06-15 22:47:05
On Thu 23.Jul'09 at 12:48:20 -0400, Anders Kaseorg wrote:
I submitted essentially the same patch in May:
http://article.gmane.org/gmane.comp.version-control.git/120097
with the additional optimization that we don't need to lookup commits at
all unless we're using -v, --merged, --no-merged, or --contains. In my
tests, it makes `git branch` 5 times faster on an uncached linux-2.6
repository.
I also tested your patch even if you said that it was "essentially the same".
But after repeating the tests 6 times for both your and Linus' patch
(taking care to let the system rest a bit after clearing the cache), your
patch is faster,
0.62 +/- 0.24 (Anders)
1.35 +/- 0.23 (Linus)
And this is the raw data for your patch,
0.00user 0.01system 0:00.54elapsed 2%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (7major+727minor)pagefaults 0swaps
0.00user 0.00system 0:00.18elapsed 5%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (1major+733minor)pagefaults 0swaps
0.00user 0.00system 0:00.66elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (9major+723minor)pagefaults 0swaps
0.00user 0.01system 0:00.74elapsed 2%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (14major+720minor)pagefaults 0swaps
0.00user 0.00system 0:00.80elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (16major+718minor)pagefaults 0swaps
0.00user 0.00system 0:00.83elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (16major+718minor)pagefaults 0swaps
and for Linus'
0.00user 0.01system 0:01.56elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (43major+755minor)pagefaults 0swaps
0.00user 0.01system 0:01.09elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (24major+775minor)pagefaults 0swaps
0.00user 0.01system 0:01.33elapsed 1%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (32major+767minor)pagefaults 0swaps
0.00user 0.00system 0:01.53elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (39major+760minor)pagefaults 0swaps
0.00user 0.01system 0:01.06elapsed 2%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (24major+775minor)pagefaults 0swaps
0.00user 0.00system 0:01.54elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (39major+760minor)pagefaults 0swaps
Thanks. Edésio Costa e Silva also gave me a useful pointer.
That original "single iteration of newton-raphson" patch was buggy, but
it's perhaps interesting as a concept patch.
I think Newton-Raphson is a brilliant but misleading idea. (As Junio said,
"egg of Columbus" - it certainly blew my mind!) However, Newton's method
works with smooth curves, but a pack index is a straight line plus
stochastic deviations. If you try to apply Newton's method then the more
you zoom in the more the random variations will send you away from the
place you want to be. So I think your first N-R patch was closer to being
right than its successors.
What you should do is ONE linear interpolation on the entire index. (i.e.
If you have N objects in the pack and you want to find one with SHA-1 id
S, take the top four bytes of S and multiply by N/2^32.) Note that if you
do a level-1 256-way fan-out lookup first then the random variations will
make you LESS likely to land near the right place.
After doing the first-order linear interpolation, it's probably sensible
to do a page-wise linear search (in case you don't land directly on
the page containing the target SHA-1) then a binary search within the
final page for efficiency with a hot cache.
This should give you O(1) seeks in the index per object lookup.
Tony.
--
f.anthony.n.finch [off-list ref] http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:47:05
Hi,
On Thu, 23 Jul 2009, Tony Finch wrote:
I think Newton-Raphson is a brilliant but misleading idea. (As Junio
said, "egg of Columbus" - it certainly blew my mind!) However, Newton's
method works with smooth curves, but a pack index is a straight line
plus stochastic deviations. If you try to apply Newton's method then the
more you zoom in the more the random variations will send you away from
the place you want to be.
No.
Think about it, absent any further information than "it is a hash, i.e.
distributed pretty equally in _any_ byte", even subsets of a sorted list
will me more or less linear. And assuming that they are linear is _still_
your best bet.
Assuming that subsets of said sorted list will _still_ minimize the
average number of steps to take until you find the correct entry.
Unless you have more information about the nature of the hashes, of
course.
This should give you O(1) seeks in the index per object lookup.
There is no way to achieve that, best thing you can hope for is _expected_
O(1) (e.g. with a hashmap, with exponential worst case).
Ciao,
Dscho
From: Tony Finch <dot@dotat.at> Date: 2016-06-15 22:47:05
On Fri, 24 Jul 2009, Johannes Schindelin wrote:
Think about it, absent any further information than "it is a hash, i.e.
distributed pretty equally in _any_ byte", even subsets of a sorted list
will me more or less linear. And assuming that they are linear is _still_
your best bet.
The even distribution of the lower-order bytes is irrelevant. We're
looking at the top 20-ish bits for a pack with a million-ish objects. The
more you zoom in the less linear a sorted list of hashes will be, so
assuming linearity at all scales is wrong. It's a bit like fractal
mountains.
There is no way to achieve [O(1) seeks], best thing you can hope for is
_expected_ O(1) (e.g. with a hashmap, with exponential worst case).
Of course it's expected. However the worst case is nowhere near
exponential: it's linear because the second-order search is a linear
pagewise scan. But I think in practice, the larger the pack the more that
the randomization of the hash function will smooth out performance
oddities. (Sorry, I don't know enough statistics to be able to say what
the expected error of the linear interpolation is, though I expect it's a
fairly simple formula.) For small packs the number of seeks is 1 anyway.
Tony.
--
f.anthony.n.finch [off-list ref] http://dotat.at/
GERMAN BIGHT HUMBER: SOUTHWEST 5 TO 7. MODERATE OR ROUGH. SQUALLY SHOWERS.
MODERATE OR GOOD.
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:47:05
Hi,
On Fri, 24 Jul 2009, Tony Finch wrote:
On Fri, 24 Jul 2009, Johannes Schindelin wrote:
quoted
Think about it, absent any further information than "it is a hash, i.e.
distributed pretty equally in _any_ byte", even subsets of a sorted list
will me more or less linear. And assuming that they are linear is _still_
your best bet.
The even distribution of the lower-order bytes is irrelevant.
I was not talking about lower-order bytes. All bytes are pretty much
evenly distributed. That's why SHA-1 is a good hash.
We're looking at the top 20-ish bits for a pack with a million-ish
objects. The more you zoom in the less linear a sorted list of hashes
will be, so assuming linearity at all scales is wrong. It's a bit like
fractal mountains.
If you really find irregularities like that, then SHA-1 is really a lousy
hash. Irregularities like this are typically exploitable.
If you know of such an irregularity, you might want to write a paper that
SHA-1 is broken and get famous.
quoted
There is no way to achieve [O(1) seeks], best thing you can hope for
is _expected_ O(1) (e.g. with a hashmap, with exponential worst case).
Of course it's expected. However the worst case is nowhere near
exponential: it's linear because the second-order search is a linear
pagewise scan. But I think in practice, the larger the pack the more that
the randomization of the hash function will smooth out performance
oddities. (Sorry, I don't know enough statistics to be able to say what
the expected error of the linear interpolation is, though I expect it's a
fairly simple formula.) For small packs the number of seeks is 1 anyway.