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: multipart/mixed; boundary="upas-htumzvofiarrcqpvcsqfctjpbt" Message-Id: <20010509132356.1923D199F0@mail.cse.psu.edu> Date: Wed, 9 May 2001 09:23:54 -0400 Topicbox-Message-UUID: 9c47f98c-eac9-11e9-9e20-41e7f4b1d025 This is a multi-part message in MIME format. --upas-htumzvofiarrcqpvcsqfctjpbt Content-Disposition: inline Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit All the devices that use devwalk have n squared behavior. It wasn't supposed to be a problem because n isn't supposed to be large for them. I agree that it's short sighted for something with potentially many files like #e. Your solution is also O(n**2), though the constant is much smaller (no devdir inside the loop). I'll replace the devwalk with your search and put it on the next update wrap. Also, on network performance, we played a bunch with TCP speed after Dong Lin showed us how slow we were. Last we tested our TCP stack, we came out somewhere between Linux and FreeBSD in speed between 2 500 MHZ Pentiums on a 100meg ether. That's partially why loopbackmedium appeared, to see how much was stack and how much driver. I'll run a new set of tests in a few weeks and post when I'm done. Since both all 3 OS's are moving targets, the validity of the tests is transient. Sic transit perfunctio. --upas-htumzvofiarrcqpvcsqfctjpbt Content-Type: message/rfc822 Content-Disposition: inline Received: from plan9.cs.bell-labs.com ([135.104.9.2]) by plan9; Wed May 9 08:05:30 EDT 2001 Received: from mail.cse.psu.edu ([130.203.4.6]) by plan9; Wed May 9 08:05:28 EDT 2001 Received: from psuvax1.cse.psu.edu (psuvax1.cse.psu.edu [130.203.6.6]) by mail.cse.psu.edu (CSE Mail Server) with ESMTP id F0D2719A15; Wed, 9 May 2001 08:05:12 -0400 (EDT) Received: from mercury.bath.ac.uk (mercury.bath.ac.uk [138.38.32.81]) by mail.cse.psu.edu (CSE Mail Server) with ESMTP id 70065199E7 for <9fans@cse.psu.edu>; Wed, 9 May 2001 08:04:33 -0400 (EDT) Received: from news by mercury.bath.ac.uk with local (Exim 3.12 #1) id 14xSYS-00066F-00 for 9fans@cse.psu.edu; Wed, 09 May 2001 12:54:56 +0100 Received: from GATEWAY by bath.ac.uk with netnews for 9fans@cse.psu.edu (9fans@cse.psu.edu) To: 9fans@cse.psu.edu From: Peter Schay Message-ID: <3AF92776.18AE2A42@pobox.com> Organization: MindSpring Enterprises Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Subject: [9fans] env walk Sender: 9fans-admin@cse.psu.edu Errors-To: 9fans-admin@cse.psu.edu X-BeenThere: 9fans@cse.psu.edu X-Mailman-Version: 2.0.1 Precedence: bulk Reply-To: 9fans@cse.psu.edu List-Id: Fans of the OS Plan 9 from Bell Labs <9fans.cse.psu.edu> List-Archive: Date: Wed, 9 May 2001 11:54:30 GMT 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;  --upas-htumzvofiarrcqpvcsqfctjpbt--