Hmmm, It's Curious

[Stan Milam]

The following code implements a strcat-like function which can receive a
variable number of arguments. I thought it would be faster if I kept a
pointer to the end of the string as it is built so that strcat() would
not always have to find the end of the string as it gets longer and
longer. To test this I called the vstrcat() function with a list of
pointers, then use the regular strcat() function in a loop to build the
same string. After 10,000,000 iteration the regular strcat() won every
time, sometimes by as much as 10 seconds. I've tried several different
approaches (as can be seen with code commented out in the vstrcat()
function) but strcat() always wins. This is using my old DOS C
compiler. On my UNIX machine they are about even.


/**********************************************************************/
/* File Id. vstrcat.c. */
/* Author: Stan Milam. */
/* Date Written: 01 Jun. 92. */
/* Description: */
/* Implement a variardic string concatenation function which will */
/* be much more efficient than successive calls to strcat(). */
/* */
/**********************************************************************/

#include <errno.h>
#include <stddef.h>
#include <string.h>
#include <stdarg.h>

/**********************************************************************/
/* Name: */
/* vstrcat() - Fast, string concatenation. */
/* */
/* Description: */
/* This function receives a variable number of string pointers */
/* and concatenates them together. The only two requirements */
/* is that the first argument which will be the target of the */
/* concatenation must have enough space to contain the entire */
/* concatenated string. The second requirement is the variable */
/* string pointers must be terminated by a NULL pointer. */
/* */
/* Arguments: */
/* char *string - A pointer to a character string where the */
/* remaining character string will be concatenated. */
/* The remaining arguments may vary in number, but must be */
/* pointers to character strings and be NULL terminated. */
/* */
/* Returns: A pointer to the concatenated string. */
/* */
/**********************************************************************/

char *
vstrcat(char *string, ...)
{
if ( string == NULL )
errno = EINVAL;
else {
va_list argptr;
char *end, *wrk;

/**************************************************************/
/* Get the address to the list of pointers. Then find the */
/* initial end of the string. */
/**************************************************************/

va_start(argptr, string);
end = *string == 0 ? string : string + (strlen(string));

/**************************************************************/
/* Pull each pointer from the list and concatenate to the end */
/* and maintain the end of the string throughout. This way */
/* we only count the characters added once. This speeds up */
/* the process tremendously. */
/**************************************************************/

while (!((wrk = va_arg(argptr, char *)) == NULL)) {
/*
strcat( end, wrk );
*/
strcpy( end, wrk );
end += strlen( wrk );
}

va_end(argptr);
}
return string;
}

#ifdef TEST
#include <time.h>
#include "adjust.h"

int
main( void )
{
int x_sub;
long l_sub;
time_t begin, end;

char wrkbuf[1000];
char *wrkarray[] = {
"This is a ",
"bunch of strings ",
"that we will concatenate ",
"very efficiently by always ",
"knowing where the end of the string is going to be. ",
"This makes vstrcat() much ",
"more efficient than successive calls to strcat!",
NULL
};

begin = time(NULL);
for ( l_sub = 0; l_sub < 10000000; l_sub++ ) {
memset(wrkbuf, 0, sizeof(wrkbuf) );
vstrcat(wrkbuf, wrkarray[0],
wrkarray[1],
wrkarray[2],
wrkarray[3],
wrkarray[4],
wrkarray[5],
wrkarray[6],
wrkarray[7],
wrkarray[8]);
}
end = time(NULL);
printf("Total time for %ld iterations of vstrcat(): %ld\n",
l_sub, (long) end - begin);

begin = time(NULL);

for( l_sub = 0; l_sub < 10000000; l_sub++ ) {
memset(wrkbuf, 0, sizeof(wrkbuf) );
for ( x_sub = 0; wrkarray[x_sub]; x_sub++ )
strcat( wrkbuf, wrkarray[x_sub] );
}

end = time(NULL);
printf("Total time for strcat(): %ld\n", (long) end - begin);


return 0;
}
#endif /* TEST */

 

[pete]

errno = EINVAL;

EINVAL isn't standard C.

