read, write, mmap을 이용한 Fast I/O 구현 (1)

Introduction

입출력 연산은 C++에서 가장 무거운 연산 중 하나입니다. 일반적인 산술 및 논리 연산은 대략 $1$초에 $1$억 번 정도 수행할 수 있는 것으로 알려져 있지만, 입출력 연산은 입력 또는 출력 값의 개수가 $10^5$ 이상만 되어도 입출력 속도가 전체 실행 시간에 상당한 영향을 줄 수 있습니다. (참고)

이럴 때 표준 스트림 함수인 cin, cout 대신 read, write와 같은 저수준 입출력 함수를 사용하면 입출력 시간을 유의미하게 줄일 수 있습니다. 다만 이 함수들은 문자열 이외의 자료형을 자동으로 처리하지 않기 때문에, 직접 파싱과 형변환을 해줘야 합니다. 이러한 방식의 입출력 최적화를 통틀어 FastIO(Fast Input/Output)라 부릅니다.

본 주제는 두 부분으로 나누어 다룰 예정입니다. 이번 글에서는 C++의 저수준 입출력 함수(read, write, mmap)의 사용법과 빠른 입력/출력 구현 방법, 그리고 비트 연산을 활용한 추가 최적화 기법을 소개합니다. 다음 글에서는 Bit-Twiddling Hack을 적용한 더 빠른 입력 기법과 Lookup Table 및 SIMD를 활용한 출력 기법을 자세히 살펴보겠습니다.

Low-Level I/O

`read`

ssize_t read(int fd, void* buf, size_t count);

read는 유닉스 계열 시스템에서 사용하는 저수준 입력 함수입니다.

fd는 파일 디스크립터로 표준 입력은 0입니다. buf는 입력 데이터를 저장할 버퍼의 시작 위치입니다. count는 데이터의 최대 바이트 수이며, 반환값은 실제로 읽은 바이트 수입니다.

read를 이용하면 길이가 count인 문자열 단위로 입력을 받을 수 있습니다.

`write`

ssize_t write(int fd, const void* buf, size_t count);

write는 유닉스 계열 시스템에서 사용하는 저수준 출력 함수입니다.

fd는 파일 디스크립터로 표준 출력은 1입니다. buf는 출력 데이터를 담은 버퍼의 시작 위치입니다. count는 데이터의 최대 바이트 수이며, 반환값은 실제로 출력한 바이트 수입니다.

write를 이용하면 길이가 count인 문자열 단위로 출력을 할 수 있습니다.

`mmap`

void* mmap(void* addr, size_t length, int prot, int flags, int fd, off_t offset);

mmap은 유닉스 계열 시스템에서 사용하는 저수준 메모리 매핑 함수입니다.

addr은 매핑할 가상 메모리 주소로 보통 nullptr을 사용하여 커널이 주소를 자동으로 선택하게 합니다. length는 매핑할 바이트 수입니다. prot는 접근 권한을 지정하며 일반적으로 읽기 전용 매핑인 PROT_READ를 이용합니다. flags는 매핑 방식을 지정하며 일반적으로 MAP_SHARED를 이용합니다. fd는 매핑할 파일의 파일 디스크립터이며, 표준 입력을 매핑하려면 0을 이용합니다. offset은 파일에서 매핑을 시작할 위치이며, 일반적으로 0으로 설정합니다.

mmap을 이용하면 입력 파일 전체를 메모리에 직접 매핑한 뒤 포인터만 이동시키며 빠르게 데이터를 읽을 수 있습니다. 이는 반복적인 read 호출이 필요 없어 대용량 입력을 처리할 때 효율적입니다.

read, write 함수는 unistd.h 헤더에, mmap 함수는 sys/mman.h 헤더에 정의되어 있습니다. 이 헤더들은 유닉스 계열 시스템(Linux, macOs 등)에서만 지원되며, Windows 환경에서는 사용할 수 없습니다. 따라서 이 함수들을 사용할 수 있는 채점 환경은 제한적이지만, 대부분의 알고리즘 온라인 저지 플랫폼인 Backjoon Online Judge, Codeforces, AtCoder 등은 Linux 기반이기 때문에 문제 없이 사용할 수 있습니다.

Fast I/O Implementation

read, write를 이용한 빠른 입력/출력 구현은 입력 버퍼 char r[rbuf_sz]와 출력 버퍼 char w[wbuf_sz]와 포인터 char* pr, char* pw를 이용합니다.

