strcat+strcat+strcat == baaad

[Martin Wilck]

Am Son, 2002-12-01 um 23.07 schrieb Shachar Shemesh:
> When I'm wrong, I'm wrong.

> sun at sun:~/sources/wine/test$ ./way1
> Operation took 0 seconds 450763 usec
> sun at sun:~/sources/wine/test$ ./way2
> Operation took 0 seconds 598408 usec
> sun at sun:~/sources/wine/test$ ./way3
> Operation took 0 seconds 427037 usec

First off, the program is wrong in that "way3" doesn't do what it's
supposed to (concatenate). Below is a patch for your benchmark with a
"WAY4" going a similar path as WAY3, but using strlen() and memcpy(),
and a WAY5 that is pretty similar to David's, but better with gcc 3.2.

My resume is: Don't try to outwit the C library. Assume that the user
has installed a good one, and use library functions. 

(Btw ever looked at the section about "strcat" in the glibc info pages?)

WAY4 below is very fast with a good C library. On i686, it is best for
all optimizations except -O1 where gcc inlines self-generated
i386-optimized code which is more than a factor of 2 slower than the
library routine. It also requires the "-march=i686" option to gcc,
otherwise gcc wrongly assumes that i386 optimizations are the best, and
uses them always.

Of course, if the lengths of the strings are known, you can speed this
up a lot by doing without strlen(). 

WAY2 depends on the "strcat" implementation in the library. It may be
slower than the snprintf solution if strcat is badly optimized. (And
it's unsafe)!

David's WAY3, being not library dependent, is quite good except for -O0.
With GCC 3.2 and optimization -O2 and above, it is necessary to reverse
the "if" and "else" clauses in str_add(), otherwise performance degrades
because gcc assumes the "if" branch is taken more often. (That reversed 
str_add is called "WAY5" below.

These are my results, obtained on a PIII system with RedHat 8.0, using
"gcc -Ox -march=i686" as optimization: (I took gcc3.2 -O0 as "reference
value" 1.0):

GCC 3.2	 -O0	-O1	-O2	-O3
WAY1	1.00	0.98	0.97	0.97
WAY2	0.93	0.98	0.92	0.93
WAY3	2.28	0.67	0.95	1.05
WAY4	0.49	1.00	0.46	0.41
WAY5	2.53	0.66	0.66	0.76
				
GCC 2.96 -O0	-O1	-O2	-O3
WAY1	1.00	0.98	1.02	1.02
WAY2	0.93	0.93	0.93	0.93
WAY3	2.21	0.67	0.69	0.63
WAY4	0.49	1.02	0.48	0.42
WAY5	2.42	0.67	0.69	0.63

Martin

--- strorg.c	Mon Dec  2 13:29:43 2002
+++ strcpy.c	Mon Dec  2 17:35:00 2002
@@ -12,15 +12,38 @@
 	int c;
 
 	do {
+#if WAY5
+		if ( s < lim ) c = *a++;
+		else {
+			s = lim - 1;
+			c = 0;
+		}
+#else
 		if (s >= lim) {
 			s = lim - 1;
 			c = 0;
 		} else
 			c = *a++;
+#endif
 		*s++ = c;
 	} while (c);
 
-	return s;
+	return --s;
+}
+
+char* 
+str1_add(char*s, int *len, const char *a)
+{
+
+    int l = strlen(a);
+    if ( l >= *len ) 
+        l = *len - 1;
+        
+    memcpy ( s, a, l ) ;
+    *len -= l;
+    s += l;
+    *s = 0;
+    return s;
 }
 
 int main()
@@ -32,7 +55,7 @@
     gettimeofday(&before, NULL);
     for( i=0; i<NUM_ITER; ++i )
     {
-#ifdef WAY1
+#if WAY1
 	strcpy( buffer, STRING );
 	strcat( buffer, STRING );
 	strcat( buffer, STRING );
@@ -46,21 +69,33 @@
 #elif WAY2
 	sprintf( buffer, "%s%s%s%s%s%s%s%s%s%s", STRING, STRING, STRING, STRING,
 		STRING, STRING, STRING, STRING, STRING, STRING );
-#elif WAY3
+#elif ( WAY3 || WAY5 )
 	char *pointer=buffer;
 	char *const limit=buffer+sizeof(buffer);
 
-	buffer[0]='\0';
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
-	pointer=str_add( buffer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+	pointer=str_add( pointer, limit, STRING );
+#elif WAY4
+        char *p = buffer;
+        int len = sizeof(buffer);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
+        p = str1_add (p, &len, STRING);
 #endif
     }
     gettimeofday(&after, NULL);
@@ -70,13 +105,7 @@
 	diff_sec=after.tv_sec-before.tv_sec;
 	diff_usec=after.tv_usec-before.tv_usec;
 
-	if( diff_usec<0 )
-	{
-	    diff_usec+=1000000;
-	    diff_sec--;
-	}
-
-	printf("Operation took %ld seconds %ld usec\n", diff_sec, diff_usec );
+	printf("Operation took %07ld usec\n", diff_sec * 1000000 +  diff_usec );
     }
 
     return 0;

-- 
Martin Wilck                Phone: +49 5251 8 15113
Fujitsu Siemens Computers   Fax:   +49 5251 8 20409
Heinz-Nixdorf-Ring 1	    mailto:Martin.Wilck at Fujitsu-Siemens.com
D-33106 Paderborn           http://www.fujitsu-siemens.com/primergy