Optimierteste Art der Verkettung in Zeichenfolgen

72

Wir sind täglich auf viele Situationen gestoßen, in denen wir mühsame und sehr viele Zeichenfolgenoperationen in unserem Code ausführen müssen. Wir alle wissen, dass String-Manipulationen teure Operationen sind. Ich würde gerne wissen, welche der verfügbaren Versionen die günstigste ist.

Die häufigste Operation ist die Verkettung (dies ist etwas, das wir bis zu einem gewissen Grad steuern können). Was ist der beste Weg, um std :: Strings in C ++ und verschiedene Problemumgehungen zu verketten, um die Verkettung zu beschleunigen?

Ich meine,

std::string l_czTempStr;

1).l_czTempStr = "Test data1" + "Test data2" + "Test data3";

2). l_czTempStr =  "Test data1"; 
    l_czTempStr += "Test data2";
    l_czTempStr += "Test data3";

3). using << operator

4). using append()

Erhalten wir auch einen Vorteil bei der Verwendung von CString gegenüber std :: string?

Bhupesh Pant
quelle
6
Warum kannst du nicht messen? Sowieso stringstreamist für diesen Anwendungsfall gebaut, stringnicht. Es ist also wahrscheinlich eine gute Wette, um damit zu beginnen stringstream.
Magnus Hoff
3
1. ist nicht legal, ITYM l_czTempStr = std::string("Test data1") + "Test data2" + "Test data3";. Ansonsten ist die Antwort, die verschiedenen Techniken zeitlich zu bestimmen. Es gibt so viele Variablen, dass es unmöglich ist, die Frage zu beantworten. Die Antwort hängt von der Anzahl und Länge der Zeichenfolgen ab, mit denen Sie arbeiten, sowie von der Plattform, auf der Sie kompilieren, und der Plattform, für die Sie kompilieren.
John
7
Ist es tatsächlich ein Engpass? Dann Benchmarking. Im Allgemeinen besteht die schnellste Methode darin, vor dem Anhängen genügend Speicherplatz für alle Daten vorab zuzuweisen und die Verwendung von temporären Daten zu vermeiden ( +erstellt ein neues Objekt mit einigen Sonderfällen in C ++ 11). Optimieren Sie dies jedoch nur, wenn Sie dies benötigen oder Ihr Code nicht lesbar ist.
Dave
6
@MagnusHoff Du hast es rückwärts. std::ostringstreamist für die Formatierung vorgesehen und sollte normalerweise nur verwendet werden, wenn Sie eine Formatierung benötigen. Alle seine Daten sind Zeichenfolgen, daher ist die std::stringVerkettung die bevorzugte Lösung.
James Kanze
3
Als Randnotiz: Bei sehr langen Saiten ist es möglicherweise eine gute Idee , ein Seil anstelle einer Saite zu verwenden.
ComicSansMS

Antworten:

75

Hier ist eine kleine Testsuite:

#include <iostream>
#include <string>
#include <chrono>
#include <sstream>

int main ()
{
    typedef std::chrono::high_resolution_clock clock;
    typedef std::chrono::duration<float, std::milli> mil;
    std::string l_czTempStr;
    std::string s1="Test data1";
    auto t0 = clock::now();
    #if VER==1
    for (int i = 0; i < 100000; ++i)
    {
        l_czTempStr = s1 + "Test data2" + "Test data3";
    }
    #elif VER==2
    for (int i = 0; i < 100000; ++i)
    {
        l_czTempStr =  "Test data1"; 
        l_czTempStr += "Test data2";
        l_czTempStr += "Test data3";
    }
    #elif VER==3
    for (int i = 0; i < 100000; ++i)
    {
        l_czTempStr =  "Test data1"; 
        l_czTempStr.append("Test data2");
        l_czTempStr.append("Test data3");
    }
    #elif VER==4
    for (int i = 0; i < 100000; ++i)
    {
        std::ostringstream oss;
        oss << "Test data1";
        oss << "Test data2";
        oss << "Test data3";
        l_czTempStr = oss.str();
    }
    #endif
    auto t1 = clock::now();
    std::cout << l_czTempStr << '\n';
    std::cout << mil(t1-t0).count() << "ms\n";
}

Auf coliru :

Kompilieren Sie mit folgendem:

clang ++ -std = c ++ 11 -O3 -DVER = 1 -Wall -pedantic -pthread main.cpp

21,6463 ms

-DVER = 2

6,61773 ms

-DVER = 3

6,7855 ms

-DVER = 4

102,015 ms

Es sieht so aus 2), +=ist der Gewinner.

(Auch das Kompilieren mit und ohne -pthreadscheint das Timing zu beeinflussen)