pr은 입력 버퍼에서 아직 읽지 않은 값의 시작 위치를 나타내며, 입력 버퍼의 끝에 도달하면 read(0, p = r, rbuf_sz)를 이용해 다시 입력 버퍼를 채웁니다. pw는 출력을 수행할 위치를 나타내며, 값을 출력할 충분한 공간이 남아있지 않다면 write(1, w, pw - w), pw = w로 출력 버퍼를 비워줍니다.

구현 코드는 $[-10^9, 10^9]$ 범위의 정수가 $2 \times 10^6$개 입력되는 BOJ 11728를 이용해 테스트했습니다. base code는 다음과 같습니다. (코드)

Fast Input Implementation using `read`

#include <unistd.h>

constexpr int rbuf_sz = 1 << 20;

int main() {
	char r[rbuf_sz], *pr = r; read(0, r, rbuf_sz);
	auto read_char = [&] {
		if (pr - r == rbuf_sz) read(0, pr = r, rbuf_sz);
		return *pr++;
	};
	auto read_int = [&] {
		int ret = 0, flag = 0;
		char c = read_char();
		while (c == ' ' || c == '\n') c = read_char();
		if (c == '-') flag = 1, c = read_char();
		while (c != ' ' && c != '\n') ret = 10 * ret + c - '0', c = read_char();
		if (flag) ret = -ret;
		return ret;
	};
}

read_char는 입력 버퍼로부터 문자를 하나 읽어오는 함수입니다. 현재 포인터 pr이 입력 버퍼 r의 끝에 도달했는지 확인한 후, 만약 도달했다면 read(0, pr = r, rbuf_sz)를 호출하여 새로운 입력을 버퍼에 채우고 포인터를 다시 시작 위치로 되돌립니다. 이후 포인터가 가리키는 문자를 반환하고 포인터를 한 칸 이동시킵니다. read_int에서는 read_char를 이용해 입력을 받습니다.

read_int는 부호 있는 정수 자료형의 입력을 받는 함수입니다. 함수는 크게 세 단계로 나뉘어 동작합니다. 먼저 입력 버퍼에 공백 또는 줄바꿈이 있다면 해당 글자를 건너뛰어줍니다. 이후 글자가 -인지 확인하며 수가 음수인지 여부를 확인합니다. 다음으로 숫자를 순서대로 순회하며 ret = 10 * ret + c - '0'로 파싱을 진행합니다.

사용 예시는 다음과 같습니다. (코드)

Fast Input Implementation using `read` with assumption

문제 입력에 공백 또는 줄바꿈이 연속해서 $2$번 이상 등장하지 않는다면 첫 번째 단계를 생략할 수 있습니다. 이때 read_int 함수가 호출되는 시점에 pr이 공백 또는 줄바꿈이 아닌 글자를 가리키고 있도록 세심한 구현이 필요합니다. 또한 입력되는 정수가 $0$ 이상이라면 두 번째 단계를 생략할 수 있습니다. 아래는 해당 조건을 가정한 read_int 함수의 구현 코드입니다.

auto read_int = [&] {
	int ret = 0;
	char c = read_char();
	while (c != ' ' && c != '\n') ret = 10 * ret + c - '0', c = read_char();
	return ret;
};

사용 예시는 다음과 같습니다. (코드)

Fast Input Implementation using `mmap`

mmap을 이용한다면 입력 버퍼를 다시 채울 필요가 없어서 read_char 대신 *pr++로 char의 입력을 받을 수 있습니다. 아래는 mmap를 이용한 구현 코드입니다.

#include <sys/mman.h>

constexpr int max_input_sz = 1 << 24;

int main() {
	char* pr = (char*)mmap(nullptr, max_input_sz, PROT_READ, MAP_SHARED, 0, 0);
	auto read_int = [&] {
		int ret = 0, flag = 0;
		while (*pr == ' ' || *pr == '\n') pr++;
		if (*pr == '-') flag = 1, pr++;
		while (*pr != ' ' && *pr != '\n') ret = 10 * ret + *pr++ - '0';
		if (flag) ret = -ret;
		return ret;
	};
}

max_input_sz는 입력 파일의 바이트 수의 최댓값입니다. 일반적으로 problem solving 환경에서 max_input_sz는 $2^{24}$ scale이며, $2^{28}$를 넘지 않습니다. sys/stat.h 헤더의 fstat 함수를 이용하면 struct stat st; fstat(0, &st);에서 st.st_size로 입력 파일의 바이트 수를 직접 알아낼 수도 있습니다.

