c++11 regex plus lent que python

Question

Bonjour, j'aimerais comprendre pourquoi le code suivant, qui effectue un fractionnement de chaîne de caractères à l'aide d'une expression rationnelle, ne fonctionne pas.

#include<regex>
#include<vector>
#include<string>

std::vector<std::string> split(const std::string &s){
    static const std::regex rsplit(" +");
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = std::sregex_token_iterator();
    auto res = std::vector<std::string>(rit, rend);
    return res;
}

int main(){
    for(auto i=0; i< 10000; ++i)
       split("a b c", " ");
    return 0;
}

est plus lent que le code python suivant

import re
for i in range(10000):
    re.split(' +', 'a b c')

voici

> python test.py  0.05s user 0.01s system 94% cpu 0.070 total
./test  0.26s user 0.00s system 99% cpu 0.296 total

J'utilise clang++ sur osx.

la compilation avec -O3 le ramène à 0.09s user 0.00s system 99% cpu 0.109 total

Answer 1

Avis

Voir aussi cette réponse : https://stackoverflow.com/a/21708215 qui a servi de base à la EDIT 2 en bas ici.

---

J'ai augmenté la boucle à 1000000 pour obtenir une meilleure mesure du temps.

C'est mon timing Python :

real    0m2.038s
user    0m2.009s
sys     0m0.024s

Voici un équivalent de votre code, juste un peu plus joli :

#include <regex>
#include <vector>
#include <string>

std::vector<std::string> split(const std::string &s, const std::regex &r)
{
    return {
        std::sregex_token_iterator(s.begin(), s.end(), r, -1),
        std::sregex_token_iterator()
    };
}

int main()
{
    const std::regex r(" +");
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r);
    return 0;
}

Timing :

real    0m5.786s
user    0m5.779s
sys     0m0.005s

---

Il s'agit d'une optimisation pour éviter la construction/allocation d'objets vectoriels et de chaînes de caractères :

#include <regex>
#include <vector>
#include <string>

void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), r, -1);
    auto rend = std::sregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.push_back(*rit);
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<std::string> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v);
    return 0;
}

Timing :

real    0m3.034s
user    0m3.029s
sys     0m0.004s

Cela représente une amélioration des performances de près de 100 %.

Le vecteur est créé avant la boucle, et peut augmenter sa mémoire lors de la première itération. Ensuite, il n'y a pas d'allocation de mémoire par clear() le vecteur maintient la mémoire et construit des chaînes de caractères. en place .

---

Une autre amélioration des performances consisterait à éviter la construction/destruction. std::string complètement, et donc l'allocation/désallocation de ses objets.

Il s'agit d'une tentative dans cette direction :

#include <regex>
#include <vector>
#include <string>

void split(const char *s, const std::regex &r, std::vector<std::string> &v)
{
    auto rit = std::cregex_token_iterator(s, s + std::strlen(s), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.push_back(*rit);
        ++rit;
    }
}

Timing :

real    0m2.509s
user    0m2.503s
sys     0m0.004s

Une amélioration ultime serait d'avoir un std::vector de const char * comme retour, où chaque pointeur de caractère pointerait vers une sous-chaîne à l'intérieur de l'original s c chaîne même. Le problème est que vous ne pouvez pas le faire parce que chacun d'entre eux ne serait pas terminé par un null (pour cela, voir l'utilisation de C++1y). string_ref dans un échantillon ultérieur).

---

Cette dernière amélioration pourrait également être obtenue grâce à cela :

#include <regex>
#include <vector>
#include <string>

void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
    auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.push_back(*rit);
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<std::string> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v); // the constant string("a b c") should be optimized
                             // by the compiler. I got the same performance as
                             // if it was an object outside the loop
    return 0;
}

---

J'ai construit les échantillons avec clang 3.3 (à partir du tronc) avec -O3. Peut-être que d'autres bibliothèques de regex sont plus performantes, mais dans tous les cas, les allocations/désallocations sont souvent un problème de performance.

---

Boost.Regex

C'est le boost::regex le timing pour le c chaîne échantillon d'arguments :

real    0m1.284s
user    0m1.278s
sys     0m0.005s

Même code, boost::regex y std::regex dans cet exemple sont identiques, il suffit de changer l'espace de noms et l'inclusion.

Je vous souhaite de vous améliorer avec le temps, les implémentations C++ stdlib regex n'en sont qu'à leurs débuts.

EDIT

Pour être complet, j'ai essayé ceci (la suggestion "d'amélioration ultime" mentionnée ci-dessus) et cela n'a pas amélioré les performances de l'équivalent std::vector<std::string> &v version en quoi que ce soit :

#include <regex>
#include <vector>
#include <string>

template<typename Iterator> class intrusive_substring
{
private:
    Iterator begin_, end_;

public:
    intrusive_substring(Iterator begin, Iterator end) : begin_(begin), end_(end) {}

    Iterator begin() {return begin_;}
    Iterator end() {return end_;}
};

