Re: Speed of rc

Re: Speed of rc

[Tom Culliton x2278]

Paul writes:
> ok, now i understand what's going on.  yes, if you use test a lot in rc,
> it will go slowly.  if your /bin/sh has a test builtin, that will run faster.
> there's no surprises here, you're just comparing apples and oranges.

The issue can't be dismissed that easily.  I've seen relatively pokey
behaviour even in scripts that have been written using exclusively
builtin functions.  I'm not espousing the idea of building test into
rc, just asking if some tuning could be done, particularly in the areas
that I mentioned before.

Tom

Re: speed of rc

[Tom Culliton x2278]

Since I started this thread I wanted stop for a moment to agree whole
heartedly with John in praise of rc.  My experience is that Byron's rc
is completely stable, bug free, solid as a rock, easily ported, clean,
polished, a pleasure to use, etc.  My comments definitely fall into the
category of nitpicking. I've pushed it in all sorts of strange and
intresting ways, and (aside from a porting bug caused by SCO's flakey
signal.h) never had it fail.  Byron has nothing to apologize for and a
great deal to be very proud of.

To Byron in particular: The design philosophy behind rc has my
strongest endorsement, perl is a monster, and like one of those "all in
one" kitchen gadgets I find it completely useless.  It is unstable and
buggy, takes forever to port, and otherwise generally makes my head
ache.  My concerns about the speed of rc come from trying to do big
production type jobs with it and trying to evangelize to the unwashed
sh/csh types around here.  (Our sysadmins can't even be bothered to
support bash, and do ksh only grudgingly.  Since rc is simple enough
for anyone to understand and bug free, it would be a perfect solution,
if I could only overcome peoples inertia.)

Byron's point about analyzing rc with prof is well taken, there are a
couple of gotchas to beware of though.  People often make to much of
flattening out the usage peaks.  A high peak doesn't necessarily mean
that means that a certain section of code is a bottle neck, it could
mean the code is optimal and efficiently doing it's work in a tight
loop. (e.g. A document format to format translator that spends 95% of
it's time in 5 lines of code that handle normal text.)  Nor does a flat
profile means that the code is optimal, it could very well mean that
lots of code extra code is getting executed. (e.g. In the translator
mentioned above doing character by character i/o rather than buffered.)
And when a program is system call bound, as Byron indicates is the case
with rc, there is still the possibility of extraneous calls. (such as
the stat call that Dave Mason and Byron mention)

Dave Mason also makes an excellent point about the size of the
environment under rc and the effect on the cost of execs.  Writing in
rc it is often natural to stick things into lists in the enviroment,
which would be in a file or pipe under sh.  Especially when trying to
avoid external programs for the sake of speed.  The fact that all
variables and functions are exported adds to this.  It wouldn't suprise
me if this was were part of my time was going under SCO ODT.  A good
thing to remember when writing scripts.

Remember, I'm not throwing stones here, just asking a question: What
can we do (if anything, and short of polluting rc with extra builtins)
to speed rc up?

Tom

PS - sorry this was so long...

Re: speed of rc

[mycroft]

> As far as I am concerned, no apologies are needed.  You have done a
> tremendous job.

I concur.  I've found this implementation to be very reliable.  The
first thing I do on a new machine now is compile rc.

Re: speed of rc

[John Mackin]

    Further disclaimer: I want to offer my apologies for not spending
    more time on rc, but things have really never been busier for me
    as a programmer.

Byron,

As far as I am concerned, no apologies are needed.  You have done a
tremendous job.  I can't speak for anyone but myself, but for my part I
appreciate your work every moment I am sitting at my terminal, and more
times besides.  I think the evidence is clear: there's a large user community
on the rc list, and what we talk about is polishing off tiny blemishes
from something that's already close to perfect.  The dearth of
patches/releases also speaks for the quality of what you've done.

I've said all this before, and if I am still around will doubtless in
time say it again.  Thank you so much.

OK,
John.

Re: Speed of rc

[John Mackin]

Chris,

Fascinating!  I want to work out what is going on here.  The first
question, and I am really in little doubt as to the answer, is: was
that rc-1.4?  You didn't say, and I know some earlier versions didn't
do the redundant stat() call that appears to be at the bottom of the
extra system time I am seeing.  Note that you, like me, see substantially
larger user times with sh than with rc; the difference was that I saw
larger system times with rc than with sh, whereas in your tests they
are on a par.

Given that you were using 1.4, I'd say the next logical step (and
this is just a suggestion, feel free to make your own if you don't like
this one) is I'll give you my rc-1.4 binary one way or another
(I can put it up for anon ftp here, probably best) and you can test
that binary under the same conditions as the others.  Let me know
what you think.

