Buscando el Santo Grial de búsqueda y reemplazo en C++

algorithm boost

Question

Recientemente estaba buscando una manera de reemplazar tokens en una cadena que es esencialmente encontrar y reemplazar (pero hay al menos un enfoque adicional al problema) y parece una tarea bastante banal. He venido con algunas implementaciones posibles, pero ninguna de ellas fue satisfactoria desde el punto de vista del rendimiento. El mejor logro fue ~ 50us por iteración. La carcasa era ideal, la cuerda nunca creció en tamaño e inicialmente he omitido el requisito de ser sensible a las mayúsculas y minúsculas
Aquí está el código en Coliru

Resultados de mi máquina:
Boost.Spirit symbols result: 3421? = 3421
100000 ciclos tomaron 6060ms.
Resultados de Boyer-Moore: 3421? = 3421
100000 ciclos tomaron 5959ms.
Resultado de Boyer Moore Hospool: 3421? = 3421
100000 ciclos tomaron 5008ms.
Resultado de Knuth Morris Pratt: 3421? = 3421
100000 ciclos tomaron 12451ms.
Naive STL buscar y reemplazar el resultado: 3421? = 3421
100000 ciclos tomaron 5532ms.
Boost replace_all result: 3421? = 3421
100000 ciclos tomaron 4860ms.

Entonces la pregunta, ¿qué lleva tanto tiempo en una tarea tan simple? Uno puede decir, ok, tarea simple, seguir adelante e implementarlo mejor. Pero la realidad es que la implementación ingenua de 15 años de MFC hace que el orden de magnitud de la tarea sea más rápido:

CString FillTokenParams(const CString& input, const std::unordered_map<std::string, std::string>& tokens)
{
    CString tmpInput = input;
    for(const auto& token : tokens)
    {
        int pos = 0;
        while(pos != -1)
        {
            pos = tmpInput.Find(token.first.c_str(), pos);
            if(pos != -1)
            {
                int tokenLength = token.first.size();
                tmpInput.Delete(pos, tokenLength);
                tmpInput.Insert(pos, token.second.c_str());
                pos += 1;
            }
        }
    }

    return tmpInput;
}

resultado:
Resultado ingenioso de búsqueda y reemplazo de MFC: 3421? = 3421
100000 ciclos tomaron 516ms.
¿Cómo es que este código torpe supera al C ++ moderno? ¿Por qué otras implementaciones fueron tan lentas? ¿Me estoy perdiendo algo fundamental?

EDIT001: He invertido en esta pregunta, el código ha sido perfilado y comprobado por triplicado. Puede estar insatisfecho con esto y aquello, pero std :: string :: replace no es lo que lleva tiempo. En cualquier implementación de STL, la búsqueda es lo que tomar la mayor parte del tiempo, impulsar espíritu desperdicia tiempo en la asignación de tst (nodo de prueba en el árbol de evaluación, supongo). No espero que nadie señale en una línea una función con "este es tu problema" y poof, el problema se ha ido. La pregunta es cómo logró MFC hacer el mismo trabajo 10 veces más rápido.

EDIT002: acaba de profundizar en la implementación de Find de MFC y escribió una función que imita la implementación de MFC

namespace mfc
{
std::string::size_type Find(const std::string& input, const std::string& subString, std::string::size_type start)
{
    if(subString.empty())
    {
        return std::string::npos;
    }

    if(start < 0 || start > input.size())
    {
        return std::string::npos;
    }

    auto found = strstr(input.c_str() + start, subString.c_str());
    return ((found == nullptr) ? std::string::npos : std::string::size_type(found - input.c_str()));
}
}

std::string MFCMimicking(const std::string& input, const std::unordered_map<std::string, std::string>& tokens)
{
    auto tmpInput = input;
    for(const auto& token : tokens)
    {
        auto pos = 0;
        while(pos != std::string::npos)
        {
            pos = mfc::Find(tmpInput, token.first, pos);
            if(pos != std::string::npos)
            {
                auto tokenLength = token.first.size();
                tmpInput.replace(pos, tokenLength, token.second.c_str());
                pos += 1;
            }
        }
    }

    return tmpInput;
}

