From 9302898500113c6f03e1967407d1b0d5699f3789 Mon Sep 17 00:00:00 2001
From: jilles <jilles@FreeBSD.org>
Date: Sat, 30 Jan 2016 19:59:58 +0000
Subject: 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.
---
 bin/test/test.c | 164 +++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 97 insertions(+), 67 deletions(-)

(limited to 'bin/test')

diff --git a/bin/test/test.c b/bin/test/test.c
index 46e9999..48b718e 100644
--- a/bin/test/test.c
+++ b/bin/test/test.c
@@ -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
-- 
cgit v1.1