사용 예시는 다음과 같습니다. (코드)

Fast Input Implementation using `mmap` with assumption

마찬가지로 연속된 공백, 줄바꿈이 없거나 $0$ 이상인 정수만 입력된다면 아래와 같이 구현을 간소화할 수 있습니다.

#include <sys/mman.h>

constexpr int max_input_sz = 1 << 24;

int main() {
	char* pr = (char*)mmap(nullptr, max_input_sz, PROT_READ, MAP_SHARED, 0, 0);
	auto read_int = [&] {
		int ret = 0;
		while (*pr != ' ' && *pr != '\n') ret = 10 * ret + *pr++ - '0';
		pr++;
		return ret;
	};
}

사용 예시는 다음과 같습니다. (코드)

Optimization using ASCII Code

입력 파일에 주로 등장하는 문자의 ASCII 코드는 아래와 같습니다.

| Character | ASCII Value | Binary Representation |
|-----------|-------------|-----------------------|
| '\n'      | 10          | 0b00001010            |
| ' '       | 32          | 0b00100000            |
| '-'       | 45          | 0b00101101            |
| '0'       | 48          | 0b00110000            |
| '1'       | 49          | 0b00110001            |
| ...       | ...         | ...                   |
| '9'       | 57          | 0b00111001            |

문자의 ASCII 코드의 이진수 표현을 관찰하면 숫자가 아닌 값은 $2^4$를 나타내는 비트가 0인 걸 알 수 있습니다. 또한 숫자는 해당 숫자의 이진수 표현에서 $2^4$, $2^5$를 나타내는 비트가 추가로 1이 된 형태입니다.

이 사실을 이용하면 비트 연산을 이용해 read_int 함수를 구현할 수 있습니다.

auto read_int = [&] {
	int ret = 0;
	while (*pr & 16) ret = 10 * ret + (*pr++ & 15);
	pr++;
	return ret;
};

사용 예시는 다음과 같습니다. (코드)

Optimization using Bitwise Operation

$10 = 2^3 + 2^1$이기 때문에 10 * n은 (n << 3) + (n << 1)과 동일합니다. 이를 이용하면 곱셈 연산 $1$개를 $2$번의 bitwise shift 연산과 $1$번의 덧셈 연산으로 대체할 수 있습니다. 하지만 대부분의 컴파일러는 이와 같은 최적화를 자동으로 수행하기 때문에, 실행 시간 상의 성능 차이는 거의 없습니다.

Fast Output Implementation using `write`

char, int의 출력은 write를 이용해 구현합니다.

#include <unistd.h>

constexpr int wbuf_sz = 1 << 20;

int main() {
	char w[wbuf_sz], *pw = w;
	auto write_char = [&](char c) {
		if (pw - w == wbuf_sz) write(1, w, pw - w), pw = w;
		*pw++ = c;
	};
	auto write_int = [&](int x) {
		if (pw - w + 100 > wbuf_sz) write(1, w, pw - w), pw = w;
		if (x < 0) *pw++ = '-', x = -x;
		char t[10], *pt = t;
		do *pt++ = x % 10 + '0'; while (x /= 10);
		do *pw++ = *--pt; while (pt != t);
	};
}

write_int는 부호 있는 정수 자료형을 출력하는 함수입니다. 함수는 크게 세 단계로 나뉘어 동작합니다. 먼저 출력 버퍼에 남은 공간이 충분하지 않다면 출력 버퍼를 비워줍니다. 이후 x가 음수라면 출력 버퍼에 -를 기록한 뒤 x를 -x로 바꿔줍니다. 마지막으로 x의 작은 자릿수부터 임시 버퍼에 기록한 뒤 역순으로 순회하며 출력 버퍼에 기록해주면 출력을 구현할 수 있습니다.

wbuf_sz는 작게 설정하면 메모리를 적게 사용하지만 write 함수 호출이 많아 느려지고, 크게 설정하면 메모리를 많이 사용하지만 실행 시간이 줄어듭니다. 일반적으로는 $2^{20}$ 정도로 설정해 사용합니다.

사용 예시는 다음과 같습니다. (코드)