Resultados:
MFC que imita el resultado expandir: 3421? = 3421
100000 ciclos tomaron 411ms.
Significado 4us. por llamada, vence ese C strstr

EDIT003: Compilación y ejecución con -Ox

MFC que imita el resultado expandir: 3421? = 3421
100000 ciclos tomaron 660ms.
Resultado ingenioso de búsqueda y reemplazo de MFC: 3421? = 3421
100000 ciclos tomaron 856ms.
Resultado de expansión manual: 3421? = 3421
100000 ciclos tomaron 1995ms.
Resultados de Boyer-Moore: 3421? = 3421
100000 ciclos tomaron 6911ms.
Resultado de Boyer Moore Hospool: 3421? = 3421
100000 ciclos tomaron 5670ms.
Resultado de Knuth Morris Pratt: 3421? = 3421
100000 ciclos tomaron 13825ms.
Naive STL buscar y reemplazar el resultado: 3421? = 3421
100000 ciclos tomaron 9531ms.
Boost replace_all result: 3421? = 3421
100000 ciclos tomaron 8996ms.

corriendo con -O2 (como en las mediciones originales) pero 10k ciclos

MFC que imita el resultado expandir: 3421? = 3421
10000 ciclos tomaron 104ms.
Resultado ingenioso de búsqueda y reemplazo de MFC: 3421? = 3421
10000 ciclos tomaron 105ms.
Resultado de expansión manual: 3421? = 3421
10000 ciclos tomaron 356ms.
Resultados de Boyer-Moore: 3421? = 3421
10000 ciclos tomaron 1355ms.
Resultado de Boyer Moore Hospool: 3421? = 3421
10000 ciclos tomaron 1101ms.
Resultado de Knuth Morris Pratt: 3421? = 3421
10000 ciclos tomaron 1973ms.
Naive STL buscar y reemplazar el resultado: 3421? = 3421
10000 ciclos tomaron 923ms.
Boost replace_all result: 3421? = 3421
10000 ciclos tomaron 880ms.

Answer 1

Entonces, tengo algunas observaciones sobre la versión de Qi.

También creó una versión X3.

Finalmente, escribí una función de expansión manual que supera a todos los demás candidatos (espero que sea más rápido que MFC, ya que no molesta con repetidas eliminaciones / inserciones).

Pase a los cuadros de referencia si lo desea.

Acerca de la versión Qi

1. sí, las tablas de símbolos sufren problemas de localidad de los contenedores basados ​​en nodos. Puede que no sean la mejor combinación que puedes usar aquí.
2. No hay necesidad de reconstruir los símbolos en cada ciclo:

3. En lugar de omitir los símbolos que no son símbolos, escanea hasta el siguiente:

   +(bsq::char_ - symbols)

inline std::string spirit_qi(const std::string& input, bsq::symbols<char, std::string> const& symbols)
{
    std::string retVal;
    retVal.reserve(input.size() * 2);

    auto beg = input.cbegin();
    auto end = input.cend();

    if(!bsq::parse(beg, end, *(symbols | +(bsq::char_ - symbols)), retVal))
        retVal = input;

    return retVal;
}

Esto es considerablemente más rápido ya. Pero:

Bucles manuales

En este ejemplo trivial, ¿por qué no haces el análisis sintáctico manualmente?

inline std::string manual_expand(const std::string& input, TokenMap const& tokens)
{
    std::ostringstream builder;
    auto expand = [&](auto const& key) {
        auto match = tokens.find(key);
        if (match == tokens.end())
            builder << "$(" << key << ")";
        else
            builder << match->second;
    };

    builder.str().reserve(input.size()*2);

    builder.str("");
    std::ostreambuf_iterator<char> out(builder);

    for(auto f(input.begin()), l(input.end()); f != l;) {
        switch(*f) {
            case ''$'' : {
                    if (++f==l || *f!=''('') {
                        *out++ = ''$'';
                        break;
                    }
                    else {
                        auto s = ++f;
                        size_t n = 0;

                        while (f!=l && *f != '')'')
                            ++f, ++n;

                        // key is [s,f] now
                        expand(std::string(&*s, &*s+n));

                        if (f!=l)
                            ++f; // skip ''}''
                    }
                }
            default:
                *out++ = *f++;
        }
    }
    return builder.str();
}

