Fast I/O
그 누구보다 빠르게
개요
PS를 할 때, 남들보다 빠른 실행시간으로 통과하면 누구라도 기분이 좋을 것이다. 프로그램의 실행시간 중 의외로 상당량의 시간을 차지하는 부분이 바로 I/O인데, 이 글에서는 빠른 I/O를 사용하여 프로그램의 실행시간을 줄이는 방법에 대해 알아볼 것이다.
보통의 사람이라면...
C++ 유저라면 기본적으로 cin이나 cout을 쓸 것이다. 그리고, 단순히 이 객체를 사용한다면 C의 scanf나 printf보다 더 느리다는 것을 체감했을 것이다. 다음의 코드를 보자.
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int a, b, ans;
cin >> a >> b;
/* 처리하는 코드 */
cout << ans << endl;
}
return 0;
}
뭐 좋다. 이렇게 짤 수 있지. 틀린 건 아니다. 하지만, 하다못해 줄바꿈을 위해 endl을 사용하지는 말 것을 권한다. 출력을 여러번 해야하는 문제의 경우 TLE나기 딱 좋은 코드다. 이를 설명하기 위해서는 먼저 버퍼에 대한 개념이 필요한데, 입력버퍼와 출력버퍼란 게 있다. 스트림에서 데이터를 읽어올 때는 버퍼를 중간에 두고 일정량만큼 버퍼에 가져온 뒤, 버퍼에서 데이터를 읽는다. 출력도 마찬가지로, 바로바로 스트림으로 출력하는 것이 아니라 버퍼에 출력할 내용물을 쌓아둔 뒤 가득차면 그 때 출력해준다(flush한다고 한다). 그리고, 여기서 endl은 flush의 역할을 한다. 이렇게 되면 속이 터질 정도로 느려지게 된다.
그럼 endl 대신 뭘 써요?
간단하다. '\n'을 쓰면 된다. 우리의 목적은 flush가 아니라 개행이니까.
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int a, b, ans;
cin >> a >> b;
/* 처리하는 코드 */
cout << ans << '\n';
}
return 0;
}
고작 endl을 '\n'로 바꿔준 것만으로도 TLE가 AC로 바뀌는 경우가 의외로 많다. 사실 맞는 코드를 짠 건데 endl 때문에 틀린 거라면 그야말로 맞왜틀이다. 하지만 여전히 C의 scanf/printf가 더 빠르다. C++은 C에게 뒤쳐져야만 하는 처지인가?
sync를 끊어주자
사실, C++의 cin/cout이 느린 이유는 따로 있다. 바로 C의 입출력 버퍼와 C++의 입출력 버퍼의 동기화 때문이다. 버퍼는 분리되어 있는데 C에서 scanf로 데이터를 읽으면 C++의 버퍼에서도 그만큼 읽었다고 동기화 처리를 해야하니 느렸던 것이다. 이 동기화는 끊는 코드는 다음과 같다.
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int a, b, ans;
cin >> a >> b;
/* 처리하는 코드 */
cout << ans << '\n';
}
return 0;
}
보통 다른 사람들은 ios_base::sync_with_stdio를 쓰거나, ios::sync_with_stdio를 쓰는 것을 한 번쯤 본 적 있을 것이다. ios는 basic_ios<char>이고 basic_ios는 ios_base를 상속한다. cin은 istream의 인스턴스이며 istream은 basic_istream<char>이다. basic_istream은 basic_ios을 상속한다. 정리하면 cin의 부모를 타고 가다보면 ios_base가 나오고, ios_base에는 sync_with_stdio가 정적 메소드로 존재한다. cin.sync_with_stdio를 써도 결국 같은 메소드를 호출하므로 상관없다. 타이핑이 더 간단해지니 이 방법을 쓰자.
이제부터 우리는 C의 입출력 함수와 C++의 입출력 함수를 혼용해서 쓸 수 없다. 뭐 쓴다고 오류날 건 아니지만 동기화가 끊어져 있으니 의도치 않은 흐름으로 동작할 수 있다. 그냥 혼용해서 쓰지 말자.
cout과의 untie
기본적으로 cin은 cout과 tie 되어있다. 이게 뭔 소리일까? cout으로 뭔가를 출력하고 cin으로 입력을 받을 경우 당연히 stdout에 출력이 먼저 된 후(flush 됨), 입력을 받을 것을 기대할 수 있다. 여기서 cin을 cout으로부터 untie 해주면 더 이상 출력이 먼저 일어나지 않는다. 출력버퍼에 내용물이 가득 차면 그때서야 stdout으로의 출력이 발생한다. 그 전까지는 출력이 되지 않으므로, 직접 실행해보면 입력을 먼저 받는 것으로 보이게 된다. 이 말인즉슨, 입력과 출력이 서로 번갈아 발생할 경우 매번 flush를 안 하게 되므로 더욱 코드가 빨라진다는 뜻이다! untie는 다음의 코드를 적어줌으로써 할 수 있다.
cin.tie(nullptr);
이게 정말 효과가 있을지 의심하는 사람들을 위해, 중간점검을 해보도록 하자.
1000만개의 정수를 읽고 출력할 때 시간 체크
- endl을 사용: 53.340541700초
- '\n'을 사용: 15.399621300초
- "\n"을 사용: 15.418385500초 (번외)
- sync 끊어줌: 15.395691000초
- untie 해줌: 13.825059300초
- scanf/printf 사용: 5.236829900초
어...... 왠진 모르겠지만 드럽게 오래 걸리고 차이가 은근 코딱지만큼인것으로 보인다. 이건 내 컴퓨터가 구데기라서 그런 것으로 생각하고 넘어가자. 근데 scanf/printf가 왜 더 빠르게 나오는진 모르겠다. 일단 변수가 너무 많아서 어디가 문제인지도 모르겠는데, 백준에서 몇백번 넘게 fastio를 실험한 내 경험에 의하면 sync 끊고 untie 한 cin/cout이 scanf/printf보다 훨씬 빠른 건 사실이다.
입력 커스터마이징
찝찝함을 뒤로 하고, 이제부터 좀 더 본격적인 내용을 다룬다. 빠른 입력을 위해서라면 함수를 직접 짜야하기 때문에 어느 정도의 귀찮음을 감수해야 한다. 가장 기본적으로 getchar를 사용하여 입력받는 방법이 있다. 아니, getchar는 문자를 받아오는 건데 숫자를 입력받는건 어쩌려고? 다 방법이 있다.
int readInt() {
int ret = 0;
char now = getchar();
while (now == 10 || now == 32) now = getchar();
while (now >= 48 && now <= 57) {
ret = ret * 10 + now - 48;
now = getchar();
}
return ret;
}
참고로 위 코드는 입력이 전부 음이 아닌 정수일 때 유효하다. 문자가 들어온다면 그건 알아서 처리하도록. 이 글을 다 읽게 될 때면 알아서 잘 터득하게 되어 있다. 그럼 음의 정수가 들어온다면? 그건 다음처럼 처리가 가능하다.
int readInt() {
int ret = 0, flg = 1;
char now = getchar();
while (now == 10 || now == 32) now = getchar();
if (now == '-') flg = -1, now = getchar();
while (now >= 48 && now <= 57) {
ret = ret * 10 + now - 48;
now = getchar();
}
return ret * flg;
}
그다지 어렵지 않다. 참고로 웬만하면 개행(10)이나 공백(32)으로 화이트스페이스가 모두 걸러지지만, 간혹 예쁘게 정제되지 않은 인풋(특히 옛날 백준문제)에는 상상도 못한 화이트스페이스가 숨어 들어가있는 경우도 있다. 버티컬 탭이라든가, 폼 피드라든가. 이런 경우는 그냥 ctype.h에 있는 isspace 함수를 사용하는 게 편할지도 모르겠다. 하지만, 웬만하면 정말 이 형태로 통과가 된다.
getchar 업그레이드
gcc 컴파일러 한정이지만, 대부분의 온라인저지는 gcc이므로 알아둬서 나쁠 건 없다. getchar_unlocked라는 함수가 있는데, 이를 사용하면 좀더 빠른 성능을 자랑한다. 위의 코드에서 getchar 부분을 모두 getchar_unlocked로 바꾸면 된다.
좀 더 로우레벨로!
getchar는 결국 한 번에 한 문자씩 입력버퍼에서 긁어오는 것이라서 그렇게 엄청 빠른 건 아니다(물론 scanf나 cin으로 입력받는 것보단 훨씬 빠르다). 이왕 긁을거면 아예 자체 버퍼를 만들어서 일단 왕창 읽어두고, 우리가 만든 버퍼에서 읽어오는 게 더 효율적이지 않을까? 여기서 fread가 등장한다.
char buf[1 << 17];
char read() {
static int idx = 1 << 17;
if (idx == 1 << 17) {
fread(buf, 1, 1 << 17, stdin);
idx = 0;
}
return buf[idx++];
}
이렇게 코드를 위에 추가하고, getchar 대신에 read를 적어주자. 딱 보면 알겠지만, 버퍼를 끝까지 읽은 경우 fread를 통해 다시 입력버퍼로부터 1 << 17 바이트를 받아와서 자체 버퍼 buf에 저장하는 것이다. 왜 하필 1 << 17인지는 백준에서 수없이 많이 테스트한 내 경험에서 우러나오는 상수이다. 웬만하면 1 << 17로 충분하고, 가끔 입력량이 무시무시하게 많은 경우에는 조금씩 키우며 조정하면 얼추 상당히 빨라진다.
그리고 이 코드도 가끔 WA를 받는데, 인풋이 정말 말도 안 되는 우연의 일치로 1 << 17의 크기가 맞아 떨어져서 코너케이스가 발생하는 모양이다. 거의 100번 중에 1번 꼴로 이런 경우가 발생하는데, 그럴땐 다음처럼 코드를 수정하면 된다. 뭐, 귀찮으면 아예 처음부터 아래의 코드로 짜도 좋다.
char buf[1 << 17];
char read() {
static int idx = 1 << 17, nidx = 1 << 17;
if (idx == nidx) {
nidx = fread(buf, 1, 1 << 17, stdin);
if (!nidx) return 0;
idx = 0;
}
return buf[idx++];
}
대충 코드를 설명하자면, read 하던 도중 idx가 nidx와 같아져서 새로 fread를 하려고 했더니, 이미 전부 읽은 상황이라 0바이트를 받아왔다는 뜻으로 0을 리턴하여 nidx에 저장하고, 만약 0이 리턴되었다면 그것이 입력이 끝이라는 의미로 0을 리턴해준다.
readInt의 최적화?
최적화라고 해서 거창한 건 아니고, 그냥 비트연산자를 이용해서 미약하지만 조금이나마 속도를 올리겠다는 취지의 코드이다. 이 코드는 음이 아닌 정수를 받아온다.
int readInt() {
int t, r = read() & 15;
while ((t = read()) & 16) r = r * 10 + (t & 15);
return r;
}
출력은 커스터마이징하지 않아도 되는가
출력은 사실 printf로도 충분히 빠르기도 하고, 애초에 입력량이 많이 출력량은 적은 경우가 대다수이다. 하지만 출력량이 많은 경우도 분명 존재는 할 터... 결국 출력도 빠르게 하려면 그때 그때 출력하기보단 직접 버퍼를 만들어서 쌓아두다가 한꺼번에 출력하는 게 함수 오버헤드도 적고 매우 빠른 수행시간을 느낄 수 있다. 이를 위해 정수를 출력하고자 하는 경우 직접 정수의 길이를 구해서 차례대로 버퍼에 앞에서부터 두는 똥꼬쇼를 감수해야 한다.
char outbuf[1 << 17];
void writeInt(int n) {
static int idx = 0;
int len = 0, t = n;
while (t) ++len, t /= 10;
for (int i = len - 1; i >= 0; --i) {
outbuf[idx + i] = n % 10;
n /= 10;
}
idx += len;
outbuf[idx++] = ' ';
}
참고로, 출력버퍼보다 실제 출력의 양이 더 클 경우 도중에 flush하여 초기화하는 작업도 해줘야 한다. 정말이지, 너무 귀찮다. 그래서 보통은 입력만 빠르게 하는 게 일반적이다. 하지만 그런 귀찮음을 감수하고 더 빠른 I/O를 원한다면...
커널에 직접 시스템 콜로 요구
이제부턴 gcc에 의존하는 코드라서 msvc에서 안 돌아간다. 우리는 syscall 함수를 사용할 건데, unistd.h에 선언되어 있으므로 이를 인클루드해야 한다. 이쯤 되면 코드량이 어느 정도 되기 때문에, namespace로 묶어서 선언하곤 한다.
#include <unistd.h>
namespace io {
const int is = 1 << 17, os = 1 << 10;
char ib[is], *ip = ib;
char ob[os + 16], *op = ob;
inline char read() {
if(ib + is == ip) syscall(0, 0, ip = ib, is);
return *ip;
}
inline int readInt() {
int n = 0;
while (read() <= ' ') ip++;
while (read() >= '0') n = (n * 10) + (*ip++ & 15);
return n;
}
inline void flush() {
syscall(1, 1, op = ob, op - ob);
}
struct f {
~f() {
flush();
}
} flusher;
inline void writeInt(int n) {
char temp[16], *t = temp;
do *t++ = n % 10 | 48; while(n /= 10);
do *op++ = *--t; while(t != temp);
*op++ = '\n';
if(op >= ob + os) flush();
}
}
이 코드는 다른 사람이 작성한 fast I/O를 적당히 가져온 것이다. 구현된 부분은 그대로 가져다 쓰고, 구현되지 않은 부분을 알아서 직접 구현하거나 자신의 입맛에 맞게 바꿔서 수정하면 된다(readInt/writeInt의 음수 처리 부분이나 출력 시 구분자 '\n', 출력 버퍼의 크기 등). 자세한 설명은 생략한다.
최후의 보루, 하드웨어 접근
일반적으로 fread등의 함수를 사용하면 프로세스 메모리 공간과 커널 메모리 공간 사이의 메모리 전달 과정이 수반된다. 하지만 리눅스에서는 응용 프로그램에서 직접 하드웨어의 I/O 주소 공간을 메모리 복사 없이 사용할 수 있게 mmap 함수를 제공한다.
#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
...
struct stat buf;
fstat(0, &buf);
char *p = (char *)mmap(0, buf.st_size, PROT_READ, MAP_SHARED, 0, 0);
// readInt example
int t = *p++ & 15;
while (*p > 32) t = t * 10 + (*p++ & 15);
...
...대충 이런 느낌으로 쓰면 되겠다. 이 부분은 궁금한 사람은 직접 찾아보고, '너무 변태 같아요' 하는 생각이 드는 사람은 자기 수준에 적당한 코드 조각을 사용하면 되겠다.
번외
이상으로 글을 마친다. 읽느라 수고 많았다.