From mboxrd@z Thu Jan  1 00:00:00 1970
From: presotto@plan9.bell-labs.com
To: 9fans@cse.psu.edu
Subject: Re: [9fans] env walk
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Message-Id: <20010509165901.CD181199E7@mail.cse.psu.edu>
Date: Wed,  9 May 2001 12:58:59 -0400
Topicbox-Message-UUID: 9c754888-eac9-11e9-9e20-41e7f4b1d025

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.