Esto es muy superior en rendimiento en mi máquina.

Otras ideas

Puede consultar Boost Spirit Lex, potencialmente con tablas de tokens generadas estáticamente: http://www.boost.org/doc/libs/1_60_0/libs/spirit/doc/html/spirit/lex/abstracts/lexer_static_model.html . Aunque no soy particularmente aficionado a Lex.

COMPARACIONES:

Ver la tabla interactiva

Eso es usar Nonius para las estadísticas de benchmarking.

Código completo de referencia: http://paste.ubuntu.com/14133072/

#include <boost/container/flat_map.hpp>

#define USE_X3
#ifdef USE_X3
#   include <boost/spirit/home/x3.hpp>
#else
#   include <boost/spirit/include/qi.hpp>
#endif

#include <boost/algorithm/string.hpp>
#include <boost/algorithm/searching/boyer_moore.hpp>
#include <boost/algorithm/searching/boyer_moore_horspool.hpp>
#include <boost/algorithm/searching/knuth_morris_pratt.hpp>
#include <string>
#include <unordered_map>
#include <iostream>
#include <fstream>
#include <nonius/benchmark.h++>
#include <nonius/main.h++>

using TokenMap = boost::container::flat_map<std::string, std::string>;

#ifdef USE_X3
    namespace x3  = boost::spirit::x3;

    struct append {
        std::string& out;
        void do_append(char const ch) const                       { out += ch;                      } 
        void do_append(std::string const& s)  const               { out += s;                       } 
        template<typename It>
        void do_append(boost::iterator_range<It> const& r)  const { out.append(r.begin(), r.end()); } 
        template<typename Ctx>
        void operator()(Ctx& ctx) const                           { do_append(_attr(ctx));          } 
    };

    inline std::string spirit_x3(const std::string& input, x3::symbols<char const*> const& symbols)
    {
        std::string retVal;
        retVal.reserve(input.size() * 2);
        append appender { retVal };

        auto beg = input.cbegin();
        auto end = input.cend();

        auto rule = *(symbols[appender] | x3::char_ [appender]);

        if(!x3::parse(beg, end, rule))
            retVal = input;

        return retVal;
    }
#else
    namespace bsq = boost::spirit::qi;

    inline std::string spirit_qi_old(const std::string& input, TokenMap const& tokens)
    {
        std::string retVal;
        retVal.reserve(input.size() * 2);
        bsq::symbols<char const, char const*> symbols;
        for(const auto& token : tokens) {
            symbols.add(token.first.c_str(), token.second.c_str());
        }

        auto beg = input.cbegin();
        auto end = input.cend();

        if(!bsq::parse(beg, end, *(symbols | bsq::char_), retVal))
            retVal = input;

        return retVal;
    }

    inline std::string spirit_qi(const std::string& input, bsq::symbols<char, std::string> const& symbols)
    {
        std::string retVal;
        retVal.reserve(input.size() * 2);

        auto beg = input.cbegin();
        auto end = input.cend();

        if(!bsq::parse(beg, end, *(symbols | +(bsq::char_ - symbols)), retVal))
            retVal = input;

        return retVal;
    }
#endif

inline std::string manual_expand(const std::string& input, TokenMap const& tokens) {
    std::ostringstream builder;
    auto expand = [&](auto const& key) {
        auto match = tokens.find(key);

        if (match == tokens.end())
            builder << "$(" << key << ")";
        else
            builder << match->second;
    };

    builder.str().reserve(input.size()*2);
    std::ostreambuf_iterator<char> out(builder);

    for(auto f(input.begin()), l(input.end()); f != l;) {
        switch(*f) {
            case ''$'' : {
                    if (++f==l || *f!=''('') {
                        *out++ = ''$'';
                        break;
                    }
                    else {
                        auto s = ++f;
                        size_t n = 0;

                        while (f!=l && *f != '')'')
                            ++f, ++n;

                        // key is [s,f] now
                        expand(std::string(&*s, &*s+n));

                        if (f!=l)
                            ++f; // skip ''}''
                    }
                }
            default:
                *out++ = *f++;
        }
    }
    return builder.str();
}

