fast IO를 알기 전에, 먼저 IO가 어떻게 동작하는지 알 필요가 있습니다.

output은 상용 프로그램이 일반적인 operation을 사용해서 할 수 있는 것이 아니기 때문에, OS에 system call로 요청을 하게 됩니다. 이것은 프로그램의 실행 주권이 내가 쓴 프로그램에 있다가 OS로 넘어가고, OS가 output을 진행하는 동안 프로그램은 기다리고 있다가, 응답(이 경우에는 "잘 출력되었음")이 돌아오면 다시 프로그램을 진행합니다.

문제는 system call은 아주 오래 걸리는 작업이라는 것입니다. 특히 출력의 경우, "a"를 화면에 출력하고 "b"를 화면에 출력하는 것이 "ab"를 화면에 출력하는 것과 크게 다르지 않다면, 프로그래머가 출력을 원할 때마다 system call을 하지 말고, 출력해야 할 내용을 계산만 해 두고 메모리 어딘가에 저장해 두었다가 한꺼번에 출력하면 훨씬 빠르게 실행할 수 있을 것입니다. 이는 printf나 puts 등이 사용하고 있는 방법입니다. 이때 저장해 두는 메모리 공간은 특별히 buffer라고 부릅니다.

cstdio가 사용하는 buffer의 기본 크기는 1024입니다. 출력해야 할 내용이 상당히 많다면, buffer를 더 크게 잡고 싶을 것입니다. 아쉽게도 PS에서 원하는 정도로(예를 들어 1048576 정도로) 이 기본 buffer를 훨씬 크게 늘려 잡을 수 있는 방법은 없습니다. 그렇지만 buffer에 쌓아 두는 작업과 system call을 날리는 작업은 일반적인 프로그램에서도 할 수 있기 때문에, printf를 사용하지 않고 그것을 직접 구현하면 system call의 횟수를 비약적으로 줄일 수 있습니다. fast IO는 이 모든 과정을 직접 구현해서 속도를 빠르게 하려는 방법입니다.

입력도 마찬가지입니다. buffer에 입력을 미리 전부 받아 놓고 필요할 때마다 연산만 해서 쓰면 system call의 횟수를 비약적으로 줄일 수 있습니다. 입력 파일은 pts(pseudo-terminal slave)에 연결되어 있는 경우 조금 다르게 동작하는데, 관련된 내용이 궁금하시다면 이 단어로 검색해 보시기 바랍니다.

iostream을 사용하시는 분들이 std::endl을 사용하지 않는 이유 역시 설명할 수 있는데, 이는 타자기 시절의 유물입니다. 한 줄을 강제로 끝내는 것(carriage-return, line-feed)은 그 줄은 더 이상 수정할 수 없음을 의미하기 때문에, 컴퓨터에서는 이 줄을 강제로 끝내고, buffer를 출력하고 비우는 system call을 날립니다(=flush). 그래서 줄의 수가 많으면 비정상적으로 느려지게 됩니다. 대신 '\n'을 출력하면 이것은 그냥 문자를 하나 출력하는 행동이기 때문에 flush를 하지 않게 됩니다.

세상에... 그렇군요.

너무 설명을 잘 해주셨습니다 너무 감사드립니다.

혹시 그럼 제가 이해한 부분이 맞는지 혹시 봐주실수있을까요?

예를들자면 1000 * 1000 짜리 matrix 형태로 정수가 들어오는 문제가있을경우 해당 데이터는

1 2 3 4 ... 1000

1001 1002 ..... 2000 

..

..

.

이런식으로 들어옵니다.

이것을 항상 cin >> number; 형태로 input 받게된다면 System Call 을 1000*1000번 진행하게 되지만,

cin.getline() 으로 받아온다면 System Call 을 1000번만 진행하게 되고

해당 라인에 대해 정수만 추출하는 문자열파싱부분만 따로 구현하는식으로 훨씬 더 빠르게 동작이 되는건가요?

만약에 1000 * 1000 짜리 input 이 1000개씩 1000줄이 아니라