Jesse Gut
quelle
1
Nett! Ihre Nummerierung hat 3) und 4) gegen die Frage getauscht. Angesichts der nicht allzu großen Unterschiede scheint die einzige feste Schlussfolgerung darin zu bestehen, Streams zu vermeiden. Dies hängt natürlich nicht nur vom Compiler (Revision) ab, sondern auch von der stdlib-Implementierung (ich denke, einer der GCCs auf coliru).
Benjamin Bannier
34
Der Test ist leider möglicherweise nicht repräsentativ. Das Problem ist, dass l_czTempStrdie Versionen 2 und 3 , wenn die Deklaration nicht in die Schleife aufgenommen wird, denselben Puffer immer wieder verwenden, während Version 1 std::string{""}jedes Mal einen neuen Puffer erstellt . Ihr Benchmark hat gezeigt, dass die Wiederverwendung des gleichen Puffers anstelle der Zuweisung / Freigabe eine 5-fache Beschleunigung ergibt (die Beschleunigung war offensichtlich, der Faktor hängt davon ab, wie lang die Teile sind und wie viele Neuzuweisungen erfolgen, wenn Sie nicht alles reservieren -Vorderseite). Ich bin mir nicht sicher, ob das OP den gleichen Puffer wiederverwenden wollte oder nicht.
Matthieu M.
2
@MatthieuM.: +1 guter Punkt. Ich habe den Code so aktualisiert, dass die anfängliche Zeichenfolge zuvor in Version 1 erstellt wurde, operator+leidet jedoch immer noch unter einer großen internen Zuweisung / Freigabe.
Jesse Good
3
Ihr stringstreamBenchmark beinhaltet das (unglaublich) langsame Timing des Aufbaus des Streams.
Rapptz
2
"Es sieht aus wie 2), + = ist der Gewinner." Ich bin nicht sicher, ob Ihre Ergebnisse statistische Unterschiede aufweisen .append(). Und sie sollten es auch nicht: Eine davon wird in Bezug auf die andere umgesetzt. Ich verstehe nicht, warum sie sich signifikant unterscheiden würden.
underscore_d
34

Neben anderen Antworten ...

Ich habe vor einiger Zeit umfangreiche Benchmarks zu diesem Problem erstellt und bin zu dem Schluss gekommen, dass die effizienteste Lösung (GCC 4.7 und 4.8 unter Linux x86 / x64 / ARM) in allen Anwendungsfällen zunächst reserve()die Ergebniszeichenfolge mit genügend Speicherplatz für alle ist die verketteten Zeichenfolgen und dann nur append()sie (oder verwenden operator +=(), das macht keinen Unterschied).

Leider habe ich diesen Benchmark gelöscht, sodass Sie nur mein Wort haben (aber Sie können den Benchmark von Mats Petersson leicht anpassen, um dies selbst zu überprüfen, wenn mein Wort nicht ausreicht).

In einer Nussschale:

const string space = " ";
string result;
result.reserve(5 + space.size() + 5);
result += "hello";
result += space;
result += "world";

Abhängig vom genauen Anwendungsfall (Anzahl, Typ und Größe der verketteten Zeichenfolgen) ist diese Methode manchmal bei weitem die effizienteste und manchmal ist sie anderen Methoden ebenbürtig, aber niemals schlechter.


Das Problem ist, dass es sehr schmerzhaft ist, die erforderliche Gesamtgröße im Voraus zu berechnen, insbesondere beim Mischen von String-Literalen und std::string(das obige Beispiel ist in dieser Angelegenheit meiner Meinung nach klar genug). Die Wartbarkeit eines solchen Codes ist absolut schrecklich, sobald Sie eines der Literale ändern oder eine andere zu verkettende Zeichenfolge hinzufügen.

Ein Ansatz wäre, sizeofdie Größe der Literale zu berechnen, aber meiner Meinung nach verursacht es so viel Chaos, wie es löst, die Wartbarkeit ist immer noch schrecklich:

#define STR_HELLO "hello"
#define STR_WORLD "world"

const string space = " ";
string result;
result.reserve(sizeof(STR_HELLO)-1 + space.size() + sizeof(STR_WORLD)-1);
result += STR_HELLO;
result += space;
result += STR_WORLD;

Eine brauchbare Lösung (C ++ 11, verschiedene Vorlagen)

Ich entschied mich schließlich für eine Reihe variabler Vorlagen, die sich effizient um die Berechnung der Zeichenfolgengrößen kümmern (z. B. wird die Größe der Zeichenfolgenliterale zur Kompilierungszeit bestimmt) reserve(), und dann alles verkettet.

Hier ist es, hoffe das ist nützlich:

namespace detail {

  template<typename>
  struct string_size_impl;

  template<size_t N>
  struct string_size_impl<const char[N]> {
    static constexpr size_t size(const char (&) [N]) { return N - 1; }
  };

  template<size_t N>
  struct string_size_impl<char[N]> {
    static size_t size(char (&s) [N]) { return N ? strlen(s) : 0; }
  };

  template<>
  struct string_size_impl<const char*> {
    static size_t size(const char* s) { return s ? strlen(s) : 0; }
  };

  template<>
  struct string_size_impl<char*> {
    static size_t size(char* s) { return s ? strlen(s) : 0; }
  };

  template<>
  struct string_size_impl<std::string> {
    static size_t size(const std::string& s) { return s.size(); }
  };

