[c++] C ++에서 stdin에서 읽는 줄이 파이썬보다 느린 이유는 무엇입니까?



Answers

그냥 호기심에서 나는 두포에서 일어나는 일을 살펴 dtruss/strace 각 테스트마다 dtruss/strace 를 사용 dtruss/strace .

C ++

./a.out < in
Saw 6512403 lines in 8 seconds.  Crunch speed: 814050

syscalls sudo dtruss -c ./a.out < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            6
pread                                           8
mprotect                                       17
mmap                                           22
stat64                                         30
read_nocancel                               25958

파이썬

./a.py < in
Read 6512402 lines in 1 seconds. LPS: 6512402

syscalls sudo dtruss -c ./a.py < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            5
pread                                           8
mprotect                                       17
mmap                                           21
stat64                                         29
Question

나는 파이썬과 C ++을 사용하는 stdin에서 문자열 입력을 읽는 것을 비교하기를 원했고 나의 C ++ 코드가 동등한 파이썬 코드보다 느린 순서로 실행되는 것을보고 놀랐다. 내 C ++이 녹슬었고 아직 Pythonista 전문가가 아니기 때문에 내가 잘못한 일을하고 있는지, 아니면 내가 오해하고 있는지 말해줘.

(TLDR 대답 : 성명을 포함 : cin.sync_with_stdio(false) 아니면 단지 대신 fgets 사용합니다.

TLDR 결과 : 맨 아래까지 스크롤하여 표를 봅니다.)

C ++ 코드 :

#include <iostream>
#include <time.h>

using namespace std;

