为什么std :: string操作性能不佳?

我做了一个testing,比较几种语言的string操作,为服务器端应用程序select一种语言。 结果似乎是正常的,直到我终于尝试C ++,这让我很吃惊。 所以我想知道我是否错过了任何优化,并来这里寻求帮助。

testing主要是密集的string操作,包括连接和search。 testing在Ubuntu 11.10 amd64上执行,GCC版本为4.6.1。 该机器是戴尔Optiplex 960,具有4G RAM和四核CPU。

在Python(2.7.2)中:

def test(): x = "" limit = 102 * 1024 while len(x) < limit: x += "X" if x.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0: print("Oh my god, this is impossible!") print("x's length is : %d" % len(x)) test() 

这给出了结果:

 x's length is : 104448 real 0m8.799s user 0m8.769s sys 0m0.008s 

在Java(OpenJDK-7)中:

 public class test { public static void main(String[] args) { int x = 0; int limit = 102 * 1024; String s=""; for (; s.length() < limit;) { s += "X"; if (s.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ") > 0) System.out.printf("Find!\n"); } System.out.printf("x's length = %d\n", s.length()); } } 

这给出了结果:

 x's length = 104448 real 0m50.436s user 0m50.431s sys 0m0.488s 

在Javascript(Nodejs 0.6.3)

 function test() { var x = ""; var limit = 102 * 1024; while (x.length < limit) { x += "X"; if (x.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0) console.log("OK"); } console.log("x's length = " + x.length); }(); 

这给出了结果:

 x's length = 104448 real 0m3.115s user 0m3.084s sys 0m0.048s 

在C ++(g ++ -Ofast)

Nodejs比Python或Javaperformance更好,这并不奇怪。 但是我期望libstdc ++会比Nodejs更好的性能,其结果真让我惊讶。

 #include <iostream> #include <string> using namespace std; void test() { int x = 0; int limit = 102 * 1024; string s(""); for (; s.size() < limit;) { s += "X"; if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != string::npos) cout << "Find!" << endl; } cout << "x's length = " << s.size() << endl; } int main() { test(); } 

这给出了结果:

 x length = 104448 real 0m5.905s user 0m5.900s sys 0m0.000s 

小结

好的,现在让我们看看总结:

  • JavaScript上的Nodejs(V8):3.1s
  • Python上的CPython 2.7.2:8.8s
  • C ++与libstdc ++:5.9s
  • Java在OpenJDK 7:50.4s

出奇! 我在C ++中尝试了“-O2,-O3”,但注意到了帮助。 C ++似乎在V8中只有50%的JavaScript性能,甚至比CPython差。 任何人都可以向我解释,如果我错过了海湾合作委员会的一些优化或是这样的情况? 万分感谢。

12 Solutions collect form web for “为什么std :: string操作性能不佳?”

这不是说std::stringperformance不佳(就像我不喜欢C ++一样),那就是string处理对于其他语言来说已经大大优化了。

你们比较弦乐表演的方式是误导性的,如果它们不仅仅是为了表示这些,那么就是放肆的。

我知道一个事实,即Pythonstring对象完全是用C实现的 ,实际上在Python 2.7中,由于unicodestring和字节之间没有分离,存在许多 优化 。 如果你在Python 3.x上运行这个testing,你会发现它相当慢。

JavaScript有许多重度优化的实现。 可以预料的是,string处理在这里非常出色。

你的Java结果可能是由于正确的string处理,或其他一些糟糕的情况。 我希望Java专家可以介入并修改这个testing。

至于你的C ++的例子,我希望性能稍微超过Python版本。 它执行相同的操作,解释器开销较less。 这反映在你的结果。 在s.reserve(limit);之前进行testings.reserve(limit); 将删除重新分配的开销。

我会重申,你只是testing语言实现的单一方面。 这个testing的结果并不能反映整个语言的速度。

我已经提供了一个C版本来展示这样的小事如何愚蠢的比赛:

 #define _GNU_SOURCE #include <string.h> #include <stdio.h> void test() { int limit = 102 * 1024; char s[limit]; size_t size = 0; while (size < limit) { s[size++] = 'X'; if (memmem(s, size, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) { fprintf(stderr, "zomg\n"); return; } } printf("x's length = %zu\n", size); } int main() { test(); return 0; } 

定时:

 matt@stanley:~/Desktop$ time ./smash x's length = 104448 real 0m0.681s user 0m0.680s sys 0m0.000s 

所以我在ideone.org上玩了一下。

这里有一个你的原始C ++程序稍微修改过的版本,但在循环中添加消除,所以它只测量对std::string::find()的调用。 请注意,我必须将迭代次数减less到〜40%,否则ideone.org将会终止进程。

 #include <iostream> #include <string> int main() { const std::string::size_type limit = 42 * 1024; unsigned int found = 0; //std::string s; std::string s(limit, 'X'); for (std::string::size_type i = 0; i < limit; ++i) { //s += 'X'; if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos) ++found; } if(found > 0) std::cout << "Found " << found << " times!\n"; std::cout << "x's length = " << s.size() << '\n'; return 0; } 

我在ideone.org的结果是time: 3.37s 。 (当然,这是非常可疑的,但放纵一下,等待另一个结果。)

现在我们把这个代码和交换注释行,来testing追加,而不是find。 请注意,这一次,我试图查看任何时间的结果,增加了十倍的迭代次数。

 #include <iostream> #include <string> int main() { const std::string::size_type limit = 1020 * 1024; unsigned int found = 0; std::string s; //std::string s(limit, 'X'); for (std::string::size_type i = 0; i < limit; ++i) { s += 'X'; //if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos) // ++found; } if(found > 0) std::cout << "Found " << found << " times!\n"; std::cout << "x's length = " << s.size() << '\n'; return 0; } 

尽pipe迭代次数增加了十倍,但我在ideone.org的结果是time: 0s

我的结论是:这个基准在C ++中是高度被search操作支配的 ,循环中字符的附加对结果根本没有影响。 那真的是你的意图吗?

惯用的C ++解决scheme是:

 #include <iostream> #include <string> #include <algorithm> int main() { const int limit = 102 * 1024; std::string s; s.reserve(limit); const std::string pattern("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); for (int i = 0; i < limit; ++i) { s += 'X'; if (std::search(s.begin(), s.end(), pattern.begin(), pattern.end()) != s.end()) std::cout << "Omg Wtf found!"; } std::cout << "X's length = " << s.size(); return 0; } 

我可以通过将string放在堆栈上,并使用memmem来加快速度 – 但似乎没有必要。 在我的机器上运行,这已经是python解决scheme速度的10倍多了。

[在我的笔记本上]

time ./test X's length = 104448 real 0m2.055s user 0m2.049s sys 0m0.001s

这是最明显的一个:请尝试做s.reserve(limit); 在主循环之前。

文档在这里 。

我应该提到,直接使用C ++中的标准类,就像您使用Java或Python所做的那样,如果您不了解桌面背后所做的工作,通常可以获得低于标准的性能。 语言本身没有神奇的performance,它只是给你正确的工具。

你在这里失踪的是查找search的固有复杂性。

您正在执行search102 * 1024 (104 448)次。 一个天真的searchalgorithm,将每次尝试匹配模式从第一个字符开始,然后第二个等…

因此,你有一个从长度为1N的string,并且在每一步你都要在这个string中search模式,这是C ++中的一个线性操作。 那就是N * (N+1) / 2 = 5 454 744 576比较。 我并不感到惊讶,因为这需要一些时间。

让我们通过使用find的重载来validation这个假设,即search单个A

 Original: 6.94938e+06 ms Char : 2.10709e+06 ms 

快大约3倍,所以我们在同一个数量级内。 因此,使用完整的string并不是很有趣。

结论? 也许这个find可以优化一下。 但问题是不值得的。

注意:对那些吹嘘Boyer Moore的人来说,恐怕针头太小了,所以没有多大的帮助。 可能会削减一个数量级(26个字符),但没有更多。

我的第一个想法是没有问题。

C ++提供了第二好的性能,比Java快了近十倍。 也许除了Java之外,其他所有的function都可以达到最佳性能,而且你应该看看如何解决Java的问题(提示StringBuilder )。

在C ++的情况下,有一些事情可以尝试提高性能。 尤其是…

  • s += 'X'; 而不是s += "X";
  • 声明string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); 在循环之外,并通过这个find调用。 一个std::string实例知道它自己的长度,而一个Cstring需要一个线性时间检查来确定,这可能(或者可能不)与std::string::find性能有关。
  • 尝试使用std::stringstream ,出于类似的原因,为什么你应该使用StringBuilder for Java,尽pipe很可能重复转换回string会产生更多的问题。

总的来说,结果并不令人吃惊。 具有良好的JIT编译器的JavaScript可能会比C ++静态编译在这种情况下允许优化一点。

有了足够的工作,您应该始终能够比JavaScript更好地优化C ++,但总会有一些情况不仅仅是自然发生,而且可能需要一定的知识和努力才能实现。

对于C ++,尝试使用std::string作为“ABCDEFGHIJKLMNOPQRSTUVWXYZ” – 在我的实现中string::find(const charT* s, size_type pos = 0) const计算string参数的长度。

我只是自己testing了C ++的例子。 如果我删除了对std::sting::find的调用,程序立即终止。 因此,string连接期间的分配在这里没有问题。

如果我添加一个variablessdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"并在std::string::find的调用中replace“ABC … XYZ”的出现,程序几乎需要与原始例。 这再一次表明,分配以及计算string的长度并不会增加运行时间。

因此,libstdc ++使用的stringsearchalgorithm似乎不像JavaScript或python的searchalgorithm那么快。 也许你想用你自己的stringsearchalgorithm再次尝试C ++,它更适合你的目的。

C / C ++语言并不容易,需要数年才能制作出快速的程序。

与从c版本修改的strncmp(3)版本:

 #define _GNU_SOURCE #include <string.h> #include <stdio.h> void test() { int limit = 102 * 1024; char s[limit]; size_t size = 0; while (size < limit) { s[size++] = 'X'; if (!strncmp(s, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) { fprintf(stderr, "zomg\n"); return; } } printf("x's length = %zu\n", size); } int main() { test(); return 0; } 

看来,在nodejssearch子string更好的algorithm。 你可以实现自我并尝试。

您的testing代码正在检查过多string连接的病态情况。 (testing中的stringsearch部分可能已经被忽略了,我敢打赌,它对最终结果几乎没有任何贡献)。过多的string连接是大多数语言警告非常强烈的一个缺陷,并且提供了众所周知的替代方法, (即StringBuilder),所以你在本质上testing的是这些语言在完全预期的失败情况下失败的程度。 这没有意义。

一个类似的毫无意义的testing的例子是比较各种语言在紧密循环中抛出和捕获exception时的性能。 所有的语言都警告说,exception抛出和捕获是非常缓慢的。 他们没有指定有多慢,他们只是警告你不要指望什么。 因此,要准确地进行testing,是毫无意义的。

因此,为了避免string连接,重复使用无意义string连接部分(s + =“X”)来替代这些语言中的每一个所提供的任何构造,会更有意义。 (比如类StringBuilder。)

正如sbi所提到的,testing用例由search操作占主导地位。 我很好奇C ++和Javascript之间的文本分配比较有多快。

系统:Raspberry Pi 2,g ++ 4.6.3,节点v0.12.0,g ++ -std = c ++ 0x -O2 perf.cpp

C ++:770ms

C ++无预留:1196ms

Javascript:2310ms

C ++

 #include <iostream> #include <string> #include <chrono> using namespace std; using namespace std::chrono; void test() { high_resolution_clock::time_point t1 = high_resolution_clock::now(); int x = 0; int limit = 1024 * 1024 * 100; string s(""); s.reserve(1024 * 1024 * 101); for(int i=0; s.size()< limit; i++){ s += "SUPER NICE TEST TEXT"; } high_resolution_clock::time_point t2 = high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count(); cout << duration << endl; } int main() { test(); } 

JavaScript的

 function test() { var time = process.hrtime(); var x = ""; var limit = 1024 * 1024 * 100; for(var i=0; x.length < limit; i++){ x += "SUPER NICE TEST TEXT"; } var diff = process.hrtime(time); console.log('benchmark took %d ms', diff[0] * 1e3 + diff[1] / 1e6 ); } test(); 
  • 将地图值复制到STL中的vector
  • 用gdb检查标准容器(std :: map)的内容
  • 将调用std :: vector :: clear()将std :: vector :: capacity()设置为零?
  • 为什么std :: map实现为红黑树?
  • 如何迭代一个priority_queue?
  • 为什么要使用函子而不是函数?
  • std :: make_pair与std :: pair的构造函数的目的是什么?
  • 如何反转C ++向量?
  • boost是否具有比STL更简单的set操作的数据types?
  • 迭代器>第二个是什么意思?
  • std :: string是STL的一部分吗?