Performances C vs C ++ (pour la gestion des chaînes courtes)

Dans certains cas au moins, la version C ++ sera nettement plus rapide.

Certaines implémentations de std::ssortingng incluent notamment ce que l’on appelle généralement “l’optimisation de chaîne courte” (ou “SSO”). Avec cela, l’object std::ssortingng lui-même inclut un espace pour une chaîne allant jusqu’à une limite spécifique (généralement environ 20 caractères). Les chaînes qui entrent dans cette mémoire tampon peuvent (et vont) éviter d’allouer de l’espace sur le tas / magasin libre pour stocker leurs données.

En théorie, vous pourriez faire à peu près la même chose C – mais quand / si vous le faites, vous devez définir votre propre structure pour contenir votre chaîne (un peu comme le fait le C ++) et chaque morceau de code manipulant ces structures de chaîne doit savoir comment ils fonctionnent et les manipulent de la même manière. C ++ facilite l’intégration de ce code dans une surcharge d’opérateur afin de masquer les détails.

L’essentiel est que C puisse théoriquement suivre le rythme, mais il faudrait assez de travail pour y arriver. Dans la pratique, les programmes qui doivent effectuer ce type de manipulation en C ++ sont presque toujours plus rapides que leurs homologues écrits en C. cela varie en fonction de la vitesse à laquelle ils fonctionnent – parfois ils le sont un peu plus vite, mais surtout lorsqu’il y a beaucoup de manipulations de chaînes relativement petites, des différences substantielles (par exemple, 2: 1 ou plus) sont assez courantes. Les différences peuvent également être assez grandes lorsque vous devez manipuler des chaînes très volumineuses, où C ++ gagne beaucoup en étant capable de trouver la taille en temps constant, où strlen nécessite du temps linéaire. Cela ne veut pas dire grand chose pour les chaînes assez petites pour tenir entièrement dans le cache L1, mais si vous pouvez lire une valeur de L1 plutôt que de lire une chaîne entière dans la mémoire principale, la différence peut être énorme .

Oui, la version C ++ est plus rapide car elle n’alloue rien POUR LES PETITES CHAÎNES!

Il a dit:

Oui, la version C ++, car elle ne doit pas compter les caractères d’argument et n’utilise pas le magasin libre (mémoire dynamic) pour les chaînes d’arguments courtes.

Pour les petites chaînes, vous pouvez tirer parti de la stack automatiquement! La plupart des compilateurs le font aujourd’hui! Pour de plus grandes chaînes, vous aurez “presque” le même résultat.

Mais, en fait, il “promeut” toujours C ++ … une fois que vous pouvez considérer que la version C utilise également la stack via des tableaux d’octets.

Même si la version C ++ peut être plus rapide pour les chaînes courtes et très longues, la version C est plus rapide pour les chaînes de longueur moyenne nécessitant une allocation de mémoire dynamic en C ++:

1. Dans la version C, il n’y a qu’une allocation pour la chaîne résultante. La version C ++ doit allouer deux mémoires tampons: une pour le résultat de name + @ et une autre pour le résultat de name + @ + domain . Cela seul confère au C ++ un handicap de plus de 250 cycles de processeur (du moins sur mon système).

2. S’il est exact que C ++ n’a pas besoin d’parsingr la chaîne d’entrée deux fois, il copie néanmoins le name la chaîne deux fois: une fois dans le calcul de name + @ et une fois dans le calcul de name + @ + domain . Cela nécessiterait un traitement spécial des concaténations de chaînes dans le compilateur (et non dans l’implémentation standard de la bibliothèque) pour éviter cet écueil.

3. La version C utilise moins de mémoire. Cela permet au processeur de mieux utiliser ses caches.

Pour que la version C ++ soit plus rapide que la version C, vous avez besoin de chaînes de domain au moins une centaine de caractères, ou de chaînes très courtes et d’une implémentation de std::ssortingng qui implémente l’optimisation de chaînes courtes. .

Et si vous avez plus que deux concaténations dans votre fonction, C ++ sera probablement plus lent, même sur de très longues chaînes, car les premières chaînes seront copiées plusieurs fois.

En gros, vous pouvez dire que dans C l’ordre de concaténation est O(N) où N est la longueur de la chaîne résultante, un chiffre indépendant de la quantité de chaînes en entrée. En C ++, en revanche, l’ordre de concaténation est O(n*m^2) où n est la longueur d’une chaîne unique et m le nombre de concaténations.

De manière générale, si vous me monsortingez une série de programmes C raisonnablement bien écrits et de plusieurs programmes C ++ assez bien écrits et me demandiez lequel d’entre eux fonctionnait le mieux, je parierais sur les programmes C.

