From owner-svn-src-all@freebsd.org Sat Jan 30 19:59:59 2016 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id BB96DA730A3; Sat, 30 Jan 2016 19:59:59 +0000 (UTC) (envelope-from jilles@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 75E41CE1; Sat, 30 Jan 2016 19:59:59 +0000 (UTC) (envelope-from jilles@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id u0UJxwd7051279; Sat, 30 Jan 2016 19:59:58 GMT (envelope-from jilles@FreeBSD.org) Received: (from jilles@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id u0UJxwfo051278; Sat, 30 Jan 2016 19:59:58 GMT (envelope-from jilles@FreeBSD.org) Message-Id: <201601301959.u0UJxwfo051278@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: jilles set sender to jilles@FreeBSD.org using -f From: Jilles Tjoelker Date: Sat, 30 Jan 2016 19:59:58 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r295082 - head/bin/test X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 30 Jan 2016 19:59:59 -0000 Author: jilles Date: Sat Jan 30 19:59:58 2016 New Revision: 295082 URL: https://svnweb.freebsd.org/changeset/base/295082 Log: test: Optimize operator lookup. The linear search using strcmp() shows up in pmcstat for several percent. Split the operators into lengths and whether they start with '-' and compare bytes using == instead of strcmp(). A simple test sh -c 'i=0; w=$(printf %0100d 7); while [ "$i" -lt 1000000 ]; do v=$(printf %sx%s "$w" "$w"); i=$((i+1)); done' is over 4% faster on an amd64 bhyve VM. Modified: head/bin/test/test.c Modified: head/bin/test/test.c ============================================================================== --- head/bin/test/test.c Sat Jan 30 18:41:56 2016 (r295081) +++ head/bin/test/test.c Sat Jan 30 19:59:58 2016 (r295082) @@ -120,51 +120,53 @@ enum token { #define TOKEN_TYPE(token) ((token) & 0xff00) -static struct t_op { - char op_text[4]; +static const struct t_op { + char op_text[2]; short op_num; -} const ops [] = { - {"-r", FILRD}, - {"-w", FILWR}, - {"-x", FILEX}, - {"-e", FILEXIST}, - {"-f", FILREG}, - {"-d", FILDIR}, - {"-c", FILCDEV}, - {"-b", FILBDEV}, - {"-p", FILFIFO}, - {"-u", FILSUID}, - {"-g", FILSGID}, - {"-k", FILSTCK}, - {"-s", FILGZ}, - {"-t", FILTT}, - {"-z", STREZ}, - {"-n", STRNZ}, - {"-h", FILSYM}, /* for backwards compat */ - {"-O", FILUID}, - {"-G", FILGID}, - {"-L", FILSYM}, - {"-S", FILSOCK}, +} ops1[] = { {"=", STREQ}, - {"==", STREQ}, - {"!=", STRNE}, {"<", STRLT}, {">", STRGT}, - {"-eq", INTEQ}, - {"-ne", INTNE}, - {"-ge", INTGE}, - {"-gt", INTGT}, - {"-le", INTLE}, - {"-lt", INTLT}, - {"-nt", FILNT}, - {"-ot", FILOT}, - {"-ef", FILEQ}, {"!", UNOT}, - {"-a", BAND}, - {"-o", BOR}, {"(", LPAREN}, {")", RPAREN}, - {"", 0} +}, opsm1[] = { + {"r", FILRD}, + {"w", FILWR}, + {"x", FILEX}, + {"e", FILEXIST}, + {"f", FILREG}, + {"d", FILDIR}, + {"c", FILCDEV}, + {"b", FILBDEV}, + {"p", FILFIFO}, + {"u", FILSUID}, + {"g", FILSGID}, + {"k", FILSTCK}, + {"s", FILGZ}, + {"t", FILTT}, + {"z", STREZ}, + {"n", STRNZ}, + {"h", FILSYM}, /* for backwards compat */ + {"O", FILUID}, + {"G", FILGID}, + {"L", FILSYM}, + {"S", FILSOCK}, + {"a", BAND}, + {"o", BOR}, +}, ops2[] = { + {"==", STREQ}, + {"!=", STRNE}, +}, opsm2[] = { + {"eq", INTEQ}, + {"ne", INTNE}, + {"ge", INTGE}, + {"gt", INTGT}, + {"le", INTLE}, + {"lt", INTLT}, + {"nt", FILNT}, + {"ot", FILOT}, + {"ef", FILEQ}, }; static int nargc; @@ -416,35 +418,71 @@ filstat(char *nm, enum token mode) } } -static enum token -t_lex(char *s) +static int +find_op_1char(const struct t_op *op, const struct t_op *end, const char *s) { - struct t_op const *op = ops; + char c; - if (s == 0) { - return EOI; + c = s[0]; + while (op != end) { + if (c == *op->op_text) + return op->op_num; + op++; } - while (*op->op_text) { - if (strcmp(s, op->op_text) == 0) { - if (((TOKEN_TYPE(op->op_num) == UNOP || - TOKEN_TYPE(op->op_num) == BUNOP) - && isunopoperand()) || - (op->op_num == LPAREN && islparenoperand()) || - (op->op_num == RPAREN && isrparenoperand())) - break; + return OPERAND; +} + +static int +find_op_2char(const struct t_op *op, const struct t_op *end, const char *s) +{ + while (op != end) { + if (s[0] == op->op_text[0] && s[1] == op->op_text[1]) return op->op_num; - } op++; } return OPERAND; } static int +find_op(const char *s) +{ + if (s[0] == '\0') + return OPERAND; + else if (s[1] == '\0') + return find_op_1char(ops1, (&ops1)[1], s); + else if (s[2] == '\0') + return s[0] == '-' ? find_op_1char(opsm1, (&opsm1)[1], s + 1) : + find_op_2char(ops2, (&ops2)[1], s); + else if (s[3] == '\0') + return s[0] == '-' ? find_op_2char(opsm2, (&opsm2)[1], s + 1) : + OPERAND; + else + return OPERAND; +} + +static enum token +t_lex(char *s) +{ + int num; + + if (s == 0) { + return EOI; + } + num = find_op(s); + if (((TOKEN_TYPE(num) == UNOP || TOKEN_TYPE(num) == BUNOP) + && isunopoperand()) || + (num == LPAREN && islparenoperand()) || + (num == RPAREN && isrparenoperand())) + return OPERAND; + return num; +} + +static int isunopoperand(void) { - struct t_op const *op = ops; char *s; char *t; + int num; if (nargc == 1) return 1; @@ -452,20 +490,16 @@ isunopoperand(void) if (nargc == 2) return parenlevel == 1 && strcmp(s, ")") == 0; t = *(t_wp + 2); - while (*op->op_text) { - if (strcmp(s, op->op_text) == 0) - return TOKEN_TYPE(op->op_num) == BINOP && - (parenlevel == 0 || t[0] != ')' || t[1] != '\0'); - op++; - } - return 0; + num = find_op(s); + return TOKEN_TYPE(num) == BINOP && + (parenlevel == 0 || t[0] != ')' || t[1] != '\0'); } static int islparenoperand(void) { - struct t_op const *op = ops; char *s; + int num; if (nargc == 1) return 1; @@ -474,12 +508,8 @@ islparenoperand(void) return parenlevel == 1 && strcmp(s, ")") == 0; if (nargc != 3) return 0; - while (*op->op_text) { - if (strcmp(s, op->op_text) == 0) - return TOKEN_TYPE(op->op_num) == BINOP; - op++; - } - return 0; + num = find_op(s); + return TOKEN_TYPE(num) == BINOP; } static int