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

Question

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

64

我做了一个测试，比较了几种语言在字符串操作方面的性能，以便选择一个适合服务器端应用的语言。结果看起来都很正常，直到我尝试了C++，这让我非常惊讶。因此，我想知道是否错过了任何优化，并在这里寻求帮助。

测试主要涉及字符串的密集操作，包括连接和搜索。测试是在Ubuntu 11.10 amd64上进行的，使用的是GCC 4.6.1版本。机器是Dell 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或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

简要总结

好的，现在让我们看一下总结：

Node.js（V8引擎）中的JavaScript：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中的优化方法，或者这就是情况？非常感谢。

- Wu Shu

17

你正在测试一个操作的混合体，你可能应该尝试将测试分成不同的测试来执行不同的性能检查，例如：增加字符串、查找等。目前你无法知道时间花费在哪里。顺便说一下，这可能是一个相当无用的测试，不能决定使用哪种语言。 - David Rodríguez - dribeas

21

在循环之前尝试使用s.reserve(limit);。 - PlasmaHH

22

可能是因为Java中的字符串是不可变的。我猜s += "X"在这里会成为性能杀手。这就是为什么有StringBuilder存在的原因。 - R. Martinho Fernandes

27

在 Java 中，字符串是不可变的并且被池化，因此速度很慢。通常使用 StringBuilder 来组装字符串。总之，这整个比较就像是在比较苹果和橘子。 - PlasmaHH

9

你的结果中还包括每种语言的运行时启动和终止。 - R. Martinho Fernandes

显示剩余17条评论

12个回答

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++中，这个基准测试非常受搜索操作的影响，循环中字符的添加对结果没有任何影响。这真的是你的目的吗？

- sbi

5

@sbi: 这就是当人们注意到在 C++ 中 find 的时间复杂度为 O(N) 而在 Python 中 indexOf 使用 Boyer-Moore 算法（正如 Duncan 在评论中所指出的）的时候。再次证明了“电池内置”的优势。 - Matthieu M.

7

@Matthieu M.: Boyer-Moore在这里并没有带来任何好处，因为搜索字符串的第一个字符在搜索到的字符串中根本找不到。相反，它可能会增加一些额外负担，使每次循环中需要处理搜索字符串，但却是多余的。 - Mike Nakis

1

我们确定string::find(const char*)不是基于string::find(const string&)实现的吗？如果是的话，这里可能会导致内存分配变得昂贵。 - Kylotan

@Tim：线性可能比线性更快 :) - Matthieu M.

@MatthieuM 当然，但是你评论的措辞暗示了某种对比。好的，我不再纠结于措辞问题了。 - Tim Seguine

显示剩余4条评论

16

典型的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倍以上。

[在我的笔记本电脑上]

time ./test X的长度为104448 真实时间 0m2.055秒用户时间 0m2.049秒系统时间 0m0.001秒

- Heptic

2

确认。g++ 4.4.3。在我的测试中，搜索需要5秒钟，查找需要12.5秒钟（两者在同一个exe中；我的测试时间更长，因为我使用std::string s(limit,'X');预先创建了字符串，即搜索和查找需要更多的工作）。结论：g++上的stdlib find()有很大的优化潜力！ - Darren Cook

1

哇，添加了一个memmem()版本，使用相同的字符串（通过c_str()访问），时间为0.75秒。（实际上是0；整个循环似乎被优化掉了；所以我在循环中添加了一些小计算来阻止这种情况。）新结论：find()和search()正在做一些奇怪的事情，即使-O3也无法优化，或者memmem正在使用某些特殊的CPU功能。令人着迷！ - Darren Cook

8

std::search比std::string::search更快的原因是因为（按照惯例？）std::search是在头文件中实现的，这给编译器更大的优化空间。另一方面，std::string::search则不是。由于调用该函数的次数很多，这也会造成很大的差异。 - Heptic

5

@Heptic：嗯，“std::string”只是“std::basic_string<char>”的一个typedef，它是一个模板，因此完全实现在头文件中。 - sbi

@sbi 除非 std::basic_string<char> 进行了特化，否则这些函数可能会在 .cpp 中实现，因为它们会像普通类的函数一样而不是模板类的函数。此外，一些编译器尝试使用各种技巧“预编译”头文件，这也可能会干扰（尽管我记得 GCC 不是其中之一）。 - Pharap

10

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

文档在这里。

