[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 실행시간이 절감되는 이유는 아래와 같다:

1. 기존의 입출력 함수는 여러 경우에 대비하기 위해 추가적인 연산을 수행한다.
2. 문제의 입출력 조건을 이용하면 모든 경우의 입출력에 대비할 필요가 없어진다.
3. 입출력 버퍼의 크기를 크게 하여 한 번에 읽고 내보내는 양을 크게 한다.

 

---

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