int main() {
    string input_line;
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    while (cin) {
        getline(cin, input_line);
        if (!cin.eof())
            line_count++;
    };

    sec = (int) time(NULL) - start;
    cerr << "Read " << line_count << " lines in " << sec << " seconds.";
    if (sec > 0) {
        lps = line_count / sec;
        cerr << " LPS: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

// Compiled with:
// g++ -O3 -o readline_test_cpp foo.cpp

동등한 파이썬 :

#!/usr/bin/env python
import time
import sys

count = 0
start = time.time()

for line in  sys.stdin:
    count += 1

delta_sec = int(time.time() - start_time)
if delta_sec >= 0:
    lines_per_sec = int(round(count/delta_sec))
    print("Read {0} lines in {1} seconds. LPS: {2}".format(count, delta_sec,
       lines_per_sec))

내 결과는 다음과 같습니다.

$ cat test_lines | ./readline_test_cpp
Read 5570000 lines in 9 seconds. LPS: 618889

$cat test_lines | ./readline_test.py
Read 5570000 lines in 1 seconds. LPS: 5570000

편집 : Mac OS X v10.6.8 (Snow Leopard) 및 Linux 2.6.32 (Red Hat Linux 6.2)에서이 작업을 시도했음을 유의해야합니다. 전자는 MacBook Pro이고, 후자는 매우 가벼운 서버입니다. 너무 적절하지는 않습니다.

편집 2 : (더 이상 적용 할 수없는 수정 사항 삭제)

$ for i in {1..5}; do echo "Test run $i at `date`"; echo -n "CPP:"; cat test_lines | ./readline_test_cpp ; echo -n "Python:"; cat test_lines | ./readline_test.py ; done
Test run 1 at Mon Feb 20 21:29:28 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 2 at Mon Feb 20 21:29:39 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 3 at Mon Feb 20 21:29:50 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 4 at Mon Feb 20 21:30:01 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 5 at Mon Feb 20 21:30:11 EST 2012
CPP:   Read 5570001 lines in 10 seconds. LPS: 557000
Python:Read 5570000 lines in  1 seconds. LPS: 5570000

3 편집 :

좋아, 나는 파이썬이 라인을 저장하도록하는 JN의 제안을 시도했지만, 파이썬의 속도에는 아무런 차이가 없었다.

또한 getd 대신 std::stringchar 배열로 scanf 를 사용하는 JN의 제안을 시도했습니다. 빙고! 이로 인해 Python과 C ++에서 동일한 성능을 보입니다. (입력 데이터가있는 3,333,333 개의 뇌 보호 시스템 (LPS). 3 개의 필드가 각각 짧은 줄로 표시되며 보통 약 20 자 정도입니다.

암호:

char input_a[512];
char input_b[32];
char input_c[512];
while(scanf("%s %s %s\n", input_a, input_b, input_c) != EOF) {
    line_count++;
};

속도:

$ cat test_lines | ./readline_test_cpp2
Read 10000000 lines in 3 seconds. LPS: 3333333
$ cat test_lines | ./readline_test2.py
Read 10000000 lines in 3 seconds. LPS: 3333333

(예, 여러 번 실행했습니다.) 그래서 getline 대신 scanf 를 사용할 것입니다. 그러나 사람들이이 성능이 std::string / getline 에서 치는 것이 전형적이고 합리적이라고 생각한다면 여전히 궁금합니다.

편집 4 (: 최종 수정 / 솔루션) :

첨가:

cin.sync_with_stdio(false);

위의 원래 while 루프는 Python보다 빠르게 실행되는 코드를 생성합니다.

20M 줄의 텍스트가있는 파일에서 원본 코드, 동기화가 비활성화 된 원본 및 원래 파이썬 코드를 각각 사용하여 새로운 성능 비교 (내 2011 MacBook Pro에 있음). 예, 디스크 캐싱 혼동을 제거하기 위해 여러 번 실행했습니다.

$ /usr/bin/time cat test_lines_double | ./readline_test_cpp
       33.30 real         0.04 user         0.74 sys
Read 20000001 lines in 33 seconds. LPS: 606060
$ /usr/bin/time cat test_lines_double | ./readline_test_cpp1b
        3.79 real         0.01 user         0.50 sys
Read 20000000 lines in 4 seconds. LPS: 5000000
$ /usr/bin/time cat test_lines_double | ./readline_test.py
        6.88 real         0.01 user         0.38 sys
Read 20000000 lines in 6 seconds. LPS: 3333333

그의 대답에 대해 @ Vaughn Cato에게 감사드립니다! 모든 사람들은 사람들이이 동기화가 일어나는 이유, 그것이 의미하는 바, 유용 할 때, 사용을 중지 할 수있을 때 후손이 크게 높이 평가할 수 있다는 점을 지적 할 수 있습니다. :-)

5 / 더 나은 솔루션 편집 :

Gandalf The Grey가 제안한 것처럼, getsscanf 또는 비동기식 cin 접근보다 훨씬 빠릅니다. 또한 scanfgets 는 모두 UNSAFE이며 버퍼 오버 플로우 가능성으로 인해 사용해서는 안된다는 것을 알게되었습니다. 그래서 fgets 사용하여이 반복을 작성했습니다. 나의 동료 멍청이들에게 적절한 라인들이있다.

char input_line[MAX_LINE];
char *result;

//<snip>

while((result = fgets(input_line, MAX_LINE, stdin )) != NULL)
    line_count++;
if (ferror(stdin))
    perror("Error reading stdin.");

이제는 매우 빠른 디스크를 사용하는 빠른 서버에서 더 큰 파일 (100M 회선, ~ 3.4GB)을 사용하여 파이썬 코드, 비동기 cinfgets 접근법을 비교하고 wc 유틸리티와 비교 한 결과가 있습니다 . [ scanf 버전 세분화가 잘못되어 문제 해결을 원치 않습니다.] :

$ /usr/bin/time cat temp_big_file | readline_test.py
0.03user 2.04system 0:28.06elapsed 7%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 28 seconds. LPS: 3571428

$ /usr/bin/time cat temp_big_file | readline_test_unsync_cin
0.03user 1.64system 0:08.10elapsed 20%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
Read 100000000 lines in 8 seconds. LPS: 12500000

$ /usr/bin/time cat temp_big_file | readline_test_fgets
0.00user 0.93system 0:07.01elapsed 13%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 7 seconds. LPS: 14285714

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU (0avgtext+0avgdata 2464maxresident)k
0inputs+0outputs (0major+182minor)pagefaults 0swaps
100000000


Recap (lines per second):
python:         3,571,428
cin (no sync): 12,500,000
fgets:         14,285,714
wc:            54,644,808

보시다시피, fgets 는 좋지만 여전히 wc 성능에서 꽤 떨어져 있습니다. 나는 이것이 wc가 메모리 복사없이 각 문자를 검사한다는 사실 때문이라고 확신한다. 나는이 시점에서 코드의 다른 부분들이 병목 현상이 될 것이라고 생각한다. 그래서 가능한 수준이라 할지라도 그 수준으로 최적화하는 것이 가치가 있다고 생각하지 않는다. (결국, 나는 실제로 읽기 라인을 저장해야하기 때문에 메모리에 저장).

또한 char * 버퍼와 fgets 대 unsynchronised cin 을 문자열에 사용하면 약간의 단점을 cin 수 있는데, 후자는 임의의 길이의 라인을 읽을 수 있지만 전자는 제한된 수의 입력을 제한해야한다는 것입니다. 실제로 이것은 버퍼가 유효한 입력에 의해 초과되지 않는 매우 큰 값으로 설정 될 수 있으므로 대부분의 행 기반 입력 파일을 읽을 때 문제가되지 않을 수도 있습니다.

이것은 교육적이었습니다. 의견과 제안에 감사드립니다.

편집 6 :

아래의 주석에서 JF Sebastian이 제안한 것처럼 GNU wc 유틸리티는 한 번에 청크 (16k 바이트)를 읽고 새 행을 세는 데 일반 read() (safe-read.c 래퍼 내)를 사용합니다. 다음은 JF의 코드를 기반으로하는 파이썬과 동일합니다 (Python for 루프를 대체하는 관련 스 니펫 만 표시합니다.

BUFFER_SIZE = 16384
count = sum(chunk.count('\n') for chunk in iter(partial(sys.stdin.read, BUFFER_SIZE), ''))

이 버전의 성능은 꽤 빠릅니다 (물론 원시 C wc 유틸리티보다 조금 더 느리지 만).

$ /usr/bin/time cat temp_big_file | readline_test3.py
0.01user 1.16system 0:04.74elapsed 24%CPU (0avgtext+0avgdata 2448maxresident)k
0inputs+0outputs (0major+181minor)pagefaults 0swaps
Read 100000000 lines in 4.7275 seconds. LPS: 21152829

다시 말하지만, C ++ fgets / cin 과 첫 번째 파이썬 코드를 wc -l 과 비교하고 마지막 두 파이썬 스 니펫을 다른 코드와 비교하는 것은 다소 바보입니다. 두 번째 코드는 실제로 읽기 라인을 저장하지 않지만 단순히 뉴 라인을 센다. 그럼에도 불구하고 모든 다른 구현을 탐색하고 성능에 미치는 영향을 생각하는 것은 흥미 롭습니다. 다시 한 번 감사드립니다!

편집 7 : 작은 벤치 마크 부록 및 요점 정리

완전성을 위해, 나는 원래의 (동기화 된) C ++ 코드와 동일한 상자에 같은 파일에 대한 읽기 속도를 업데이트 할 것이라고 생각했습니다. 다시 말하지만, 이것은 빠른 디스크의 100M 라인 파일에 대한 것입니다. 다음은 완전한 테이블입니다.

Implementation      Lines per second
python (default)           3,571,428
cin (default/naive)          819,672
cin (no sync)             12,500,000
fgets                     14,285,714
wc (not fair comparison)  54,644,808



답변의 첫 번째 요소는 <iostream> 이 느립니다. 젠장. 아래처럼 scanf 하면 성능이 크게 향상되지만 파이썬보다 두 배 느립니다.

#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

int main() {
    char buffer[10000];
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    int read = 1;
    while(read > 0) {
        read = scanf("%s", buffer);
        line_count++;
    };
    sec = (int) time(NULL) - start;
    line_count--;
    cerr << "Saw " << line_count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = line_count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } 
    else
        cerr << endl;
    return 0;
}



나는 여기서 몇 년 뒤이지만 :

원래 게시물의 'Edit 4/5/6'에서 건설을 사용하고 있습니다 :

$ /usr/bin/time cat big_file | program_to_benchmark

이것은 몇 가지 다른 방식으로 잘못되었습니다.

  1. 실제로 벤치 마크가 아닌`cat`의 실행을 타이밍하고 있습니다. 'user'와 'sys'CPU 사용량은`time`에 의해 표시되며 벤치 마크 프로그램이 아니라`cat`의 값입니다. 더 나쁜 것은 '진짜'시간도 반드시 정확하지는 않습니다. 지역 OS의`cat`과 파이프 라인의 구현에 따라`cat`이 최종 거대한 버퍼를 작성하고 독자 프로세스가 끝나기 오래 전에 끝날 수도 있습니다.

  2. `cat`의 사용은 불필요하며 실제로 비생산적입니다. 당신은 움직이는 부분을 추가하고 있습니다. 만약 당신이 충분히 오래된 시스템 (예를 들어 하나의 CPU와 특정 세대의 컴퓨터에서 I / O가 CPU보다 빠름)이라면,`cat`이 실행되었다는 단순한 사실만으로도 결과를 실질적으로 채색 할 수 있습니다. 또한 입력 및 출력 버퍼링과`cat`이 처리 할 수있는 다른 처리의 대상이됩니다. (랜달 슈왈츠 (Randal Schwartz)의 경우 '고양이의 쓸모없는 사용'상을받을 수 있습니다. https://en.wikipedia.org/wiki/Cat_(Unix)#UUOC_(Useless_Use_Of_Cat) )

더 나은 구조는 다음과 같습니다.

$ /usr/bin/time program_to_benchmark < big_file

이 명령문에서 big_file을 열어 이미 열려있는 파일 설명자로 프로그램에 전달하는 입니다. 실제로 프로그램을 하위 프로세스로 실행하는`time`에 전달합니다. 파일 읽기의 100 %는 엄격하게 벤치마킹하려는 프로그램의 책임입니다. 이것은 당신에게 가짜 합병증없이 성능을 실제로 읽을 수있게 해줍니다.

나는 가능한 두 가지 가능성을 언급 할 것이다. 그러나 실제로는 잘못된 것인데, 또한 고칠 수있는 '고침'이있다. (그러나 나는 원래의 게시물에서 틀린 것들이 아니기 때문에 다르게 숫자를 매긴다.)

A. 프로그램을 타이밍 만 정하면이 문제를 해결할 수 있습니다.

$ cat big_file | /usr/bin/time program_to_benchmark

B. 전체 파이프 라인 타이밍을 맞추거나 :

$ /usr/bin/time sh -c 'cat big_file | program_to_benchmark'

이것들은 # 2와 같은 이유로 잘못되었습니다 : 그들은 여전히`cat`을 불필요하게 사용하고 있습니다. 몇 가지 이유로 다음과 같이 언급합니다.

  • POSIX 셸의 I / O 리디렉션 기능에 완전히 익숙하지 않은 사람들에게 더 자연 스럽습니다.

  • `cat ' 필요한 경우가있을 수 있습니다 (예 : 읽을 파일에 액세스 할 수있는 권한이 필요하며 벤치 마크 대상 프로그램에 해당 권한을 부여하고 싶지 않음). sudo cat / dev / sda | / usr / bin / time my_compression_test --no-output`)을 실행합니다.

  • 실제로 , 현대 기계에서, 파이프 라인에 추가 된`cat`은 아마도 실제 결과가 아닙니다.

그러나 나는 주저하면서 그 마지막 것을 말한다. '편집 5'에서 마지막 결과를 검토하면

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU ...

- 이것은`cat`이 테스트 동안 CPU의 74 %를 소비했다는 주장입니다. 실제로 1.34 / 1.83은 약 74 %입니다. 아마도 다음 중 하나의 실행 :

$ /usr/bin/time wc -l < temp_big_file

49 초 남았을뿐입니다! 아마도 'cat'은 'disk'(실제로는 버퍼 캐시)에서 파일을 전송 한 read () 시스템 호출 (또는 동등한 것)과 'wc'에 전달할 파이프 쓰기에 대해 지불해야합니다. 올바른 테스트는 여전히 read () 호출을 수행해야했습니다. write-to-pipe와 read-from-pipe 호출 만 저장되고 꽤 저렴해야합니다.

아직도, 나는 당신이`cat file | wc -l`과`wc -l <file`을 사용하여 눈에 띄는 (2 자리 백분율) 차이를 찾습니다. 각 느린 시험은 절대 시간에 비슷한 벌점을 지불 할 것입니다; 그러나 그것은 더 큰 전체 시간의 작은 부분에 해당합니다.

실제로 리눅스 3.13 (우분투 14.04) 시스템에서 1.5 기가 바이트의 가비지 파일을 사용하여 몇 가지 빠른 테스트를 수행했으며 결과는 다음과 같습니다 (실제로 캐시를 초기화 한 후 '최고 3'결과입니다).

$ time wc -l < /tmp/junk
real 0.280s user 0.156s sys 0.124s (total cpu 0.280s)
$ time cat /tmp/junk | wc -l
real 0.407s user 0.157s sys 0.618s (total cpu 0.775s)
$ time sh -c 'cat /tmp/junk | wc -l'
real 0.411s user 0.118s sys 0.660s (total cpu 0.778s)

두 파이프 라인 결과는 실시간보다 많은 CPU 시간 (user + sys)을 사용했다고 주장합니다. 이것은 내가 파이프 (Bash)의 빌트인 'time'명령을 사용하고 있기 때문이다. 이것은 파이프 라인을 인식하고있다. 그리고 파이프 라인의 개별 프로세스가 별도의 코어를 사용하여 실시간보다 CPU 시간을 더 빨리 누적 할 수있는 멀티 코어 시스템을 사용하고 있습니다. / usr / bin / time을 사용하면 실시간보다 CPU 시간이 적게 걸립니다. 명령 줄에서 전달 된 단일 파이프 라인 요소의 시간 만 측정 할 수 있음을 보여줍니다. 또한 쉘의 출력은 밀리 초를, / usr / bin / time은 초를 허락합니다.

그래서`wc -l`의 효율성 수준에서`cat`은 409 / 283 = 1.453 또는 45.3 % 더 많은 실시간과 775 / 280 = 2.768, 또는 무려 177 % 더 많은 CPU가 사용되었습니다. 내 무작위로 - 그것은 - 시간 테스트 상자에있었습니다.

나는이 시험 스타일 사이에 적어도 하나의 다른 중요한 차이점이 있다는 것을 덧붙여 야한다. 나는 그것이 유익한 지 잘못인지 말할 수 없다. 당신 스스로 이것을 결정해야합니다 :

`cat big_file |을 실행하면 / usr / bin / time my_program`의 경우 프로그램은`cat`에 의해 보내진 속도와`cat`에 의해 쓰여진 것보다 큰 조각들로 파이프로부터 입력을 받고 있습니다.

`/ usr / bin / time my_program <big_file`을 실행하면 프로그램은 실제 파일에 열린 파일 기술자를받습니다. 프로그램 이나 - 대부분의 경우, 쓰여진 언어의 I / O 라이브러리는 - 정규 파일을 참조하는 파일 설명자와 함께 제시 될 때 다른 동작을 취할 수 있습니다. 명시 적 read (2) 시스템 호출 대신에 mmap (2)을 사용하여 입력 파일을 주소 공간에 매핑 할 수 있습니다. 이러한 차이는`cat` 바이너리 실행의 작은 비용보다 벤치 마크 결과에 훨씬 더 큰 영향을 줄 수 있습니다.

물론 동일한 프로그램이 두 경우간에 현저하게 다르게 수행하는 경우 이는 흥미로운 벤치 마크 결과입니다. 실제로 프로그램이나 I / O 라이브러리 mmap ()을 사용하는 것과 같이 흥미로운 작업을 수행하고 있음을 보여줍니다. 따라서 실제로는 두 가지 방법으로 벤치 마크를 실행하는 것이 좋습니다. `cat` 자체를 실행하는 비용을 "용서하는"작은 요인에 의해`cat` 결과를 할인 할 수도 있습니다.




다음 코드는 지금까지 게시 된 다른 코드보다 훨씬 빠릅니다. (Visual Studio 2013, 64 비트, 500MB 파일, 줄 길이가 [0, 1000]로 균등합니다).

const int buffer_size = 500 * 1024;  // Too large/small buffer is not good.
std::vector<char> buffer(buffer_size);
int size;
while ((size = fread(buffer.data(), sizeof(char), buffer_size, stdin)) > 0) {
    line_count += count_if(buffer.begin(), buffer.begin() + size, [](char ch) { return ch == '\n'; });
}

그것은 나의 모든 파이썬 시도를 두 번째 요소 이상으로 이깁니다.




그런데 C ++ 버전의 줄수가 파이썬 버전의 개수보다 큰 이유는 eof 플래그가 eof 이상으로 읽으려는 시도가있을 때만 설정된다는 것입니다. 올바른 루프는 다음과 같습니다.

while (cin) {
    getline(cin, input_line);

    if (!cin.eof())
        line_count++;
};



Links