我应该提到，在C++中直接使用标准类，并像Java或Python一样使用它们，如果你不知道背后发生了什么，通常会给你带来次优性能。语言本身没有神奇的性能，它只是提供了正确的工具。

- Mihails Strasuns

在我的电脑上，在循环之前添加s.reserve(limit)对性能没有明显的影响。 - NPE

我总体上同意你的观点，但你测试过吗？使用gcc 4.6时，使用string::reserve并没有加速。你能展示一下如何以快速的方式进行连接，并利用类在后台的工作原理吗？ - Szabolcs

这真的是一个问题吗？每个 string::operator++ 只附加一个字符，因此内存重新分配和复制不应该是一个大负担。 - user180247

是的，我尝试过 s.reserve(102 * 1024)，但没有帮助。它大约需要5.895秒，改善很小。我认为瓶颈在于字符串搜索。 - Wu Shu

1

好的，实践证明了这一点。将 s += "X" 替换为 string s(102*1024, 'X') 可以极大地提高速度（在我的 VBox 中真正的时间是 0m0.003s）。尽管我说过 std::string::reserve 没有帮助，但它应该具有相同的效果（在我看来）。需要再深入研究一下。编辑：哈哈，现在才注意到循环语句的写法 :) 好的，回滚所有操作。 - Mihails Strasuns

1

当然，构建字符串可以极大地提高速度。然后你完全绕过了循环... 如果你先分配字符串，那么你需要改变循环条件以迭代一个 i = 0 变量，然后你会注意到搜索才是真正的问题。 - Matthieu M.

8

我的第一反应是没有什么问题。

C++的表现排名第二，比Java快近十倍。也许除了Java之外的所有功能都已经接近最佳性能，您应该考虑如何解决Java问题（提示- StringBuilder ）。

在C++的情况下，有一些可尝试的方法来稍微提高性能。具体来说...

s += 'X'; 而不是 s += "X";
在循环外声明 string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); 并将其传递给 find 调用。一个 std::string 实例知道它自己的长度，而C字符串需要一个线性时间检查来确定，这可能（或可能不）与 std :: string :: find 性能相关。
尝试使用 std::stringstream ，与为Java使用 StringBuilder 的原因类似，尽管最可能的是重复转换回 string 会创建更多的问题。

总的来说，结果并不太令人惊讶。 JavaScript，配备良好的JIT编译器，可能能够比C++静态编译允许在这种情况下进行更好的优化。

通过足够的工作，您应该始终能够比JavaScript更好地优化C ++，但总会有一些情况不会自然发生，需要花费相当多的知识和努力才能实现。

- user180247

性能受“查找”调用限制，而不是分配。例如，在测试第二个点时，根本没有任何区别。 - Matthieu M.

@Matthieu - 嗯，我并没有说我的任何想法一定会有所不同。然而，第二点全部关于find调用。重点是使用一个不同的find重载，它将搜索模式作为std::string而不是C字符串，并因此（可能但不一定）避免在find调用中使用strlen调用。另一个想法是，由于搜索模式是常量，编译模式方法可能会更快（例如Boyer-Moore字符串搜索），但这是欺骗行为 - 除非例如JavaScript优化器比我预期的要聪明得多。 - user180247

我测试了一个朴素的Boyer-Moore算法（每一步都构建表格），但它的性能更差。针很小（26个字符），相比于大海量的干草堆（104448个字符），所以额外的复杂度抵消了可能预期的加速效果。我猜想在外部构建表格可能会有所帮助...但也许没有预期的那么多。 - Matthieu M.

3

Stringstream在这里不会带来任何性能改进。std::string已经是可变的，并且可以在恒定分摊时间内进行插入。 - Billy ONeal

7

您在这里忽略了查找搜索的固有复杂性。您正在执行搜索102 * 1024（104448）次。一个天真的搜索算法会每次从第一个字符开始尝试匹配模式，然后是第二个字符等等...... 因此，您有一个字符串从长度1到N，并且在每个步骤中，您都会对该字符串执行模式搜索，这是C ++中的线性操作。也就是说，N *（N + 1）/ 2 = 5454744576次比较。我并不像您一样惊讶，这需要一些时间...... 让我们通过使用查找单个A的重载来验证假设：

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

大约快了3倍，所以我们处于同一数量级内。因此，使用完整字符串并不真正有趣。

结论？也许find可以进行一些优化。但这个问题不值得。

注意：对于那些吹嘘Boyer Moore的人，很遗憾，针头太小了，所以它不会帮助太多。可能会减少一个数量级(26个字符)，但不会更多。

