From mboxrd@z Thu Jan  1 00:00:00 1970
To: 9fans@cse.psu.edu
From: Peter Schay <pschay@pobox.com>
Message-ID: <3AF9CB94.C507F463@pobox.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
References: <20010509165901.CD181199E7@mail.cse.psu.edu>
Subject: Re: [9fans] env walk
Date: Thu, 10 May 2001 08:33:48 +0000
Topicbox-Message-UUID: 9cb75c50-eac9-11e9-9e20-41e7f4b1d025

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.