Puzzled, but
OK,
John.

speed of rc

[Byron Rakitzis]

John pointed out to me that the rc path search does a stat() before
an exec(), even for an absolute path name. Optimizing out that
stat should take care of the "pus" problem, if indeed that file
is full of lines which say "/tmp/xx".

Disclaimer: I haven't tried to reproduce any of this stuff here yet.
Further disclaimer: I want to offer my apologies for not spending
more time on rc, but things have really never been busier for me
as a programmer.

Re: Speed of rc

[Chris Siebenmann]

 Interestingly, I ran similar tests to John Mackin's, and got more or less
the reverse of his results; on a DECstation 5000/133 with everything on a
fairly pokey and slow local disk, the sh './xx' case was noticably slower
than the rc case. I've seen these numbers replicated across some other
machines (including a SunOS box in my testing, although it was hard to
get a consistent load average on that machine).

 Here are the numbers themselves:
! : whirlwind.sys ; l=(1 2 3 4 5)
! : whirlwind.sys ; for (i in $l) {/bin/time sh -c 'cat pus2 | ./rc.gcc'}
!        25.0 real         1.0 user        22.2 sys  
!        24.3 real         1.1 user        21.8 sys  
!        25.1 real         1.1 user        22.4 sys  
!        24.2 real         1.0 user        21.7 sys  
!        23.1 real         1.0 user        21.4 sys  
! : whirlwind.sys ; for (i in $l) {/bin/time sh -c 'cat pus2 | ./rc.c89'}
!        25.5 real         0.9 user        22.2 sys  
!        24.0 real         1.1 user        21.8 sys  
!        26.6 real         1.0 user        23.1 sys  
!        23.8 real         1.1 user        21.7 sys  
!        25.3 real         0.9 user        22.9 sys  
! : whirlwind.sys ; for (i in $l) {/bin/time sh -c 'cat pus2 | /bin/sh'}
!        30.4 real         9.0 user        20.1 sys  
!        31.0 real         9.1 user        20.3 sys  
!        30.7 real         9.2 user        20.2 sys  
!        29.4 real         8.9 user        19.7 sys  
!        29.4 real         8.9 user        19.8 sys  
[rc.gcc and rc.c89 are rc binaries compiled with gcc 2.2.2 and DEC's
 c89 ANSI compiler, respectively.]

	- cks

Re: Speed of rc

[Paul Haahr]

i haven't read most of this note, (still catching up on my mail), but

> any idea why the es executable is so large?

it shrinks in size dramatically if you turn off assertions.  some of the
things that have to be done for the garbage collector generate a lot of
assertions which should really just be compile-time checks.

the other thing is that es has lots of functionality (taken generally
out of the shared libraries, with only a little bit of glue code) that
rc does not have, even if it is minor:  ~-expansion, builtin time(), etc.
a lot of this can be thought of as code bloat.  nevertheless, es w/o
assertions should be roughly the size of a csh linked in the same way.

thanks for your analysis.

paul

Re: Speed of rc

[Chris Siebenmann]

 Dynamically linking programs that fork() looses big on SunOS
and Solaris; I always static-link rc on those machines. It's
a quite dramatic difference. I really wish Sun could get their
act together about it, too; I was appalled to see it continue
in Solaris.

	- cks

Speed of rc

[Dave Mason]

 Ignoring rude comments about my conjectures...

 John is of course right, that in his tests both sh and rc had the
same environments, so the environment copy time will be the same
(although from his numbers it's clear this is a significant cost and
it may be worth looking for a different way to handle environments on
Unix) and we have to look for other differences...

 Well, the obvious one (for me) is that /bin/sh is built to be static,
and when I built rc and es, I took the sun defaults which build
to use dynamic libraries.