  template<typename String> size_t string_size(String&& s) {
    using noref_t = typename std::remove_reference<String>::type;
    using string_t = typename std::conditional<std::is_array<noref_t>::value,
                                              noref_t,
                                              typename std::remove_cv<noref_t>::type
                                              >::type;
    return string_size_impl<string_t>::size(s);
  }

  template<typename...>
  struct concatenate_impl;

  template<typename String>
  struct concatenate_impl<String> {
    static size_t size(String&& s) { return string_size(s); }
    static void concatenate(std::string& result, String&& s) { result += s; }
  };

  template<typename String, typename... Rest>
  struct concatenate_impl<String, Rest...> {
    static size_t size(String&& s, Rest&&... rest) {
      return string_size(s)
           + concatenate_impl<Rest...>::size(std::forward<Rest>(rest)...);
    }
    static void concatenate(std::string& result, String&& s, Rest&&... rest) {
      result += s;
      concatenate_impl<Rest...>::concatenate(result, std::forward<Rest>(rest)...);
    }
  };

} // namespace detail

template<typename... Strings>
std::string concatenate(Strings&&... strings) {
  std::string result;
  result.reserve(detail::concatenate_impl<Strings...>::size(std::forward<Strings>(strings)...));
  detail::concatenate_impl<Strings...>::concatenate(result, std::forward<Strings>(strings)...);
  return result;
}

Der einzig interessante Teil, was die öffentliche Oberfläche betrifft, ist die allerletzte template<typename... Strings> std::string concatenate(Strings&&... strings)Vorlage. Die Verwendung ist unkompliziert:

int main() {
  const string space = " ";
  std::string result = concatenate("hello", space, "world");
  std::cout << result << std::endl;
}

Wenn die Optimierungen aktiviert sind, sollte jeder anständige Compiler in der Lage sein, den concatenateAufruf auf denselben Code wie in meinem ersten Beispiel zu erweitern, in dem ich alles manuell geschrieben habe. In Bezug auf GCC 4.7 und 4.8 ist der generierte Code ebenso wie die Leistung ziemlich identisch.

Syam
quelle
Ich verstehe den Grund für die Verwendung universeller Referenzen hier nicht. Können Sie erklären, welchen Vorteil sie gegenüber normalen (lvalue) Verweisen auf const bieten könnten?
Paul Groke
Haben Sie eine Wstring-Implementierung durchgeführt? Es sieht so aus, als wäre es unkompliziert.
KarlM
mit oder ohne "Reserve" -Funktion zeigt in meinem Test keinen Unterschied, manchmal ist die "Reserve" -Funktion schlechter.
Hao
@Hao, vielleicht passt "Hallo Welt" in einen std :: string, der die Optimierung kleiner Strings verwendet, so dass die Reserveoperation effektiv nichts bewirkt.
Emile Cormier
20

Das schlimmste mögliche Szenario ist die Verwendung von alt strcat(oder sprintf), da strcateine C-Zeichenfolge verwendet wird, und diese muss "gezählt" werden, um das Ende zu finden. Für lange Saiten ist das ein echter Leistungseinbrecher. Zeichenfolgen im C ++ - Stil sind viel besser, und die Leistungsprobleme liegen wahrscheinlich eher in der Speicherzuweisung als in der Zählung der Längen. Andererseits wächst die Saite geometrisch (verdoppelt sich jedes Mal, wenn sie wachsen muss), also ist es nicht so schrecklich.

Ich würde sehr vermuten, dass alle oben genannten Methoden die gleiche oder zumindest sehr ähnliche Leistung erbringen. Wenn überhaupt, würde ich erwarten, dass dies stringstreamaufgrund des Overheads bei der Unterstützung der Formatierung langsamer ist - aber ich vermute auch, dass es marginal ist.

Da so etwas "Spaß" macht, werde ich mit einem Benchmark zurückkommen ...

Bearbeiten:

Beachten Sie, dass diese Ergebnisse für MEINEN Computer gelten, auf dem x86-64 Linux ausgeführt wird und der mit g ++ 4.6.3 kompiliert wurde. Andere Betriebssysteme, Compiler und Implementierungen der C ++ - Laufzeitbibliothek können variieren. Wenn die Leistung für Ihre Anwendung wichtig ist, vergleichen Sie die für Sie kritischen Systeme anhand der von Ihnen verwendeten Compiler.

Hier ist der Code, den ich geschrieben habe, um dies zu testen. Es ist vielleicht nicht die perfekte Darstellung eines realen Szenarios, aber ich denke, es ist ein repräsentatives Szenario:

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <cstring>

using namespace std;

static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

string build_string_1(const string &a, const string &b, const string &c)
{
    string out = a + b + c;
    return out;
}

string build_string_1a(const string &a, const string &b, const string &c)
{
    string out;
    out.resize(a.length()*3);
    out = a + b + c;
    return out;
}

string build_string_2(const string &a, const string &b, const string &c)
{
    string out = a;
    out += b;
    out += c;
    return out;
}

