strcat+strcat+strcat == baaad

[David Fraser]

Shachar Shemesh wrote:

> Benchmark will follow soon. In the mean time, think about the fact 
> that, compared to linear copying of the strings in, these are the 
> overheads (neglecting function call overhead, which is not neglectible 
> but is fair):
> n - number of strings in the final string
> m(i) - length of string i (0<i<=n)
> sm(i) - sigma of all lengths up to i (0<i<=n)
> sm(n) - total length of all strings
> with sprintf - parsing the format string*n+sm(n)
> with strcpy+strcat - for each strcat we have to find the end of the 
> string (sm(i-1)), and then write our own string (m(i)).

Shachar Shemesh wrote:

> When I'm wrong, I'm wrong.
>
> sun at sun:~/sources/wine/test$ gcc -O0 strcpy.c -o way1 -DWAY1
> sun at sun:~/sources/wine/test$ gcc -O0 strcpy.c -o way2 -DWAY2
> sun at sun:~/sources/wine/test$ gcc -O0 strcpy.c -o way3 -DWAY3
> 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
>
Was going to say earlier, but didn't get to it ... the reason is 
probably that
you were underestimating the time required to parse the format string,
which is probably greater than anything else. Everything else is simple
searching and copying whereas the parsing is probably at least a
quadratic-order function. Anyway you've now demonstrated that so
this isn't that relevant anymore...

David