为什么std :: string操作执行不佳?

我进行了测试,比较了几种语言的字符串操作,以选择服务器端应用程序的语言。 在我最终尝试使用C ++之前,结果似乎是正常的,这使我感到非常惊讶。 所以我想知道我是否错过了任何优化并来这里寻求帮助。

测试主要是密集的字符串操作,包括连接和搜索。 该测试是在GCC版本4.6.1的Ubuntu 11.10 amd64上执行的。 该机器是带有4G RAM和四核CPU的Dell Optiplex 960。

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

毫不奇怪,Node Js的性能优于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(V8)上的JavaScript:3.1秒
  • CPython 2.7.2上的Python:8.8秒
  • 带有libstdc ++的C ++:5.9秒
  • OpenJDK 7上的Java:50.4s

出奇! 我在C ++中尝试了“ -O2,-O3”,但发现有所帮助。 在V8中,C ++似乎仅占javascript性能的50%,甚至比CPython还差。 谁能向我解释我是否错过了GCC的某些优化,或者只是这种情况? 非常感谢。

Wu Shu asked 2019-10-08T14:42:05Z
12个解决方案
71 votes

并不是说s.reserve(limit);的性能很差(就我而言,我不喜欢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
Matt Joiner answered 2019-10-08T14:43:47Z
34 votes

因此,我在ideone.org上玩了一些。

这里是原始C ++程序的略微修改版本,但是消除了循环中的附加操作,因此它仅测量对time: 0s的调用。请注意,我必须将迭代次数减少到〜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: 0s。(当然,这是非常可疑的,但是请您稍等一下,然后等待其他结果。)

现在,我们使用此代码并交换注释的行,以测试添加而不是查找。 请注意,这次,尝试查看所有时间结果时,迭代次数增加了十倍。

#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 answered 2019-10-08T14:45:01Z
14 votes

惯用的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倍以上。

[在我的笔记本电脑上]

时间./测试X的长度= 104448真正的0m2.055s用户0m2.049ssys 0m0.001s

Heptic answered 2019-10-08T14:45:56Z
8 votes

那是最明显的一种:请尝试在主循环之前执行s.reserve(limit);

文档在这里。

我应该提到的是,如果您不知道在桌子后面要做的事情,那么与在Java或Python中使用C ++一样,直接使用C ++中的标准类通常会获得低于标准的性能。 语言本身没有神奇的表现,只是为您提供了正确的工具。

Mihails Strasuns answered 2019-10-08T14:46:44Z
6 votes

您缺少的是查找搜索的固有复杂性。

您正在执行find(104 448)搜索。 天真的搜索算法每次都会尝试从第一个字符开始匹配模式,然后从第二个字符开始进行匹配,依此类推...

因此,您有一个字符串,其长度为findA,并且在每个步骤中都针对该字符串搜索模式,这是C ++中的线性运算。 那就是N * (N+1) / 2 = 5 454 744 576比较。 我不像您那样惊讶,这将需要一些时间。

让我们通过使用find的重载来验证假设,该重载将搜索单个A

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

快大约3倍,因此我们处于相同的数量级。 因此,使用完整的字符串并不是很有趣。

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

注意:对于那些吹捧博耶·摩尔的人来说,恐怕针头太小了,所以帮不上什么忙。 可以减少一个数量级(26个字符),但不能再减少一个。

Matthieu M. answered 2019-10-08T14:48:12Z
5 votes

我首先想到的是没有问题。

C ++提供第二好的性能,比Java快近十倍。 也许除了Java之外,所有其他产品都正在接近该功能所能达到的最佳性能,并且您应该研究如何解决Java问题(提示-std::stringstream)。

在C ++情况下,有些事情可以尝试稍微提高性能。 尤其是...

  • std::stringstream,而不是StringBuilder
  • 在循环外声明std::stringstream,并将其传递给StringBuilder调用。 string实例知道自己的长度,而C字符串则需要进行线性时间检查来确定该长度,这可能(也可能不)与std::string::find的性能有关。
  • 尝试使用std::stringstream,与使用StringBuilder用于Java的原因类似,尽管重复转换回string很有可能会产生更多问题。

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

通过足够的工作,您应该总是能够比JavaScript更好地优化C ++,但是在某些情况下,这并非自然而然地发生,并且可能需要相当多的知识和精力才能实现。

Steve314 answered 2019-10-08T14:49:44Z
4 votes

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

dimba answered 2019-10-08T14:50:17Z
4 votes

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 answered 2019-10-08T14:50:59Z
3 votes

我只是自己测试了C ++示例。 如果我取消对sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"的调用,该程序将立即终止。 因此,字符串连接期间的分配在这里没有问题。

如果我添加了一个变量sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"并替换了std::string::find的调用中出现的“ ABC ... XYZ”,则该程序需要与原始示例几乎相同的时间来完成。 这再次表明分配以及计算字符串的长度不会对运行时增加太多。

因此,对于您的示例,libstdc ++使用的字符串搜索算法似乎不如javascript或python的搜索算法快。 也许您想使用自己的字符串搜索算法再次尝试C ++,它更适合您的目的。

swegi answered 2019-10-08T14:51:51Z
1 votes

似乎在nodejs中,搜索子字符串的更好算法。 您可以实现自我并尝试一下。

xandox answered 2019-10-08T14:52:24Z
1 votes

您的测试代码正在检查字符串串联过多的病理情况。 (该测试的字符串搜索部分可能已被省略,我敢打赌,它几乎对最终结果没有任何贡献。)过多的字符串连接是大多数语言都强烈警告并提供替代方法的一个陷阱, (即StringBuilder),因此您在这里实质上要测试的是在完全预期的失败情况下这些语言的失败程度。 那没有意义。

类似的无意义测试的一个示例是比较在紧密循环中引发和捕获异常时各种语言的性能。 所有语言都警告说,异常的抛出和捕获非常慢。 他们没有指定速度有多慢,只是警告您不要期望任何事情。 因此,继续进行精确测试是没有意义的。

因此,用这些语言中的每一种为避免字符串连接而提供的任何构造来重复用无意识的字符串连接部分(s + =“ X”)来重复测试会更有意义。 (例如StringBuilder类。)

Mike Nakis answered 2019-10-08T14:53:20Z
0 votes

如sbi所述,测试用例由搜索操作主导。我很好奇,C ++和Javascript之间的文本分配相比有多快。

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

C ++:770毫秒

没有保留的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();
Pascalius answered 2019-10-08T14:54:40Z
translate from https://stackoverflow.com:/questions/8310039/why-do-stdstring-operations-perform-poorly