strcat

Version imprimable

12/01/2005, 03h23
moldavi

strcat
Je développe un logiciel qui doit manipuler des chaînes de caractères.

Pour gérer les erreurs, j'ai écrit une version personnalisée de strcat. Ceci me permet de contrôler que les tableaux se terminent bien par '\0', et que le tableau qui est concaténé a suffisamment de place.

Puis pour la version release, j'utilise strcat du C standard, lorsque bien sur je sais que mes initialisations et mes gestions de tableaux sont correctes.

Mais par curiosité j'ai écrit des versions de strcat et j'ai comparé les vitesses d'exécution:
Code:

1 2 3 4 5 6 7 8 9 void szcpy2(char* tab1, const char* tab2){ tab1 += strlen(tab1); while(*tab2) *tab1++ = *tab2++; *tab1 = '\0'; }
Code:

1 2 3 4 5 6 7 8 9 void szcpy1(char* tab1, const char* tab2, size_t iSize){ tab1 += iSize; while(*tab2) *tab1++ = *tab2++; *tab1 = '\0'; }
Code:

1 2 3 4 5 6 7 8 9 10 void szcpy(char* tab1, const char* tab2){ while(*tab1) tab1++; while(*tab2) *tab1++ = *tab2++; *tab1 = '\0'; }
J'ai affiché les fonctions de la plus rapide à la moins rapide. Et bien à ma grande surprise il y a une différence significative avec la fonction strcat du C standard. Je me demande comment se fait-il que mes fonctions soient beaucoup plus lentes.

Est-ce que strcat est écrit en assembleur? Ou alors mes codes sont-ils pourris?

voici le code de strcat standard:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char * __cdecl strcat (
        char * dst,
        const char * src
        )
{
        char * cp = dst;
 
        while( *cp )
                cp++;                   /* find end of dst */
 
        while( *cp++ = *src++ ) ;       /* Copy src to end of dst */
 
        return( dst );                  /* return dst */
 
}

Même avec cette fonction ce n'est pas mieux:

Code:

1
2
3
4
5
6
7
8
9
void szcat(char* tab1, const char* tab2){
 
  while(*tab1)
    tab1++;
 
  while(*tab1++ = *tab2++);
}
 
je ne mémorise pas le pointeur de départ et bien c'est moins rapide quand même!!!!

12/01/2005, 06h28
SKZ81

8O 8O Effectivement...
Ce qui me parraît louche chez toi c'est que szcpy1() est plus lent que szcpy2(), alors qu'on économise l'appel à strlen() 8O Tu es sûr que tu ne le fait pas avant d'appeler la fonction?
Comment mesure tu le temps d'éxecution ? (il faut faire attention à ne pas mesurer le temps passé hors du processus, i.e. temps système et autres tâches).

