[9fans] env walk

[Peter Schay <pschay@pobox.com>]

This posting got truncated at the ".".  2nd attempt:

Here's more on the performance subject; I hope the
following optimization is useful and not too inelegant.

The algorithm for walking in #e seems to be O(n*n).
I think it's pretty easy to make it O(n).

For example, on my system the following script takes no
time with 42 environment variables takes 4 seconds with
441 vars:

	term% time /fd/0 <<.
	#!/bin/rc
	rfork e
	eval X^(`{seq 1})^('=1')
	echo nvars `{ls /env | wc -l}
	.
	nvars 42
	0.01u 0.02s 0.06r        /fd/0

	term% time /fd/0 <<.
	#!/bin/rc
	rfork e
	eval X^(`{seq 400})^('=1')
	echo nvars `{ls /env | wc -l}
	.
	nvars 441
	0.14u 3.59s 4.14r        /fd/0

(OK, this was an abusive script.  But the effect can be
noticable for non-abusers too.)

Usually you really only lose time when rc forks, I think,
and even then not always.  I'm not exactly sure.

Changing envwalk() has a big impact on large (ok, bloated)
make projects.  Even on the small job of compiling the
Plan 9 kernel you save a few per cent of system time.  And I'm
sure there are many truly abusive projects out there that
could build much faster.

IMHO, rc and mk are masterpieces and it's a shame
to limit them by wasting time on walks in #e.

So here's a proposed optimization of envwalk(), to avoid
spending too much time in envgen():

term% diff /sys/src/9/port/devenv.c .
60c60,78
<       return devwalk(c, name, 0, 0, envgen);
---
>       Evalue *e;
>       Egrp *eg = up->egrp;
> 
>       isdir(c);
>       if(name[0]=='.' && name[1]==0)
>               return 1;
> 
>       qlock(eg);
>       for(e = eg->entries; e; e = e->link)
>               if(!strcmp(e->name, name))
>                       break;
>       if(e) {
>               c->qid = e->qid;
>               qunlock(eg);
>               return 1;
>       }
>       qunlock(eg);
>       strncpy(up->error, Enonexist, NAMELEN);
>       return 0;
\x01\x01\x01\x01