std :: string 작업이 제대로 수행되지 않는 이유는 무엇입니까?

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

자바 (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

자바 스크립트 (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 (V8)의 javascript : 3.1 초
• CPython 2.7.2의 Python : 8.8s
• libstdc ++를 사용하는 C ++ : 5.9s
• OpenJDK 7 : 50.4s의 Java

놀랍게도! 나는 C ++에서 "-O2, -O3"를 시도했지만 도움이되었다. C ++는 V8에서 자바 스크립트의 성능이 50 %에 불과하며 CPython보다 열악합니다. GCC에서 최적화를 놓친 경우 누구든지 설명해 주시겠습니까? 아니면 이것이 사실입니까? 정말 고마워.

---

std::string성능이 저조한 것이 아니라 (C ++를 싫어하는만큼) 문자열 처리가 다른 언어에 매우 최적화되어 있다는 것입니다.

문자열 성능에 대한 비교는 오해의 소지가 있으며 그 이상을 나타내려는 의도라면 주제 넘습니다.

나는 파이썬 문자열 객체가 C로 완전히 구현 된다는 사실을 알고 있으며 실제로 파이썬 2.7에서는 유니 코드 문자열과 바이트 사이의 분리 부족으로 인해 수많은 최적화 가 존재합니다. 이 테스트를 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

---

그래서 나는 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입니다. (물론 이것은 매우 의심 스럽지만 잠시 나를 탐닉하고 다른 결과를 기다리십시오.)

이제이 코드를 가져 와서 주석 처리 된 줄을 바꾸어 찾기보다는 추가를 테스트합니다. 이번에는 모든 시간 결과를 확인하기 위해 반복 횟수를 10 배 늘 렸습니다.

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

반복 횟수가 10 배 증가 했음에도 불구하고 ideone.org 에서의 결과 는 time: 0s.

내 결론 :이 벤치 마크는 C ++ 에서 검색 작업에 크게 좌우되며 루프에 문자를 추가해도 결과에 전혀 영향을주지 않습니다. 그게 정말 당신의 의도 였나요?

---

관용적 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을 사용하여 속도를 상당히 높일 수 있지만 필요하지 않은 것 같습니다. 내 컴퓨터에서 실행하면 이미 파이썬 솔루션의 10 배 이상입니다.

[내 노트북에서]

시간 ./test X의 길이 = 104448 실제 0m2.055s 사용자 0m2.049s sys 0m0.001s

---

이것이 가장 명백한 것입니다. s.reserve(limit);메인 루프 전에 시도하십시오 .

문서는 여기에 있습니다 .

Java 또는 Python에서 사용하는 것과 동일한 방식으로 C ++에서 표준 클래스를 직접 사용하면 책상 뒤에서 수행되는 작업을 알지 못하는 경우 종종 하위 수준의 성능이 제공됩니다. 언어 자체에는 마법 같은 성능이 없으며 올바른 도구를 제공 할뿐입니다.

---

여기서 누락 된 것은 찾기 검색의 고유 한 복잡성입니다.

검색 102 * 1024(104448) 회 실행 중 입니다. 순진한 검색 알고리즘은 매번 첫 번째 문자에서 시작하여 두 번째 문자부터 패턴을 일치 시키려고 시도합니다.

따라서 길이에서 진행되는 문자열이 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보다 거의 10 배 빠른 두 번째로 우수한 성능을 제공합니다. Java를 제외한 모든 기능이 해당 기능에 대해 달성 할 수있는 최상의 성능에 가깝게 실행되고있을 수 있으며 Java 문제를 해결하는 방법을 살펴 봐야합니다 (힌트- StringBuilder).

C ++의 경우 성능을 약간 향상시키기 위해 시도 할 몇 가지 사항이 있습니다. 특히...

• s += 'X'; 보다는 s += "X";
• string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ");루프 외부에서 선언 하고이를 find호출에 전달하십시오 . std::stringC 문자열가를 결정하는 선형 시간 검사를 필요로하는 반면 인스턴스는, 그것의 자신의 길이를 알고,이 (또는하지 않을 수 있습니다) 관련 될 수있는 std::string::find성능을 제공합니다.
• Java std::stringstream를 사용해야하는 이유와 비슷한 이유로를 사용해보십시오 StringBuilder. 반복되는 변환으로 string인해 더 많은 문제가 발생할 가능성이 높습니다 .

전반적으로 결과는 그리 놀라운 것은 아닙니다. 좋은 JIT 컴파일러를 사용하는 JavaScript는이 경우 C ++ 정적 컴파일이 허용하는 것보다 약간 더 최적화 할 수 있습니다.

충분한 작업을 통해 항상 JavaScript보다 C ++를 더 잘 최적화 할 수 있어야하지만, 자연스럽게 발생하지 않고이를 달성하기 위해 상당한 지식과 노력이 필요한 경우가 항상있을 것입니다.

---

C ++의 경우 std::string"ABCDEFGHIJKLMNOPQRSTUVWXYZ"를 사용해보십시오. 구현시 string::find(const charT* s, size_type pos = 0) const문자열 인수의 길이를 계산합니다.

---

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

---

방금 C ++ 예제를 직접 테스트했습니다. 에 대한 호출을 제거하면 std::sting::find프로그램이 즉시 종료됩니다. 따라서 문자열 연결 중 할당은 여기서 문제가되지 않습니다.

If I add a variable sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" and replace the occurence of "ABC...XYZ" in the call of std::string::find, the program needs almost the same time to finish as the original example. This again shows that allocation as well as computing the string's length does not add much to the runtime.

Therefore, it seems that the string search algorithm used by libstdc++ is not as fast for your example as the search algorithms of javascript or python. Maybe you want to try C++ again with your own string search algorithm which fits your purpose better.

---

Your test code is checking a pathological scenario of excessive string concatenation. (The string-search part of the test could have probably been omitted, I bet you it contributes almost nothing to the final results.) Excessive string concatenation is a pitfall that most languages warn very strongly against, and provide very well known alternatives for, (i.e. StringBuilder,) so what you are essentially testing here is how badly these languages fail under scenarios of perfectly expected failure. That's pointless.

An example of a similarly pointless test would be to compare the performance of various languages when throwing and catching an exception in a tight loop. All languages warn that exception throwing and catching is abysmally slow. They do not specify how slow, they just warn you not to expect anything. Therefore, to go ahead and test precisely that, would be pointless.

So, it would make a lot more sense to repeat your test substituting the mindless string concatenation part (s += "X") with whatever construct is offered by each one of these languages precisely for avoiding string concatenation. (Such as class StringBuilder.)

---

It seems that in nodejs there are better algorithms for substring search. You can implement it by yourself and try it out.

---

As mentioned by sbi, the test case is dominated by the search operation. I was curious how fast the text allocation compares between C++ and Javascript.

System: Raspberry Pi 2, g++ 4.6.3, node v0.12.0, g++ -std=c++0x -O2 perf.cpp

C++ : 770ms

C++ without reserve: 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();

참고URL : https://stackoverflow.com/questions/8310039/why-do-stdstring-operations-perform-poorly