[C++] Fast I/O | 빠른 입출력
Fast Input/Output
빠른 입출력
- C/C++에서 많은 I/O(입출력)이 발생하는 경우에 실행시간을 유의미하게 줄일 수 있는 방법이다.
- 주요 언어군에서의 입력 방법에 따른 실행시간 순위는 아래와 같다. (URL)
(천만 개의 10,000 이하 자연수가 적힌 파일을 입력받기를 10회 실시하여 소요시간의 평균을 측정하여 순위를 산정)
| 순위 | 언어 | 입력 방법 | 평균 (sec) |
| 1 | C11 | mmap |
0.043 |
| 2 | C11 | fread |
0.0799 |
| 3 | C11 | getchar |
0.3496 |
| 4 | C++17 | ios_base::sync_with_stdio(false);cin.tie(NULL); |
0.5938 |
| 5 | C++17 | ios_base::sync_with_stdio(false); |
0.6348 |
| 6 | Java | BufferedReader, Integer.parseInt |
0.6585 |
| 7 | C11 | scanf |
0.9206 |
| 8 | PyPy | int(sys.stdin.readline()) |
0.9229 |
| 9 | PyPy | map(int,os.read(0, 100000000).split('\n')) |
1.1169 |
| 10 | PyPy3 | map(int,os.read(0, 100000000).decode('utf-8').split('\n')) |
1.5408 |
| 11 | PyPy | int(raw_input()) |
1.925 |
| 12 | C++17 | cin.tie(NULL); |
2.059 |
| 13 | C++17 | cin |
2.1742 |
| 14 | C# 6.0 | int.Parse(Console.ReadLine()) |
2.9635 |
| 15 | Python 3 | map(int,os.read(0, 100000000).decode('utf-8').split('\n')) |
4.4033 |
| 16 | Python 3 | int(sys.stdin.readline()) |
4.4394 |
| 17 | Java | Scanner |
4.8448 |
| 18 | Python 2 | map(int,os.read(0, 100000000).split('\n')) |
4.8553 |
| 19 | Python 2 | int(sys.stdin.readline()) |
5.7471 |
| 20 | PyPy3 | int(sys.stdin.readline()) |
6.6291 |
| 21 | Python 2 | int(raw_input()) |
8.9765 |
| 22 | Python 3 | int(input()) |
12.4443 |
| 23 | PyPy3 | int(input()) |
17.3772 |
| 24 | Python 2 | input() |
37.7823 |
| 25 | PyPy | input() |
110.3676 |
- 실행시간의 상위권을 차지하는 함수일수록 하드웨어를 직접 제어하는 Low-Level인 경향을 보이고 있다.
- Low-Level I/O 함수를 이용하여 입출력을 처리할 때 I/O 실행시간이 절감되는 이유는 아래와 같다:
- 기존의 입출력 함수는 여러 경우에 대비하기 위해 추가적인 연산을 수행한다.
- 문제의 입출력 조건을 이용하면 모든 경우의 입출력에 대비할 필요가 없어진다.
- 입출력 버퍼의 크기를 크게 하여 한 번에 읽고 내보내는 양을 크게 한다.
C11
#include <sys/mman.h>
/* creates a new mapping in the virtual address space of the calling process. */
void *mmap(
void *addr, // starting address for the new mapping
size_t length, // specifies the length of the mapping (which must be greater than 0)
int prot, // describes the desired memory protection of the mapping (and must not conflict with the open mode of the file)
int flags, // determines whether updates to the mapping are visible to other processes mapping the same region, and whether updates are carried through to the underlying file
int fd, // referred to by the file descriptor
off_t offset // must be a multiple of the page size as returned by sysconf(_SC_PAGE_SIZE).
);
/*
* deletes the mappings for the specified address range,
* and causes further references to addresses within the range
* to generate invalid memory references.
*/
int munmap(
void *addr, // must be a multiple of the page size (but length need not be)
size_t length // specifies the length of the mapping (which must be greater than 0)
);
Example. mmap() Usage
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define handle_error(msg) \
do { perror(msg); exit(EXIT_FAILURE); } while (0)
int
main(int argc, char *argv[])
{
char *addr;
int fd;
struct stat sb;
off_t offset, pa_offset;
size_t length;
ssize_t s;
if (argc < 3 || argc > 4) {
fprintf(stderr, "%s file offset [length]\n", argv[0]);
exit(EXIT_FAILURE);
}
fd = open(argv[1], O_RDONLY);
if (fd == -1)
handle_error("open");
if (fstat(fd, &sb) == -1) /* To obtain file size */
handle_error("fstat");
offset = atoi(argv[2]);
pa_offset = offset & ~(sysconf(_SC_PAGE_SIZE) - 1);
/* offset for mmap() must be page aligned */
if (offset >= sb.st_size) {
fprintf(stderr, "offset is past end of file\n");
exit(EXIT_FAILURE);
}
if (argc == 4) {
length = atoi(argv[3]);
if (offset + length > sb.st_size)
length = sb.st_size - offset;
/* Can't display bytes past end of file */
} else { /* No length arg ==> display to end of file */
length = sb.st_size - offset;
}
addr = mmap(NULL, length + offset - pa_offset, PROT_READ,
MAP_PRIVATE, fd, pa_offset);
if (addr == MAP_FAILED)
handle_error("mmap");
s = write(STDOUT_FILENO, addr + offset - pa_offset, length);
if (s != length) {
if (s == -1)
handle_error("write");
fprintf(stderr, "partial write");
exit(EXIT_FAILURE);
}
munmap(addr, length + offset - pa_offset);
close(fd);
exit(EXIT_SUCCESS);
}
C++17
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
1. ios_base::sync_with_stdio(false);
- C의 I/O Standard Stream과 C++의 I/O Standard Stream 간의 Synchronization(동기화)를 해제하여
C와 C++의 Stream을 동기화하는데 소요되는 시간을 절감한다.
(C++에서는 모든 Standard Stream이 서로 동기화되어 있는 것이 Default이다.)
- C와 C++의 Stream간 동기화를 위 코드처럼 해제시키면, C++ Stream은 독립적인 Buffer를 갖게된다.
- 이로 인해, C++의 I/O 함수와 C의 I/O 함수를 혼용하여 사용하면 어떤 것이 먼저 I/O를 처리되는지를 알 수 없게 된다.
(함수를 호출한 순서대로 I/O가 처리된다는 보장이 없어진다.)
※ Sync를 끊은 후에는 C++ 계열의 I/O 함수들(cin, cout 등)만을 사용하던가,
C 계열의 I/O 함수들(printf(), scanf() 등)만을 사용해야 한다.
(한 쪽 언어의 I/O 함수들만 사용해야 한다.)
※ Synchronized C++ Stream은 Thread-Safe하다.
※ Asynchronized C++ Stream은 Thread-Unsafe하다.
(그러므로, Single Thread 환경에서만 사용해야 한다.)
2. cin.tie(NULL);
- cout의 Stream과 묶여있던 cin의 Stream을 Untie한다.
- cin 동작하기 전에 cout의 Stream Buffer를 Flush하지 않게 하여 Flush하는데 소요되는 시간을 절감한다.
- C++에서 cin과 cout의 Stream은 Tie되어있는 형태가 Default이므로,
cin이 호출되면 cout의 Buffer를 Flush하고, cout이 호출되면 cin의 Buffer를 Flush한다.
- cin.tie(1)을 호출한 다음, (즉, cin의 Buffer와 cout의 Buffer가 Tied 상태이면)
cout을 호출하고 cin을 호출한 경우
cout이 먼저 수행되고 cin이 나중에 수행되는 것이 보장된다.
※ cin.tie(NULL)을 호출한 경우, cin과 cout의 수행 순서가 코드로 나열된 순서로 보장되지 않음에 유의해야 한다.
// Case 1 : cout이 수행된 이후에 cin이 수행된다는 보장이 없다.
// (대신, Buffer를 Flush하는 시간이 절감된다.)
std::cin.tie(0); // Untied
std::cout << "Enter name:";
std::cin >> name;
// Case 2 : cout이 수행된 이후에 cin이 수행될 것이 보장된다.
// (대신, Buffer를 Flush하는 시간이 필요하다.)
std::cin.tie(1); // Tied (Default)
std::cout << "Enter name:";
std::cin >> name;
3. 개행이 필요한 경우, std::endl대신 '\n' 사용
- endl 의 경우, 개행을 함과 동시에 Buffer를 Flush하는 역할도 수행하므로,
단순히 개행만을 원할 경우, '\n'을 출력시켜주는것이 수행시간을 절감할 수 있다.
Reference: BAEKJOON Online Judge, 입력 속도 비교, URL
Reference: Jinhan's Note, FastIO 구현 코드, URL
Reference: Stack Overflow, Significance of ios_base::sync_with_stdio(false);cin.tie(NULL); ,URL
Reference: Linux manual page, mmap(2), URL
Reference: Doocong, Fast Input by mmap, Doocong's Journey,
20218년 2월 11일 작성, 2022년 11월 23일 검색, URL