stat very inefficient

stat very inefficient

[David S. Miller]

All of the *stat*() syscall routines copy the inode attributes
around a whopping _3_ times before they get to userspace.

1) From inode to "struct kstat"
2) From "struct kstat" to "struct stat{,64}" on local kernel stack
3) From local kernel stack to userspace

That's rediculious.  And also the stores into the various
structures are not done in ascending order and thus all of
the store buffers on various cpus never get a reasonable
store stream for maximal store buffer compression.

The reason things happen this way is that each implementation
of the various stat structures have padding in different places
and/or have other layout issues.  The simplest thing to do
is memset() the thing, fill in the non-pad parts, and copy
it into user space.

We should be able to do this with just 2 copies as I recognize
the reason why the struct kstat abstraction exists.

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.c should call
upon arch-specific stat{,64} structure fillin routines that
can do the magic, given a kstat struct.

Comments?

Re: stat very inefficient

[Andi Kleen]

"David S. Miller" <davem@redhat.com> writes:

> 1) From inode to "struct kstat"
> 2) From "struct kstat" to "struct stat{,64}" on local kernel stack
> 3) From local kernel stack to userspace

[...]

> 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.c should call
> upon arch-specific stat{,64} structure fillin routines that
> can do the magic, given a kstat struct.

I think wrappers are preferable to callbacks.  Basically step (2) 
should be eliminated. 

Most architectures can use a generic wrapper for that, together
with a standard macro that clears all the padding in user space.

-Andi

Re: stat very inefficient

[David S. Miller]

On Wed, 28 Jul 2004 12:16:40 +0200
Andi Kleen <ak@muc.de> wrote:

> Most architectures can use a generic wrapper for that, together
> with a standard macro that clears all the padding in user space.

They can't be seperate though, I don't want:

	fill_in_stat_bits();
	zero_out_padding_parts();

because that disturbs the ascending store stream which
I'm trying to retain.

What I really want to do on Sparc64 is a special inline
assembly that looks a lot like put_user() but uses one
exception table entry for all the stores into the stat{,64}
structure in userspace.

How would you wrapper look?  Perhaps I'm confused and it
allows what I want to do.

Re: stat very inefficient

[viro]

On Tue, Jul 27, 2004 at 08:13:01PM -0700, David S. Miller wrote:
 
> 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.c should call
> upon arch-specific stat{,64} structure fillin routines that
> can do the magic, given a kstat struct.
> 
> Comments?

I'm not sure that it's worth doing for anything below the "widest" version
of stat.  For that one - yeah, no objections.

Re: stat very inefficient

[Peter Chubb]

>>>>> "viro" == viro  <viro@parcelfarce.linux.theplanet.co.uk> writes:

On Tue, Jul 27, 2004 at 08:13:01PM -0700, David S. Miller wrote:
>> 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.c should 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*

Re: stat very inefficient

[David S. Miller]

On Thu, 29 Jul 2004 08:33:59 +1000
Peter Chubb <peter@chubb.wattle.id.au> 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.

Re: stat very inefficient

[Chris Wedgwood]

On Wed, Jul 28, 2004 at 03:45:23PM -0700, David S. Miller wrote:

> "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

Re: stat very inefficient

[David S. Miller]

On Wed, 28 Jul 2004 17:08:37 -0700
Chris Wedgwood <cw@f00f.org> 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.

Re: stat very inefficient

[Chris Wedgwood]

On Wed, Jul 28, 2004 at 05:14:14PM -0700, David S. Miller wrote:

> 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.146s

that 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

Re: stat very inefficient

[viro]

On Wed, Jul 28, 2004 at 05:14:14PM -0700, David S. Miller wrote:
> On Wed, 28 Jul 2004 17:08:37 -0700
> Chris Wedgwood <cw@f00f.org> 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.).

Re: stat very inefficient

[Ulrich Drepper]

David S. Miller wrote:

> "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.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

Re: stat very inefficient

[Paul Jackson]

> 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?

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: stat very inefficient

[Ulrich Drepper]

Paul Jackson wrote:

> 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.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

Re: stat very inefficient

[Paul Jackson]

Thank-you for your response, Ulrich.

I had missed noticing the findutils-d_type.patch.

Now I see it - good.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: stat very inefficient

[Peter Chubb]

>>>>> "viro" == viro  <viro@parcelfarce.linux.theplanet.co.uk> writes:

>> On Wed, 28 Jul 2004 17:08:37 -0700 Chris Wedgwood <cw@f00f.org>
>> 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*

Re: stat very inefficient

[Andrew Morton]

Peter Chubb <peter@chubb.wattle.id.au> wrote:
>
> 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

Re: stat very inefficient

[Ulrich Drepper]

Peter Chubb wrote:

> 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.

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖

Re: stat very inefficient

[Paul Jackson]

Andrew wrote:
> hmm.  Here's a Pentium III profile ...

What conclusion do your draw from this profile?

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: stat very inefficient

[Andrew Morton]

Paul Jackson <pj@sgi.com> wrote:
>
> Andrew wrote:
>  > 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.

Re: stat very inefficient

[Peter Chubb]

>>>>> "Andrew" == Andrew Morton <akpm@osdl.org> writes:

Andrew> Paul Jackson <pj@sgi.com> wrote:
>>  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*
 

Re: stat very inefficient

[Nigel Rantor]

David S. Miller wrote:
> On Wed, 28 Jul 2004 17:08:37 -0700
> Chris Wedgwood <cw@f00f.org> 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.

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