So I tried John's test looking at the system calls for static and
dynamic cases... essentially no difference...

But the execution time is very different.  At least on this Sun 4/590,
dynamic libraries cost a lot of system time, and when I run static
versions my rc has virtually identical system times as sh and es only
uses about 7% more system time (which may well be because of the 3
times larger binary and demand-load paging). (And es' *total* time is
within a couple percent of sh.)

John's mileage may vary.  (e.g. if he's not running dynamic libraries.)

Paul & Byron: any idea why the es executable is so large?

../Dave

; /bin/time /bin/sh -c '/bin/cat pus2 | /bin/sh'
; /bin/cat pus2|trace -c /bin/sh

 rc-stat      rc es-stat      es      sh

     90K     82K    286K    163K    106K text+data size

     1.4     2.3     1.1     2.0     4.6 user time
    32.5    44.2    36.0    49.3    32.4 system time
    37.5    49.4    40.9    58.9    40.1 real time

    1059    1068    1007    1064    1076 wait4
    1076    1076    1062    1062    1071 sigblock
    1034    1034    1023    1023    1063 sigstack
    1000    1000    1000    1000    1000 SIGCHLD (20)
    1000    1000    1000    1000     999 fork
      78      78      72      72      14 sigvec
      41      41      38      38       7 sigsetmask
       1       1       1       1       1 exit
       8       8       9       9         brk
       1       1       1       1         getpid
       1       1       1       1         ioctl
       1       1       1       1         getpagesize

(Some or all of the following calls are attributable to Dynamic
libraries):
      33      36       9      12      63 read
       7      14       7      14       4 close
       3      10               7         open
       1       2               1         getuid
       1       2               1         getgid
              10              10         mmap
               4               4         getdents
               2               2         fstat
               1               1         getrlimit

Only rc:
    1000    1000                         stat
       1       1                         getgroups

Only es:
                       3       3         dup
                       1       1         sigcleanup

(As an aside, I find it interesting that there is little correlation
between the number of wait4, sigblock and sigstack calls among the
shells, and I don't see how sh gets 1000 SIGCHLD's with only 999
forks!  But this is repeatable: sh definitely elides the last fork.
Whether that optimization is worthwhile is unclear.)

Re: Speed of rc

[John Mackin]

Summary: Dave Mason shows us, once again, that shots from the hip
usually miss.

    rc will have a significantly larger environment (rc functions) than
    sh, and many systems have *abysmal* exec performance because of the
    time spent copying the environment.

I don't know if you just didn't bother to read my mail, Dave, or what.
rc and sh were both being executed with precisely the same environment.
So whatever contribution exec makes in copying the environment will
have been the same for both.

For the record, I just did a wc of my environment and it is around 2100
characters.

