Il modo più ottimizzato di concatenazione nelle stringhe

Ci siamo sempre imbattuti in molte situazioni quotidiane in cui dobbiamo fare noiose e molte operazioni con le stringhe nel nostro codice. Sappiamo tutti che le manipolazioni delle stringhe sono operazioni costose. Vorrei sapere qual è il meno costoso tra le versioni disponibili.

Le operazioni più comuni sono la concatenazione (questo è qualcosa che possiamo controllare in una certa misura). Qual è il modo migliore per concatenare std :: string in C ++ e varie soluzioni alternative per accelerare la concatenazione?

Intendo,

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

Inoltre, abbiamo qualche vantaggio nell’usare CString su std :: string?

Ecco una piccola suite di test:

 #include  #include  #include  #include  int main () { typedef std::chrono::high_resolution_clock clock; typedef std::chrono::duration 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"; } 

Sul coliru :

Compilare con il seguente:

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

21.6463ms

-DVER = 2

6.61773ms

-DVER = 3

6.7855ms

-DVER = 4

102.015ms

Sembra 2) , += è il vincitore.

(Anche la compilazione con e senza -pthread sembra influenzare i tempi)

Oltre alle altre risposte …

Ho fatto alcuni benchmark approfonditi su questo problema qualche tempo fa e sono giunto alla conclusione che la soluzione più efficiente (GCC 4.7 e 4.8 su Linux x86 / x64 / ARM) in tutti i casi d’uso è prima di reserve() la stringa risultante con abbastanza spazio per contenere tutte le stringhe concatenate e quindi append() (o usare l’ operator +=() , che non fa differenza).

Sfortunatamente sembra che abbia cancellato quel benchmark in modo da avere solo la mia parola (ma puoi facilmente adattare il benchmark di Mats Petersson per verificarlo da solo, se la mia parola non è abbastanza).

In poche parole:

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

A seconda del caso d’uso esatto (numero, tipi e dimensioni delle stringhe concatenate), a volte questo metodo è di gran lunga il più efficiente, e altre volte è alla pari con altri metodi, ma non è mai peggiore.


Il problema è che questo è davvero doloroso calcolare in anticipo le dimensioni totali richieste, specialmente quando si mescolano stringhe letterali e std::string (credo che l’esempio sopra sia abbastanza chiaro in merito). La manutenibilità di tale codice è assolutamente orribile non appena si modifica uno dei letterali o si aggiunge un’altra stringa da concatenare.

Un approccio sarebbe quello di usare sizeof per calcolare la dimensione dei letterali, ma IMHO crea tanto disordine di quanto risolva, la manutenibilità è ancora terribile:

 #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; 

Una soluzione utilizzabile (C ++ 11, modelli variadici)

Alla fine ho optato per una serie di modelli variadici che si occupano in modo efficiente del calcolo delle dimensioni delle stringhe (ad esempio la dimensione dei letterali stringa è determinata al momento della compilazione), reserve() secondo necessità e quindi concatenano tutto.

Eccolo, spero che questo sia utile:

 namespace detail { template struct string_size_impl; template struct string_size_impl { static constexpr size_t size(const char (&) [N]) { return N - 1; } }; template struct string_size_impl { static size_t size(char (&s) [N]) { return N ? strlen(s) : 0; } }; template<> struct string_size_impl { static size_t size(const char* s) { return s ? strlen(s) : 0; } }; template<> struct string_size_impl { static size_t size(char* s) { return s ? strlen(s) : 0; } }; template<> struct string_size_impl { static size_t size(const std::string& s) { return s.size(); } }; template size_t string_size(String&& s) { using noref_t = typename std::remove_reference::type; using string_t = typename std::conditional::value, noref_t, typename std::remove_cv::type >::type; return string_size_impl::size(s); } template struct concatenate_impl; template struct concatenate_impl { static size_t size(String&& s) { return string_size(s); } static void concatenate(std::string& result, String&& s) { result += s; } }; template struct concatenate_impl { static size_t size(String&& s, Rest&&... rest) { return string_size(s) + concatenate_impl::size(std::forward(rest)...); } static void concatenate(std::string& result, String&& s, Rest&&... rest) { result += s; concatenate_impl::concatenate(result, std::forward(rest)...); } }; } // namespace detail template std::string concatenate(Strings&&... strings) { std::string result; result.reserve(detail::concatenate_impl::size(std::forward(strings)...)); detail::concatenate_impl::concatenate(result, std::forward(strings)...); return result; } 

L’unica parte interessante, per quanto riguarda l’interfaccia pubblica, è l’ultimo template std::string concatenate(Strings&&... strings) . L’utilizzo è semplice:

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

Con le ottimizzazioni triggerste, qualsiasi compilatore decente dovrebbe essere in grado di espandere la chiamata concatenate allo stesso codice del mio primo esempio in cui ho scritto manualmente tutto. Per quanto riguarda GCC 4.7 e 4.8, il codice generato è praticamente identico così come le prestazioni.

