매우 빠른 입출력

FAST IO

사실 입출력은 우리가 짜는 명령어만으로는 구현할 수 없다. 덧셈, 뺄셈 등등으로는 파일에 내용을 작성하는 등의 동작이 불가능하기 때문이다. 이러한 동작은 시스템 콜(system call)로서 이루어진다. OS에서 제공하는 API를 호출하여 원하는 내용을 작성할 수 있도록 OS에게 알려주면, OS에서 출력을 실행하고, 실행 결과를 알려준다. 보통 사용하는 printf와 scanf역시 내부에서는 입출력 관련한 시스템 콜을 호출하여, 원하는 동작을 처리한다.

입출력 관련된 시스템 콜은 여러가지 있지만 그 중에서도 read과 write를 이용했다. fread, fwrite를 이용해도 되지만, 어차피 두 API의 작성 난이도가 크게 차이나지 않았기 때문이다.

작동방식은 다음과 같다.

입력

1. 버퍼에 일정 크기만큼 open을 이용해 표준입력으로부터 데이터를 담고, 커서를 0으로 초기화한다.
2. int, char, string 등의 입력을 위해, 커서를 1씩 증가시키며 데이터를 읽는다.
   • 이 때, 현재 커서가 버퍼 크기에 도달하면 다시 표준 입력으로부터 데이터를 담고 커서를 0으로 초기화한다.

출력

1. 커서를 0으로 초기화한다.
2. 버퍼에 우리가 원하는 데이터를 작성한다.
   • 만약 작성 중에 커서가 버퍼 사이즈에 도달한다면 write를 호출하여 표준 출력에 출력하고 커서를 0으로 초기화한다.
3. 프로그램이 종료될 때, 즉 클래스가 소멸할때 파괴자에게 버퍼를 표준 출력에 출력하도록 한다.

아래는 구현한 내용으로, cin, cout으로 이용 가능하다.

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <string>
#include <unistd.h>
#include <iostream>
#include <cstring>
#define BUF_SIZE (1 << 20)
struct INPUT {
	int endcursor;
	int cursor;
	char buf[BUF_SIZE] = {0,};

	void read_buf() { cursor = 0; endcursor = read(0, buf, BUF_SIZE); }
	INPUT() { read_buf(); }
	void check_endpoint() { if (cursor == endcursor) read_buf(); }
	void eat_whitespace() { 
		while (buf[cursor] == ' ' || buf[cursor] == '\n') {
			cursor++; check_endpoint();
		}
	}
	template<typename T> T readint() {
		eat_whitespace(); bool minus = false;
		if (buf[cursor] == '-') { minus = true; cursor++; }
		int ret = 0;
		while (buf[cursor] != ' ' && buf[cursor] != '\n' && buf[cursor] != 0) {
			ret *= 10; ret += buf[cursor++] - '0'; check_endpoint();
		}
		return minus ? -ret : ret;
	}
	char readchar() {
		char ret = buf[cursor++]; check_endpoint();
		return ret;
	}
	std::string readstring() {
		eat_whitespace(); std::string ret;
		while (buf[cursor] != ' ' && buf[cursor] != '\n') {
			ret.push_back(buf[cursor++]); check_endpoint();
		}
		return ret;
	}
    std::string getline() {
        std::string ret;
        while (buf[cursor] != '\n') {
            ret.push_back(buf[cursor++]); check_endpoint();
        }
        return ret;
    }
	void readcstring(char *c) {
		eat_whitespace(); int cur = 0;
		while (buf[cursor] != ' ' && buf[cursor] != '\n') {
			c[cur++] = buf[cursor++]; check_endpoint();
		}
		c[cur] = 0;
	}
} _input;

struct OUTPUT {
	char buf[BUF_SIZE];
	int cursor;	
	void write_buf() {
		write(1, buf, cursor); cursor = 0;
	}
	OUTPUT() : cursor(0) {}
	~OUTPUT() { write_buf(); }
	void check_endpoint() { if (cursor == BUF_SIZE) write_buf(); }
	template<typename T> void writeint(T &t) {
        if (!t) { buf[cursor++] = '0'; check_endpoint(); }
		char tmp[22]; int cur = 0; bool minus = false;
        if (t < 0) minus = true, t = -t;
		while (t) { tmp[cur++] = t % 10 + '0'; t /= 10; }
		if (minus) tmp[cur++] = '-';
		for (int i = cur - 1; i >= 0; --i) { 
            buf[cursor++] = tmp[i]; check_endpoint(); 
        }
	}
	void writechar(char &c) { buf[cursor++] = c; check_endpoint(); }
	void writestring(std::string &s) { for (int i = 0; i < s.size(); ++i) { buf[cursor++] = s[i]; check_endpoint();} }
} _output;
#undef BUF_SIZE

INPUT& operator>>(INPUT &in, int &t) { t = in.readint<int>(); return in; }
INPUT& operator>>(INPUT &in, long long &t) { t = in.readint<long long>(); return in; }
INPUT& operator>>(INPUT &in, std::string &s) { s = in.readstring(); return in; }
INPUT& operator>>(INPUT &in, char &c) { c = in.readchar(); return in; }
INPUT& operator>>(INPUT &in, char *c) { in.readcstring(c); return in; }
OUTPUT& operator<<(OUTPUT &out, int t) { out.writeint<int>(t); return out; }
OUTPUT& operator<<(OUTPUT &out, long long t) { out.writeint<long long>(t); return out; }
OUTPUT& operator<<(OUTPUT &out, char c) { out.writechar(c); return out; }
OUTPUT& operator<<(OUTPUT &out, std::string s) { out.writestring(s);	return out; }
OUTPUT& operator<<(OUTPUT &out, char *c) { for (int i=0; c[i]; ++i) out.writechar(c[i]); return out; }

#define cin _input
#define cout _output
#define endl '\n'

여기서 -O3옵션과 -avx2옵션을 주지 않으면 속도가 좀 느렸는데, 이 이유는 사실 추측이 잘 안된다. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 로 빠른 입출력을 구현한 것보다 대략 2배 이상은 더 빠른 것으로 보인다. 이러한 low-level fastio는 항상 박진한님이 작성한 것으로 사용했었는데, 이렇게 스스로 작성하고 보니 상당히 뿌듯하다.

버그

1. 정수 자료형의 overflow로 인해서 $-2^{31}$, $-2^{63}$ 등을 인식하지 못하는 버그가 있습니다.