As to `rc functions,' never forget than an important factor in the
_startup_ time of Byron's rc is that it imports functions lazily.
Of course, startup time is specifically not at issue here.

    So, John: try a version of rc with an empty environment.  I suspect
    the system times will be as fast as those for sh.

BZZZZZT!  Sorry, Player One, you lose this time, but thanks for trying...

: mod;; env - sh
$ /bin/time /bin/sh -c '/bin/cat pus2 | /usr/local/bin/rc'
       27.5 real         1.3 user        24.7 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /usr/local/bin/rc'
       27.7 real         1.2 user        25.1 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /usr/local/bin/rc'
       27.5 real         1.1 user        25.0 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /usr/local/bin/rc'
       27.4 real         1.1 user        24.7 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /bin/sh'
       17.2 real         1.3 user        14.9 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /bin/sh'
       16.8 real         1.4 user        14.4 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /bin/sh'
       16.8 real         1.5 user        14.2 sys  
$ /bin/time /bin/sh -c '/bin/cat pus2 | /bin/sh'
       16.9 real         1.4 user        14.8 sys  

Clearly, with an empty environment, we can't do any path searching,
so I tried only pus2 this time, with the "./xx"s in it.

We still see rc using a much higher system time than sh.  Interestingly,
sh's user-time has come down to on a par with rc's.  I won't offer
any speculation on that one.

OK,
John.

Speed of rc

[Dave Mason]

 Of course it was 10 seconds after I finished reading (and deleting)
John Mackin(sp?)'s note that I realized the problem:
	environment

rc will have a significantly larger environment (rc functions) than
sh, and many systems have *abysmal* exec performance because of the
time spent copying the environment.  I did some benchmarks on a MIPS
M/120 (13 Specmarks) running RiscOS and a National Semiconductor 32016
(.75 Specmarks) running Sys5r2, and I don't remember the exact
results, but execing with a 0K environment was about the expected
factor of 20 faster on the MIPS, and with a 5K environment it was
*much* slower - maybe a factor of only 4, and I calculated that in a
research O/S we were working on (although it never ran so I couldn't
verify this) the exec (with 5K environment) would run *faster* on the
NS32016 than the existing one on the M/120.

So, John: try a version of rc with an empty environment.  I suspect
the system times will be as fast as those for sh.

../Dave

Re: Speed of rc

[John Mackin]

Here are a few comments on the speed of rc.  I hope they're not too
incoherent, but it's now or never.

Someone said that they had a problem in that their test command was
built into sh, and that therefore every time they wanted to do a test
inside an rc script they ended up having to fire up an sh to do it.
I'm sure you can do much better than that.  I have encountered that
situation on various different Unix machines (sorry, in my current
state of mind the details escape me).  There _are_ machines where
the _only_ test command is built into some flavour of sh; I think
some versions of RS/6000 AIX may be like that.  There are also
machines where, yes, test is built into sh, but a test binary
is also supplied (looking for a binary named "[" can often win).
On these latter machines, clearly the problem is solved, just use
the supplied test binary.  On machines where there really and
definitely isn't a binary for test, just compile one.  I
am sure there are sources floating around on the net.  If all
else fails there is certainly a gnu version.  That way you will
end up with a much lighter-weight operation than having to start
up a copy of sh just to do "test".  Hell if it came to that, anyone
around here could code up test.c in short order.

Now for my personal experiences and some numbers.  I have always found
rc to be acceptably fast with one exception.  When I am coding shell
scripts I am not looking for blazing performance.  It always seems to
deliver the goods, sometimes even faster than I expected.  The exception
is this.  I use a mail system called "mace" written by Boyd Roberts.  It
is a little bit like MH in that you incorporate your mail into an
inbound mail folder.  He has a facility where as the mail is incorporated,
each item's headers can optionally be matched against some REs and if
they match, a command is queued up to be executed on that mail item
after the incorporation is complete.  I am on a fairly high-volume
mailing list where it is not uncommon for thirty or forty items to
arrive while I am away from my terminal (should I not come in for
a whole weekend, I usually see hundreds).  I have it set up to
automatically move these items to the correct box, so one command
gets executed per item at the end of the incorporation.  This takes
an excruciatingly long time if there are a lot to move.  There are,
of course, many variables and it is hard to measure.  What Boyd does
is fire up a single copy of $SHELL (rc in my case) and send all the
commands down a pipe to its standard input; clearly a better idea
than one shell per command.  So I just did some simple measurements
on that.  In /tmp, I created an executable called "xx" which was just
the null C program.  I created "pus" which had 1000 lines, each saying
"xx".  I got some interesting numbers.  (This is on a DECstation 5000/120
running Ultrix 4.2, so sh is a very old version.)

: mod;; /bin/time sh -c 'cat pus | sh'
       27.8 real         5.2 user        21.1 sys  
: mod;; /bin/time sh -c 'cat pus | sh'
       27.2 real         5.3 user        20.8 sys  
: mod;; /bin/time sh -c 'cat pus | sh'
       27.5 real         5.3 user        21.0 sys  
: mod;; /bin/time sh -c 'cat pus | sh'
       27.3 real         5.4 user        20.7 sys  
: mod;; /bin/time sh -c 'cat pus | rc'
       34.7 real         1.8 user        31.3 sys  
: mod;; /bin/time sh -c 'cat pus | rc'
       34.8 real         1.8 user        31.1 sys  
: mod;; /bin/time sh -c 'cat pus | rc'
       34.5 real         1.7 user        31.1 sys  
: mod;; /bin/time sh -c 'cat pus | rc'
       34.8 real         1.8 user        31.3 sys  

I wish I had time to find out why rc used a whole third more system time.
I suspect this might be at the root of my mace performance problem.
I thought initally that it might be something to do with path searching,
so I tried cutting that out of the picture, to no obvious effect: "pus2"
contained lines with "./xx", and "pus3" lines with "/tmp/xx".

: mod;; /bin/time sh -c 'cat pus2 | sh'
       27.1 real         5.2 user        20.5 sys  
: mod;; /bin/time sh -c 'cat pus2 | sh'
       27.0 real         5.2 user        20.5 sys  
: mod;; /bin/time sh -c 'cat pus2 | sh'
       27.5 real         5.3 user        20.8 sys  
: mod;; /bin/time sh -c 'cat pus2 | rc' 
       33.7 real         1.6 user        30.5 sys  
: mod;; /bin/time sh -c 'cat pus2 | rc' 
       37.3 real         1.6 user        31.7 sys  
: mod;; /bin/time sh -c 'cat pus2 | rc' 
       35.5 real         1.5 user        31.5 sys  


: mod;; /bin/time sh -c 'cat pus3 | sh'
       27.7 real         5.3 user        21.2 sys  
: mod;; /bin/time sh -c 'cat pus3 | sh'
       27.5 real         5.3 user        20.8 sys  
: mod;; /bin/time sh -c 'cat pus3 | sh'
       27.9 real         5.4 user        21.1 sys  
: mod;; /bin/time sh -c 'cat pus3 | rc'
       34.6 real         1.7 user        31.3 sys  
: mod;; /bin/time sh -c 'cat pus3 | rc'
       34.8 real         1.8 user        31.2 sys  
: mod;; /bin/time sh -c 'cat pus3 | rc'
       34.3 real         1.6 user        31.0 sys  

As you can see, the results are substantially the same.  Note that rc
wins on user time, which is why it isn't drastically slower overall.

Maybe someone will be inspired to look at this further.  I would, and
I still might, but certainly not now and I don't know if I will get a
chance.

OK,
John.

Re: Speed of rc

[Scott Schwartz]

Just some random thoughts...

Tom writes:
| I actually spent a fair amount of time once trying to figure out a
| stunt to run co-processes under rc so I can fire up sh (for test), and
| something else to do math, exactly once and then have functions that
| talk to them.  In the end I decided it either couldn't be done or
| wasn't worth the effort.

Yet another defect in Unix, where IPC is so limited that even simple
and obvious things are so painful that no one does them.  Similarly, if
dynamic loading were fundamental and pervasive one could envision
taking any a.out file, mapping it once, and then calling its entry
points.  For example, make the system (OS, language runtime, etc)
understand /bin/sh/glob.  Then the normal execve means calling
/bin/sh/main.

The problem with being spartan is that you end up being stoic.

Re: Speed of rc

[Paul Haahr]

ok, now i understand what's going on.  yes, if you use test a lot in rc,
it will go slowly.  if your /bin/sh has a test builtin, that will run faster.
there's no surprises here, you're just comparing apples and oranges.

i think that there are two very good reasons that test is not built into rc:
(1) with one glaring exception (echo), rc really has no extraneous builtins,
and (2) the semantics of test are, at best, awful.  in addition, i know that
Byron hesitated before deviating seriously from the bell labs version of rc.

personally, if test had nice semantics, i would prefer to see it built in
to rc.  it doesn't.

paul

ps:  as many of you know, Byron and i have been doing a new shell, es, in
which we felt no obligation to be compatible with rc.  es needed to have
a builtin for doing some test-like things because path-searching is done
by functions written in es rather than c.  because of this, we exposed an
access function, which does many things that test does, albeit cleaner.

Re: Speed of rc

[Tom Culliton x2278]

me> When running commands or scripts it seems that rc often takes longer
me> than it should, especially compared to sh or ksh.

paul> i don't find this true at all.  i haven't ever used ksh seriously, but
paul> rc feels (that's not is, but feels) much faster than sh on all machines
paul> i've tried it on.

I've actually rewritten rc scripts for sh so that they would be used by
more of our users, and seen notable speed differences.  (I'm talking
about jobs that take minutes (in either shell) rather than seconds
here, can run up to a couple hundred lines of script and chew up whole
directory hierarchies and many megabytes of data.)  Except in cases
where rc made it easy to use a better algorithm, which created fewer
processes or invoked fewer external commands, sh wins.

There seem to be a couple of components to this.  First sh has test
builtin, and on our machines, for rc to use test means firing up sh to
do it.  Second when I use pattern matching to any significant extent,
or do lots of fiddling with lists, rc seems to bog down.  Heavy `{}
usage also seems to chew lots of time.