- Matthieu M.

干草堆中没有 A，因此它应该仅检查字符串中的每个字符是否未找到，并且不查看模式的其他字符。您似乎在描述 find_any_of 方法，这里应该可以非常快地找到 'X'。 - UncleBens

@UncleBens：完全不是，我说的是find，即使对于字符串模式，如果它不匹配，则应该在模式的第一个字符停止并在“干草堆”中继续移动。寻找单个字符A（模式的第一个字符）只快了3倍，这表明我的怀疑不是模式搜索慢，而是在如此长的字符串中多次查找模式本身就很慢。 - Matthieu M.

4

如果使用C ++，请尝试使用std :: string来代替"ABCDEFGHIJKLMNOPQRSTUVWXYZ" - 在我的实现中string :: find（const charT * s，size_type pos = 0）const 计算字符串参数的长度。

- dimba

3

我亲自测试了这个C++例子。如果我删除对std::string::find的调用，程序会在瞬间终止。因此，在字符串连接期间进行的分配并不是问题。

如果我添加一个变量sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"并将调用std::string::find中的"ABC...XYZ"替换掉，那么程序完成所需的时间几乎与原始示例相同。这再次表明，分配以及计算字符串长度并没有显著增加运行时间。

因此，似乎libstdc++使用的字符串搜索算法对于您的示例并不像javascript或python的搜索算法那样快速。也许您想再次尝试使用适合您目的的自己的字符串搜索算法来使用C++。

- swegi

如果您删除string :: find，那么这只是字符串连接，并且在为字符串优化的语言/运行时之间没有太大区别：C ++中的字符串也比C中的字符串（作为char数组）更加优化。 string :: find不仅是搜索算法的测试，而且还是遍历字符串的测试。我会进行另一个测试。 - Wu Shu

3

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

- Gabrielix

2

你的测试代码检查了一种过度字符串连接的病态场景。（测试中的字符串搜索部分可能本可以省略，我敢打赌它几乎对最终结果没有什么贡献。）过度字符串连接是大多数编程语言都强烈警告的一个陷阱，并提供了非常出名的替代方案（例如 StringBuilder），因此你在这里实际上测试的是这些编程语言在完全预料到失败的情况下失败得有多惨烈，这是毫无意义的。

类似于这样毫无意义的测试的一个例子是，在紧密循环中抛出和捕获异常时比较各种编程语言的性能。所有编程语言都警告说抛出和捕获异常异常地慢。虽然他们没有指定有多慢，但他们警告你不要期望太高。因此，去测试这一点就是毫无意义的。

所以，重复你的测试，将毫无头脑的字符串连接部分（s +="X"）替换为每种编程语言提供的旨在避免字符串连接的任何结构（例如 class StringBuilder）。这将会更有意义。

- Mike Nakis

1

我刚刚亲自检查了示例代码，结果发现几乎所有的运行时间都花费在字符串搜索上。 - swegi

o_O -- 好的，那么一定有非常奇怪的事情发生了。在发布我的答案之前，我检查了上述所有语言中所有find()和indexOf()方法的文档，以确保它们都执行纯粹的非正则表达式、区分大小写的搜索。因此，如果搜索是问题，尽管任务微不足道，我也不知道该说什么。 - Mike Nakis

@MikeNakis - 一个直接的搜索可以从知道搜索模式的长度中受益 - 限制它搜索的范围，甚至可以完全排除在短字符串中搜索长模式的可能性。C字符串不知道自己的长度，所以find操作要么对每次调用都使用线性时间的strlen函数来计算模式的长度，要么就没有这种高级长度知识而进行更多的搜索工作。 - user180247

1

@swegi 你检查了哪些语言？我预计它们之间可能会有所不同。在我的系统上，使用Python 2.7编写的代码需要13.1秒，删除find调用后只需要0.019秒。因此，在测试中，字符串连接（至少在Python中）是无关紧要的部分。这可能仅适用于C版本的Python，因为它使用引用计数，并且可以在检测到字符串只有一个引用时原地执行连接操作。 - Duncan

3

std::string::operator+= 是C++提供的构造函数，用于避免Java中导致字符串连接变慢的问题。 std::string 是一个可变类，与 StringBuilder 相同。老实说，我认为这个问题有点令人困惑，因为它问的是“为什么C ++很慢？”，但包括Java结果，它们非常慢，促使各种人解释为什么Java结果很慢。这与问题无关;-) - Steve Jessop

显示剩余7条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Joiner · Accepted Answer

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