Pourquoi ne std::string effectuer des opérations de mal?
J'ai fait un test pour comparer les opérations de la chaîne en plusieurs langues pour le choix d'une langue pour l'application côté serveur. Les résultats semblait normal jusqu'à ce que j'ai finalement essayé C++, ce qui m'a surpris beaucoup. Donc je me demande si je n'avais pas compris tout de l'optimisation et de venir ici pour vous aider.
Le test sont principalement intensive opérations de la chaîne, y compris les concaténer et de la recherche. Le test est effectué sur Ubuntu 11.10 amd64, avec GCC version 4.6.1. La machine est Dell Optiplex 960, avec la 4G de RAM et PROCESSEUR Quad-core.
en Python (2.7.2):
def test():
x = ""
limit = 102 * 1024
while len(x) < limit:
x += "X"
if x.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0:
print("Oh my god, this is impossible!")
print("x's length is : %d" % len(x))
test()
qui donne le résultat:
x's length is : 104448
real 0m8.799s
user 0m8.769s
sys 0m0.008s
en Java (OpenJDK-7):
public class test {
public static void main(String[] args) {
int x = 0;
int limit = 102 * 1024;
String s="";
for (; s.length() < limit;) {
s += "X";
if (s.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ") > 0)
System.out.printf("Find!\n");
}
System.out.printf("x's length = %d\n", s.length());
}
}
qui donne le résultat:
x's length = 104448
real 0m50.436s
user 0m50.431s
sys 0m0.488s
en Javascript (Nodejs 0.6.3)
function test()
{
var x = "";
var limit = 102 * 1024;
while (x.length < limit) {
x += "X";
if (x.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0)
console.log("OK");
}
console.log("x's length = " + x.length);
}();
qui donne le résultat:
x's length = 104448
real 0m3.115s
user 0m3.084s
sys 0m0.048s
en C++ g++ -Ofast)
Il n'est pas surprenant que Nodejs effectue mieux que Python ou Java. Mais je m'attendais à libstdc++ donnerait une bien meilleure performance que Nodejs, dont le résultat vraiment surpris moi.
#include <iostream>
#include <string>
using namespace std;
void test()
{
int x = 0;
int limit = 102 * 1024;
string s("");
for (; s.size() < limit;) {
s += "X";
if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != string::npos)
cout << "Find!" << endl;
}
cout << "x's length = " << s.size() << endl;
}
int main()
{
test();
}
qui donne le résultat:
x length = 104448
real 0m5.905s
user 0m5.900s
sys 0m0.000s
Bref Résumé
OK, maintenant nous allons voir le résumé:
- javascript sur Nodejs(V8): 3.1 s
- Python sur Disponible 2.7.2 : 8,8 s
- C++ avec la bibliothèque libstdc++: 5.9 s
- Java OpenJDK 7: 50.4 s
Surprise! J'ai essayé "-O2-O3" en C++, mais en notant aidé. C++ semble qu'environ 50% des performances de javascript V8, et même les pauvres que Disponible. Quelqu'un pourrait-il m'expliquer si j'avais manqué quelques-uns d'optimisation de GCC ou est-ce le cas? Je vous remercie beaucoup.
- Vous êtes le test d'un mélange des opérations, vous devriez probablement essayer de diviser le test dans les différents tests que d'effectuer différents contrôles de performance, par exemple: la croissance des chaînes, ou trouver, ou ... actuellement, vous ne pouvez pas savoir où le temps est passé. Et BTW, c'est probablement l'un tout à fait inutile de test de décider sur une langue...
- Essayez
s.reserve(limit);
avant la boucle. - peut-être parce que chaînes de caractères en Java sont immuables. Je suppose que
s += "X"
est une performance killer là. C'est la raison pourStringBuilder
existe. - Ouais, c'est vraiment de 50 ans, et j'ai essayé plusieurs fois. - Je censé Java devrait faire mieux que Python au moins, si.
- Se débarrasser de la sortie de la console de votre test, il sera l'inclinaison de vos résultats
- En java, les chaînes sont immuables et mis en commun, donc très lente. Normalement, vous utilisez stringbuilders pour assembler des chaînes de caractères. Tout cela ici, c'est comparer des pommes et des oranges, de toute façon.
- Vous êtes aussi, y compris l'exécution de démarrage et de fin de chaque langue dans vos résultats.
- Je ne pense pas que la sortie de la console est censé se produire, sauf pour une seule ligne à la fin...
- Peut-être essayer un autre compilateur. J'ai compilé l'échantillon à l'aide de Visual Studio 2010. Runtime 1.79 Secondes sur un XEON 2.8 GHz.
- Il serait vide de sens si je test chaque type d'opération séparément, il n'y aura pas de gagnants sur l'ensemble des opérations. Ce test est d'émuler un démon serveur qui écoute sur une socket ou l'attend sur le terminal pour les flux de caractères, et l'analyse en temps réel. Mais pour des raisons de simplicité, le programme de test omet beaucoup de pas-si-opérations pertinentes.
- Avez-vous l'intention sur le chargement d'un caractère à la fois? Si oui, alors ce test est représentatif de votre utilisation, et la meilleure chose que vous pouvez le faire de ne pas décider d'une langue, mais à la recherche d'une meilleure approche. Divisant le test avec plus d'informations, car il vous permettra de savoir pour chaque langue, ce que sont les opérations les plus coûteuses et donc vous permettent d'optimiser votre traitement, et encore, le test va être absurde. Juste en C++, en changeant de
s+="X"
às.push_back('X')
aura probablement un impact plus important que les différences avec d'autres langues... - Euh, comment avez-C++ effectuer plus de mal que de Disponible? (Vous montrer 5.5 s avec C++, 8.8 secondes avec Disponible)
- Pas aussi important pour le C++ partie de la Question, mais Matt Joiner est correcte dans son évaluation de la solution Java. Utiliser un StringBuffer pour concaténer au lieu d'une Chaîne de caractères. Cordes de Java ne sont pas mutables, et il va créer une nouvelle Chaîne chaque fois que vous += pour elle. À partir de docs.oracle.com/javase/1.5.0/docs/api/java/lang/..., "Une mémoire tampon de chaîne, c'est comme un String, mais peut être modifié. "
- Je confirme qu'un autre compilateur peut vous aider. Sur ma machine de la compilation avec (visual studio 2010) cl /EHsc -O2 donne 1.753 s (près de vos résultats) tout en python 2.7.1 prend 6.266 s (plus ou moins en ligne avec les OP résultats)
- Vous devriez demander à quelqu'un qui connaît la langue pour mettre en œuvre votre cas de test. Simplement à l'aide de StringBuilder en Java coupe le temps d'exécution de 75 secondes à 4 sur ma machine.
- J'ai essayé de s.push_back ("X"), mais seulement une amélioration de l'ordre de 0,1 s. Comme d'autres " et mon option, le col de la bouteille est principalement la procédure de recherche. Et j'ai aussi testé string::trouver est plus rapide que strstr ou memmem si "-O" handicapé", mais beaucoup plus lentement si "-O2" est activé. Donc, string::trouverez peut-être difficile à optimiser.
- Eh bien, ce n'est pas juste de comparer directement Disponible et C++ à l'aide de 'temps' de la commande, pour Disponible passe plus de temps qu'en C++ pour démarrer le moteur, qui est, de chargement et de compilation en byte-code. J'ai donc supposé Disponible plus rapidement si il C++ n'a pas dépasse de beaucoup plus, ce qui bien sûr, n'est pas très précise.
- Ouais vous avez raison. J'ai testé avec StringBuilder et Java a donné le score de 2,8 s, la meilleure performance au sein de tous les tests, ce qui bien sûr encore plus lent que strstr en pur C (environ 1,6 s). Alors que bizarrement Java avec StringBuilder encore effectuée environ 30% plus lent que Nodejs sur mon Thinkpad R400 ordinateur portable.
- Vous pouvez faire le même argument à l'encontre de Java ou d'un Nœud. (Essayez d'écrire un minimum de bonjour tout le monde python application et de soustraire le temps que prend à partir de l'indice de référence a pris, ce qu'il faudrait se débarrasser de retard de démarrage)
- Notez que Lua chaînes sont aussi immuables et mis en commun (internés), et j'ai trouvé que Lua version de ce test s'exécute plus de deux fois plus rapide que la prochaine plus rapide de l'interprète (nodejs/v8). [à propos de 1,5 s pour Lua contre environ 3,1 s pour nodejs]
- Vous pourriez aussi essayer de profil guidée optimisations -- en C et C++ ceci peut être important pour les boucles comme ceci (nœud.js/V8 sont certainement compilé avec de telles choses sur)
- Il semble que GNU libstdc++ inline codé d'une boucle for std::string trouver. Muet déplacer. memmem et strstr sont beaucoup plus optimisé à la main, les versions écrites à l'assemblée de prendre avantage de SSE2 et SSE4 extensions.
Vous devez vous connecter pour publier un commentaire.
Ce n'est pas que
std::string
fonctionne mal (autant que je n'aime pas le C++), c'est que la manipulation des chaînes est donc fortement optimisée pour les autres langues.Vos comparaisons de la chaîne de performance sont trompeuses, et présomptueux si elles sont censées représenter plus que cela.
Je sais pour un fait que Chaîne Python objets sont complètement implémenté en C, et en effet sur Python 2.7, de nombreux optimisations exister en raison de l'absence de séparation entre les chaînes unicode et d'octets. Si vous avez effectué ce test sur Python 3.x vous trouverez qu'il est beaucoup plus lent.
Javascript a de nombreuses largement optimisé implémentations. Il est à prévoir que la manipulation des chaînes est excellent ici.
Votre Java résultat peut être dû à une mauvaise manipulation des chaînes, ou de quelque autre mauvaise. J'attends qu'un expert Java pourrait intervenir et de corriger ce test avec quelques modifications.
Comme pour votre exemple C++, je m'attends performance légèrement supérieure à la version de Python. Il effectue les mêmes opérations, avec moins d'interprète les frais généraux. Cela se reflète dans vos résultats. Précédant le test avec
s.reserve(limit);
permettrait de supprimer la réallocation de la surcharge.Je vais répéter ce que vous êtes seulement un test sur un seul aspect de l'langues " implémentations. Les résultats de ce test ne reflète pas l'ensemble de la langue de vitesse.
J'ai fourni une version en C pour montrer comment stupide tels pisser concours peut être:
Calendrier:
std::string::find
.J'ai donc joué un peu avec ce sur ideone.org.
Ici une version légèrement modifiée de l'original de votre programme C++, mais avec l'ajout de la boucle est éliminé, alors il ne mesure que l'appel à
std::string::find()
. Noter que j'ai dû réduire le nombre d'itérations à ~40%, sinon ideone.org tuer le processus.Mes résultats à ideone.org sont
time: 3.37s
. (Bien sûr, c'est très douteuse, mais offrez-moi un instant et attendre que l'autre résultat.)Maintenant, nous prenons ce code et de permuter les lignes commentées, afin de tester l'ajout, plutôt que de trouver. Noter que, cette fois, j'avais augmenté le nombre d'itérations de dix fois en essayant de voir à tout moment suite à tous.
Mes résultats à ideone.org, en dépit de l'augmentation de dix fois dans itérations, sont
time: 0s
.Ma conclusion: Ce cas-test est, en C++, fortement dominée par la recherche de l'opération, l'ajout du personnage dans la boucle n'a pas d'influence sur le résultat à toutes. Était-ce vraiment votre intention?
find
est O(N), tandis que dansPython
indexOf
utilise Boyer-Moore (comme indiqué par Duncan dans un commentaire). Une fois de plus, "piles".memmem
.La idiomatiques C++ solution serait:
Je pouvais accélérer considérablement en plaçant la chaîne sur la pile, et à l'aide de memmem -- mais il semble y avoir aucun besoin. En cours d'exécution sur ma machine, c'est plus de 10 fois la vitesse de la python solution déjà..
[Sur mon ordinateur portable]
temps ./test
X longueur = 104448
réel 0m2.055s
l'utilisateur 0m2.049s
sys 0m0.001s
std::string s(limit,'X');
I. e. rechercher et trouver avait plus de travail à faire.) CONCLUSION: stdlib find() sur g++ a beaucoup de potentiel pour l'optimisation!std::string
est mais un typedef pourstd::basic_string<char>
, qui est un modèle, et en tant que tel pleinement mis en œuvre dans les en-têtes.Qui est le plus évident: s'il vous plaît essayer de faire
s.reserve(limit);
avant la boucle principale.Documentation est ici.
Je dois mentionner que l'utilisation directe de la norme classes en C++ de la même manière que vous avez utilisé pour le faire en Java ou Python sera souvent vous donner de la sous-performance des si vous êtes pas au courant de ce qui se fait derrière le bureau. Il n'y a pas de formule magique de la performance dans la langue elle-même, il vous donne simplement des bons outils.
s.reserve(limit)
avant que la boucle ne fait aucune différence perceptible à la performance.string::reserve
. Pouvez-vous montrer comment faire la concaténation dans un moyen rapide, l'exploitation de la connaissance de la façon dont les classes à travailler en arrière-plan?string::operator++
est seulement en ajoutant un caractère unique, de sorte réallocation de mémoire et la copie ne devrait pas être un gros drain.i = 0
variable si vous allouer de la chaîne d'abord, et puis vous remarquerez que la recherche est la vraie question.Ce qui vous manque ici est la complexité inhérente de la recherche.
Vous êtes l'exécution de la recherche
102 * 1024
(104 448) fois. Une naïve de l'algorithme de recherche sera, à chaque fois, essayer de faire correspondre le motif de départ à partir du premier caractère, puis le second, etc...Donc, vous avez une chaîne qui va de la longueur
1
àN
, et ce, à chaque étape de votre recherche du modèle sur cette chaîne, qui est une opération linéaire en C++. C'estN * (N+1) /2 = 5 454 744 576
comparaisons. Je ne suis pas surpris que vous êtes que ce serait prendre un certain temps...Laissez-nous vérifier l'hypothèse par l'aide de la surcharge de
find
que les recherches d'un seulA
:Environ 3 fois plus vite, nous sommes donc dans le même ordre de grandeur. Par conséquent, l'utilisation d'une chaîne complète n'est pas vraiment intéressant.
Conclusion ? Peut-être que
find
pourrait être optimisé un peu. Mais le problème n'est pas la peine.Note: et pour ceux qui tout Boyer Moore, j'ai peur que l'aiguille est trop petit, donc il ne l'aide pas beaucoup. Peut couper un ordre de grandeur (26 caractères), mais pas plus.
A
dans le foin de la pile, donc il faut juste vérifier chaque caractère de la chaîne qu'il n'est pas trouvé et ne pas regarder les autres personnages de la répétition. Vous semblez décrirefind_any_of
méthode, qui devrait à nouveau trouver la'X'
très rapide ici.find
, qui, même pour un modèle de chaîne doit s'arrêter sur le premier caractère du modèle si elle ne correspond pas et de passer dans la botte de foin. Le fait que la recherche d'un caractère uniqueA
(le premier caractère du modèle) est à seulement 3 fois plus vite confirme mon doute bien que ce n'est pas la recherche du modèle qui est lent, mais simplement que la recherche d'un motif dans une longue chaîne de si nombreuses fois est clair lent en lui-même.Ma première pensée est qu'il n'y a pas un problème.
C++ donne la deuxième meilleure performance, près de dix fois plus rapide que Java. Peut-être tous, mais le Java sont en cours d'exécution proche de la meilleure performance possible pour que la fonctionnalité, et vous devriez être à la recherche à la façon de fixer le Java problème (indice -
StringBuilder
).Dans le C++ cas, il y a quelques choses à essayer d'améliorer les performances un peu. En particulier,...
s += 'X';
plutôt ques += "X";
string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
en dehors de la boucle, et de les remettre pour lefind
appels. Unstd::string
instance connaît sa propre longueur, tandis qu'une chaîne C nécessite un linéaire de la vérification en temps afin de déterminer que, et cela peut (ou ne peut pas) être pertinents pourstd::string::find
performance.std::stringstream
, pour les mêmes raisons pour lesquelles vous devriez utiliserStringBuilder
pour Java, même si les plus susceptibles à la répétition des conversions retour àstring
va créer plus de problèmes.Dans l'ensemble, le résultat n'est pas trop surprenant. JavaScript, avec un bon compilateur JIT, peut-être en mesure d'optimiser un peu mieux que le C++ de la compilation statique est autorisé dans ce cas.
Avec un peu de travail, vous devriez toujours être en mesure d'optimiser le C++ mieux que JavaScript, mais il y aura toujours des cas où ce n'est pas seulement naturellement se produire et où il peut prendre un peu juste de la connaissance et de l'effort pour y parvenir.
find
appel, non pas la répartition. Par exemple, les tests de la 2ème point, il n'y a pas de différence (à tous).find
appel. Le point est d'utiliser un autre surcharge defind
qui prend le motif de recherche comme unstd::string
plutôt que comme une chaîne C, et donc (peut-être, mais certainement pas) éviterstrlen
appels au sein de l'find
appel. Une autre idée est que, depuis le modèle de recherche est constante, la compilation d'un modèle d'approche peut fonctionner plus rapidement (Boyer-Moore chaîne de recherche, par exemple), mais c'est de la triche - sauf par exemple JavaScript optimiseurs sont beaucoup plus intelligents que je m'attends.std::string
est déjà mutable et pouvez l'insérer dans constant amorti temps.Pour le C++, essayez d'utiliser
std::string
pour "ABCDEFGHIJKLMNOPQRSTUVWXYZ" - dans ma mise en œuvrestring::find(const charT* s, size_type pos = 0) const
calcule la longueur de la chaîne argument.Langage C/C++ ne sont pas faciles et prendre des années de prendre rapidement des programmes.
avec strncmp(3) de la version modifiée de la version c:
Je viens de tester le C++ exemple moi-même. Si je supprime l'appel à
std::sting::find
, le programme se termine en un rien de temps. Ainsi, les allocations lors de la concaténation de chaîne n'est pas un problème ici.Si j'ajoute une variable
sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
et remplacer l'occurence de "ABC...XYZ" dans l'appel destd::string::find
, le programme doit presque dans le même temps de finir comme le modèle original. Ce qui montre encore une fois que l'allocation ainsi que le calcul de la longueur de la chaîne n'ajoute pas beaucoup à l'exécution.Par conséquent, il semble que la chaîne de l'algorithme de recherche utilisé par libstdc++ n'est pas aussi rapide pour votre exemple que les algorithmes de recherche de javascript ou python. Peut-être vous voulez essayer C++ à nouveau avec votre propre chaîne de l'algorithme de recherche qui s'adapte à votre objectif de mieux.
Votre code de test est de vérifier pathologique scénario excessif de la concaténation de chaîne. (La chaîne de recherche partie de l'épreuve aurait probablement été omis, je vous parie qu'il ne contribue en rien au résultat final.) Excessive de concaténation de chaîne est un écueil que la plupart des langues avertir très fortement contre, et très bien connue des solutions de rechange pour, (c'est à dire StringBuilder,) donc, ce que vous êtes essentiellement en test ici est de savoir comment mal ces langues échouer dans des scénarios de parfaitement échec prévisible. C'est inutile.
Un exemple de la même inutile de tester serait de comparer la performance de différentes langues lors de la lancer et attraper une exception dans une boucle serrée. Toutes les langues avertir que l'exception lancer et attraper est incroyablement lent. Ils ne précisent pas comment lent, ils ont juste vous avertir de ne pas s'attendre à quoi que ce soit. Donc, aller de l'avant et de test justement, serait inutile.
Donc, il serait beaucoup plus judicieux de répéter votre test de substitution de l'aveugle de concaténation de chaîne partie (s += "X") avec ce montage est offert par chacun de ces langues, c'est précisément pour éviter de concaténation de chaîne. (Comme la classe StringBuilder.)
find
opération va utiliser un linéaire en tempsstrlen
sur le modèle pour chaque appel, ou bien il va travailler sans connaissance avancée de la longueur et de faire plus de travail de recherche en conséquence.find
appel il prend en 0.019 s. Donc la concaténation de chaîne (au moins sur le langage Python) est la pertinence d'une partie du test. C'est probablement vrai, car la version C de Python utilise le comptage de référence et peut faire la concaténation en place quand il peut détecter qu'il n'y a qu'une seule référence à la chaîne.std::string::operator+=
est, le concept proposé par le C++ pour éviter la chose qui en Java causes de concaténation de Chaîne à être lent.std::string
est un mutant de classe, de même queStringBuilder
. TBH je pense que c'est un peu déroutant que la question est "pourquoi le C++ est lent?", mais comprend Java résultats qui sont waaay plus lent, en invitant des personnes différentes pour expliquer pourquoi les résultats Java sont lents. Qui n'est pas pertinent pour la question 😉'A' != 'X'
). Cette même soulève des questions sur juste la façon intelligente d'optimiseurs de peut-être trouver le bon langage et le compilateur et peut-être tous à la recherche sera optimisé loin (avérées inutiles) au moment de la compilation. Avec Haskell et de GHC, par exemple, vous pouvez constater que l'exécutable final juste sorties d'une constante "x longueur ..." chaîne de caractères.Comme mentionné par le sbi, le cas de test est dominé par l'opération de recherche.
J'étais curieux de voir comment rapide le texte de l'allocation compare entre C++ et Javascript.
Système: Raspberry Pi 2, g++ 4.6.3, nœud v0.12.0, g++ -std=c++0x -O2 perf.cpp
C++ : 770ms
C++ sans réserve: 1196ms
Javascript: 2310ms
C++
JavaScript
Il semble que dans nodejs il y a de meilleurs algorithmes pour la sous-chaîne de recherche. Vous pouvez la mettre en œuvre par vous-même et de l'essayer.