Re: [9fans] env walk

[presotto@plan9.bell-labs.com]

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.