char *wrkarray[] = {
"This is a ",
"bunch of strings ",
"that we will concatenate ",
"very efficiently by always ",
"knowing where the end of the string is going to be. ",
"This makes vstrcat() much ",
"more efficient than successive calls to strcat!",
NULL

That array has 8 elements.

vstrcat(wrkbuf, wrkarray[0],
wrkarray[1],
wrkarray[2],
wrkarray[3],
wrkarray[4],
wrkarray[5],
wrkarray[6],
wrkarray[7],
wrkarray[8]);

wrkarray[8] is the ninth element of an 8 element array.

 

[CBFalconer]

.... snip ...
char *wrkarray[] = {
"This is a ",
"bunch of strings ",
"that we will concatenate ",
"very efficiently by always ",
"knowing where the end of the string is going to be. ",
"This makes vstrcat() much ",
"more efficient than successive calls to strcat!",
NULL
};

begin = time(NULL);
for ( l_sub = 0; l_sub < 10000000; l_sub++ ) {
memset(wrkbuf, 0, sizeof(wrkbuf) );
vstrcat(wrkbuf, wrkarray[0],
wrkarray[1],
wrkarray[2],
wrkarray[3],
wrkarray[4],
wrkarray[5],
wrkarray[6],
wrkarray[7],
wrkarray[8]);
}

There is no wrkarray[8], so you are invoking undefined behavior
here.

 

[Stan Milam]

Stan Milam wrote:

... snip ...

char *wrkarray[] = {
"This is a ",
"bunch of strings ",
"that we will concatenate ",
"very efficiently by always ",
"knowing where the end of the string is going to be. ",
"This makes vstrcat() much ",
"more efficient than successive calls to strcat!",
NULL
};

begin = time(NULL);
for ( l_sub = 0; l_sub < 10000000; l_sub++ ) {
memset(wrkbuf, 0, sizeof(wrkbuf) );
vstrcat(wrkbuf, wrkarray[0],
wrkarray[1],
wrkarray[2],
wrkarray[3],
wrkarray[4],
wrkarray[5],
wrkarray[6],
wrkarray[7],
wrkarray[8]);
}

There is no wrkarray[8], so you are invoking undefined behavior
here.

I fixed it. It is still slower.

 

[pete]

It is still slower.

Try
*wrkbuf = '\0';
intstead of
memset(wrkbuf, 0, sizeof(wrkbuf) );

 

[pete]

end = *string == 0 ? string : string + (strlen(string));

Why not just
end = string + strlen(string);
?

I'm philosophically opposed to optimizing the degenerate case
at any expense at all to the general case.

{
/*
strcat( end, wrk );
*/
strcpy( end, wrk );
end += strlen( wrk );
}

You could also try:

{
size_t length = strlen( wrk );

memcpy( end, wrk, 1 + length );
end += length ;
}

#include "adjust.h"

It works better on my system if I replace that with
#include <stdio.h>

 

[pete]

The following code implements a strcat-like
function which can receive a
variable number of arguments.
I thought it would be faster if I kept a
pointer to the end of the string as it is built so that strcat() would
not always have to find the end of the string as it gets longer and
longer. To test this I called the vstrcat() function with a list of
pointers,
then use the regular strcat() function in a loop to build the
same string.
After 10,000,000 iteration the regular strcat() won every
time, sometimes by as much as 10 seconds.
I've tried several different
approaches (as can be seen with code commented out in the vstrcat()
function) but strcat() always wins. This is using my old DOS C
compiler. On my UNIX machine they are about even.

I changed it a little bit. This is what I got:

Total tme for strcat(): 9.328000
Total time for 10000000 iterations of vstrcat(): 8.454000

/* BEGIN new.c */

#include <string.h>
#include <stdarg.h>

char *
vstrcat(char *string, ...)
{
va_list argptr;
char *end, *wrk;

end = string + strlen(string);
va_start(argptr, string);
wrk = va_arg(argptr, char *);
while (wrk != NULL) {
strcpy( end, wrk );
end += strlen( wrk ) ;
wrk = va_arg(argptr, char *);
}
va_end(argptr);
return string;
}

#include <time.h>
#include <stdio.h>

int
main( void )
{
long l_sub;
time_t begin, end;
char wrkbuf[1000];
char *wrkarray[] = {
"This is a ",
"bunch of strings ",
"that we will concatenate ",
"very efficiently by always ",
"knowing where the end of the string is going to be. ",
"This makes vstrcat() much ",
"more efficient than successive calls to strcat!",
NULL
};

begin = clock();
for( l_sub = 0; l_sub < 10000000; l_sub++ ) {
*wrkbuf = '\0';
strcat( wrkbuf, wrkarray[0 ] );
strcat( wrkbuf, wrkarray[1 ] );
strcat( wrkbuf, wrkarray[2 ] );
strcat( wrkbuf, wrkarray[3 ] );
strcat( wrkbuf, wrkarray[4 ] );
strcat( wrkbuf, wrkarray[5 ] );
strcat( wrkbuf, wrkarray[6 ] );
}
end = clock();
printf("Total tme for strcat(): %f\n",
(double) (end - begin) / CLOCKS_PER_SEC);
begin = clock();
for ( l_sub = 0; l_sub < 10000000; l_sub++ ) {
*wrkbuf = '\0';
vstrcat(wrkbuf, wrkarray[0],
wrkarray[1],
wrkarray[2],
wrkarray[3],
wrkarray[4],
wrkarray[5],
wrkarray[6]);
}
end = clock();
printf("Total time for %ld iterations of vstrcat(): %f\n",
l_sub, (double) (end - begin) / CLOCKS_PER_SEC);
return 0;
}

/* END new.c */

 

[pete]

pete wrote:

int
main( void )
{
long l_sub;
time_t begin, end;

That should be clock_t instead of time_t.

printf("Total tme for strcat(): %f\n",
(double) (end - begin) / CLOCKS_PER_SEC);

printf("Total time for %ld iterations of vstrcat(): %f\n",
l_sub, (double) (end - begin) / CLOCKS_PER_SEC);

The last argument to both of those printf calls, should be:

(double) (end - begin) / (double) CLOCKS_PER_SEC

in case CLOCKS_PER_SEC is of type long double.

 

[Netocrat]

I changed it a little bit. This is what I got:

Total tme for strcat(): 9.328000
Total time for 10000000 iterations of vstrcat(): 8.454000

And this is what I got:

Total tme for strcat(): 8.850000
Total time for 10000000 iterations of vstrcat(): 24.930000

vstrcat(wrkbuf, wrkarray[0], [...]
wrkarray[6]);

What happened to wrkarray[7]? You now have no NULL terminator, for your
test:

while (wrk != NULL) {

I added it and with that fixed, I got 12.750000s for vstrcat.

So the OP's complaint would appear at first sight to be still true (on
my system anyway). What's going on? Well the answer is that firstly
different functions are being compared: vstrcat is in fact using strcpy
which we are comparing to multiple runs of strcat; and secondly varargs
are being used which for some reason causes the slowdown on my system.

I tried the alternative:
strcat( end, wrk );
and I got 9.290000s for vstrcat.

A lot better but still slower that multiple strcats.

So I tried an alternative function to test whether it was the varargs that
were causing the slowdown:

char *
vstrcat(char *string, char **strings) {
char *end, *wrk;

end = string + strlen(string);
wrk = *strings;
while (wrk) {
strcpy( end, wrk );
end += strlen( wrk ) ;
strings++;
wrk = *strings;
}
return string;
}

This gave times of:

11.700000s (using strcpy as above) - slightly faster than the
varargs-vstrcat; and,
8.650000s for the strcat alternative; this is faster than varargs-vstrcat
_and_ the multiple strcats... so we can finally invalidate our OP's
complaint.

Unfortunately it's less convenient to call this function than the varargs
alternative; but perhaps the OP will just have to accept that his function
isn't necessarily going to save time on all systems - this is true at
least on mine and his; though judging by your post possibly not yours pete.

Using your other suggestion:
size_t length = strlen( wrk );
memcpy( end, wrk, 1 + length );
end += length ;
I got 10.990000 secs for varargs-vstrcat and 11.320000s for array-vstrcat.

No one else has commented on the incongruity of:

strcpy( end, wrk );
end += strlen( wrk );

The vstrcat function was designed to save the cost of running strlen on
the entire in-progress string, but here we have a separate duplication
because this strlen repeats some of the preceding strcpy's work. So I
tried replacing these 2 lines with:
for ( ; *end = *wrk; end++, wrk++) ;
and I got 16.870000s for varargs-vstrcat and 18.470000s for array-vstrcat.
I didn't get the improvement I'd hoped for; obviously there's a bit of
optimisation going on in those library functions.

So the moral of the story is... you can't predict savings... but at least
try to compare apples with apples and eliminate/evaluate any differences
between the two approaches where you can.

 

[Stan Milam]

Stan Milam wrote:

I changed it a little bit. This is what I got:

Total tme for strcat(): 9.328000
Total time for 10000000 iterations of vstrcat(): 8.454000

And this is what I got:

Total tme for strcat(): 8.850000
Total time for 10000000 iterations of vstrcat(): 24.930000

vstrcat(wrkbuf, wrkarray[0],
[...]

wrkarray[6]);

What happened to wrkarray[7]? You now have no NULL terminator, for your
test:

while (wrk != NULL) {

I added it and with that fixed, I got 12.750000s for vstrcat.

So the OP's complaint would appear at first sight to be still true (on
my system anyway). What's going on? Well the answer is that firstly
different functions are being compared: vstrcat is in fact using strcpy
which we are comparing to multiple runs of strcat; and secondly varargs
are being used which for some reason causes the slowdown on my system.

I tried the alternative:
strcat( end, wrk );
and I got 9.290000s for vstrcat.

A lot better but still slower that multiple strcats.

So I tried an alternative function to test whether it was the varargs that
were causing the slowdown:

char *
vstrcat(char *string, char **strings) {
char *end, *wrk;

end = string + strlen(string);
wrk = *strings;
while (wrk) {
strcpy( end, wrk );
end += strlen( wrk ) ;
strings++;
wrk = *strings;
}
return string;
}

This gave times of:

11.700000s (using strcpy as above) - slightly faster than the
varargs-vstrcat; and,
8.650000s for the strcat alternative; this is faster than varargs-vstrcat
_and_ the multiple strcats... so we can finally invalidate our OP's
complaint.

Unfortunately it's less convenient to call this function than the varargs
alternative; but perhaps the OP will just have to accept that his function
isn't necessarily going to save time on all systems - this is true at
least on mine and his; though judging by your post possibly not yours pete.

Using your other suggestion:
size_t length = strlen( wrk );
memcpy( end, wrk, 1 + length );
end += length ;
I got 10.990000 secs for varargs-vstrcat and 11.320000s for array-vstrcat.

No one else has commented on the incongruity of:

strcpy( end, wrk );
end += strlen( wrk );

The vstrcat function was designed to save the cost of running strlen on
the entire in-progress string, but here we have a separate duplication
because this strlen repeats some of the preceding strcpy's work. So I
tried replacing these 2 lines with:
for ( ; *end = *wrk; end++, wrk++) ;
and I got 16.870000s for varargs-vstrcat and 18.470000s for array-vstrcat.
I didn't get the improvement I'd hoped for; obviously there's a bit of
optimisation going on in those library functions.

So the moral of the story is... you can't predict savings... but at least
try to compare apples with apples and eliminate/evaluate any differences
between the two approaches where you can.

Thanks! I really wasn't complaining. This is the kind of discussion I
was hoping for, not more o that "undefined behavior" shit. I just
thought it curious that I was trying to get around what appeared obvious
to me: that strcat() would have to spend time finding the end of a
continually longer string upon each call. I did a little digging into
the implementation of the string functions for my old, cheap C compiler.
The string functions were written in assembler and strcat() is the
model of efficiency. It sets a count register to 0, establishes an
address to the string in an index register then uses just one
instruction to find the end of the string. You can't beat that. Now,
if the string library had been written in C I think my vstrcat() might
have performed better. Hmmm, I feel a new project coming on....

To the poster who pointed out the EINVAL is not standard. Thanks, I did
not know that. However, I pulled out my copy of Plauger's "Standard C
Library" and found there are only three or four required values (EDOM,
ERANGE) and perhaps a couple of others, but an implementation may define
it's own set of values and be completely within the standard. So, I
suppose that is where EINVAL comes in. Anyway, it has always worked on
any machine I've ever developed on.

Regards,
Stan Milam.

 

[Chris Dollin]

I did a little digging into
the implementation of the string functions for my old, cheap C compiler.
The string functions were written in assembler and strcat() is the
model of efficiency. It sets a count register to 0, establishes an
address to the string in an index register then uses just one
instruction to find the end of the string. You can't beat that.

That isn't obvious. Sometimes, complicated single instructions
run more slowly than sequence of simple instructions with the
same effect (and are also less amenable to optimisation).

[I'm particularly thinking of the VAX `index` instruction, which
on at least some machines was slower than the corresponding
sequence of simple integer instructions. It all depends on how
the instruction is implemented and how many special cases it
has to cater for and how much room there is on the chip and
whether the moon is made of green cheese.]

 

[Stan Milam]

No one else has commented on the incongruity of:



The vstrcat function was designed to save the cost of running strlen on
the entire in-progress string, but here we have a separate duplication
because this strlen repeats some of the preceding strcpy's work. So I
tried replacing these 2 lines with:
for ( ; *end = *wrk; end++, wrk++) ;
and I got 16.870000s for varargs-vstrcat and 18.470000s for array-vstrcat.
I didn't get the improvement I'd hoped for; obviously there's a bit of
optimisation going on in those library functions.

So the moral of the story is... you can't predict savings... but at least
try to compare apples with apples and eliminate/evaluate any differences
between the two approaches where you can.

You are completely correct. That is incongrous. I changed the crital
loop within vstrcat to:


while (!((wrk = va_arg(argptr, char *)) == NULL))
while ( *wrk != 0 ) *end++ = *wrk++;

The result? More than a 50% increase in speed! It now blows away the
repeatitive strcat().

Thanks for jarring the mental cobwebs!

Regards,
Stan Milam.

 

[Stan Milam]

Stan Milam wrote:

I did a little digging into
the implementation of the string functions for my old, cheap C compiler.
The string functions were written in assembler and strcat() is the
model of efficiency. It sets a count register to 0, establishes an
address to the string in an index register then uses just one
instruction to find the end of the string. You can't beat that.

That isn't obvious. Sometimes, complicated single instructions
run more slowly than sequence of simple instructions with the
same effect (and are also less amenable to optimisation).

[I'm particularly thinking of the VAX `index` instruction, which
on at least some machines was slower than the corresponding
sequence of simple integer instructions. It all depends on how
the instruction is implemented and how many special cases it
has to cater for and how much room there is on the chip and
whether the moon is made of green cheese.]

Well, I was trying not to be too specific. I used to program a fair
amount in 8086 assembler (seems like a lifetime ago) and I was refering
to the "repnz scasb" instruction which is extremely fast.

Stan.

 

[Netocrat]

Netocrat wrote:

Thanks! I really wasn't complaining.

Inaccurate manner-of-speech: s/complaint/interesting problem/.

This is the kind of discussion I
was hoping for, not more o that "undefined behavior" shit. I just thought
it curious that I was trying to get around what appeared obvious to me:
that strcat() would have to spend time finding the end of a continually
longer string upon each call.

Well I find that undefined behaviour discussion useful since it's good to
know whether your code is guaranteed to compile properly on
standards-compliant compilers. But, yes I do find it interesting working
out what's going on with problems like this, especially when results don't
match my intuitions/summary analysis. It's counter to what I would expect
that using varargs actually impedes performance on my machine to the point
that it eliminates the gains we get from avoiding strcat having to seek to
the end of the increasing string. But there it is - and I can't find
fault with the test.

I did a little digging into the
implementation of the string functions for my old, cheap C compiler.
The string functions were written in assembler and strcat() is the
model of efficiency. It sets a count register to 0, establishes an
address to the string in an index register then uses just one
instruction to find the end of the string. You can't beat that.

It sounds fast, but you weren't trying to beat it; you were eliminating it
altogether. So no matter what, I would have expected your function to
perform better... except that there are obviously other factors at play
which I _believe_ is the varargs - seems to be on my system anyway.

Now, if the string library had been written in C I think my vstrcat()
might have performed better. Hmmm, I feel a new project coming on....

If you're going to be rewriting your function in assembler, consider an
assembler implementation of my for loop - it will avoid the duplication of
the strlen.

 

[Mark]

I changed it a little bit. This is what I got:

Total tme for strcat(): 9.328000
Total time for 10000000 iterations of vstrcat(): 8.454000

It shouldn't have worked at all, the call to vstrcat() invokes UBH
how will va_arg know where to stop? (no (char *)NULL terminator)

As for your implementation, a little messy and contains unnecessary
overhead...
Here's how I would code it:

char *
vstrcat(char *s, ...)
{
char *p = &s[strlen(s)], *wrk;
va_list ap;
va_start(ap, s);
while((wrk = va_arg(ap, char *)) != NULL)
p += sprintf(p, wrk);
va_end(ap);
return s;
}


Untested (I know it won't work with the driver below for as
I've previously stated, it's flawed) but it should outperform
both your and the original poster's functions
If you do decide to test it, let us know the results.

Mark

/* BEGIN new.c */

#include <string.h>
#include <stdarg.h>

char *
vstrcat(char *string, ...)
{
va_list argptr;
char *end, *wrk;

end = string + strlen(string);
va_start(argptr, string);
wrk = va_arg(argptr, char *);
while (wrk != NULL) {
strcpy( end, wrk );
end += strlen( wrk ) ;
wrk = va_arg(argptr, char *);
}
va_end(argptr);
return string;
}

#include <time.h>
#include <stdio.h>

int
main( void )
{
long l_sub;
time_t begin, end;
char wrkbuf[1000];
char *wrkarray[] = {
"This is a ",
"bunch of strings ",
"that we will concatenate ",
"very efficiently by always ",
"knowing where the end of the string is going to be. ",
"This makes vstrcat() much ",
"more efficient than successive calls to strcat!",
NULL
};

begin = clock();
for( l_sub = 0; l_sub < 10000000; l_sub++ ) {
*wrkbuf = '\0';
strcat( wrkbuf, wrkarray[0 ] );
strcat( wrkbuf, wrkarray[1 ] );
strcat( wrkbuf, wrkarray[2 ] );
strcat( wrkbuf, wrkarray[3 ] );
strcat( wrkbuf, wrkarray[4 ] );
strcat( wrkbuf, wrkarray[5 ] );
strcat( wrkbuf, wrkarray[6 ] );
}
end = clock();
printf("Total tme for strcat(): %f\n",
(double) (end - begin) / CLOCKS_PER_SEC);
begin = clock();
for ( l_sub = 0; l_sub < 10000000; l_sub++ ) {
*wrkbuf = '\0';
vstrcat(wrkbuf, wrkarray[0],
wrkarray[1],
wrkarray[2],
wrkarray[3],
wrkarray[4],
wrkarray[5],
wrkarray[6]);
}
end = clock();
printf("Total time for %ld iterations of vstrcat(): %f\n",
l_sub, (double) (end - begin) / CLOCKS_PER_SEC);
return 0;
}

/* END new.c */

 

[Ben Pfaff]

I used to program a fair
amount in 8086 assembler (seems like a lifetime ago) and I was
refering to the "repnz scasb" instruction which is extremely fast.

As I understand it, `repnz scasb' is faster than the equivalent
sequence of simple instructions on some chips, but slower on
others.

 

[Stan Milam]

As I understand it, `repnz scasb' is faster than the equivalent
sequence of simple instructions on some chips, but slower on
others.

I have heard that before, but like I said it was a long time ago for me
and I have not kept up with that corner of the tech field. Now I use C
for just about everything .

Stan.

 

[Netocrat]

As for your implementation, a little messy and contains unnecessary
overhead... [snip code]
Untested (I know it won't work with the driver below for as I've
previously stated, it's flawed) but it should outperform both your and the
original poster's functions If you do decide to test it, let us know
the results.

Approximately 4 times slower on my machine. Why did you expect better
performance? Even though you are getting back the length and don't have
to do a separate strlen, sprintf is by its nature much more complex than
strcat or strcpy and no doubt these two simple library functions are
much more highly optimised for this task, probably by using processor
instructions that copy many bytes at a time, which I would not expect
sprintf to be optimised to do.

But yes, your implementation is neat and concise.

 

[CBFalconer]

.... snip ...

Well, I was trying not to be too specific. I used to program a
fair amount in 8086 assembler (seems like a lifetime ago) and I
was refering to the "repnz scasb" instruction which is extremely
fast.

Which has widely variable running time, and has to access every
byte on the way up. In the bad old days it was also subject to
failure to restart after an interrupt.

 

[Netocrat]

I have heard that before, but like I said it was a long time ago for me
and I have not kept up with that corner of the tech field. Now I use C
for just about everything .

Stan.

Stan if you're interested in collaborating on some fusion asm-C, send me
an email at the address above.