string build_string_3(const string &a, const string &b, const string &c)
{
    string out;
    out = a;
    out.append(b);
    out.append(c);
    return out;
}


string build_string_4(const string &a, const string &b, const string &c)
{
    stringstream ss;

    ss << a << b << c;
    return ss.str();
}


char *build_string_5(const char *a, const char *b, const char *c)
{
    char* out = new char[strlen(a) * 3+1];
    strcpy(out, a);
    strcat(out, b);
    strcat(out, c);
    return out;
}



template<typename T>
size_t len(T s)
{
    return s.length();
}

template<>
size_t len(char *s)
{
    return strlen(s);
}

template<>
size_t len(const char *s)
{
    return strlen(s);
}



void result(const char *name, unsigned long long t, const string& out)
{
    cout << left << setw(22) << name << " time:" << right << setw(10) <<  t;
    cout << "   (per character: " 
         << fixed << right << setw(8) << setprecision(2) << (double)t / len(out) << ")" << endl;
}

template<typename T>
void benchmark(const char name[], T (Func)(const T& a, const T& b, const T& c), const char *strings[])
{
    unsigned long long t;

    const T s1 = strings[0];
    const T s2 = strings[1];
    const T s3 = strings[2];
    t = rdtsc();
    T out = Func(s1, s2, s3);
    t = rdtsc() - t; 

    if (len(out) != len(s1) + len(s2) + len(s3))
    {
        cout << "Error: out is different length from inputs" << endl;
        cout << "Got `" << out << "` from `" << s1 << "` + `" << s2 << "` + `" << s3 << "`";
    }
    result(name, t, out);
}


void benchmark(const char name[], char* (Func)(const char* a, const char* b, const char* c), 
               const char *strings[])
{
    unsigned long long t;

    const char* s1 = strings[0];
    const char* s2 = strings[1];
    const char* s3 = strings[2];
    t = rdtsc();
    char *out = Func(s1, s2, s3);
    t = rdtsc() - t; 

    if (len(out) != len(s1) + len(s2) + len(s3))
    {
        cout << "Error: out is different length from inputs" << endl;
        cout << "Got `" << out << "` from `" << s1 << "` + `" << s2 << "` + `" << s3 << "`";
    }
    result(name, t, out);
    delete [] out;
}


#define BM(func, size) benchmark(#func " " #size, func, strings ## _ ## size)


#define BM_LOT(size) BM(build_string_1, size); \
    BM(build_string_1a, size); \
    BM(build_string_2, size); \
    BM(build_string_3, size); \
    BM(build_string_4, size); \
    BM(build_string_5, size);

int main()
{
    const char *strings_small[]  = { "Abc", "Def", "Ghi" };
    const char *strings_medium[] = { "abcdefghijklmnopqrstuvwxyz", 
                                     "defghijklmnopqrstuvwxyzabc", 
                                     "ghijklmnopqrstuvwxyzabcdef" };
    const char *strings_large[]   = 
        { "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
          "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz", 

          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc"

          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc" 
          "defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabc", 

          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
          "ghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef"
        };

    for(int i = 0; i < 5; i++)
    {
        BM_LOT(small);
        BM_LOT(medium);
        BM_LOT(large);
        cout << "---------------------------------------------" << endl;
    }
}

Hier sind einige repräsentative Ergebnisse:

build_string_1 small   time:      4075   (per character:   452.78)
build_string_1a small  time:      5384   (per character:   598.22)
build_string_2 small   time:      2669   (per character:   296.56)
build_string_3 small   time:      2427   (per character:   269.67)
build_string_4 small   time:     19380   (per character:  2153.33)
build_string_5 small   time:      6299   (per character:   699.89)
build_string_1 medium  time:      3983   (per character:    51.06)
build_string_1a medium time:      6970   (per character:    89.36)
build_string_2 medium  time:      4072   (per character:    52.21)
build_string_3 medium  time:      4000   (per character:    51.28)
build_string_4 medium  time:     19614   (per character:   251.46)
build_string_5 medium  time:      6304   (per character:    80.82)
build_string_1 large   time:      8491   (per character:     3.63)
build_string_1a large  time:      9563   (per character:     4.09)
build_string_2 large   time:      6154   (per character:     2.63)
build_string_3 large   time:      5992   (per character:     2.56)
build_string_4 large   time:     32450   (per character:    13.87)
build_string_5 large   time:     15768   (per character:     6.74)

Gleicher Code, ausgeführt als 32-Bit:

build_string_1 small   time:      4289   (per character:   476.56)
build_string_1a small  time:      5967   (per character:   663.00)
build_string_2 small   time:      3329   (per character:   369.89)
build_string_3 small   time:      3047   (per character:   338.56)
build_string_4 small   time:     22018   (per character:  2446.44)
build_string_5 small   time:      3026   (per character:   336.22)
build_string_1 medium  time:      4089   (per character:    52.42)
build_string_1a medium time:      8075   (per character:   103.53)
build_string_2 medium  time:      4569   (per character:    58.58)
build_string_3 medium  time:      4326   (per character:    55.46)
build_string_4 medium  time:     22751   (per character:   291.68)
build_string_5 medium  time:      2252   (per character:    28.87)
build_string_1 large   time:      8695   (per character:     3.72)
build_string_1a large  time:     12818   (per character:     5.48)
build_string_2 large   time:      8202   (per character:     3.51)
build_string_3 large   time:      8351   (per character:     3.57)
build_string_4 large   time:     38250   (per character:    16.35)
build_string_5 large   time:      8143   (per character:     3.48)

