为什么std::string操作性能差？

Question

我做了一个测试，比较了几种编程语言在字符串操作上的表现，目的是为了选择一个适合服务器端应用的语言。结果看起来还不错，直到我试了C++，这让我大吃一惊。所以我想知道我是不是漏掉了什么优化，来这里寻求帮助。

这个测试主要是对字符串进行大量操作，包括拼接和搜索。测试是在Ubuntu 11.10 amd64上进行的，使用的是GCC 4.6.1版本。我的机器是戴尔Optiplex 960，配有4G内存和四核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或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

简要总结

好了，现在我们来看看总结：

• Nodejs上的Javascript (V8): 3.1秒
• CPython 2.7.2上的Python : 8.8秒
• 使用libstdc++的C++: 5.9秒
• OpenJDK 7上的Java: 50.4秒

真是令人惊讶！我在C++中尝试了“-O2, -O3”选项，但没有任何帮助。C++的性能似乎只有V8中Javascript的50%左右，甚至还不如CPython。有人能告诉我，我是不是在GCC中漏掉了什么优化，还是说这就是结果？非常感谢。

Answer 1

标准的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
系统时间 0m0.001s

Answer 2

我在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上的结果是时间: 3.37秒。（当然，这个结果有点可疑，但请先听我说完，等会儿会有其他结果。）

接下来我们把代码中的注释行互换，来测试追加操作，而不是查找。这次，我把循环的次数增加了十倍，想看看能否得到任何时间结果。

#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上的结果，尽管循环次数增加了十倍，却是时间: 0秒。

我的结论是：在C++中，这个基准测试主要受查找操作的影响，循环中的字符追加操作对结果没有任何影响。这真的是你想要的结果吗？

Answer 3

并不是说 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