inline std::string boost_replace_all(const std::string& input, TokenMap const& tokens)
{
    std::string retVal(input);
    retVal.reserve(input.size() * 2);

    for(const auto& token : tokens)
    {
        boost::replace_all(retVal, token.first, token.second);
    }
    return retVal;
}

inline void naive_stl(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next = std::search(input.cbegin(), input.cend(), token.first.begin(), token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = std::search(input.cbegin(), input.cend(), token.first.begin(), token.first.end());
        }
    }
}

inline void boyer_more(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next =
            boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(), token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(),
                                                        token.first.end());
        }
    }
}

inline void bmh_search(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next = boost::algorithm::boyer_moore_horspool_search(input.cbegin(), input.cend(), token.first.begin(),
                                                                  token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(),
                                                        token.first.end());
        }
    }
}

inline void kmp_search(std::string& input, TokenMap const& tokens)
{
    input.reserve(input.size() * 2);
    for(const auto& token : tokens)
    {
        auto next = boost::algorithm::knuth_morris_pratt_search(input.cbegin(), input.cend(), token.first.begin(),
                                                                token.first.end());
        while(next != input.cend())
        {
            input.replace(next, next + token.first.size(), token.second);
            next = boost::algorithm::boyer_moore_search(input.cbegin(), input.cend(), token.first.begin(),
                                                        token.first.end());
        }
    }
}