Daraus können wir schließen:

  1. Die beste Option ist das Anhängen eines Stücks ( out.append()oder out +=), wobei der "verkettete" Ansatz ziemlich nahe kommt.

  2. Das Vorabzuweisen der Zeichenfolge ist nicht hilfreich.

  3. Die Verwendung stringstreamist eine ziemlich schlechte Idee (zwischen 2-4x langsamer).

  4. Die char *Verwendungen new char[]. Die Verwendung einer lokalen Variablen in der aufrufenden Funktion macht es am schnellsten - aber etwas unfair, das zu vergleichen.

  5. Das Kombinieren von kurzen Zeichenfolgen ist mit einem gewissen Aufwand verbunden. Das Kopieren von Daten sollte höchstens einen Zyklus pro Byte umfassen [es sei denn, die Daten passen nicht in den Cache].

edit2

Hinzugefügt, wie in den Kommentaren:

string build_string_1b(const string &a, const string &b, const string &c)
{
    return a + b + c;
}

und

string build_string_2a(const string &a, const string &b, const string &c)
{
    string out;
    out.reserve(a.length() * 3);
    out += a;
    out += b;
    out += c;
    return out;
}

Welches gibt diese Ergebnisse:

build_string_1 small   time:      3845   (per character:   427.22)
build_string_1b small  time:      3165   (per character:   351.67)
build_string_2 small   time:      3176   (per character:   352.89)
build_string_2a small  time:      1904   (per character:   211.56)

build_string_1 large   time:      9056   (per character:     3.87)
build_string_1b large  time:      6414   (per character:     2.74)
build_string_2 large   time:      6417   (per character:     2.74)
build_string_2a large  time:      4179   (per character:     1.79)

(Ein 32-Bit-Lauf, aber der 64-Bit-Lauf zeigt sehr ähnliche Ergebnisse).

Mats Petersson
quelle
1
Schöner Benchmark, +1. In Bezug auf 1a (Vorzuweisung der Zeichenfolge) werfen Sie in der Realität den vorab zugewiesenen Puffer weg: Das Ergebnis von operator +()ist ein temporärer Puffer , in den verschoben (oder RVO-fähig) wird, outsodass die Vorzuweisung nutzlos ist. Ein interessanter Benchmark wäre, 2a / 3a- Fälle zu erstellen, in denen Sie reserve()die Ergebniszeichenfolge vor sich haben und dann append()oder +=alle Parameter Ihrer Ergebniszeichenfolge. Wie ich in meiner Antwort erläutere, habe ich vor einiger Zeit solche Benchmarks durchgeführt und bin zu dem Schluss gekommen, dass dies tatsächlich die effizienteste Lösung ist.
Syam
Ich habe Ihren Code genommen und eine build_string_1bFunktion hinzugefügt , die gerade ausgeführt wurde return a + b + c;und sich in einigen Läufen als die schnellste Funktion herausstellte (VS2012).
Blastfurnace
1
Nur Nitpicking bezüglich 2a : Derzeit haben Sie zwei Speicherzuordnungen (kopieren Sie adann reserve), dies könnte weiter verbessert werden, indem Sie reserveeine leere Zeichenfolge und nur dann += alle Ihre Parameter verwenden (was Ihnen eine einzige Speicherzuweisung gibt, die reserve). Ich würde das selbst bearbeiten, aber die Timings sind für Ihre Maschine, also lasse ich Sie es tun. ;)
Syam
@Syam: Ich habe das letztendlich tatsächlich geschrieben, aber ich muss den Code geschrieben haben - die Ergebnisse beziehen sich auf den Code, den ich jetzt gepostet habe.
Mats Petersson
11

Wie bei den meisten Mikrooptimierungen müssen Sie den Effekt jeder Option messen, nachdem Sie zunächst durch Messung festgestellt haben, dass dies tatsächlich ein Flaschenhals ist, der optimiert werden sollte. Es gibt keine endgültige Antwort.

appendund +=sollte genau das gleiche tun.

+ist konzeptionell weniger effizient, da Sie Provisorien erstellen und zerstören. Ihr Compiler kann dies möglicherweise so optimieren, dass es so schnell wie das Anhängen ist.

Anrufe reservemit der Gesamtgröße können die Anzahl der erforderlichen Speicherzuordnungen verringern - dies ist wahrscheinlich der größte Engpass.

<<(vermutlich auf a stringstream) kann schneller sein oder nicht; Sie müssen das messen. Es ist nützlich, wenn Sie Nicht-String-Typen formatieren müssen, aber wahrscheinlich nicht besonders gut oder schlechter mit Strings umgehen können.