Et cela vient d’un passionné de C ++. Mais il existe de nombreuses tendances dans les programmes C ++ selon lesquelles les utilisateurs utilisent beaucoup plus de mémoire et / ou encourent beaucoup plus d’allocations de tas que nécessaire lorsqu’on travaille avec des chaînes, ce qui a tendance à l’emporter sur les dépassements séquentiels qui facilitent le cache votre programme C pourrait utiliser des appels supplémentaires à strlen alors qu’il aurait pu conserver la taille de la chaîne.

Comme exemple de base, un développeur C ++ souhaitant stocker un grand nombre de chaînes pour un access aléatoire peut procéder comme suit:

 std::vector boatload_of_ssortingngs; 

… et cela implique soit beaucoup plus d’allocations de tas que nécessaire, soit un chargement de bateau plus de mémoire que nécessaire. Avec la plupart des compilateurs modernes implémentant des optimisations de petites chaînes, même stocker une entrée pour “a” ou “I” pourrait finir par stocker 24 octets uniquement pour cette chaîne d’un caractère lorsque vous n’avez besoin que de 2 octets. En attendant, le programmeur C qui manque de telles commodités pourrait stocker ceci:

 // One contiguous buffer for all ssortingngs, realloced when // capacity is exceeded. char* boatload_of_ssortingngs; // Starting position of each ssortingng. int* ssortingng_start; 

… avec la nième chaîne terminée par un caractère NULL, accessible de la manière suivante:

 const char* nth_ssortingng = boatload_of_ssortingngs + ssortingng_start[n]; 

Et cela est tellement plus efficace: plus convivial en cache, moins de mémoire utilisée, etc. Bien sûr, l’écriture prend plus de temps et est plus sujette aux erreurs, et si la question concerne la productivité en travaillant avec des chaînes plutôt que l’efficacité de calcul / mémoire, Je changerais rapidement mon vote en C ++. Bien sûr, un développeur C ++ pourrait également faire:

 // One contiguous buffer for all ssortingngs. vector boatload_of_ssortingngs; // Starting position of each ssortingng. vector ssortingng_start; 

… et c’est un moyen très efficace de représenter une charge complète de chaînes qui doivent être accessibles de manière aléatoire. Mais ce sujet concerne les tendances , et je pense que la plupart des développeurs C ++ sont plus susceptibles d’utiliser std::ssortingng ici qu’un vector char . Nous ne pouvons parler que de tendances, car un programmeur C peut également stocker une longueur de chaîne dans une struct . Le programmeur CA pourrait également faire quelque chose de très inefficace et stocker le caractère char** boatload_of_ssortingngs et allouer chaque chaîne teeny séparément. Nous ne parlons que de ce que les gens ont tendance à faire et, compte tenu de ce que j’ai vu, les gens ont tendance à le faire dans ces deux langues, je parie que les programmes C ont généralement un avantage en termes d’efficacité avec des chaînes.

Il est bon de noter que le manque de chaînes C qui gardent la longueur risque d’entraîner plus de passages linéaires que nécessaire, mais il s’agit là encore de passages linéaires respectant le cache qui passent dans un tampon contigu. Ce serait un peu comme de faire valoir qu’une liste chaînée qui alloue chaque nœud séparément à un allocateur à usage général est plus efficace pour les push_backs que std::vector car elle n’a pas besoin de réaffecter et de copier un tampon en temps linéaire. L’efficacité de la mémoire dépasse certaines passes linéaires supplémentaires ici et là, et std::ssortingng ne sera jamais parfaitement optimal du sharepoint vue de l’efficacité de la mémoire, en particulier lorsqu’il est utilisé pour stocker des données persistantes. Il utilise soit trop de mémoire pour de très petites chaînes avec l’optimisation de petites chaînes, soit trop d’allocations de tas pour les chaînes de taille moyenne, car l’optimisation de petites chaînes favorisait un tampon très petit.

Il peut y avoir de véritables cas où le C ++ possède un avantage dans les cas d’utilisation pratique, mais la plupart du temps, j’ai des améliorations majeures en performances, remplaçant le code C ++ à l’aide de std::ssortingng avec de simples tampons de caractères normaux, et non l’inverse. également trouvé. Il serait rare pour moi de rencontrer un cas réel, mesuré et profilé en conséquence avant et après, où le remplacement de code C écrit de manière compétente à l’aide de tampons de caractères entraîne une amélioration des performances après l’utilisation, par exemple, de std::ssortingng ou de std::wssortingng .

Strlen