using intrusive_char_substring = intrusive_substring<const char *>;

void split(const std::string &s, const std::regex &r, std::vector<intrusive_char_substring> &v)
{
    auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear(); // This can potentially be optimized away by the compiler because
               // the intrusive_char_substring destructor does nothing, so
               // resetting the internal size is the only thing to be done.
               // Formerly allocated memory is maintained.
    while(rit != rend)
    {
        v.emplace_back(rit->first, rit->second);
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<intrusive_char_substring> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v);

    return 0;
}

Cela a à voir avec le Proposition de array_ref et string_ref . Voici un exemple de code l'utilisant :

#include <regex>
#include <vector>
#include <string>
#include <string_ref>

void split(const std::string &s, const std::regex &r, std::vector<std::string_ref> &v)
{
    auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
    auto rend = std::cregex_token_iterator();
    v.clear();
    while(rit != rend)
    {
        v.emplace_back(rit->first, rit->length());
        ++rit;
    }
}

int main()
{
    const std::regex r(" +");
    std::vector<std::string_ref> v;
    for(auto i=0; i < 1000000; ++i)
       split("a b c", r, v);

    return 0;
}

Il sera également plus économique de retourner un vecteur de string_ref plutôt que string copies pour le cas de split avec retour vectoriel.

EDIT 2

Cette nouvelle solution est capable d'obtenir la sortie par retour. J'ai utilisé la méthode de Marshall Clow string_view ( string_ref (qui a été renommé) de libc++ qui se trouve à l'adresse https://github.com/mclow/string_view .

#include <string>
#include <string_view>
#include <boost/regex.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/transform_iterator.hpp>

using namespace std;
using namespace std::experimental;
using namespace boost;

string_view stringfier(const cregex_token_iterator::value_type &match) {
    return {match.first, static_cast<size_t>(match.length())};
}

using string_view_iterator =
    transform_iterator<decltype(&stringfier), cregex_token_iterator>;

iterator_range<string_view_iterator> split(string_view s, const regex &r) {
    return {
        string_view_iterator(
            cregex_token_iterator(s.begin(), s.end(), r, -1),
            stringfier
        ),
        string_view_iterator()
    };
}

int main() {
    const regex r(" +");
    for (size_t i = 0; i < 1000000; ++i) {
        split("a b c", r);
    }
}

Timing :

real    0m0.385s
user    0m0.385s
sys     0m0.000s

Notez à quel point ce résultat est plus rapide que les résultats précédents. Bien sûr, il ne s'agit pas de remplir un vector à l'intérieur de la boucle (et il est probable qu'il n'y ait pas non plus de correspondance à l'avance), mais vous obtenez tout de même une plage, sur laquelle vous pouvez étendre la plage avec la fonction for ou même l'utiliser pour remplir un vector .

Comme on peut le voir sur le iterator_range crée string_view sur un original string (ou un chaîne de caractères à terminaison nulle ), cela devient très léger, ne générant jamais d'allocations de chaînes inutiles.

Juste pour comparer en utilisant ceci split mais qui remplit en fait une vector nous pourrions le faire :

int main() {
    const regex r(" +");
    vector<string_view> v;
    v.reserve(10);
    for (size_t i = 0; i < 1000000; ++i) {
        copy(split("a b c", r), back_inserter(v));
        v.clear();
    }
}

Ceci utilise l'algorithme de copie de plage de boost pour remplir le vecteur à chaque itération, le timing est :

real    0m1.002s
user    0m0.997s
sys     0m0.004s

Comme on peut le voir, il n'y a pas de grande différence par rapport à la méthode optimisée. string_view sortie param version.

Notez également qu'il y a une proposition de std::split qui fonctionnerait comme ceci.

Answer 2

Pour les optimisations, en général, vous voulez éviter deux choses :

• brûler les cycles du CPU pour des choses inutiles
• attendre sans rien faire que quelque chose se passe (lecture de la mémoire, lecture du disque, lecture du réseau, ...)

Les deux peuvent être antithétiques, car il est parfois plus rapide de calculer quelque chose que de le mettre en cache en mémoire... c'est donc un jeu d'équilibre.

Analysons votre code :

std::vector<std::string> split(const std::string &s){
    static const std::regex rsplit(" +"); // only computed once

    // search for first occurrence of rsplit
    auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);

    auto rend = std::sregex_token_iterator();

    // simultaneously:
    // - parses "s" from the second to the past the last occurrence
    // - allocates one `std::string` for each match... at least! (there may be a copy)
    // - allocates space in the `std::vector`, possibly multiple times
    auto res = std::vector<std::string>(rit, rend);

    return res;
}

Peut-on faire mieux ? Eh bien, si nous pouvions réutiliser le stockage existant au lieu d'allouer et de désallouer constamment de la mémoire, nous devrions constater une amélioration significative [1] :

// Overwrites 'result' with the matches, returns the number of matches
// (note: 'result' is never shrunk, but may be grown as necessary)
size_t split(std::string const& s, std::vector<std::string>& result){
    static const std::regex rsplit(" +"); // only computed once

    auto rit = std::cregex_token_iterator(s.begin(), s.end(), rsplit, -1);
    auto rend = std::cregex_token_iterator();

    size_t pos = 0;

    // As long as possible, reuse the existing strings (in place)
    for (size_t max = result.size();
         rit != rend && pos != max;
         ++rit, ++pos)
    {
        result[pos].assign(rit->first, rit->second);
    }

    // When more matches than existing strings, extend capacity
    for (; rit != rend; ++rit, ++pos) {
        result.emplace_back(rit->first, rit->second);
    }

    return pos;
} // split

Dans le test que vous effectuez, où le nombre de sous-matchs est constant d'une itération à l'autre, cette version a peu de chances d'être battue : elle n'alloue de la mémoire que lors de la première exécution (tant pour les rsplit y result ) et continuer à réutiliser la mémoire existante.

[1] : Disclaimer, j'ai seulement prouvé que ce code est correct, je ne l'ai pas testé (comme dirait Donald Knuth).

Answer 3

Que pensez-vous de cette version ? Ce n'est pas une expression rationnelle, mais elle résout le problème assez rapidement ...

#include <vector>
#include <string>
#include <algorithm>

size_t split2(const std::string& s, std::vector<std::string>& result)
{
    size_t count = 0;
    result.clear();
    std::string::const_iterator p1 = s.cbegin();
    std::string::const_iterator p2 = p1;
    bool run = true;
    do
    {
        p2 = std::find(p1, s.cend(), ' ');
        result.push_back(std::string(p1, p2));
        ++count;

        if (p2 != s.cend())
        {
            p1 = std::find_if(p2, s.cend(), [](char c) -> bool
            {
                return c != ' ';
            });
        }
        else run = false;
    } while (run);
    return count;
}

int main()
{
    std::vector<std::string> v;
    std::string s = "a b c";
    for (auto i = 0; i < 100000; ++i)
        split2(s, v); 
    return 0;
}

$ time splittest.exe

réel 0m0.132s user 0m0.000s sys 0m0.109s

Answer 4

Je dirais que le regex C++11 est beaucoup plus lent que perl et peut-être que python.

Pour mesurer correctement les performances, il est préférable de faire les tests en utilisant une expression non triviale, sinon vous mesurez tout sauf la mais la regex elle-même.

Par exemple, pour comparer C++11 et perl

Code de test C++11

  #include <iostream>
  #include <string>
  #include <regex>
  #include <chrono>

  int main ()
  {
     int veces = 10000;
     int count = 0;
     std::regex expres ("([^-]*)-([^-]*)-(\\d\\d\\d:\\d\\d)---(.*)");

     std::string text ("some-random-text-453:10--- etc etc blah");
     std::smatch macha;

     auto start = std::chrono::system_clock::now();

     for (int ii = 0;  ii < veces; ii ++)
        count += std::regex_search (text, macha, expres);

     auto milli = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start).count();

     std::cout << count << "/" << veces << " matches " << milli << " ms --> " << (milli / (float) veces) << " ms per regex_search" << std::endl;
     return 0;
  }

