La forma más optimizada de concatenación en cadenas

Siempre nos encontramos con muchas situaciones a diario en las que tenemos que hacer tediosas y muchas operaciones de cadena en nuestro código. Todos sabemos que las manipulaciones de cadenas son operaciones costosas. Me gustaría saber cuál es la menos costosa entre las versiones disponibles.

Las operaciones más comunes son la concatenación (esto es algo que podemos controlar en cierta medida). ¿Cuál es la mejor manera de concatenar std :: strings en C ++ y varias soluciones para acelerar la concatenación?

Quiero decir,

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

Además, ¿tenemos alguna ventaja de usar CString sobre std :: string?

Aquí hay un pequeño conjunto de pruebas:

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

En coliru :

Comstack con lo siguiente:

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

21.6463 ms

-DVER = 2

6.61773ms

-DVER = 3

6.7855ms

-DVER = 4

102.015ms

Parece que 2) , += es el ganador.

(También comstackr con y sin -pthread parece afectar los tiempos)

Además de otras respuestas …

Hice puntos de referencia extensos sobre este problema hace algún tiempo y llegué a la conclusión de que la solución más eficiente (GCC 4.7 y 4.8 en Linux x86 / x64 / ARM) en todos los casos de uso es primero reserve() la cadena resultante con suficiente espacio para mantener todas las cadenas concatenadas, y luego solo append() o usar el operator +=() , eso no hace ninguna diferencia).

Lamentablemente, parece que borré ese punto de referencia, así que solo tienes mi palabra (pero puedes adaptar fácilmente el punto de referencia de Mats Petersson para verificarlo por ti mismo, si mi palabra no es suficiente).

En una palabra:

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

Dependiendo del caso de uso exacto (número, tipos y tamaños de las cadenas concatenadas), a veces este método es con mucho el más eficiente, y otras veces está a la par con otros métodos, pero nunca es peor.


El problema es que esto es realmente doloroso para calcular el tamaño total requerido de antemano, especialmente cuando se mezclan cadenas literales y std::string (el ejemplo anterior es lo suficientemente claro en ese sentido, creo). El mantenimiento de dicho código es absolutamente horrible tan pronto como modifique uno de los literales o agregue otra cadena para concatenar.

Un enfoque sería usar sizeof para calcular el tamaño de los literales, pero en mi humilde opinión crea tanto lío de lo que resuelve, el mantenimiento es aún terrible:

 #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 solución utilizable (C ++ 11, plantillas variadas)

Finalmente me conformé con un conjunto de plantillas variadas que de manera eficiente se encargan de calcular los tamaños de cadena (por ejemplo, el tamaño de los literales de cadena se determina en tiempo de comstackción), reserve() según sea necesario y luego concatenar todo.

Aquí está, espero que esto sea útil:

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

La única parte interesante, en lo que se refiere a la interfaz pública, es la template std::string concatenate(Strings&&... strings) última template std::string concatenate(Strings&&... strings) . El uso es directo:

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

Con las optimizaciones activadas, cualquier comstackdor decente debería poder expandir la llamada de concatenate al mismo código que mi primer ejemplo donde escribí todo manualmente. En lo que respecta a GCC 4.7 y 4.8, el código generado es prácticamente idéntico al rendimiento.

El peor escenario posible es el uso de strcat simple (o sprintf ), ya que strcat toma una cadena C, y eso tiene que “contarse” para encontrar el final. Para cuerdas largas, eso es una verdadera víctima del rendimiento. Las cadenas de estilo de C ++ son mucho mejores, y los problemas de rendimiento probablemente sean con la asignación de memoria, en lugar de las longitudes de conteo. Pero, una vez más, la cuerda crece geométricamente (se dobla cada vez que necesita crecer), así que no es tan terrible.

Sospecho que todos los métodos anteriores terminan con el mismo rendimiento, o al menos muy similar. En todo caso, espero que el stringstream sea ​​más lento, debido a la sobrecarga en el formato de soporte, pero también sospecho que es marginal.