Don't get me wrong, this is not meant to be a criticism of rc, I love
it and wouldn't want to give it up.  It was about 10 times easier to
write the scripts in rc than it would be in sh, and they're often much
smaller and cleaner.  Using rc encourages me to write things when it
wouldn't seem worth the effort in sh or (shudder!) perl.  (I think that
Perl is exactly the wrong solution for the same reasons that PL/1 was.)

paul> the last major performance
paul> tweak that i recall was that there were some list operations being done
paul> in O(n^2) time when they didn't have to be, and that fixed, but i'm not
paul> sure if that was a pre- or post-1.4 change.

I remember this as a pre-1.4 change, but operations on big lists still
seem to take a fair amount of time.

paul> profiling code & looking for hot spots is always a good thing to do.
paul> i think you'll find that rc is pretty much flat and not spending an
paul> inordinate amount of time in any particular kind of operation.

The difference may well be simply one of usage styles, and the answer
may be as simple as some hints about how to improve the efficiency of
rc scripts.  For example using find where appropriate is usually a BIG
win especially since test isn't builtin. 

Tom

PS - I actually spent a fair amount of time once trying to figure out a
stunt to run co-processes under rc so I can fire up sh (for test), and
something else to do math, exactly once and then have functions that
talk to them.  In the end I decided it either couldn't be done or
wasn't worth the effort.

