From mboxrd@z Thu Jan  1 00:00:00 1970
Content-Type: text/plain;
  charset="iso-8859-1"
From: Sam <sah@softcardsystems.com>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] env walk
References: <20010509165901.CD181199E7@mail.cse.psu.edu>
In-Reply-To: <20010509165901.CD181199E7@mail.cse.psu.edu>
MIME-Version: 1.0
Message-Id: <01050913344601.04828@softnet>
Content-Transfer-Encoding: 8bit
Date: Wed,  9 May 2001 13:34:46 -0400
Topicbox-Message-UUID: 9c7b48fa-eac9-11e9-9e20-41e7f4b1d025

schweet

John had looked at it on Monday and it said Showers Sat-Mon...guess the storm 
got pushed back.

... ok, I'm getting a little excited now.

:)

On Wednesday 09 May 2001 12:58, you 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.

-- 


Sam Hopkins
------------------------------------------------
QOTD:
"Design top down, implement bottom up."