1개씩 1000*1000 줄이라면, 그렇다면 fastio 를 굳이 사용할필요가 없게되는건가요?

무슨 Fast IO를 물어보는건지 궁금합니다. 사람마다 다른 의미로 사용하더라고요.

1. ios_base::sync_with_stdio(false); cin.tie(nullptr); 인가요

2. 아니면 위에 kipa00님이 설명한 방법인가요?

Fast IO 에 종류가 여러가지 있는줄은 몰랐습니다.

제가 제일 궁금했던 방식이 C언어로 구현하신분들 코드중 따로 함수를 사용해서 fast IO를 하신분들 코드가 궁금해서 질문을 드린거였습니다.

해당 질문이 해결되면...

C++에서  ios_base::sync_with_stdio(false); cin.tie(nullptr); 의 동작원리도 질문드리고 싶습니다.

저는 위에서 kipa00님이 설명한 방식만 Fast IO라 생각합니다. 

이것을 항상 cin >> number; 형태로 input 받게된다면 System Call 을 1000*1000번 진행하게 되지만,
cin.getline() 으로 받아온다면 System Call 을 1000번만 진행하게 되고
해당 라인에 대해 정수만 추출하는 문자열파싱부분만 따로 구현하는식으로 훨씬 더 빠르게 동작이 되는건가요?

cin >> number; 형태로 받아온다고 해도 system call을 1,000,000번 진행하는 것은 아닙니다. 위에서는 출력만 설명했지만, 출력과 마찬가지로 입력도 필요한 것보다 더 많이 받은 다음 buffer에 넣습니다. 따라서 실제로는 1,000,000번보다는 작을 것입니다. 물론 cin.getline()은 한 줄을 전부 받아서 처리하기 때문에, (모든 줄이 buffer의 크기보다 길기만 하다면) 1,000번의 system call이 일어나게 될 것입니다. 이 경우 엄청난 속도 향상이 있을 것 같지는 않습니다.

fread 등의 함수를 사용하면, 줄 수(혹은 '\n')와 관계없이 여러 문자를 한 번에 읽을 수 있게 됩니다. 예를 들어 1,048,576개의 문자씩 읽는다면 전체 데이터를 읽는 데 3~10번의 system call이면 끝날 것입니다. 이 정도로 줄여야 비로소 입력 시간에 대한 득을 볼 수 있습니다.

만약에 1000 * 1000 짜리 input 이 1000개씩 1000줄이 아니라
1개씩 1000*1000 줄이라면, 그렇다면 fastio 를 굳이 사용할필요가 없게되는건가요?

반은 맞는 말입니다. 정확하게는 cin.getline()으로 입력을 받는 경우와 cin >> number;로 입력을 받는 것에 차이가 없이 똑같이 느리다고 할 수 있겠습니다. 속도의 이득을 보려면 개행 문자도 일반 문자와 똑같이 취급하고 무식하게 많이 읽는 fread 등의 함수를 사용해야 합니다.

Fast IO 에 종류가 여러가지 있는줄은 몰랐습니다.
제가 제일 궁금했던 방식이 C언어로 구현하신분들 코드중 따로 함수를 사용해서 fast IO를 하신분들 코드가 궁금해서 질문을 드린거였습니다.

PS의 여러 학술지에 소개된 technique들과는 다르게 fast IO는 논문에 소개된 technique는 아닙니다. 적어도 제 quick research는 fast IO가 반도체 쪽에서 일하시는 분들이 semiconductor/bus 등을 최적화해서 만든 것들에 이 이름을 다는 것 같습니다. (term이 여기서 따온 것일 수는 있습니다. 혹시 다른 분이 fast IO를 PS에서 쓰는 대로 논문에서 쓰는 용례를 발견하셨다면, 자유롭게 반박해 주세요.) 전혀 다른 의미로 사용되고 있으니 fast IO라고 하면서 뭘 부르시든 누가 논거를 들어 반박할 수는 없을 것 같습니다. 다만 PS계에서의 consensus에 따르면 fast IO는 "C/C++ 계열의 언어에서 종종 발생하는, 표준 header에서 제공되는 buffer를 회피해서 출력하는 방법"을 통틀어 이르는 말로 사용되고 있습니다.