Dans mon ordinateur, en compilant avec gcc 4.9.3, j'obtiens le résultat suivant

 10000/10000 matches 1704 ms --> 0.1704 ms per regex_search

code de test en perl

  use Time::HiRes qw/ time sleep /;

  my $veces = 1000000;
  my $conta = 0;
  my $phrase = "some-random-text-453:10--- etc etc blah";

  my $start = time;

  for (my $ii = 0; $ii < $veces; $ii++)
  {   
     if ($phrase =~ m/([^-]*)-([^-]*)-(\d\d\d:\d\d)---(.*)/)
     {
        $conta = $conta + 1;
     }
  }
  my $elapsed = (time - $start) * 1000.0;
  print $conta . "/" . $veces . " matches " . $elapsed . " ms --> " . ($elapsed / $veces) . " ms per regex\n";

j'utilise à nouveau perl v5.8.8 sur mon ordinateur

  1000000/1000000 matches 2929.55303192139 ms --> 0.00292955303192139 ms per regex

Ainsi, dans ce test, le rapport C++11 / perl est de

   0.1704 / 0.002929 = 58.17 times slower than perl

Dans des scénarios réels, j'obtiens des rapports environ 100 à 200 fois plus lents. Ainsi, par exemple, l'analyse d'un gros fichier contenant un million de lignes prend une seconde pour perl alors que cela peut prendre plusieurs minutes( !) pour un programme C++11 utilisant regex.