Pourquoi les opérations std :: string fonctionnent-elles mal?

Question

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()

ce 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());
    }
}

ce 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);
}();

ce 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();
}

ce 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

Étonnamment! 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.

Answer 1

Ce n'est pas qu' std::string fonctionne mal (d'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 la chaîne Python objets sont complètement implémenté en C, et en effet sur Python 2.7, de nombreuses optimisations existent 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û à la bonne 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.

Quant à 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 la vitesse.

J'ai fourni une version en C pour montrer comment stupide tels pisser concours peuvent être:

#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>

void test()
{
    int limit = 102 * 1024;
    char s[limit];
    size_t size = 0;
    while (size < limit) {
        s[size++] = 'X';
        if (memmem(s, size, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) {
            fprintf(stderr, "zomg\n");
            return;
        }
    }
    printf("x's length = %zu\n", size);
}

int main()
{
    test();
    return 0;
}

Calendrier:

matt@stanley:~/Desktop$ time ./smash 
x's length = 104448

real    0m0.681s
user    0m0.680s
sys     0m0.000s

Answer 2

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 à l' std::string::find(). Notez que j'ai dû réduire le nombre d'itérations à ~40%, sinon ideone.org tuer le processus.

#include <iostream>
#include <string>

int main()
{
    const std::string::size_type limit = 42 * 1024;
    unsigned int found = 0;

    //std::string s;
    std::string s(limit, 'X');
    for (std::string::size_type i = 0; i < limit; ++i) {
        //s += 'X';
        if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos)
            ++found;
    }

    if(found > 0)
        std::cout << "Found " << found << " times!\n";
    std::cout << "x's length = " << s.size() << '\n';

    return 0;
}

Mes résultats au 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. Notez que, cette fois, j'avais augmenté le nombre d'itérations de dix fois en essayant de voir à tout moment.

#include <iostream>
#include <string>

int main()
{
    const std::string::size_type limit = 1020 * 1024;
    unsigned int found = 0;

    std::string s;
    //std::string s(limit, 'X');
    for (std::string::size_type i = 0; i < limit; ++i) {
        s += 'X';
        //if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos)
        //    ++found;
    }

    if(found > 0)
        std::cout << "Found " << found << " times!\n";
    std::cout << "x's length = " << s.size() << '\n';

    return 0;
}

Mes résultats au ideone.orgmalgré 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. Était-ce vraiment votre intention?

Answer 3

La solution idiomatique C ++ serait:

 #include <iostream>
#include <string>
#include <algorithm>

int main()
{
    const int limit = 102 * 1024;
    std::string s;
    s.reserve(limit);

    const std::string pattern("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

    for (int i = 0; i < limit; ++i) {
        s += 'X';
        if (std::search(s.begin(), s.end(), pattern.begin(), pattern.end()) != s.end())
            std::cout << "Omg Wtf found!";
    }
    std::cout << "X's length = " << s.size();
    return 0;
}
 

Je pourrais accélérer considérablement en mettant la chaîne sur la pile et en utilisant memmem - mais cela ne semble pas être nécessaire. En cours d’exécution sur ma machine, c’est déjà plus de 10 fois la vitesse de la solution python.

[Sur mon ordinateur portable]

durée ./test X longueur = 104448 real 0m2.055s utilisateur 0m2.049s sys 0m0.001s

Answer 4

C’est le plus évident: essayez de faire s.reserve(limit); avant la boucle principale.

La documentation est ici .

Je devrais mentionner que l'utilisation directe de classes standard en C ++ de la même façon que vous le faites en Java ou que Python vous donnera souvent des performances sous-égales si vous n'êtes pas au courant de ce qui se fait derrière le bureau. Il n'y a pas de performance magique dans le langage lui-même, cela vous donne juste les bons outils.

Answer 5

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 longueur 1 de 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'est - N * (N+1) / 2 = 5 454 744 576 des 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 l' find que les recherches d'un seul A:

Original: 6.94938e+06 ms
Char    : 2.10709e+06 ms

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 c' find a pu ê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.