Il est également important de garder à l’esprit que strlen est souvent mis en œuvre de manière très efficace. Par exemple, MSVC le traite comme un compilateur insortingnsèque avec des fonctions comme memset . Ils ne les traitent pas comme des appels de fonction normaux et génèrent des instructions très efficaces, bien plus efficaces que si vous venez de rouler à la main une boucle de base comptant le nombre de caractères dans une chaîne avant d’atteindre un terminateur nul.

Ainsi, non seulement il s’agit d’une boucle séquentielle conviviale pour le cache via un tampon contigu, mais également d’une boucle optimisée à mort. Je n’ai jamais, jamais vu l’utilisation de strlen apparaître comme un point chaud dans une session de profilage sur une base de code. J’ai certainement vu ma part de points chauds liés à std::ssortingng et à QSsortingng dans VTune.

[…] n’utilise pas la mémoire libre (mémoire dynamic) pour les chaînes d’arguments courtes.

Je ne sais pas quel type de programmes C Bjarne examinait, mais la plupart des programmes C que je vois n’utilisent généralement pas d’allocations de tas pour les petites chaînes. Ils utilisent souvent des tampons sur la stack comme ceci:

 char buf[256]; 

… qui n’est pas très robuste mais ne va certainement pas invoquer des allocations de tas, ni utiliser des VLA avec C99 comme ceci:

 char buf[n]; 

… ce qui risque de provoquer des débordements de stack mais, encore une fois, ne pas appeler des allocations de tas inutiles, ou quelque chose comme ceci:

 char buf[256]; char* data = (n < 256) ? buf: malloc(n+1); ... if (data != buf) free(data); 

... qui est le plus robuste et évite encore l’allocation de tas dans les cas courants. En plus de cela, les gens affirmaient que std::ssortingng était plus rapide que votre code C moyen depuis bien longtemps, bien avant les optimisations de petites chaînes et même à l'époque où la plupart std::ssortingng implémentations de std::ssortingng utilisaient la copie sur écriture. Et les résultats du monde réel ne sont jamais tout à fait à la hauteur de ces affirmations dans cette affaire.

Exemple de composition

Ok, alors ouf, voici l'exemple de compose :

 char* compose(const char* name, const char* domain) { char* res = malloc(strlen(name)+strlen(domain)+2); // space for ssortingngs, '@', and 0 char* p = strcpy(res,name); p += strlen(name); *p = '@'; strcpy(p+1,domain); return res; } 

Tout d'abord, je ne rencontre pas souvent des personnes écrivant du code C comme celui-ci avec une fonction qui alloue une chaîne et lui renvoie un pointeur pour que le client libère du code de production. Beaucoup plus souvent, je vois des gens faire des choses comme:

 char buf[512]; sprintf(buf, "%s@%s", name, domain); 

... qui, encore une fois, n'est pas le code le plus sûr, mais certainement pas celui qui entraîne plus d'allocations de tas que l'autre et il n'a pas besoin d'effectuer de passe supplémentaire pour déterminer la longueur de ces chaînes car le tampon est déjà pré-enregistré. taille. Mais si nous disséquons la version C ++:

 ssortingng compose(const ssortingng& name, const ssortingng& domain) { return name+'@'+domain; } 

ssortingng::operator+ peut potentiellement s'en tirer avec un passage moins linéaire entre ces deux chaînes, car elles stockent une taille, mais si ces chaînes sont minuscules, la surcharge est si sortingviale. C'est économiser des sous, mais en échange d'un coût. Si ces chaînes ne sont pas minuscules, l'optimisation des petites chaînes ne résout pas le problème, elle fait vraiment mal et génère plus de perte de mémoire, et vous obtiendrez tout de même une allocation de tas. La solution ci-dessus est bien plus robuste que la solution sprintf utilisant un tampon de taille fixe, mais je ne parle ici que d’efficacité par rapport aux tendances courantes.

De manière très générale, effectuer une passe linéaire supplémentaire dans les données contiguës pour déterminer la taille est souvent meilleur marché que les alternatives qui pourraient potentiellement nécessiter des allocations de tas plus importantes / plus grandes. Par exemple, si vous faites cela:

 int count = 0; // count how many elements there are: for (...) { ... ++count; } // Now size the vector accordingly: vector values(count); // Do a second pass through the same data. for (...) ... 

... cela tend souvent à être plus efficace que:

 vector values; // Do a single pass through the data with push_backs. for (...) ... 

Et un principe similaire s'applique aux chaînes. Plus de passages linéaires à travers une chaîne ne sont pas nécessairement plus coûteux si cela entraîne une utilisation moindre de la mémoire, moins d'allocations de tas, etc.