CString hat den Nachteil, dass es nicht portabel ist und dass ein Unix-Hacker wie ich Ihnen nicht sagen kann, welche Vorteile es haben kann oder nicht.

Mike Seymour
quelle
3

Ich beschloss, einen Test mit dem vom Benutzer Jesse Good bereitgestellten Code durchzuführen , der leicht modifiziert wurde, um die Beobachtung von Rapptz zu berücksichtigen , insbesondere die Tatsache, dass der Ostringstream in jeder einzelnen Iteration der Schleife konstruiert wurde. Daher habe ich einige Fälle hinzugefügt, von denen einige der Ostringstream sind, der mit der Sequenz " oss.str (" "); oss.clear () " gelöscht wurde.

Hier ist der Code

#include <iostream>
#include <string>
#include <chrono>
#include <sstream>
#include <functional>


template <typename F> void time_measurement(F f, const std::string& comment)
{
    typedef std::chrono::high_resolution_clock clock;
    typedef std::chrono::duration<float, std::milli> mil;
    std::string r;
    auto t0 = clock::now();
    f(r);
    auto t1 = clock::now();
    std::cout << "\n-------------------------" << comment << "-------------------\n" <<r << '\n';
    std::cout << mil(t1-t0).count() << "ms\n";
    std::cout << "---------------------------------------------------------------------------\n";

}

inline void clear(std::ostringstream& x)
{
    x.str("");
    x.clear();
}

void test()
{
    std:: cout << std::endl << "----------------String Comparison---------------- " << std::endl;
    const int n=100000;
    {
        auto f=[](std::string& l_czTempStr)
        {
            std::string s1="Test data1";
            for (int i = 0; i < n; ++i)
            {
                l_czTempStr = s1 + "Test data2" + "Test data3";
            }
        };
        time_measurement(f, "string, plain addition");
   }

   {
        auto f=[](std::string& l_czTempStr)
        {
            for (int i = 0; i < n; ++i)
            {
                l_czTempStr =  "Test data1";
                l_czTempStr += "Test data2";
                l_czTempStr += "Test data3";
            }
        };
        time_measurement(f, "string, incremental");
    }

    {
         auto f=[](std::string& l_czTempStr)
         {
            for (int i = 0; i < n; ++i)
            {
                l_czTempStr =  "Test data1";
                l_czTempStr.append("Test data2");
                l_czTempStr.append("Test data3");
            }
         };
         time_measurement(f, "string, append");
     }

    {
         auto f=[](std::string& l_czTempStr)
         {
            for (int i = 0; i < n; ++i)
            {
                std::ostringstream oss;
                oss << "Test data1";
                oss << "Test data2";
                oss << "Test data3";
                l_czTempStr = oss.str();
            }
         };
         time_measurement(f, "oss, creation in each loop, incremental");
     }

    {
         auto f=[](std::string& l_czTempStr)
         {
            std::ostringstream oss;
            for (int i = 0; i < n; ++i)
            {
                oss.str("");
                oss.clear();
                oss << "Test data1";
                oss << "Test data2";
                oss << "Test data3";
            }
            l_czTempStr = oss.str();
         };
         time_measurement(f, "oss, 1 creation, incremental");
     }

    {
         auto f=[](std::string& l_czTempStr)
         {
            std::ostringstream oss;
            for (int i = 0; i < n; ++i)
            {
                oss.str("");
                oss.clear();
                oss << "Test data1" << "Test data2" << "Test data3";
            }
            l_czTempStr = oss.str();
         };
         time_measurement(f, "oss, 1 creation, plain addition");
     }

    {
         auto f=[](std::string& l_czTempStr)
         {
            std::ostringstream oss;
            for (int i = 0; i < n; ++i)
            {
                clear(oss);
                oss << "Test data1" << "Test data2" << "Test data3";
            }
            l_czTempStr = oss.str();
         };
         time_measurement(f, "oss, 1 creation, clearing calling inline function, plain addition");
     }


    {
         auto f=[](std::string& l_czTempStr)
         {
            for (int i = 0; i < n; ++i)
            {
                std::string x;
                x =  "Test data1";
                x.append("Test data2");
                x.append("Test data3");
                l_czTempStr=x;
            }
         };
         time_measurement(f, "string, creation in each loop");
     }

}

Hier sind die Ergebnisse:

/*

g++ "qtcreator debug mode"
----------------String Comparison---------------- 

-------------------------string, plain addition-------------------
Test data1Test data2Test data3
11.8496ms
---------------------------------------------------------------------------

-------------------------string, incremental-------------------
Test data1Test data2Test data3
3.55597ms
---------------------------------------------------------------------------

-------------------------string, append-------------------
Test data1Test data2Test data3
3.53099ms
---------------------------------------------------------------------------

-------------------------oss, creation in each loop, incremental-------------------
Test data1Test data2Test data3
58.1577ms
---------------------------------------------------------------------------

-------------------------oss, 1 creation, incremental-------------------
Test data1Test data2Test data3
11.1069ms
---------------------------------------------------------------------------

-------------------------oss, 1 creation, plain addition-------------------
Test data1Test data2Test data3
10.9946ms
---------------------------------------------------------------------------

-------------------------oss, 1 creation, clearing calling inline function, plain addition-------------------
Test data1Test data2Test data3
10.9502ms
---------------------------------------------------------------------------

-------------------------string, creation in each loop-------------------
Test data1Test data2Test data3
9.97495ms
---------------------------------------------------------------------------


g++ "qtcreator release mode" (optimized)
----------------String Comparison----------------

-------------------------string, plain addition-------------------
Test data1Test data2Test data3
8.41622ms
---------------------------------------------------------------------------

-------------------------string, incremental-------------------
Test data1Test data2Test data3
2.55462ms
---------------------------------------------------------------------------

-------------------------string, append-------------------
Test data1Test data2Test data3
2.5154ms
---------------------------------------------------------------------------

-------------------------oss, creation in each loop, incremental-------------------
Test data1Test data2Test data3
54.3232ms
---------------------------------------------------------------------------

-------------------------oss, 1 creation, incremental-------------------
Test data1Test data2Test data3
8.71854ms
---------------------------------------------------------------------------

-------------------------oss, 1 creation, plain addition-------------------
Test data1Test data2Test data3
8.80526ms
---------------------------------------------------------------------------

-------------------------oss, 1 creation, clearing calling inline function, plain addition-------------------
Test data1Test data2Test data3
8.78186ms
---------------------------------------------------------------------------

-------------------------string, creation in each loop-------------------
Test data1Test data2Test data3
8.4034ms
---------------------------------------------------------------------------
*/

Jetzt ist die Verwendung von std :: string immer noch schneller und das Anhängen ist immer noch der schnellste Weg zur Verkettung, aber ostringstream ist nicht mehr so ​​unglaublich schrecklich wie zuvor.

DrHell
quelle
1

Da die akzeptierte Antwort dieser Frage ziemlich alt ist, habe ich beschlossen, die Benchmarks mit dem modernen Compiler zu aktualisieren und beide Lösungen von @ jesse-good und die Vorlagenversion von @syam zu vergleichen

Hier ist der kombinierte Code:

#include <iostream>
#include <string>
#include <chrono>
#include <sstream>
#include <vector>
#include <cstring>


#if VER==TEMPLATE
namespace detail {

  template<typename>
  struct string_size_impl;

  template<size_t N>
  struct string_size_impl<const char[N]> {
    static constexpr size_t size(const char (&) [N]) { return N - 1; }
  };

  template<size_t N>
  struct string_size_impl<char[N]> {
    static size_t size(char (&s) [N]) { return N ? strlen(s) : 0; }
  };

  template<>
  struct string_size_impl<const char*> {
    static size_t size(const char* s) { return s ? strlen(s) : 0; }
  };

  template<>
  struct string_size_impl<char*> {
    static size_t size(char* s) { return s ? strlen(s) : 0; }
  };

  template<>
  struct string_size_impl<std::string> {
    static size_t size(const std::string& s) { return s.size(); }
  };

  template<typename String> size_t string_size(String&& s) {
    using noref_t = typename std::remove_reference<String>::type;
    using string_t = typename std::conditional<std::is_array<noref_t>::value,
                                              noref_t,
                                              typename std::remove_cv<noref_t>::type
                                              >::type;
    return string_size_impl<string_t>::size(s);
  }

  template<typename...>
  struct concatenate_impl;

  template<typename String>
  struct concatenate_impl<String> {
    static size_t size(String&& s) { return string_size(s); }
    static void concatenate(std::string& result, String&& s) { result += s; }
  };

  template<typename String, typename... Rest>
  struct concatenate_impl<String, Rest...> {
    static size_t size(String&& s, Rest&&... rest) {
      return string_size(s)
           + concatenate_impl<Rest...>::size(std::forward<Rest>(rest)...);
    }
    static void concatenate(std::string& result, String&& s, Rest&&... rest) {
      result += s;
      concatenate_impl<Rest...>::concatenate(result, std::forward<Rest>(rest)...);
    }
  };

} // namespace detail

template<typename... Strings>
std::string concatenate(Strings&&... strings) {
  std::string result;
  result.reserve(detail::concatenate_impl<Strings...>::size(std::forward<Strings>(strings)...));
  detail::concatenate_impl<Strings...>::concatenate(result, std::forward<Strings>(strings)...);
  return result;
}

#endif

