Wu *_*Shu 59 c++ python performance stl node.js
我做了一个测试来比较几种语言的字符串操作,以便为服务器端应用程序选择一种语言.结果似乎很正常,直到我最终尝试了C++,这让我感到非常惊讶.所以我想知道我是否错过了任何优化并来到这里寻求帮助.
测试主要是密集的字符串操作,包括连接和搜索.测试在Ubuntu 11.10 amd64上进行,GCC版本为4.6.1.该机器是戴尔Optiplex 960,配备4G内存和四核CPU.
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
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
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
Nodejs的性能优于Python或Java,这并不奇怪.但我希望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
好的,现在让我们看一下摘要:
出奇!我在C++中尝试了"-O2,-O3"但注意到了帮助.在V8中,C++似乎只有50%的javascript性能,甚至比CPython差.任何人都可以向我解释我是否错过了海湾合作委员会的一些优化或者情况如何？非常感谢.
Mat*_*ner 71
这并不是std::string表现不佳(尽管我不喜欢C++),而是字符串处理对其他语言进行了大量优化.
你对字符串性能的比较是误导性的,如果它们不仅仅是为了代表它们,那么它就是冒昧的.
我知道Python字符串对象完全用C实现,事实上在Python 2.7上,由于unicode字符串和字节之间缺乏分离,因此存在大量 优化.如果你在Python 3.x上运行这个测试,你会发现它相当慢.
Javascript有许多经过大量优化的实现.可以预期,字符串处理非常好.
您的Java结果可能是由于不正确的字符串处理或其他一些不良情况造成的.我希望Java专家可以介入并通过一些更改来修复此测试.
至于你的C++示例,我希望性能稍微超过Python版本.它执行相同的操作,减少了解释器开销.这反映在您的结果中.在测试之前s.reserve(limit);将删除重新分配开销.
我再说一遍,你只测试语言实现的一个方面.此测试的结果不反映整体语言速度.
我已经提供了一个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
sbi*_*sbi 34
所以我去了ideone.org上玩了一下.
这里是原始C++程序的略微修改版本,但是在循环中附加消除,所以它只测量调用std::string::find().请注意,我必须将迭代次数减少到~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.(当然,这是非常值得怀疑的,但请放纵我一会儿等待其他结果.)
现在我们采用此代码并交换注释行,以测试追加,而不是查找.请注意,这一次,我在尝试查看任何时间结果时增加了十倍的迭代次数.
#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;
}
尽管迭代次数增加了十倍,但我在ideone.org上的结果是time: 0s.
我的结论:在C++中,这个基准是由搜索操作高度支配的,循环中字符的追加对结果没有任何影响.这真的是你的意图吗？
Hep*_*tic 14
惯用的C++解决方案是:
#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;
}
我可以通过将字符串放在堆栈上并使用memmem来大大提高速度 - 但似乎没有必要.在我的机器上运行,这已经超过python解决方案的速度的10倍..
[在我的笔记本上]
时间./test X的长度= 104448实际0m2.055s用户0m2.049s sys 0m0.001s
您在这里缺少的是查找搜索的固有复杂性.
您正在执行搜索102 * 1024(104 448)次.一个天真的搜索算法,每次都会尝试匹配从第一个字符开始,然后是第二个字符等的模式......
因此,您有一个从长度1到字符串的字符串N,并且在每一步中您都会针对此字符串搜索模式,这是C++中的线性操作.这是N * (N+1) / 2 = 5 454 744 576比较.我并不像你那样惊讶,这需要一些时间......
让我们通过使用find搜索单个的重载来验证假设A:
Original: 6.94938e+06 ms
Char : 2.10709e+06 ms
大约快3倍,因此我们处于同一数量级.因此,使用完整的字符串并不是很有趣.
结论？也许这find可以稍微优化一下.但问题不值得.
注意:对于那些吹嘘Boyer Moore的人,我担心针太小了,所以它无济于事.可能会减少一个数量级(26个字符),但不会更多.
我的第一个想法是没有问题.
C++提供了第二好的性能,比Java快近十倍.也许除了Java之外的所有功能都接近该功能可实现的最佳性能,您应该考虑如何修复Java问题(提示 - StringBuilder).
在C++的情况下,有一些事情要尝试提高性能.特别是...
s += 'X'; 而不是 s += "X";string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ");在循环外声明,并将其传递给find调用.一个std::string实例知道它自己的长度,而C字符串需要线性时间的检查,以确定这一点,这可能(也可能不会)是相关的std::string::find性能.std::stringstream,出于类似的原因,为什么你应该使用StringBuilderJava,虽然很可能重复转换string将产生更多的问题.总的来说,结果并不令人惊讶.具有良好JIT编译器的JavaScript可能能够比在这种情况下允许C++静态编译更好地优化.
有了足够的工作,你应该总是能够比JavaScript更好地优化C++,但总会有这样的情况,这不仅仅是自然发生的,也可能需要相当多的知识和努力才能实现.