namespace testdata {
    std::string const expected =
        "Five and Seven said nothing, but looked at Two. Two began in a low voice, ''Why the fact is, you see, Miss, "
        "this here ought to have been a red rose-tree, and we put a white one in by mistake; and if the Queen was to "
        "find it out, we should all have our heads cut off, you know. So you see, Miss, we''re doing our best, afore "
        "she comes, to—'' At this moment Five, who had been anxiously looking across the garden, called out ''The Queen! "
        "The Queen!'' and the three gardeners instantly threw themselves flat upon their faces. There was a sound of "
        "many footsteps, and Alice looked round, eager to see the Queen.First came ten soldiers carrying clubs; these "
        "were all shaped like the three gardeners, oblong and flat, with their hands and feet at the corners: next the "
        "ten courtiers; these were ornamented all over with diamonds, and walked two and two, as the soldiers did. "
        "After these came the royal children; there were ten of them, and the little dears came jumping merrily along "
        "hand in hand, in couples: they were all ornamented with hearts. Next came the guests, mostly Kings and "
        "Queens, and among them Alice recognised the White Rabbit: it was talking in a hurried nervous manner, smiling "
        "at everything that was said, and went by without noticing her. Then followed the Knave of Hearts, carrying "
        "the King''s crown on a crimson velvet cushion; and, last of all this grand procession, came THE KING AND QUEEN "
        "OF HEARTS.Alice was rather doubtful whether she ought not to lie down on her face like the three gardeners, "
        "but she could not remember ever having heard of such a rule at processions; ''and besides, what would be the "
        "use of a procession,'' thought she, ''if people had all to lie down upon their faces, so that they couldn''t see "
        "it?'' So she stood still where she was, and waited.When the procession came opposite to Alice, they all "
        "stopped and looked at her, and the Queen said severely ''Who is this?'' She said it to the Knave of Hearts, who "
        "only bowed and smiled in reply.''Idiot!'' said the Queen, tossing her head impatiently; and, turning to Alice, "
        "she went on, ''What''s your name, child?''''My name is Alice, so please your Majesty,'' said Alice very politely; "
        "but she added, to herself, ''Why, they''re only a pack of cards, after all. I needn''t be afraid of them!''''And "
        "who are these?'' said the Queen, pointing to the three gardeners who were lying round the rosetree; for, you "
        "see, as they were lying on their faces, and the pattern on their backs was the same as the rest of the pack, "
        "she could not tell whether they were gardeners, or soldiers, or courtiers, or three of her own children.''How "
        "should I know?'' said Alice, surprised at her own courage. ''It''s no business of mine.''The Queen turned crimson "
        "with fury, and, after glaring at her for a moment like a wild beast, screamed ''Off with her head! "
        "Off—''''Nonsense!'' said Alice, very loudly and decidedly, and the Queen was silent.The King laid his hand upon "
        "her arm, and timidly said ''Consider, my dear: she is only a child!''The Queen turned angrily away from him, "
        "and said to the Knave ''Turn them over!''The Knave did so, very carefully, with one foot.''Get up!'' said the "
        "Queen, in a shrill, loud voice, and the three gardeners instantly jumped up, and began bowing to the King, "
        "the Queen, the royal children, and everybody else.''Leave off that!'' screamed the Queen. ''You make me giddy.'' "
        "And then, turning to the rose-tree, she went on, ''What have you been doing here?''";
    std::string const inputWithtokens =
        "Five and Seven said nothing, but looked at $(Two). $(Two) began in a low voice, ''Why the fact is, you see, "
        "Miss, "
        "this here ought to have been a red rose-tree, and we put a white one in by mistake; and if the Queen was to "
        "find it out, we should all have our $(heads) cut off, you know. So you see, Miss, we''re doing our best, afore "
        "she comes, to—'' At this moment Five, who had been anxiously looking across the garden, called out ''The Queen! "
        "The Queen!'' and the three gardeners instantly threw themselves flat upon their faces. There was a sound of "
        "many footsteps, and Alice looked round, eager to see the $(Queen).First came ten soldiers carrying clubs; "
        "these "
        "were all shaped like the three gardeners, oblong and flat, with their hands and feet at the corners: next the "
        "ten courtiers; these were ornamented all over with $(diamonds), and walked two and two, as the soldiers did. "
        "After these came the royal children; there were ten of them, and the little dears came jumping merrily along "
        "hand in hand, in couples: they were all ornamented with hearts. Next came the guests, mostly Kings and "
        "Queens, and among them Alice recognised the White Rabbit: it was talking in a hurried nervous manner, smiling "
        "at everything that was said, and went by without noticing her. Then followed the Knave of Hearts, carrying "
        "the King''s crown on a crimson velvet cushion; and, last of all this grand procession, came THE KING AND QUEEN "
        "OF HEARTS.Alice was rather doubtful whether she ought not to lie down on her face like the three gardeners, "
        "but she could not remember ever having heard of such a rule at processions; ''and besides, what would be the "
        "use of a procession,'' thought she, ''if people had all to lie down upon their faces, so that they couldn''t see "
        "it?'' So she stood still where she was, and waited.When the procession came opposite to Alice, they all "
        "stopped and looked at her, and the $(Queen) said severely ''Who is this?'' She said it to the Knave of Hearts, "
        "who "
        "only bowed and smiled in reply.''Idiot!'' said the Queen, tossing her head impatiently; and, turning to Alice, "
        "she went on, ''What''s your name, child?''''My name is Alice, so please your Majesty,'' said Alice very politely; "
        "but she added, to herself, ''Why, they''re only a pack of cards, after all. I needn''t be afraid of them!''''And "
        "who are these?'' said the $(Queen), pointing to the three gardeners who were lying round the rosetree; for, "
        "you "
        "see, as they were lying on their faces, and the $(pattern) on their backs was the same as the rest of the "
        "pack, "
        "she could not tell whether they were gardeners, or soldiers, or courtiers, or three of her own children.''How "
        "should I know?'' said Alice, surprised at her own courage. ''It''s no business of mine.''The Queen turned crimson "
        "with fury, and, after glaring at her for a moment like a wild beast, screamed ''Off with her head! "
        "Off—''''Nonsense!'' said $(Alice), very loudly and decidedly, and the Queen was silent.The $(King) laid his hand "
        "upon "
        "her arm, and timidly said ''Consider, my dear: she is only a child!''The $(Queen) turned angrily away from him, "
        "and said to the $(Knave) ''Turn them over!''The $(Knave) did so, very carefully, with one foot.''Get up!'' said "
        "the "
        "Queen, in a shrill, loud voice, and the three gardeners instantly jumped up, and began bowing to the King, "
        "the Queen, the royal children, and everybody else.''Leave off that!'' screamed the Queen. ''You make me giddy.'' "
        "And then, turning to the rose-tree, she went on, ''What have you been doing here?''";

