The following reply was made to PR bin/36092; it has been noted by GNATS.

From: B K <mtbakerguy@yahoo.com>
To: gnats-bugs@NetBSD.org
Cc: 
Subject: Re: bin/36092: algorithmic inefficiency in bin/test/test.c:t_lex
Date: Tue, 27 Mar 2007 14:25:10 -0700 (PDT)

 Hi Christos--
 
 H'mmm, significantly improved performance without
 sacrificing readability versus significantly improved
 performance and camaro on blocks ugly.
 
 Definitely an improvement.
 
 --Brad
 
 --- Christos Zoulas <christos@zoulas.com> wrote:
 
 > The following reply was made to PR bin/36092; it has
 > been noted by GNATS.
 > 
 > From: christos@zoulas.com (Christos Zoulas)
 > To: gnats-bugs@NetBSD.org, gnats-admin@netbsd.org,
 > 	netbsd-bugs@netbsd.org
 > Cc: 
 > Subject: Re: bin/36092: algorithmic inefficiency in
 > bin/test/test.c:t_lex
 > Date: Tue, 27 Mar 2007 12:54:24 -0400
 > 
 >  On Mar 27,  5:10am, mtbakerguy@yahoo.com
 > (mtbakerguy@yahoo.com) wrote:
 >  -- Subject: bin/36092: algorithmic inefficiency in
 > bin/test/test.c:t_lex
 >  
 >  | >Number:         36092
 >  | >Category:       bin
 >  | >Synopsis:       algorithmic inefficiency in
 > bin/test/test.c:t_lex
 >  | >Confidential:   no
 >  | >Severity:       serious
 >  | >Priority:       medium
 >  | >Responsible:    bin-bug-people
 >  | >State:          open
 >  | >Class:          change-request
 >  | >Submitter-Id:   net
 >  | >Arrival-Date:   Tue Mar 27 05:10:00 +0000 2007
 >  | >Originator:     Knotwell
 >  | >Release:        3.1
 >  | >Organization:
 >  | home
 >  | >Environment:
 >  | NetBSD bradwkstn 3.1 NetBSD 3.1 (GENERIC.PROF)
 > #7: Thu Dec 14 21:54:41 PST 2006 
 >
 root@bradwkstn:/usr/src/usr/src/sys/arch/i386/compile/GENERIC.PROF
 > i386
 >  | >Description:
 >  | While profiling /bin/sh for fun, I noticed
 > several things:
 >  | 
 >  |    o the test builtin is *extremely* expensive
 > with massive calls to strcmp in the t_lex function. 
 > Specifically, it does linear walks of the operations
 > to do a match.
 >  |    o profiling /bin/sh is difficult because
 > bin/sh/trap.c:exitshell uses _exit instead of exit
 > (NB:  this isn't a bug but probably belongs in a
 > README somewhere)
 >  |    o arithmetic operations are also more
 > expensive than they need to be since there are two
 > calls made to ioctl (via isatty) when
 > arith_lex_reset is called.  In my limited testing, I
 > commented out the YY_NEW_FILE stanza and cut the
 > number of syscalls substantially in a shell doing a
 > large amount of arithmetic.
 >  | 
 >  | At this cost of some codespace as well as
 > readability*, I created a substantially improved
 > parser for the test operations that dropped strcmp
 > and t_lex off the profiler (almost) entirely.  On a
 > shell doing a significant number of boolean
 > comparisons, I cut the run time by approximately
 > 15%.
 >  | 
 >  | I've attached a diff below as well as a small
 > shell that I used to validate the change (I noticed
 > TEST.csh as I was preparing the diff).
 >  | 
 >  | *unfortunately, my change loses the data-driven
 > clarity of the original code and it wasn't obvious
 > to me how you'd get a data-driven solution nearly as
 > efficient as mine.  There's probably a simpler and
 > more elegant solution but code review's difficult on
 > a home project.
 >  
 >  How about this?
 >  
 >  christos
 >  
 >  Index: test.c
 > 
 >
 ===================================================================
 >  RCS file: /cvsroot/src/bin/test/test.c,v
 >  retrieving revision 1.30
 >  diff -u -u -r1.30 test.c
 >  --- test.c	24 Sep 2006 13:24:08 -0000	1.30
 >  +++ test.c	27 Mar 2007 16:53:02 -0000
 >  @@ -95,50 +95,60 @@
 >   	PAREN
 >   };
 >   
 >  -static struct t_op {
 >  +struct t_op {
 >   	const char *op_text;
 >   	short op_num, op_type;
 >  -} const ops [] = {
 >  -	{"-r",	FILRD,	UNOP},
 >  -	{"-w",	FILWR,	UNOP},
 >  -	{"-x",	FILEX,	UNOP},
 >  -	{"-e",	FILEXIST,UNOP},
 >  -	{"-f",	FILREG,	UNOP},
 >  -	{"-d",	FILDIR,	UNOP},
 >  -	{"-c",	FILCDEV,UNOP},
 >  -	{"-b",	FILBDEV,UNOP},
 >  -	{"-p",	FILFIFO,UNOP},
 >  -	{"-u",	FILSUID,UNOP},
 >  -	{"-g",	FILSGID,UNOP},
 >  -	{"-k",	FILSTCK,UNOP},
 >  -	{"-s",	FILGZ,	UNOP},
 >  -	{"-t",	FILTT,	UNOP},
 >  -	{"-z",	STREZ,	UNOP},
 >  -	{"-n",	STRNZ,	UNOP},
 >  -	{"-h",	FILSYM,	UNOP},		/* for backwards compat */
 >  -	{"-O",	FILUID,	UNOP},
 >  -	{"-G",	FILGID,	UNOP},
 >  -	{"-L",	FILSYM,	UNOP},
 >  -	{"-S",	FILSOCK,UNOP},
 >  -	{"=",	STREQ,	BINOP},
 >  -	{"!=",	STRNE,	BINOP},
 >  -	{"<",	STRLT,	BINOP},
 >  -	{">",	STRGT,	BINOP},
 >  -	{"-eq",	INTEQ,	BINOP},
 >  -	{"-ne",	INTNE,	BINOP},
 >  -	{"-ge",	INTGE,	BINOP},
 >  -	{"-gt",	INTGT,	BINOP},
 >  -	{"-le",	INTLE,	BINOP},
 >  -	{"-lt",	INTLT,	BINOP},
 >  -	{"-nt",	FILNT,	BINOP},
 >  -	{"-ot",	FILOT,	BINOP},
 >  -	{"-ef",	FILEQ,	BINOP},
 >  +};
 >  +
 >  +static const struct t_op cop[] = {
 >   	{"!",	UNOT,	BUNOP},
 >  -	{"-a",	BAND,	BBINOP},
 >  -	{"-o",	BOR,	BBINOP},
 >   	{"(",	LPAREN,	PAREN},
 >   	{")",	RPAREN,	PAREN},
 >  -	{0,	0,	0}
 >  +	{"<",	STRLT,	BINOP},
 >  +	{"=",	STREQ,	BINOP},
 >  +	{">",	STRGT,	BINOP},
 >  +};
 >  +
 >  +static const struct t_op cop2[] = {
 >  +	{"!=",	STRNE,	BINOP},
 >  +};
 >  +
 >  +static const struct t_op mop3[] = {
 >  +	{"ef",	FILEQ,	BINOP},
 >  +	{"eq",	INTEQ,	BINOP},
 >  +	{"ge",	INTGE,	BINOP},
 >  +	{"gt",	INTGT,	BINOP},
 >  +	{"le",	INTLE,	BINOP},
 >  +	{"lt",	INTLT,	BINOP},
 >  +	{"ne",	INTNE,	BINOP},
 >  +	{"nt",	FILNT,	BINOP},
 >  +	{"ot",	FILOT,	BINOP},
 >  +};
 >  +
 >  +static const struct t_op mop2[] = {
 >  +	{"G",	FILGID,	UNOP},
 >  +	{"L",	FILSYM,	UNOP},
 >  +	{"O",	FILUID,	UNOP},
 >  +	{"S",	FILSOCK,UNOP},
 >  +	{"a",	BAND,	BBINOP},
 >  +	{"b",	FILBDEV,UNOP},
 >  +	{"c",	FILCDEV,UNOP},
 >  +	{"d",	FILDIR,	UNOP},
 >  +	{"e",	FILEXIST,UNOP},
 >  +	{"f",	FILREG,	UNOP},
 >  +	{"g",	FILSGID,UNOP},
 >  +	{"h",	FILSYM,	UNOP},		/* for backwards compat */
 >  +	{"k",	FILSTCK,UNOP},
 >  +	{"n",	STRNZ,	UNOP},
 >  +	{"o",	BOR,	BBINOP},
 >  +	{"p",	FILFIFO,UNOP},
 >  +	{"r",	FILRD,	UNOP},
 >  +	{"s",	FILGZ,	UNOP},
 >  +	{"t",	FILTT,	UNOP},
 >  +	{"u",	FILSUID,UNOP},
 >  +	{"w",	FILWR,	UNOP},
 >  +	{"x",	FILEX,	UNOP},
 >  +	{"z",	STREZ,	UNOP},
 >   };
 >   
 >   static char **t_wp;
 >  @@ -390,26 +400,68 @@
 >   	}
 >   }
 >   
 >  +#define VTOC(x)	(const unsigned char *)((const
 > struct t_op *)x)->op_text
 >  +
 >  +static int
 >  +compare1(const void *va, const void *vb)
 >  +{
 >  +	const unsigned char *a = va;
 >  +	const unsigned char *b = VTOC(vb);
 >  +
 > 
 === message truncated ===
 
 
 
  
 ____________________________________________________________________________________
 Food fight? Enjoy some healthy debate 
 in the Yahoo! Answers Food & Drink Q&A.
 http://answers.yahoo.com/dir/?link=list&sid=396545367