Il peggior scenario ansible è l’utilizzo di semplici strcat vecchi (o sprintf ), dal momento che strcat accetta una stringa C e che deve essere “contata” per trovare la fine. Per le corde lunghe, questo è un vero malato delle prestazioni. Le stringhe di stile C ++ sono molto migliori e i problemi di prestazioni sono probabilmente dovuti all’allocazione della memoria, piuttosto che al conteggio delle lunghezze. Ma poi di nuovo, la corda cresce geometricamente (raddoppia ogni volta che ha bisogno di crescere), quindi non è così terribile.

Sospetto molto che tutti i suddetti metodi finiscano con le stesse prestazioni, o per lo meno molto simili. Se mai, mi aspetto che lo stringstream sia più lento, a causa del sovraccarico nel supportare la formattazione, ma sospetto anche che sia marginale.

Dato che questo genere di cose è “divertente”, tornerò con un punto di riferimento …

Modificare:

Nota che questi risultati si applicano alla mia macchina, con Linux x86-64, compilato con g ++ 4.6.3. Altre implementazioni di librerie di runtime di sistemi operativi, compilatori e C ++ possono variare. Se le prestazioni sono importanti per la tua applicazione, quindi fai un benchmark sui sistemi che sono fondamentali per te, usando il / i compilatore / i che usi.

Ecco il codice che ho scritto per testarlo. Potrebbe non essere la rappresentazione perfetta di uno scenario reale, ma penso che sia uno scenario rappresentativo:

 #include  #include  #include  #include  #include  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 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 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; } } 

Ecco alcuni risultati rappresentativi:

 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) 

Lo stesso codice, eseguito come 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) 

Da questo, possiamo concludere:

  1. L'opzione migliore è l'aggiunta di un bit alla volta ( out.append() o out += ), con l'approccio "concatenato" ragionevolmente vicino.

  2. La pre-allocazione della stringa non è utile.

  3. L'utilizzo di stringstream è un'idea piuttosto scarsa (tra 2-4x più lento).

  4. Il char * utilizza il new char[] . L'utilizzo di una variabile locale nella funzione di chiamata lo rende il più veloce, ma leggermente ingiusto, per compararlo.

  5. C'è un bel po 'di overhead nel combinare una stringa breve: solo i dati di copia dovrebbero essere al massimo un ciclo per byte [a meno che i dati non si adattino alla cache].

EDIT2

Aggiunto, come da commenti:

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

e

 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; } 

Quale dà questi risultati:

 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) 

(Un'esecuzione a 32 bit, ma il 64-bit mostra risultati molto simili su questi).

Come con la maggior parte delle micro-ottimizzazioni, è necessario misurare l’effetto di ciascuna opzione, avendo stabilito in primo luogo attraverso la misurazione che si tratta di un collo di bottiglia che vale la pena ottimizzare. Non c’è una risposta definitiva.

append e += dovrebbero fare esattamente la stessa cosa.

+ è concettualmente meno efficiente, dal momento che stai creando e distruggendo i provvisori. Il tuo compilatore potrebbe o potrebbe non essere in grado di ottimizzarlo per essere veloce quanto aggiungerlo.

Chiamare la reserve con la dimensione totale può ridurre il numero di allocazioni di memoria necessarie: probabilmente saranno il collo di bottiglia più grande.

<< (presumibilmente su uno stringstream ) può essere o non essere più veloce; dovrai misurarlo. È utile se è necessario formattare i tipi non stringa, ma probabilmente non sarà particolarmente migliore o peggiore nel gestire le stringhe.

CString ha lo svantaggio di non essere portabile e che un hacker Unix come me non può dirti quali potrebbero essere i suoi vantaggi o meno.

Ho deciso di eseguire un test con il codice fornito dall’utente Jesse Good , leggermente modificato per tenere conto dell’osservazione di Rapptz , in particolare il fatto che lo stringstream è stato costruito in ogni singola iterazione del loop. Pertanto ho aggiunto alcuni casi, un paio dei quali è stato ostreggiato con la sequenza ” oss.str (” “); oss.clear ()

Ecco il codice

 #include  #include  #include  #include  #include  template  void time_measurement(F f, const std::string& comment) { typedef std::chrono::high_resolution_clock clock; typedef std::chrono::duration mil; std::string r; auto t0 = clock::now(); f(r); auto t1 = clock::now(); std::cout << "\n-------------------------" << comment << "-------------------\n" < 

Ecco i risultati:

 /* 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 --------------------------------------------------------------------------- */ 

Ora usare std :: string è ancora più veloce, e l'append è ancora il modo più veloce di concatenazione, ma ostringstream non è più così terribilmente terribile come prima.

Ci sono alcuni parametri significativi, che hanno un potenziale impatto sulla decisione del “modo più ottimizzato”. Alcuni di questi sono: dimensioni stringa / contenuto, numero di operazioni, ottimizzazione del compilatore, ecc.

Nella maggior parte dei casi, string::operator+= sembra funzionare meglio. Tuttavia, a volte, su alcuni compilatori, si osserva anche che ostringstream::operator<< funziona meglio [come - MingW g ++ 3.2.3, 1,8 GHz con processore singolo PC Dell ]. Quando arriva il contesto del compilatore, allora è in modo rilevante l'ottimizzazione del compilatore che potrebbe avere un impatto. Inoltre, le stringstreams sono oggetti complessi rispetto alle stringhe semplici e pertanto si aggiungono al sovraccarico.

Per maggiori informazioni - discussione , articolo .