    static TokenMap const raw_tokens {
        {"Two", "Two"},           {"heads", "heads"},
        {"diamonds", "diamonds"}, {"Queen", "Queen"},
        {"pattern", "pattern"},   {"Alice", "Alice"},
        {"King", "King"},         {"Knave", "Knave"},
        {"Why", "Why"},           {"glaring", "glaring"},
        {"name", "name"},         {"know", "know"},
        {"Idiot", "Idiot"},       {"children", "children"},
        {"Nonsense", "Nonsense"}, {"procession", "procession"},
    };

    static TokenMap const tokens {
        {"$(Two)", "Two"},           {"$(heads)", "heads"},
        {"$(diamonds)", "diamonds"}, {"$(Queen)", "Queen"},
        {"$(pattern)", "pattern"},   {"$(Alice)", "Alice"},
        {"$(King)", "King"},         {"$(Knave)", "Knave"},
        {"$(Why)", "Why"},           {"$(glaring)", "glaring"},
        {"$(name)", "name"},         {"$(know)", "know"},
        {"$(Idiot)", "Idiot"},       {"$(children)", "children"},
        {"$(Nonsense)", "Nonsense"}, {"$(procession)", "procession"},
    };

}

NONIUS_BENCHMARK("manual_expand", [](nonius::chronometer cm)     {
    std::string const tmp = testdata::inputWithtokens;
    auto& tokens = testdata::raw_tokens;

    std::string result;
    cm.measure([&](int) {
        result = manual_expand(tmp, tokens);
    });
    assert(result == testdata::expected);
})

#ifdef USE_X3
NONIUS_BENCHMARK("spirit_x3", [](nonius::chronometer cm) {
    auto const symbols = [&] {
        x3::symbols<char const*> symbols;
        for(const auto& token : testdata::tokens) {
            symbols.add(token.first.c_str(), token.second.c_str());
        }
        return symbols;
    }();

    std::string result;
    cm.measure([&](int) {
            result = spirit_x3(testdata::inputWithtokens, symbols);
        });
    //std::cout << "====/n" << result << "/n====/n";
    assert(testdata::expected == result);
})
#else
NONIUS_BENCHMARK("spirit_qi", [](nonius::chronometer cm) {
    auto const symbols = [&] {
        bsq::symbols<char, std::string> symbols;
        for(const auto& token : testdata::tokens) {
            symbols.add(token.first.c_str(), token.second.c_str());
        }
        return symbols;
    }();

    std::string result;
    cm.measure([&](int) {
            result = spirit_qi(testdata::inputWithtokens, symbols);
        });
    assert(testdata::expected == result);
})

NONIUS_BENCHMARK("spirit_qi_old", [](nonius::chronometer cm) {
    std::string result;
    cm.measure([&](int) {
            result = spirit_qi_old(testdata::inputWithtokens, testdata::tokens);
        });
    assert(testdata::expected == result);
})
#endif

NONIUS_BENCHMARK("boyer_more", [](nonius::chronometer cm) {
    cm.measure([&](int) {
        std::string tmp = testdata::inputWithtokens;
        boyer_more(tmp, testdata::tokens);
        assert(tmp == testdata::expected);
    });
})

NONIUS_BENCHMARK("bmh_search", [](nonius::chronometer cm) {
    cm.measure([&](int) {
        std::string tmp = testdata::inputWithtokens;
        bmh_search(tmp, testdata::tokens);
        assert(tmp == testdata::expected);
    });
})

