strcat+strcat+strcat == baaad
Michal Janusz Miroslaw
M.Miroslaw at elka.pw.edu.pl
Mon Dec 2 01:39:34 CST 2002
On Mon, 2 Dec 2002, 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
> With higher O values, the difference becomes bigger, but I'm not sure
> then that some of the operations are not optimized out of the process,
> which makes the entire benchmark useless.
>
> So, what are our conclusions? Do we just implement strlcpy and strlcat
> so that everyone has a function that is both efficient AND secure?
>
> Do we go for David's suggestion, that is more efficient, but is also
> more cubersome and requires two extra vars to implement right?
Well, I tested this further. Result's attached (test.log).
Columns are: WAY1 (strcat), WAY2 (sprintf), WAY2_5(snprintf),
WAY3 (str_add), WAY4(stpcpy). WAY4 is something I remembered from old DOS
days, but it's nonstandard and probably available only in glibc.
Since I used glibc compiled for i686 (pentium2), we probably should not
consider entries with '-mcpu=pentium4' in comparision.
Test platform: Pentium4 Northwood; linux-2.4.20;
glibc-2.2.4 compiled with optimizations for Pentium2.
My vote is for sprintf, as it can easily be converted to safer version
and is easier to read.
My two cents only. :)
Michal Miroslaw
-------------- next part --------------
optimizations: -O0
2.925630 1.428031 1.415671 6.830230 0.933030 1000
2.643828 1.311451 1.297314 6.145886 0.842082 900
2.322319 1.177947 1.155085 5.477385 0.763962 800
2.055421 1.091778 1.072613 4.780460 0.678389 700
1.790840 0.956147 0.938855 4.097505 0.570346 600
1.473005 0.846538 0.833682 3.427522 0.490020 500
1.220861 0.711159 0.698492 2.745263 0.400367 400
0.907726 0.601574 0.587237 2.061580 0.315453 300
0.626842 0.475204 0.458666 1.383094 0.221342 200
0.332765 0.359272 0.342352 0.706845 0.132525 100
0.324317 0.369975 0.356941 0.641440 0.138774 90
0.268343 0.337921 0.321134 0.572311 0.110025 80
0.255103 0.328366 0.313709 0.505588 0.114754 70
0.217799 0.334316 0.319583 0.437710 0.092911 60
0.199289 0.311325 0.299846 0.369897 0.095742 50
0.146663 0.286867 0.273045 0.302714 0.081934 40
0.119861 0.273387 0.256234 0.234491 0.043444 30
0.085151 0.226072 0.208869 0.168637 0.036405 20
0.070228 0.172906 0.157192 0.100742 0.030363 10
optimizations: -O1
2.909446 1.428294 1.408609 3.405742 0.931165 1000
2.648363 1.308918 1.292236 3.061225 0.860551 900
2.371671 1.168194 1.159424 2.719813 0.761357 800
2.070428 1.092065 1.077162 2.392787 0.673142 700
1.768915 0.959079 0.942025 2.061097 0.565163 600
1.479999 0.846035 0.828957 1.701686 0.485289 500
1.196981 0.715236 0.697436 1.366277 0.386535 400
0.916646 0.603014 0.584415 1.028291 0.303204 300
0.610184 0.473252 0.457404 0.699250 0.211881 200
0.329980 0.358688 0.343558 0.352458 0.128013 100
0.325086 0.373707 0.355741 0.327152 0.135022 90
0.271328 0.336760 0.320182 0.292601 0.110385 80
0.261461 0.327786 0.314498 0.259647 0.112917 70
0.215130 0.334218 0.324297 0.219472 0.097777 60
0.196848 0.316169 0.295127 0.192091 0.095513 50
0.143622 0.289223 0.270030 0.159459 0.076105 40
0.118739 0.273194 0.256876 0.124247 0.043409 30
0.084827 0.226031 0.208585 0.089663 0.037765 20
0.069345 0.173843 0.156696 0.061054 0.029129 10
optimizations: -O2
2.926220 1.427674 1.408928 3.405458 0.892890 1000
2.622081 1.308464 1.292384 3.062085 0.867009 900
2.363464 1.169335 1.152487 2.727685 0.740690 800
2.041044 1.089567 1.072333 2.392878 0.656994 700
1.776868 0.961844 0.939509 2.052435 0.581547 600
1.475763 0.843419 0.827785 1.712919 0.486133 500
1.191509 0.711448 0.697306 1.383520 0.392607 400
0.929707 0.600976 0.585319 1.033434 0.296106 300
0.616224 0.474247 0.458438 0.696729 0.216387 200
0.330736 0.357966 0.338154 0.358755 0.131919 100
0.317279 0.371345 0.354066 0.325248 0.134290 90
0.266885 0.337228 0.320308 0.291095 0.111172 80
0.258562 0.326651 0.310362 0.257567 0.112924 70
0.214379 0.333883 0.317327 0.224012 0.094164 60
0.196770 0.313147 0.293314 0.190855 0.092348 50
0.150237 0.286512 0.271773 0.157010 0.075744 40
0.119881 0.272563 0.255693 0.122030 0.042610 30
0.084110 0.226567 0.206505 0.089100 0.034843 20
0.069855 0.170332 0.154248 0.064323 0.030286 10
optimizations: -O3
2.942428 1.433216 1.407076 3.399584 0.893529 1000
2.641505 1.315982 1.295463 3.075709 0.853599 900
2.356297 1.169211 1.159545 2.728766 0.763332 800
2.057784 1.090530 1.072154 2.388681 0.659578 700
1.752200 0.951311 0.936308 2.045367 0.575463 600
1.488033 0.842985 0.829275 1.707826 0.470810 500
1.202276 0.711996 0.698895 1.371388 0.397342 400
0.913355 0.601383 0.586208 1.033479 0.314630 300
0.610480 0.474676 0.459156 0.694701 0.210426 200
0.334435 0.355694 0.341353 0.354297 0.126860 100
0.329906 0.372304 0.356827 0.329800 0.136730 90
0.275683 0.350809 0.333730 0.294297 0.112565 80
0.261189 0.325472 0.311150 0.254024 0.114781 70
0.214059 0.335485 0.318874 0.219993 0.094655 60
0.198788 0.318126 0.297642 0.189285 0.092593 50
0.144770 0.287304 0.269066 0.152130 0.075626 40
0.120926 0.272678 0.255376 0.117373 0.042947 30
0.084795 0.229965 0.207382 0.084496 0.034257 20
0.070170 0.172611 0.153161 0.060101 0.029292 10
optimizations: -O9
2.935145 1.422116 1.402519 3.403004 0.902521 1000
2.636768 1.308993 1.291912 3.061335 0.863081 900
2.351775 1.164242 1.149017 2.729575 0.762053 800
2.078044 1.100088 1.082689 2.403582 0.652978 700
1.767174 0.951429 0.939484 2.048560 0.570384 600
1.477613 0.844435 0.827500 1.706625 0.473997 500
1.178117 0.712841 0.700511 1.371989 0.391728 400
0.900485 0.601350 0.588236 1.033393 0.304656 300
0.620561 0.475165 0.459864 0.692925 0.214230 200
0.330640 0.358898 0.339695 0.355246 0.131818 100
0.324434 0.373494 0.357284 0.325978 0.141450 90
0.272054 0.336196 0.320559 0.286776 0.110199 80
0.256900 0.328531 0.310390 0.254071 0.111890 70
0.224501 0.333857 0.322486 0.223912 0.094049 60
0.193915 0.318204 0.294354 0.185490 0.092950 50
0.143907 0.285356 0.268471 0.152272 0.076676 40
0.121545 0.273192 0.256317 0.121331 0.042402 30
0.083851 0.228884 0.211705 0.084496 0.033986 20
0.067663 0.170953 0.153446 0.059375 0.029067 10
optimizations: -O1 -march=i686
2.922572 1.434443 1.414050 3.430342 0.921480 1000
2.630393 1.311895 1.297846 3.054697 0.880356 900
2.366480 1.180587 1.657326 2.729436 0.780568 800
2.091423 1.110963 1.339587 2.401242 0.658811 700
1.754475 0.954752 0.939316 2.028923 0.560946 600
1.466964 0.843092 0.826277 1.718026 0.481415 500
1.220152 0.712090 0.697149 1.361177 0.380961 400
0.912941 0.599993 0.583450 1.022008 0.311554 300
0.610315 0.474602 0.458712 0.681435 0.219358 200
0.327424 0.360759 0.343948 0.360792 0.127681 100
0.319892 0.371894 0.355231 0.320720 0.137695 90
0.271563 0.338744 0.326568 0.294226 0.110880 80
0.262542 0.340405 0.309769 0.259033 0.113188 70
0.214272 0.332642 0.323559 0.226505 0.096927 60
0.200354 0.312343 0.297632 0.191788 0.092134 50
0.143970 0.285348 0.272063 0.157971 0.076979 40
0.121547 0.271212 0.255598 0.125401 0.044275 30
0.082244 0.227636 0.207887 0.090857 0.035589 20
0.068995 0.171354 0.155045 0.062033 0.030122 10
optimizations: -O1 -march=i686 -mcpu=pentium4
2.957177 1.422307 1.405452 2.649858 0.923530 1000
2.643925 1.314184 1.299356 2.320025 0.854961 900
2.343244 1.169884 1.152418 2.114584 0.778276 800
2.057531 1.098920 1.079421 1.844352 0.672329 700
1.781101 0.953718 0.938371 1.582069 0.588013 600
1.483120 0.842096 0.826306 1.337835 0.477563 500
1.203584 0.712710 0.696099 1.077982 0.387711 400
0.898162 0.600776 0.581269 0.815386 0.295444 300
0.612761 0.475534 0.458773 0.543791 0.220403 200
0.332816 0.359626 0.343559 0.275060 0.130657 100
0.320611 0.372808 0.354988 0.246978 0.134966 90
0.267640 0.338065 0.318774 0.233535 0.110446 80
0.256817 0.326473 0.311392 0.199094 0.114368 70
0.212469 0.334220 0.317903 0.179323 0.092981 60
0.195162 0.314696 0.292236 0.149321 0.093068 50
0.142692 0.284339 0.269246 0.119155 0.077114 40
0.130709 0.272780 0.255864 0.091655 0.044390 30
0.082049 0.225922 0.208294 0.072589 0.035767 20
0.069124 0.172931 0.154811 0.049068 0.029852 10
optimizations: -O2 -march=i686
2.922711 1.424294 1.407527 3.391952 0.906006 1000
2.645165 1.308179 1.288658 3.061746 0.880488 900
2.325340 1.165986 1.153086 2.723679 0.766390 800
2.081531 1.089461 1.071599 2.385834 0.688307 700
1.770655 0.952956 0.938945 2.047302 0.561713 600
1.495025 0.843789 0.828535 1.710844 0.482044 500
1.189064 0.711156 0.697051 1.372360 0.398250 400
0.911640 0.598478 0.585654 1.032216 0.299012 300
0.610902 0.475305 0.459678 0.696739 0.214418 200
0.325654 0.359112 0.340346 0.359103 0.133121 100
0.327363 0.371676 0.353598 0.324510 0.136732 90
0.274866 0.335520 0.319851 0.290918 0.111550 80
0.260239 0.328189 0.308436 0.257828 0.111979 70
0.213117 0.335145 0.319746 0.224094 0.094250 60
0.200418 0.312753 0.293941 0.190196 0.094352 50
0.142584 0.284594 0.268697 0.156370 0.075338 40
0.124542 0.272727 0.254311 0.122616 0.044725 30
0.087001 0.226725 0.208284 0.088943 0.034214 20
0.070547 0.170288 0.152564 0.062645 0.029187 10
optimizations: -O2 -march=i686 -mcpu=pentium4
2.939568 1.419928 1.401097 2.380822 0.893804 1000
2.641707 1.306407 1.288285 2.159631 0.866862 900
2.350556 1.164217 1.151505 1.895193 0.758133 800
2.066941 1.089702 1.071433 1.660155 0.643767 700
1.780274 0.951717 0.936842 1.444399 0.572592 600
1.457980 0.843611 0.824995 1.192479 0.471189 500
1.188029 0.712043 0.696446 0.978281 0.400860 400
0.912270 0.600515 0.586774 0.757300 0.310936 300
0.610998 0.473951 0.458737 0.511684 0.211849 200
0.329585 0.359664 0.344247 0.253913 0.127771 100
0.328537 0.373716 0.357806 0.234605 0.135502 90
0.279159 0.337982 0.318657 0.205667 0.111195 80
0.259430 0.327559 0.311506 0.193550 0.114791 70
0.215587 0.335760 0.316926 0.165760 0.095894 60
0.197384 0.311734 0.293301 0.136596 0.094902 50
0.141679 0.285333 0.270999 0.114283 0.075268 40
0.129348 0.271980 0.254447 0.088966 0.047577 30
0.080743 0.224225 0.205943 0.071240 0.035770 20
0.069135 0.172673 0.155844 0.044972 0.030480 10
-------------- next part --------------
#define _GNU_SOURCE
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <time.h>
#include <alloca.h>
#ifndef NUM_ITER
#define NUM_ITER 100000
#endif
#ifndef STRING_LEN
#define STRING_LEN 1000
#endif
#define BUFLEN (STRING_LEN * 10 + 1)
char *
str_add(char *s, char *lim, const char *a)
{
int c;
do {
if (s >= lim) {
s = lim - 1;
c = 0;
} else
c = *a++;
*s++ = c;
} while (c);
return s;
}
void
sub_time(struct timeval *time, struct timeval *begin)
{
time->tv_sec -= begin->tv_sec;
time->tv_usec -= begin->tv_usec;
if (time->tv_usec < 0) {
time->tv_usec += 1000000;
--time->tv_sec;
}
printf("%4ld.%06ld ", time->tv_sec, time->tv_usec);
}
int main()
{
struct timeval start, end;
char *buffer = (char *)alloca(BUFLEN);
int i, l;
char *STRING = (char *)alloca(STRING_LEN + 1);
memset(STRING, '1', STRING_LEN);
for(l = STRING_LEN; l >= 10; (l > 100) ? (l -= 100) : (l -= 10)) {
STRING[l] = 0;
// WAY1
gettimeofday(&start, NULL);
for( i=0; i<NUM_ITER; ++i )
{
strcpy( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
strcat( buffer, STRING );
}
gettimeofday(&end, NULL);
sub_time(&end, &start);
// WAY2
gettimeofday(&start, NULL);
for( i=0; i<NUM_ITER; ++i )
{
sprintf( buffer, "%s%s%s%s%s%s%s%s%s%s", STRING, STRING, STRING, STRING,
STRING, STRING, STRING, STRING, STRING, STRING );
}
gettimeofday(&end, NULL);
sub_time(&end, &start);
// WAY2.5
gettimeofday(&start, NULL);
for( i=0; i<NUM_ITER; ++i )
{
snprintf( buffer, BUFLEN, "%s%s%s%s%s%s%s%s%s%s", STRING, STRING, STRING, STRING,
STRING, STRING, STRING, STRING, STRING, STRING );
}
gettimeofday(&end, NULL);
sub_time(&end, &start);
// WAY3
gettimeofday(&start, NULL);
for( i=0; i<NUM_ITER; ++i )
{
char *pointer=buffer;
char *const limit=buffer+BUFLEN;
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 );
}
gettimeofday(&end, NULL);
sub_time(&end, &start);
// WAY4
gettimeofday(&start, NULL);
for( i=0; i<NUM_ITER; ++i )
{
char *pointer=buffer;
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
pointer=stpcpy(pointer, STRING);
}
gettimeofday(&end, NULL);
sub_time(&end, &start);
printf("%4d\n", l);
}
return 0;
}
-------------- next part --------------
#!/bin/bash
for opt in '-O0' '-O1' '-O2' '-O3' '-O9' '-O1 -march=i686' '-O1 -march=i686 -mcpu=pentium4' \
'-O2 -march=i686' '-O2 -march=i686 -mcpu=pentium4'; do
gcc $opt -o test strcpy.c
echo "optimizations: $opt"
./test
done
More information about the wine-devel
mailing list