最优化的串联方式

我们每天总是遇到很多情况，在代码中我们必须做繁琐而且非常多的string操作。 我们都知道string操作是昂贵的操作。 我想知道哪些是可用版本中最便宜的。

最常见的操作是串联（这是我们可以在一定程度上控制的东西）。 在C ++中连接std :: strings和各种解决方法以加快串联的最佳方式是什么？

我的意思是，

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

另外，我们可以通过使用CString而不是使用std :: string吗？

Answer 1

这里是一个小testing套件：

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

在coliru上 ：

编译如下：

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

它看起来像2) ， +=是胜利者。

（编译有和没有-pthread似乎影响时间）

Answer 2

除了其他的答案…

前一段时间，我对这个问题做了大量的基准testing，得出的结论是，在所有使用情况下，最有效的解决scheme（Linux x86 / x64 / ARM上的GCC 4.7＆4.8）首先reserve()来保存所有连接的string，然后只append()它们（或使用operator +=() ，这没有什么区别）。

不幸的是，我似乎删除了基准，所以你只有我的话（但是你可以很容易地适应Mats Petersson的基准来validation这一点，如果我的话是不够的）。

简而言之：

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

根据确切的用例（串联string的数量，types和大小），有时这种方法是最有效的，而有时这种方法与其他方法一致，但从不会更糟糕。

---

问题是，事先计算所需的总大小非常痛苦，特别是在混合string文本和std::string （上面的示例足够清晰，我相信）的时候。 这样的代码的可维护性是绝对可怕的，只要你修改其中一个文字或添加另一个string连接。

一种方法是使用sizeof来计算文字的大小，但恕我直言，它创造了比它解决的一样多的混乱，可维护性仍然是可怕的：

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

一个可用的解决scheme（C ++ 11，可变模板）

我终于find了一套有效的计算string大小的可变参数模板（例如，在编译时确定string的大小），根据需要reserve() ，然后连接所有的东西。

在这里，希望这是有用的：

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

就公共接口而言，唯一有趣的部分是最后一个template<typename... Strings> std::string concatenate(Strings&&... strings)模板。 用法很简单：

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

随着优化打开，任何体面的编译器应该能够扩展concatenate调用相同的代码，我手动写入所有东西的第一个例子。 就GCC 4.7和4.8而言，生成的代码与性能非常相似。

Answer 3

最糟糕的情况是使用普通的旧strcat （或sprintf ），因为strcat需要一个Cstring，并且必须“计数”才能find结尾。 对于长string，这是一个真正的性能受害者。 C ++风格的string要好得多，性能问题可能与内存分配有关，而不是计算长度。 但是再一次，琴弦几何增长（每次需要增长时翻倍），所以并不是那么糟糕。

我非常怀疑，所有上述方法的结果都是相同的，或者至less是非常相似的performance。 如果有的话，我期望stringstream是比较慢的，因为支持格式化的开销 – 但我也怀疑它是边缘的。

由于这种事情是“有趣的”，我会拿回一个基准…

编辑：

请注意，这些结果适用于使用g ++ 4.6.3编译的运行x86-64 Linux的MY机器。 其他操作系统，编译器和C ++运行时库实现可能会有所不同。 如果性能对于您的应用程序非常重要，那么使用您使用的编译器对基于您的系统进行基准testing。

这是我写的testing代码。 这可能不是真实场景的完美performance，但我认为这是一个具有代表性的场景：

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

以下是一些有代表性的结果

 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) 

相同的代码，以32位运行：

 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) 

由此可以得出结论：

1. 最好的select是一次追加（ out.append()或out += ），而“链接”方法相当接近。

2. 预分配string没有帮助。

3. 使用stringstream是相当可怜的想法（慢2-4倍之间）。

4. char *使用new char[] 。 在调用函数中使用局部variables使得它是最快的 – 但稍有不公平的比较。

5. 在组合短string时有相当多的开销 – 只需要复制数据，每个字节最多只有一个周期[除非数据不适合caching]。

EDIT2

根据意见添加：

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

和

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

这给出了这些结果：

 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) 

（32位运行，但64位显示非常相似的结果）。

Answer 4

与大多数微观优化一样，您需要测量每个选项的效果，通过测量首先确定这确实是一个值得优化的瓶颈。 没有确切的答案。

append和+=应该完全一样。

+在概念上效率较低，因为你正在创build和销毁临时对象。 您的编译器可能会或可能不会将其优化为与追加一样快。

使用总大小调用reserve可能会减less所需的内存分配数 – 它们可能是最大的瓶颈。

<< （可能在stringstream ）可能会也可能不会更快; 你需要测量一下。 如果您需要格式化非stringtypes，这很有用，但在处理string时可能不会特别好或更差。

CString的缺点是不可移植，像我这样的Unix黑客不能告诉你它的好处是什么，也可能不是。

Answer 5

有一些重要的参数，对决定“最优化的方式”有潜在的影响。 其中一些是 – string/内容大小，操作次数，编译器优化等。

在大多数情况下， string::operator+=似乎工作得最好。 然而有时候，在某些编译器上，也可以观察到ostringstream::operator<<最好[像 – MingW g ++ 3.2.3,1.8 GHz单处理器Dell PC ]。 当编译器的上下文到来，那么它主要是在编译器的影响优化。 还要提一下，与简单string相比，stringstream是复杂的对象，因此会增加开销。

有关更多信息 – 讨论 ， 文章 。