NONIUS_BENCHMARK("kmp_search", [](nonius::chronometer cm) {
    cm.measure([&](int) {
        std::string tmp = testdata::inputWithtokens;
        kmp_search(tmp, testdata::tokens);
        assert(tmp == testdata::expected);
    });
})

NONIUS_BENCHMARK("naive_stl", [](nonius::chronometer cm) {
    cm.measure([&](int) {
            std::string tmp = testdata::inputWithtokens;
            naive_stl(tmp, testdata::tokens);
            assert(tmp == testdata::expected);
        });
})

NONIUS_BENCHMARK("boost_replace_all", [](nonius::chronometer cm)     {
    std::string const tmp = testdata::inputWithtokens;

    std::string result;
    cm.measure([&](int) {
        result = boost_replace_all(testdata::inputWithtokens, testdata::tokens);
    });
    assert(result == testdata::expected);
})

Answer 2

Entonces la pregunta, ¿qué lleva tanto tiempo en una tarea tan simple? Uno puede decir, ok, tarea simple, seguir adelante e implementarlo mejor. Pero la realidad es que la implementación ingenua de MFC hace 15 años hace que el orden de magnitud sea más rápido

La respuesta es realmente simple.

Primero compilé tu código en mi macbook pro usando apple clang 7.0:

$ cc --version
Apple LLVM version 7.0.0 (clang-700.1.76)
Target: x86_64-apple-darwin15.2.0
Thread model: posix

Los resultados parecen coincidir con los de OP ...

Boost.Spirit symbols result: 3425?=3425
10000 cycles took 8906ms.
Boyer-Moore results:3425?=3425
10000 cycles took 2891ms.
Boyer Moore Hospool result:3425?=3425
10000 cycles took 2392ms.
Knuth Morris Pratt result: 3425?=3425
10000 cycles took 4363ms.
Naive STL search and replace result: 3425?=3425
10000 cycles took 4333ms.
Boost replace_all result:3425?=3425
10000 cycles took 23284ms.
MFCMimicking result:3425?=3425
10000 cycles took 426ms.    <-- seemingly outstanding, no?

Luego agregué el indicador -O3:

Boost.Spirit symbols result: 3425?=3425
10000 cycles took 675ms.
Boyer-Moore results:3425?=3425
10000 cycles took 788ms.
Boyer Moore Hospool result:3425?=3425
10000 cycles took 623ms.
Knuth Morris Pratt result: 3425?=3425
10000 cycles took 1623ms.

Naive STL search and replace result: 3425?=3425
10000 cycles took 562ms.                    <-- pretty good!!!

Boost replace_all result:3425?=3425
10000 cycles took 748ms.
MFCMimicking result:3425?=3425
10000 cycles took 431ms.                    <-- awesome but not as outstanding as it was!

Y ahora los resultados están en el mismo orden de magnitud que los resultados de MFC CString.

¿Por qué?

Porque cuando compila contra BOOST y / o STL, está expandiendo plantillas y el código de la biblioteca adopta la misma configuración de optimización que su unidad de compilación.

Cuando se vincula con MFC, se está vinculando con una biblioteca compartida compilada con optimizaciones activadas.

Cuando utilizas strstr estás llamando a la biblioteca c que está precompilada, optimizada y en algunas partes, escrita a mano. ¡Por supuesto que va a ser rápido!

resuelto :)

10000 ciclos, no 100000, máquina diferente ...

como referencia, aquí están los resultados de la versión de 100,000 ciclos que se ejecuta en la computadora portátil con la energía de la batería. Optimización completa (-O3):

Boost.Spirit symbols result: 3425?=3425
100000 cycles took 6712ms.
Boyer-Moore results:3425?=3425
100000 cycles took 7923ms.
Boyer Moore Hospool result:3425?=3425
100000 cycles took 6091ms.
Knuth Morris Pratt result: 3425?=3425
100000 cycles took 16330ms.

Naive STL search and replace result: 3425?=3425
100000 cycles took 6719ms.