auto write_int = [&](int x) {
	if (pw - w + 100 > wbuf_sz) write(1, w, pw - w), pw = w;
	char t[10], *pt = t;
	do *pt++ = x % 10 | 48; while (x /= 10);
	do *pw++ = *--pt; while (pt != t);
};

출력하는 값이 $0$ 이상이라면 두 번째 단계를 생략할 수 있으며, '0'를 더하는 부분은 ASCII 코드를 이용해 | 48로 대체할 수 있습니다.

사용 예시는 다음과 같습니다. (코드)

auto write_int = [&](int x) {
	if (pw - w + 100 > wbuf_sz) write(1, w, pw - w), pw = w;
	int sz = 1, t = x;
	while (t >= 10) sz++, t /= 10;
	for (int i = sz - 1; i >= 0; i--) pw[i] = x % 10 | 48, x /= 10;
	pw += sz;
};

임시 버퍼를 이용하는 대신 수의 자릿수를 먼저 구하는 방식으로도 구현할 수 있습니다. 하지만 이 방법은 나눗셈 횟수가 증가하기 때문에 임시 버퍼를 활용하는 방식에 비해 성능 면에서 비효율적일 수 있습니다.

사용 예시는 다음과 같습니다. (코드)

Summary

이번 글에서는 저수준 입출력 함수(read, write, mmap)를 활용하여 입력과 출력을 빠르게 처리하는 방법을 살펴보았습니다. read 함수는 메모리 사용량이 적고 구현이 간단하다는 장점이 있지만, 입력 버퍼를 주기적으로 다시 채워야 하므로 대규모 입력에서는 성능 저하가 발생할 수 있습니다. 반면 mmap은 입력 파일 전체를 메모리에 매핑하여 포인터 연산만으로 데이터를 읽어올 수 있어 더욱 빠른 처리가 가능하지만, 상대적으로 메모리 사용량이 많아집니다. 이러한 특성에 따라 사용 환경에 맞는 방식을 선택하는 것이 중요합니다. write 함수는 출력 버퍼를 직접 관리하여 여러 번의 출력 호출을 최소화함으로써 출력 속도를 크게 향상시킬 수 있으며, 특히 수많은 정수를 출력해야 하는 경우 매우 효과적입니다.

또한 입력 데이터의 특성을 활용하여 추가적인 최적화를 적용하는 방법에 대해서도 알아보았습니다. 입력에 음수가 등장하지 않거나 연속된 공백이 포함되지 않는 경우 불필요한 검사를 생략함으로써 입출력 속도를 더욱 향상시킬 수 있습니다. 이처럼 데이터의 조건을 적극적으로 활용하면 실행 시간을 추가로 단축할 수 있습니다.

대부분의 알고리즘 문제에서는 저수준 입출력 함수만 적용하더라도 입출력에 소요되는 시간을 충분히 줄일 수 있습니다. 특히 입력 크기가 수십만 개 이상인 경우, 표준 스트림(cin, cout) 대신 저수준 함수를 사용하는 것만으로도 실행 시간을 획기적으로 단축할 수 있습니다.

이보다 더 극단적인 성능 최적화가 필요한 특수한 경우에는 Bit-Twiddling Hack, Lookup Table, SIMD 명령어 등을 활용한 추가 최적화 기법이 필요할 수 있습니다. 다음 글에서는 이러한 복잡한 최적화 기법들을 구체적으로 살펴보고, 각각의 방법이 입출력 성능을 어떤 원리로 향상시키는지 알아보겠습니다.

References

[1] https://man7.org/linux/man-pages/man2/read.2.html

[2] https://man7.org/linux/man-pages/man2/write.2.html

[3] https://man7.org/linux/man-pages/man2/mmap.2.html

[4] https://cgiosy.github.io/posts/fast-io

read, write, mmap을 이용한 Fast I/O 구현 (1)

Introduction

Low-Level I/O

read

write

mmap

Fast I/O Implementation

Fast Input Implementation using read

Fast Input Implementation using read with assumption

Fast Input Implementation using mmap

Fast Input Implementation using mmap with assumption

Optimization using ASCII Code

Optimization using Bitwise Operation

Fast Output Implementation using write

Summary

References

cracking mysql_hash_password

`read`

`write`

`mmap`

Fast Input Implementation using `read`

Fast Input Implementation using `read` with assumption

Fast Input Implementation using `mmap`

Fast Input Implementation using `mmap` with assumption

Fast Output Implementation using `write`