From: Peter Schay <pschay@pobox.com>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] env walk
Date: Thu, 10 May 2001 08:33:48 +0000 [thread overview]
Message-ID: <3AF9CB94.C507F463@pobox.com> (raw)
In-Reply-To: <20010509165901.CD181199E7@mail.cse.psu.edu>
Thanks for looking into this! Sorry for beating it to death, but...
I still think more time is spent in envgen, because, as you said,
the algorithm is O(n**3).
Also devdir and all the extra qlocking contribute as well.
(see the kprof results below).
I changed your example to be triply nested,
int i, j, k;
for(i = 0; i < nelem(x)-1; i++)
x[i].next = &x[i+1];
for(i = 0; i < nelem(x); i++)
for(j = 0; j < nelem(x); j++)
for(k = 0, p = x; k < j && p != nil; p = p->next, k++)
;
and it took around 11 seconds instead of .01. This is a good
example of what happens with the triply nested loops of
rc, devwalk, and envgen.
Sorry, the original example I gave was misleading for two reasons.
First, you are right and it does walk to all the /env entries
of course so I should have said this was O(n**3).
I was talking about the time to walk to a *single* entry
being O(n**2). Indeed the time to walk to all the entries is
O(n**3) which is why it really starts to get slow.
My example was also misleading because the time taken is
not because of ls /env. You can get a similar delay from forking
any process because rc walks to all the /env entries. (I think).
The following example is also slow because of the O(n**3) effect,
and it doesn't use ls /env.
term% echo startclr > /dev/kpctl
term% time /fd/0 <<.
#!/bin/rc
rfork e
eval X^(`{seq 400})^('=1')
echo `{echo x | wc -c}
.
2
0.14u 3.14s 3.68r /fd/0
term% echo stop > /dev/kpctl
term% kprof /n/9fat/9pcdisk /dev/kpdata | sed 12q
total: 3684 in kernel text: 3528 outside kernel text: 156
KTZERO 80100000
ms % sym
732 20.7 envgen
540 15.3 i8259isr
348 9.8 sched
348 9.8 runproc
216 6.1 lock
132 3.7 devdir
132 3.7 cycletimer
132 3.7 memmove
96 2.7 qunlock
term%
-Pete
presotto@plan9.bell-labs.com wrote:
>
> The n**2 comes from the ls M* walking each entry in the environment
> with envwalk walking from the first to that entry every time. All the
> time is spent in the devdir+convM2D in procgen. The
>
> for(e = eg->entries; e && s; e = e->link)
> s--;
>
> is pretty much fleeting even for 1000 entries. Otherwise the algorithm for
> your example would be n**3.
>
> for example:
>
> #include <u.h>
> #include <libc.h>
>
> struct X
> {
> struct X *next;
> };
>
> struct X x[1000];
>
> void
> main(void)
> {
> struct X *p;
> int i, j;
>
> for(i = 0; i < nelem(x)-1; i++)
> x[i].next = &x[i+1];
>
> for(i = 0; i < nelem(x); i++)
> for(j = 0, p = x; j < i && p != nil; p = p->next, j++)
> ;
>
> }
>
> takes .01 seconds on my crufty old machine.
> The advantage to your loop is that you take all the useless stuff
> that devdir does out of the inner loop, not too mention the call
> itself.
next prev parent reply other threads:[~2001-05-10 8:33 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-05-09 16:58 presotto
2001-05-09 17:34 ` Sam
2001-05-09 17:39 ` Sam
2001-05-10 8:33 ` Peter Schay [this message]
-- strict thread matches above, loose matches on Subject: below --
2001-05-10 14:48 rog
2001-05-10 14:41 presotto
2001-05-10 13:49 rob pike
2001-05-10 13:39 rog
2001-05-10 13:04 presotto
2001-05-10 12:58 presotto
2001-05-09 13:23 presotto
2001-05-09 15:45 ` Peter Schay
2001-05-09 11:54 Peter Schay
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3AF9CB94.C507F463@pobox.com \
--to=pschay@pobox.com \
--cc=9fans@cse.psu.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).