Boost replace_all result:3425?=3425
100000 cycles took 7353ms.

MFCMimicking result:3425?=3425
100000 cycles took 4076ms.

Answer 3

EDIT2 para MFCMimicking: Bueno desde su código, es obvio por qué la versión de MFC es más rápida: no busca en la cadena completa cada reemplazo como lo hacen algunas de sus otras versiones (todavía no puedo explicar boost :: spirit). Tan pronto como lo reemplaza, comienza a buscar desde el punto de reemplazo, no desde el principio de la cadena, por lo que es completamente obvio que será más rápido.

EDITAR: Después de investigar un poco más y ver ( Algoritmo para encontrar varias coincidencias de cadenas ), parece que utilizar los buenos algoritmos de coincidencia única para encontrar varios términos de búsqueda es el problema real aquí. Probablemente su mejor opción sea usar un algoritmo apropiado (se mencionan algunos en esa pregunta).

En cuanto a por qué MFC es más rápido? Sugiero destilar eso a una pregunta diferente "¿Por qué eliminar e insertar en CString mucho más rápido que std :: string" o algo así, y asegúrese de etiquetarlo C ++ y MFC para que las personas con la experiencia adecuada puedan ayudar ( Tengo experiencia con C ++ estándar pero no puedo ayudar con las optimizaciones que VC ++ puso en CString).

Respuesta original: OK, debido al gran volumen de código, solo expandTokens3 pero supongo que todas las versiones tienen el mismo problema. Su código tiene dos problemas de rendimiento potencialmente significativos:

• Busca la cadena completa cada vez que hace un reemplazo. Si tiene que reemplazar diez variables en una cadena, tomará el orden de diez veces más de lo necesario.

• Ejecuta cada reemplazo in situ en la cadena de entrada en lugar de construir la cadena de resultados de cada pieza. Esto puede dar como resultado la asignación de memoria y la copia para cada reemplazo que realice, lo que también aumenta significativamente el tiempo de ejecución.

Answer 4

Su uso cuestionable de std::string:replacees tan lento sin sentido que ninguna otra cosa en los asuntos de código.

Answer 5

Ok, será una larga historia. Solo para recordarte las preguntas.

1. ¿Por qué la búsqueda y el reemplazo usando C ++ (varios enfoques) son tan lentos?
2. ¿Por qué el MFC busca y reemplaza tan rápido?

Sorprendentemente, ambas preguntas tienen la misma respuesta. Debido a la sobrecarga de C ++. Sí. Nuestro brillante y moderno C ++ tiene una sobrecarga que en su mayoría descartamos por su flexibilidad y elegancia.

Sin embargo, cuando se trata de resoluciones de sub-microsegundos (no es que C ++ no sea capaz de hacer cosas en resoluciones de nanosegundos) la sobrecarga se vuelve más prominente.

Permítanme mostrar con el mismo código que he publicado en la pregunta, pero es más coherente con las cosas que se hacen en cada función.

Live On Coliru

Utiliza el Nonius antes mencionado (gracias a @sehe) y los resultados interactivos están aquí .

Puede hacer clic en la leyenda para mostrar / ocultar series particulares.

Conclusiones

Hay dos resultados sobresalientes

• MFC que imita la función y
• mi propio reemplazo manual

Estas funciones, al menos un orden de magnitud, son más rápidas que el resto, entonces, ¿cuál es la diferencia?

Todas estas funciones "lentas" están escritas en C ++ cuando el ayuno está escrito en C (no C puro, yo era demasiado flojo para manejar malloc / realloc de los buffers de salida cuando el tamaño de la salida aumenta). Bueno, creo que está claro que a veces no hay más remedio que recurrir a la pura C. Personalmente, estoy en contra de usar C por razones de seguridad y falta de seguridad. Además, simplemente requiere más experiencia y atención para escribir código C de alta calidad.

No lo marcaré como respuesta por un tiempo, esperando comentarios sobre esta conclusión.

Quiero agradecer a todos los que participaron activamente en la discusión, levantó las ideas y señaló inconsistencias en mi ejemplo.