int main ()
{
typedef std::chrono::high_resolution_clock clock;
typedef std::chrono::duration<float, std::milli> ms;
std::string l_czTempStr;


std::string s1="Test data1";


auto t0 = clock::now();
#if VER==PLUS
for (int i = 0; i < 100000; ++i)
{
    l_czTempStr = s1 + "Test data2" + "Test data3";
}
#elif VER==PLUS_EQ
for (int i = 0; i < 100000; ++i)
{
    l_czTempStr =  "Test data1"; 
    l_czTempStr += "Test data2";
    l_czTempStr += "Test data3";
}
#elif VER==APPEND
for (int i = 0; i < 100000; ++i)
{
    l_czTempStr =  "Test data1"; 
    l_czTempStr.append("Test data2");
    l_czTempStr.append("Test data3");
}
#elif VER==STRSTREAM
for (int i = 0; i < 100000; ++i)
{
    std::ostringstream oss;
    oss << "Test data1";
    oss << "Test data2";
    oss << "Test data3";
    l_czTempStr = oss.str();
}
#elif VER=TEMPLATE
for (int i = 0; i < 100000; ++i)
{
    l_czTempStr = concatenate(s1, "Test data2", "Test data3");
}
#endif

#define STR_(x) #x
#define STR(x) STR_(x)

auto t1 = clock::now();
//std::cout << l_czTempStr << '\n';
std::cout << STR(VER) ": " << ms(t1-t0).count() << "ms\n";
}

Die Testanweisung:

for ARGTYPE in PLUS PLUS_EQ APPEND STRSTREAM TEMPLATE; do for i in `seq 4` ; do clang++ -std=c++11 -O3 -DVER=$ARGTYPE -Wall -pthread -pedantic main.cpp && ./a.out ; rm ./a.out ; done; done

Und Ergebnisse (verarbeitet über eine Tabelle, um die durchschnittliche Zeit anzuzeigen):

PLUS       23.5792   
PLUS       23.3812   
PLUS       35.1806   
PLUS       15.9394   24.5201
PLUS_EQ    15.737    
PLUS_EQ    15.3353   
PLUS_EQ    10.7764   
PLUS_EQ    25.245    16.773425
APPEND     22.954    
APPEND     16.9031   
APPEND     10.336    
APPEND     19.1348   17.331975
STRSTREAM  10.2063   
STRSTREAM  10.7765   
STRSTREAM  13.262    
STRSTREAM  22.3557   14.150125
TEMPLATE   16.6531   
TEMPLATE   16.629    
TEMPLATE   22.1885   
TEMPLATE   16.9288   18.09985

Die Überraschung strstreamscheint, dass C ++ 11 und spätere Verbesserungen viel Nutzen bringen. Wahrscheinlich hat das Entfernen der erforderlichen Zuordnung aufgrund der Einführung der Verschiebungssemantik einen gewissen Einfluss.

Sie können es selbst auf coliru testen

Bearbeiten: Ich habe den Test auf coliru aktualisiert, um g ++ - 4.8 zu verwenden: http://coliru.stacked-crooked.com/a/593dcfe54e70e409 . Ergebnisse in Grafik hier: g ++ - 4.8 Testergebnisse

(Erklärung - "stat. Durchschnitt" bedeutet Durchschnitt über alle Werte mit Ausnahme von zwei extremen - einem minimalen und einem maximalen Wert)

Yatsek
quelle
1
Es ist immer noch erwähnenswert, dass YMMV und Sie Ihre eigenen Benchmarks durchführen sollten, da meine Kompilierung gegen g ++ 4.8.5 mit verschiedenen anderen aktivierten Flags zu einer Stream-Leistung führte, die ungefähr doppelt so hoch ist wie die von + = und Anhängen sowie zu einer 50% igen Steigerung im Vergleich zu + .
Devyndraen
@devyndraen - 100% wahr - jeder Aspekt ist wichtig. 2x ist jedoch immer noch viel besser als ~ 20x, ursprünglich von Jesse Good berichtet . Hier sind meine (kombinierte - Summe von 4 Läufen) Ergebnisse mit g ++ - 7 BTW: PLUS: 18.49352, PLUS_EQ: 19.03214, APPEND: 18.70595, STRSTREAM: 19.17043, TEMPLATE: 21.98324
yatsek
versuchte, Tests mit g ++ - 4.8 auf coliru zu wiederholen: coliru.stacked-crooked.com/a/593dcfe54e70e409 , Grafik hier: i.imgur.com/w4TXPO3.png (stat. Durchschn. ist Durchschnitt aller minus min. und max. Werte)
Yatsek
0

Es gibt einige wichtige Parameter, die potenzielle Auswirkungen auf die Entscheidung über den "optimiertesten Weg" haben. Einige davon sind - Zeichenfolgen- / Inhaltsgröße, Anzahl der Operationen, Compileroptimierung usw.

In den meisten Fällen string::operator+=scheint es am besten zu funktionieren. Bei einigen Compilern wird jedoch manchmal auch beobachtet, dass dies am ostringstream::operator<<besten funktioniert [wie - MingW g ++ 3.2.3, 1,8 GHz Einzelprozessor Dell PC ]. Wenn der Compilerkontext kommt, sind es hauptsächlich die Optimierungen beim Compiler, die sich auswirken würden. Zu erwähnen ist auch, dass dies stringstreamsim Vergleich zu einfachen Zeichenfolgen komplexe Objekte sind und daher den Overhead erhöhen.

Für weitere Informationen - Diskussion , Artikel .

Parasrish
quelle