해당 질문이 해결되면...
C++에서 ios_base::sync_with_stdio(false); cin.tie(nullptr); 의 동작원리도 질문드리고 싶습니다.

ios_base::sync_with_stdio(false); cin.tie(nullptr);는 조금 많이 다른 얘기입니다. 이 두 구문을 써 줘야 iostream에서 속도의 이득을 볼 수 있다는 것은 iostream이 내부적으로 일관성을 위해 여러 buffer의 눈치를 보기 때문입니다.

iostream은 cstdio보다 풍부한 입출력을 지원하기 위해 자체적인 buffer를 사용합니다. 즉 iostream으로 출력하는 경우 iostream의 버퍼를 거치고 출력해야 할 때 printf 등이 사용하는 buffer를 거쳐서 출력됩니다. (참고하시되 이해하지 않으셔도 좋은 내용은, 이것을 double buffering으로 부르지 않습니다: double buffering은 사용자에게 보이는 pts의 출력을 매끄럽게 하기 위해 화면의 buffer를 이중으로 들고 있는 것을 말합니다.) 만일 사용자가 iostream의 함수들과 cstdio의 함수들을 섞어 쓰면, 사용자가 이들 함수를 호출한 순서와 다르게 cstdio의 버퍼 크기와 관련해서 입출력이 뒤죽박죽 섞이는 현상이 일어납니다. 따라서 기본적으로 iostream은 cstdio의 눈치를 보면서 행동하는데, 이 과정에서 매번 system call이 사용됩니다.

ios_base::sync_with_stdio(false);는, 앞으로는 눈치 보느라 system call을 안 써도 되니 입출력의 일관성을 무시하고 관리하고 있는 버퍼를 직접 flush하라는 명령입니다. system call의 횟수가 줄어들 테니 당연히 속도는 빨라지고, cstdio 쪽을 신경쓰지 않으니 당연히 cstdio의 함수들과 섞어서 호출하면 입출력이 뒤죽박죽 섞이게 되는 현상이 일어납니다.

cstdio의 눈치만 안 보면 될까요? PS에서는 상관없겠지만, 많은 real-world console application에서는 출력을 prompt의 형태로도 사용합니다.

쉬운 말로 하면, 이를테면 "나이를 입력하세요: "와 같은 것을 출력하고 입력을 기다리는데 출력을 buffer에 저장해 놓고만 있다면, 사용자는 아무 것도 안 보이는데 프로그램이 멈춘 것처럼 보입니다. 이를 방지하기 위해서 iostream에서는 cout를 통해 출력된 것을 cin 때 모두 flush하게 됩니다. flush하면 system call이 일어나게 되고, 그래서 결국 출력할 때마다 flush하는 것과 별반 다르지 않게 됩니다. 이도 결국 입력할 때마다 출력 buffer의 눈치를 보는 셈입니다. cin.tie(nullptr);은 이마저도 신경쓰지 말고 알아서 하라는 뜻입니다.

결론적으로, 이 두 구문을 사용하면 iostream의 입출력이 본인들의 buffer만 사용해서 일어나게 되고, 그래서 cstdio 정도로 빨라지게 됩니다. cstdio가 이런 일을 할 필요가 없는 이유는 결론적으로는 프로그래머들이 system call을 직접 날리는 것에 익숙지 않고, 그래서 cstdio의 여러 library function들을 사용해서 작업을 진행하도록 합의했기 때문입니다. 이에 대해서는 궁금하시면 추가로 글을 더 작성하도록 하겠습니다.

너무 감사드리고 여러번 들어와 읽게 될 것 같습니다. 감사합니다.

@kipa00

질문자는 아니지만 너무나도 흥미롭고 유익한 지식을 공유해주셔서 감사합니다. 괜찮으시다면 cstdio의 여러 라이브러리 함수들을 사용해서 작업을 진행하도록 했다는 부분에 대해서 설명 혹은 관련 내용에 대한 링크를 부탁드려도 될까요?