Como este tipo de cosas son “divertidas”, regresaré con un punto de referencia …

Editar:

Tenga en cuenta que estos resultados se aplican a MI máquina, ejecutando x86-64 Linux, comstackdo con g ++ 4.6.3. Otros sistemas operativos, comstackdores y implementaciones de la biblioteca en tiempo de ejecución C ++ pueden variar. Si el rendimiento es importante para su aplicación, realice una evaluación comparativa de los sistemas que son críticos para usted, utilizando el (los) comstackdor (es) que usa.

Aquí está el código que escribí para probar esto. Puede que no sea la representación perfecta de un escenario real, pero creo que es un escenario representativo:

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

Aquí hay algunos resultados representativos:

 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) 

Mismo código, ejecute como 32 bits:

 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) 

De esto, podemos concluir:

  1. La mejor opción se agrega un poco a la vez ( out.append() o out += ), con el enfoque "encadenado" razonablemente cerca.

  2. Preasignar la cadena no es útil.

  3. Usar stringstream es una idea bastante pobre (entre 2 y 4 veces más lenta).

  4. El char * usa un new char[] . Usar una variable local en la función de llamada lo convierte en el más rápido, pero ligeramente injusto para compararlo.

  5. Hay un poco de sobrecarga al combinar series cortas: solo copiar los datos debe ser como máximo de un ciclo por byte [a menos que los datos no quepan en el caché].

edit2

Agregado, según los comentarios:

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

y

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

Que da estos resultados:

 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) 

(Una ejecución de 32 bits, pero la de 64 bits muestra resultados muy similares en estos).

Al igual que con la mayoría de las micro-optimizaciones, necesitará medir el efecto de cada opción, habiendo establecido primero a través de la medición que esto es realmente un cuello de botella que vale la pena optimizar. No hay una respuesta definitiva.

append y += deberían hacer exactamente lo mismo.

+ es conceptualmente menos eficiente, ya que estás creando y destruyendo temporales. Su comstackdor puede o no ser capaz de optimizar esto para que sea tan rápido como agregar.

La reserve llamadas con el tamaño total puede reducir el número de asignaciones de memoria necesarias, probablemente sean el mayor cuello de botella.

<< (presumiblemente en una stringstream ) puede o no ser más rápido; deberás medir eso. Es útil si necesita formatear tipos que no sean cadenas, pero probablemente no será particularmente mejor o peor al tratar con cadenas.

CString tiene la desventaja de que no es portátil, y que un pirata informático de Unix como yo no puede decirle cuáles pueden ser sus ventajas o no.

Decidí ejecutar una prueba con el código proporcionado por el usuario Jesse Good , ligeramente modificado para tener en cuenta la observación de Rapptz , específicamente el hecho de que el ostringstream se construyó en cada iteración del ciclo. Por lo tanto, agregué algunos casos, algunos de ellos siendo el ostringstream despejado con la secuencia ” oss.str (” “); oss.clear ()

Aquí está el código

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

Aquí están los resultados:

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

Ahora, usar std :: string es aún más rápido, y el append sigue siendo la forma más rápida de concatenación, pero ostringstream no es tan increíblemente terrible como lo era antes.

Hay algunos parámetros importantes que tienen un impacto potencial al decidir la “forma más optimizada”. Algunos de estos son: tamaño de cadena / contenido, número de operaciones, optimización del comstackdor, etc.

En la mayoría de los casos, string::operator+= parece estar funcionando mejor. Sin embargo, a veces, en algunos comstackdores, también se observa que ostringstream::operator<< funciona mejor [como - MingW g ++ 3.2.3, PC Dell de un solo procesador a 1.8 GHz ]. Cuando llega el contexto del comstackdor, lo que más impactaría serían las optimizaciones en el comstackdor. Además, mencionar que las stringstreams son objetos complejos en comparación con cadenas simples y, por lo tanto, se sumn a la sobrecarga.

Para más información - discusión , artículo .