stat very inefficient
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"viro" == viro <[email protected]> writes:
Quoted 7 lines · David S. Miller
Quoted 7 lines
I was about to make sparc64 specific copies of all the stat system calls in order to optimize this properly. But that makes little sense, instead I think
fs/stat.cshould call upon arch-specific stat{,64} structure fillin routines that can do the magic, given a kstat struct.Comments?
viro> I'm not sure that it's worth doing for anything below the viro> "widest" version of stat. For that one - yeah, no objections.
Agree -- glibc redirects stat() to stat64() under many compilation models.
But is stat{,64} actually showing up badly in profiles? If it's not I don't think it's worth doing *anything* (I can imagine loads where it would, e.g., make on a large sourcetree, or running a backup)
--
Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au The technical we do immediately, the political takes *forever*
Quoted 4 lines · On Thu, 29 Jul 2004 08:33:59 +1000 Peter Chubb <[email protected]> wrote:
But is stat{,64} actually showing up badly in profiles? If it's not I don't think it's worth doing *anything* (I can imagine loads where it would, e.g., make on a large sourcetree, or running a backup)
"find . -type f" is probably the most often run command somewhere in a shell pipeline when I'm doing kernel work and grepping around.
Quoted 2 lines · David S. Miller
"find . -type f" is probably the most often run command somewhere in a shell pipeline when I'm doing kernel work and grepping around.
Just How bad is it for you? I just tested stat on my crapbox and for a short path 1M stats takes 0.5s and for a longer path (30 bytes or so) 2.8s.
Sure, it's always nice to make things faster, but given that whatever else I'm doing with this information will most likely be *many* times slower I'm not sure if reducing it to zero would make any appreciable difference here...
--cw
Quoted 3 lines · On Wed, 28 Jul 2004 17:08:37 -0700 Chris Wedgwood <[email protected]> wrote:
Just How bad is it for you? I just tested stat on my crapbox and for a short path 1M stats takes 0.5s and for a longer path (30 bytes or so) 2.8s.
Run "time find . -type f" on the kernel tree, both before and after removing the third unnecessary copy. Many machines sit all day and stat files.
Quoted 3 lines · David S. Miller
Run "time find . -type f" on the kernel tree, both before and after removing the third unnecessary copy. Many machines sit all day and stat files.
On an old crappy ia32 machine:
cw@taniwha:~/wk/linux/cw-current$ time find . -noleaf | wc
42372 42372 1549653 real 0m0.188s
user 0m0.042s
sys 0m0.146sthat 0.2s to make almost 50K stat64 calls (if you strace and grep you can see that count).
Since I have to do something with that data (ie. build a kernel) and that's *probably* going to take many seconds, even making the stat overhead 0 wouldn't put much of dent into the overall time.
What am I missing?
--cw
Quoted 9 lines · David S. Miller
Quoted 3 lines · On Wed, 28 Jul 2004 17:08:37 -0700 Chris Wedgwood <[email protected]> wrote:
Just How bad is it for you? I just tested stat on my crapbox and for a short path 1M stats takes 0.5s and for a longer path (30 bytes or so) 2.8s.
Run "time find . -type f" on the kernel tree, both before and after removing the third unnecessary copy.
... with hot cache, otherwise IO time will dominate. I don't disagree with you, but in all realistic cases I can think of it's going to be noise (e.g. this find over kernel tree is almost certainly followed by xargs grep, etc.).
Quoted 11 lines
Quoted 11 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
"viro" == viro <[email protected]> writes:
Quoted 1 line · On Wed, 28 Jul 2004 17:08:37 -0700 Chris Wedgwood <[email protected]> wrote:
Just How bad is it for you? I just tested stat on my crapbox and
for > a short path 1M stats takes 0.5s and for a longer path (30 bytes or > so) 2.8s.
Run "time find . -type f" on the kernel tree, both before and after removing the third unnecessary copy.
viro> ... with hot cache, otherwise IO time will dominate. I don't viro> disagree with you, but in all realistic cases I can think of viro> it's going to be noise (e.g. this find over kernel tree is viro> almost certainly followed by xargs grep, etc.).
With hot cache the system time is really small.
On a 2GHz Pentium 4, Compare
find .-type f -mtime -2000 >/dev/null with find . -type f -mtime -2000
in a freshly checked out 2.8 kernel tree.
(the -mtime test is to force a stat, otherwise, as Ulrich says, almost no stat system calls will take place)
to xterm >/dev/null | xargs grep foo
sys 0.34 0.103 0.35
user 0.29 0.08 0.104
real 18.551 0.204 220.25
Using strace reveals that around 60% of the system time in the redirected to /dev/null case is lstat64 --- 41465 calls, 1.5usec per call. Where it's in a pipe that uses the files, the time is swamped by the time to process the files, and the time spent in write() --- lstat64 drops to around 16% of the time in find.
The nice thing about the current three-copy implementation is that it's simple and obviously correct. Personally, I don't think that the increased complexity of arhcitecture-specific callbacks, etc., is worth the small performance gain.
--
Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au The technical we do immediately, the political takes *forever*
Quoted 6 lines · Peter Chubb
The nice thing about the current three-copy implementation is that it's simple and obviously correct. Personally, I don't think that the increased complexity of arhcitecture-specific callbacks, etc., is worth the small performance gain.
hmm. Here's a Pentium III profile of a 260,000-file `find 00000000 -type f -mtime 2000':
00000000c015fcb0 __user_walk 233 3.0658 00000000c0122498 current_kernel_time 241 3.5441 00000000c01700b0 __mark_inode_dirty 263 0.7225 00000000c016dacc set_fs_pwd 264 1.8333 00000000c0163510 vfs_readdir 315 2.3864 00000000c01f9fc8 copy_to_user 330 4.8529 00000000c01375f0 find_get_page 332 4.3684 00000000c015e7e4 path_release 368 6.5714 00000000c015e580 getname 381 2.3813 00000000c0143c0c set_page_address 411 1.0275 00000000c0143b80 page_address 449 3.2071 00000000c01a1cc0 ext2_readdir 482 0.8087 00000000c01637fc filldir64 499 2.2277 00000000c01678b0 dput 533 1.1897 00000000c013f4b8 kmem_cache_alloc 612 7.2857 00000000c013f794 kmem_cache_free 625 8.2237 00000000c01f9c98 strncpy_from_user 695 8.2738 00000000c015eb2c do_lookup 738 5.5909 00000000c01f9db0 __copy_user_intel 741 4.6312 00000000c01f9510 atomic_dec_and_lock 801 10.6800 00000000c015b488 cp_new_stat64 1065 4.2262 00000000c01f9ef0 __copy_to_user_ll 1090 10.4808 00000000c015af14 vfs_getattr 1097 8.3106 00000000c0105c0f sysenter_past_esp 1201 10.6283 00000000c015ae70 generic_fillattr 1815 11.0671 00000000c015fa1c path_lookup 1833 4.9810 00000000c015ebb0 link_path_walk 1915 0.5940 00000000c0168710 __d_lookup 6170 22.0357
00000000c0104034 default_idle 108054 1929.5357
0000000000000000 total 138203 0.0547
Quoted 1 line · Andrew
hmm. Here's a Pentium III profile ...
What conclusion do your draw from this profile?
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373Quoted 5 lines · Paul Jackson
Quoted 1 line · Andrew
hmm. Here's a Pentium III profile ...
What conclusion do your draw from this profile?
At a quick squint: we spend about 10% of total system time in those copy functions. If we halve their runtime (which would be good), we don't gain much.
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
"Andrew" == Andrew Morton <[email protected]> writes:
Quoted 3 lines · Andrew> Paul Jackson <[email protected]> wrote:
Quoted 3 lines
Andrew wrote: > hmm. Here's a Pentium III profile ...
What conclusion do your draw from this profile?
Andrew> At a quick squint: we spend about 10% of total system time in Andrew> those copy functions. If we halve their runtime (which would Andrew> be good), we don't gain much.
And the proposal only removes one of the three copies, so you're probably looking at around a 30% rather than a 50% reduction in the 10%. Plus whatever knock on effects there might be from different cache usage.
Is it worth the effort, and added complexity? Unless there's some other architecture where the memcpys are really expensive, the answer at present appears to be, no.
--
Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au The technical we do immediately, the political takes *forever*
Quoted 1 line · Peter Chubb
With hot cache the system time is really small.
But this is not all you'll have to look at.
Single application performs does not really tell the whole story. If you touch more memory, more cache is used. In SMP machines the cost of cacheline transfers are added. And in multi-core processors the cores even share some cache which means every bit used might decrease system performance ever so slightly.
If the added complexity is manageable the avoided memory operations should be a win even if you cannot directly measure it.
Signature · 1 line
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
Quoted 4 lines · David S. Miller
On Wed, 28 Jul 2004 17:08:37 -0700
Chris Wedgwood <[email protected]> wrote:
Quoted 8 lines
Quoted 3 lines
Just How bad is it for you? I just tested stat on my crapbox and for a short path 1M stats takes 0.5s and for a longer path (30 bytes or so) 2.8s.
Run "time find . -type f" on the kernel tree, both before and after removing the third unnecessary copy. Many machines sit all day and stat files.
P2 350MHz 256Mb RAM circa 1998
bash$ time find . -type f
gives
real 0m16.142s user 0m0.432s sys 0m2.893s
I'd be interested to see what machine you have that takes all day.
N
Quoted 2 lines · David S. Miller
"find . -type f" is probably the most often run command somewhere in a shell pipeline [...]
I hope you're testing this on a recent system with a good find implementation. Nowadays find calls stat for this command line only for directories and symlinks. Those types along with normal files are all known to find through the readdir calls (i.e., the d_type field).
Check your strace output to see whether your system is recent enough.
Signature · 1 line
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
Quoted 1 line
Check your strace output to see whether your system is recent enough.
The latest findutils package I can find is version 4.1.20, and its most recent ChangeLog entry is dated 2001-06-09.
It doesn't have this feature of find not stat'ing the regular files, but using dirent d_type instead.
I also found a March 2004 thread presenting a patch to use d_type, at:
http://lists.gnu.org/archive/html/bug-findutils/2004-03/msg00004.html
But the thread seemed to end inconclusively, after just a few messages discussing various alternative implementations of some stuff.
Ulrich - could you provide a clue where to find a find that does what you describe?
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373Quoted 2 lines · Paul Jackson
Ulrich - could you provide a clue where to find a find that does what you describe?
If I claim to see this behavior you could have guessed that at least Red Hat releases have this feature enabled. If you unpack the .src.rpm you'll see a file findutils-d_type.patch. There have been attempts to get the patch upstream but they failed.
Signature · 1 line
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
Thank-you for your response, Ulrich.
I had missed noticing the findutils-d_type.patch.
Now I see it - good.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373