Re: [PATCH] Correct dir.c to compile on Solaris 9

söndag 15 april 2007 23:03 skrev Josef Weidendorfer:

On Sunday 15 April 2007, Johannes Schindelin wrote:

quoted

On Sun, 15 Apr 2007, Shawn O. Pearce wrote:

quoted

 static int simple_length(const char *match)
 {
-	const char special[256] = {
-		[0] = 1, ['?'] = 1,
-		['\\'] = 1, ['*'] = 1,
-		['['] = 1
-	};
 	int len = -1;
 
 	for (;;) {
 		unsigned char c = *match++;
 		len++;
-		if (special[c])
+		switch (c) {
+		case 0: case '?':
+		case '\\': case '*':
+		case '[':
 			return len;
+		}
 	}
 }

You are replacing a table-based check with a switch based, which might be 
substantially slower (depends on how often cmp_name() is called).

Or faster. When the table gives a cache miss and has to be
loaded from main memory, I am quite sure that 5 compares in a row are
faster than the cache miss.

It is five compares time the length of the path being examined. The cache miss
only occurs once per invocation even inthe worst case.  Judging from where
the code is invoked, cache misses should be rare which means the table is much
faster. 

As for the table being a micro-optimization, that still holds true 

Actually, with the switch, the compiler is free to implement it with a
table (and gcc usually does this, probably even using a substantially
smaller table). The table-based check in contrast looks

It usually uses binary search. For gcc to create a lookup table you'll need
a large number of case's.

like some kind of micro-optimization which makes the code IMHO more
difficult to read, and which only would be justified with meassured
improvements.

The table lookup *is* faster (meastured), but that doesn't make a big difference
on the total CPU used. The muliple-case-per line thing (both versions, however makes is hard
to read.  

-- robin

diff --git a/dir.c b/dir.c
index 7426fde..0780f23 100644
--- a/dir.c
+++ b/dir.c

@@ -423,12 +423,22 @@ static int cmp_name(const void *p1, const void *p2)
  */
 static int simple_length(const char *match)
 {
-       const char special[256] = {
-               [0] = 1, ['?'] = 1,
-               ['\\'] = 1, ['*'] = 1,
-               ['['] = 1
-       };
        int len = -1;
+       static const char special[256] = {
+               1,0,0,0,0,0,0,0, /* nul */
+               0,0,0,0,0,0,0,0,
+               0,0,0,0,0,0,0,0,
+               0,0,0,0,0,0,0,0,
+               0,0,0,0,0,0,0,0,
+               0,0,1,0,0,0,0,0, /* * */
+               0,0,0,0,0,0,0,0,
+               0,0,0,0,0,0,0,1, /* ? */
+
+               0,0,0,0,0,0,0,0,
+               0,0,0,0,0,0,0,0,
+               0,0,0,0,0,0,0,0,
+               0,0,0,1,1,0,0,0  /* [ \ */
+       };

        for (;;) {
                unsigned char c = *match++;