Re: Speed of rc

[Byron Rakitzis]

I seem to remember the "benchmark" posted on c.u.s as being quite
artificial.

That said, I'll tell you what I know about rc's speed: I don't think
you will make rc ever go faster by examining prof output. The fat
just isn't there. The slowest routine is probably yacc, but it's not
even close to the time you spend in Unix system calls.

The problem can be viewed in one of two ways: either (1) rc is
not perl, or (2) Unix is too slow. Take your pick. rc has to go
do fork/exec for a lot of tasks which a featureful shell or
perl might cram in as a builtin.

I agree that the speed at which scripts run is a valid concern,
and all I can say is that I don't have a good answer at this
time. I can't bring myself to buy into the perl philosophy.

Re: Speed of rc

[Paul Haahr]

> When running commands or scripts it seems that rc often takes longer
> than it should, especially compared to sh or ksh.

i don't find this true at all.  i haven't ever used ksh seriously, but
rc feels (that's not is, but feels) much faster than sh on all machines
i've tried it on.

> I also seem to
> remember seeing something in comp.unix.shell within the last couple of
> months, about the relative speed of various shells, which showed rc as
> being substantially slower.

i don't remember it that way.  as i recall, the numbers from rc looked
about the same as all other shells, which was not surprising, given that
the benchmark seemed to be testing just how fast the machine forked.

> What this leads me to wonder is, if anyone
> has ever bothered to do any serious timing tests or profile rc and find
> out where it's spending its time?

i know that Byron had done this on at least several times during his work
on rc, but i don't think he's done it recently.  the last major performance
tweak that i recall was that there were some list operations being done
in O(n^2) time when they didn't have to be, and that fixed, but i'm not
sure if that was a pre- or post-1.4 change.

profiling code & looking for hot spots is always a good thing to do.
i think you'll find that rc is pretty much flat and not spending an
inordinate amount of time in any particular kind of operation.

paul

Speed of rc

[Tom Culliton x2278]

When running commands or scripts it seems that rc often takes longer
than it should, especially compared to sh or ksh.  I also seem to
remember seeing something in comp.unix.shell within the last couple of
months, about the relative speed of various shells, which showed rc as
being substantially slower.  What this leads me to wonder is, if anyone
has ever bothered to do any serious timing tests or profile rc and find
out where it's spending its time?

I raised this issue with Byron once, but he had bigger fish to fry at
the time. (and rightly so)  However the shell has been stable for quite
a while, and it might be well worth exploring, especially now that a
version 1.5 is being considered.

Tom