Pour le reste c'est probablement une question d'optimisation du compilateur.
Le fait d'utiliser une variable locale (cp) dans la version standard permet au compilo d'en faire une variable register, ce qui économise un accès mémoire à chaque pas (dax le cache proce est rapide mais pas plus qu'un registre).
12/01/2005, 08h02
Emmanuel Delahaye

Re: strcat

Citation:

Envoyé par moldavi

Est-ce que strcat est écrit en assembleur? Ou alors mes codes sont-ils pourris?

Pour faire des copies rapides, il faut utiliser memcpy()...

D'autre part, les fonctions de la bibliothèque sont écrites dans n'importe quel langage, car la norme décrit le comportement et non l'implémentation (heureusement). C'est ce qui permet à chaque bibliothèque d'être optimisée pour chaque cible, alors que le langage reste identique et portable.
12/01/2005, 09h31
gege2061

Re: strcat

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par moldavi

Est-ce que strcat est écrit en assembleur? Ou alors mes codes sont-ils pourris?

Pour faire des copies rapides, il faut utiliser memcpy()...

D'autre part, les fonctions de la bibliothèque sont écrites dans n'importe quel langage, car la norme décrit le comportement et non l'implémentation (heureusement). C'est ce qui permet à chaque bibliothèque d'être optimisée pour chaque cible, alors que le langage reste identique et portable.

C'est d'ailleur étonant que sa ne soit pas en assembleur!
12/01/2005, 10h55
Emmanuel Delahaye

Re: strcat

Citation:

Envoyé par gege2061

C'est d'ailleur étonant que sa ne soit pas en assembleur!

Qu'en sais tu ? memcpy() est souvent une fonction inline qui est implémentée à coup de copies rapides par blocs... (du moins en x86...)
12/01/2005, 18h44
thewho

Bonjour,

Si tu utilises VC++:
l'algorithme standard que tu donnes n'est pas celui utilisé par le compilateur, même si on le trouve dans strcat.c

Regarde le source strcat.c, il y a dedans

Code:

#pragma function (strcpy, strcat)

Ceci signifiant que strcpy et strcat sont des fonctions spéciales.
(va voir l'aide de #pragma, option function).

Il y a d'autres sources pour ces fonctions dans:
C:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\crt\src\intel\strcat.asm

et même celles-là ne semblent pas être le code utilisé par le compilateur (au moins en mode release) : ces fonctions "spéciales" ne sont normalement pas fournies en source.

De toute manière, j'ai regardé le code généré, c'est tellement optimisé (la fonction standard), qu'il ne faut pas trop espérer faire mieux, ou alors très difficilement.
12/01/2005, 19h43
moldavi
Je n'attendais pas autant de réponses :D

Je pense que vous êtes tous dans le vrai. Effectivement, j'utilise visual c++.net et je compile à la norme C++. C'est la raison pour laquelle j'ai omis les inline dans mes fonctions.

Code:

Comment mesure tu le temps d'éxecution ?

Pour faire mes tests, j'ai utilisé queryperformancecounter avec des boucles de 10000 évaluations, mais pour 100 évaluations les résultats sont similaires. Même si windows est multitâche et même si les résultats ne sont pas précis, le fait d'utiliser une boucle et de faire la moyenne permet d'avoir un ordre d'idée sur les vitesses d'exécution, et de pouvoir dire que tel fonction s'exécute plus vite qu'une autre.

Citation:

Ce qui me parraît louche chez toi c'est que szcpy1() est plus lent que szcpy2()

Effectivement, ce n'est pas vrai à chaque fois, mais dans l'ensemble oui.
En fait j'utilise strlen dans l'appel de fonction à szcpy2()

Code:

szcpy1(tab1, tab2, strlen(tab1));

Je suis aussi surpris que toi.

Citation:

Le fait d'utiliser une variable locale (cp) dans la version standard permet au compilo d'en faire une variable register

Très intéressant, je vais regardé ça de plus près.

Citation:

Pour faire des copies rapides, il faut utiliser memcpy()...

Je pense que strcat utilise memcpy effectivement.

Citation:

Ceci signifiant que strcpy et strcat sont des fonctions spéciales.
(va voir l'aide de #pragma, option function).

Tu as raison et plus tard j'ai remarqué ces #pragma. Il y a le #pragma intrinsic avec des valeurs comme _enable et _disable qui indiquerai au système d'exploitation de ne pas faire de multitâche entre ces deux indicateurs. Je vais regarder ça de plus près.

Citation:

De toute manière, j'ai regardé le code généré, c'est tellement optimisé (la fonction standard), qu'il ne faut pas trop espérer faire mieux, ou alors très difficilement.

Je suis entièrement d'accord avec toi. L'idée général pour moi était de redéfinir strcat pour pouvoir utiliser une version en debug et une autre version en release.
Code:

1 2 3 4 5 6 #ifdefine _DEBUG #define szcat szcat1 #else #define szcat szcat2 #endif
Mais vu que strcat est plus optimisée que szcat j'ai dû feinté.
Code:

1 2 3 4 #ifdefine _DEBUG static char* strcat(char*, const char*); #endif
J'aimerais faire la même chose avec l'opérateur new sans surcharge, mais je posterai dans le forum C++.
[/code]

Re: strcat

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par gege2061

C'est d'ailleur étonant que sa ne soit pas en assembleur!

Qu'en sais tu ? memcpy() est souvent une fonction inline qui est implémentée à coup de copies rapides par blocs... (du moins en x86...)
Citation:
voici le code de strcat standard:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 char * __cdecl strcat ( char * dst, const char * src ) { char * cp = dst; while( *cp ) cp++; /* find end of dst */ while( *cp++ = *src++ ) ; /* Copy src to end of dst */ return( dst ); /* return dst */ }
:lol: quelque underscore et trois mot d'anglais dans une source et je pense que c'est tiré de la bibliothèque standard:

Citation:

voici le code de strcat standard

Re: strcat

Citation:

Envoyé par gege2061

Citation:

voici le code de strcat standard:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
char * __cdecl strcat (
        char * dst,
        const char * src
        )
{
        char * cp = dst;
 
        while( *cp )
                cp++;                   /* find end of dst */
 
        while( *cp++ = *src++ ) ;       /* Copy src to end of dst */
 
        return( dst );                  /* return dst */
 
}

quelque underscore et trois mot d'anglais dans une source et je pense que c'est tiré de la bibliothèque standard:

Citation:

voici le code de strcat standard

"La bibliothèque standard" ça n'existe pas, du moins du point de vue implémentation. Encore une fois, ce que tu nous montres est une implémentation parmi d'autres de strcat().

Code Composer (pour Texas Instrument DSP TMS320C54) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
/*****************************************************************************/
/* string.h   v3.83                                                         */
/* Copyright (c) 1993-2002 Texas Instruments Incorporated                    */
/*****************************************************************************/
<...>
#if defined(_INLINE) || defined(_STRCAT)
_OPT_IDEFN char *strcat(char *string1, const char *string2)
{
   char       *s1 = string1 - 1;
   const char *s2 = string2 - 1;
 
   while (*++s1);		     /* FIND END OF STRING   */
   s1--;  			     /* BACK UP OVER NULL    */
   while (*++s1 = *++s2);	     /* APPEND SECOND STRING */
   return string1;
}
#endif /* _INLINE || _STRCAT */

Les normes et les standards c'est tellement compliqué, même pour ceux qui les définissent, que je ne fais pas toujours attention à ce que je dis.

Je corrige:

Voici comment strcat est implémentée avec mon compilateur:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char * __cdecl strcat ( 
        char * dst, 
        const char * src 
        ) 
{ 
        char * cp = dst; 
 
        while( *cp ) 
                cp++;                   /* find end of dst */ 
 
        while( *cp++ = *src++ ) ;       /* Copy src to end of dst */ 
 
        return( dst );                  /* return dst */ 
 
}

:ccool: