Bỏ qua

Tối ưu hóa I/O

Bài viết giới thiệu cách tối ưu I/O dựa trên stream và I/O kiểu C.

Lưu ý

Tốc độ I/O stream và C thay đổi theo môi trường (compiler, OS, phần cứng). Nếu muốn phân tích sâu hơn, hãy dựa vào kết quả thực nghiệm và kiểm soát biến.

I/O dựa trên stream

Với stream (như std::cin/std::cout), tối ưu phổ biến là tắt đồng bộ với C stream và tách liên kết input-output.

Tắt đồng bộ

Dùng std::ios::sync_with_stdio(false) để tắt đồng bộ với C stream. C++ đồng bộ với C để tránh乱 khi dùng printf và std::cout. C++ stream đồng bộ là thread-safe.

Đây là biện pháp bảo thủ. Khi bật đồng bộ, mỗi I/O sẽ đồng bộ với C buffer; nếu không dùng I/O kiểu C thì là thừa. Vì vậy có thể tắt trước khi I/O. Nhưng sau đó không được同时 dùng std::cin với scanf, cũng không同时 dùng std::cout với printf; tuy nhiên có thể dùng std::cin với printf, hoặc scanf với std::cout.

Tách liên kết

Dùng tie() để tách liên kết giữa input và output.

Mặc định std::cin liên kết với &std::cout, nên mỗi lần nhập sẽ gọi std::cout.flush(), tăng负担. Có thể std::cin.tie(nullptr) để tách liên kết, tăng hiệu suất.

Lưu ý

Không được bỏ tham số thành std::cin.tie(), như vậy không tách mà chỉ trả về stream liên kết. Cũng không cần std::cout.tie(nullptr) vì mặc định không có output stream liên kết với std::cout.

Mã mẫu

1
2
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

Lưu ý

Sau khi làm hai thao tác này, cần tự flush để đảm bảo std::cout hiển thị trước khi std::cin đọc. Vì lúc này std::cin không tự flush std::cout. Ví dụ:

1
2
3
4
5
6
7
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << "Please input your name: "
          << std::flush;  // Hoặc: std::endl;
                          // Mỗi lần dùng std::endl sẽ flush, còn \n thì không.
// Nếu bỏ std::flush, sẽ không hiện提示 trước khi nhập
std::cin >> name;

I/O kiểu C

scanf và printf vẫn còn space tăng tốc, chủ yếu ở chuyển đổi số nguyên và chuỗi.

Lưu ý

Tối ưu đọc/ghi ở đây针对 số nguyên. Tối ưu số thực phức tạp; đọc tham khảo Bellerophon, ghi tham khảo Ryū.

Thiết kế

Lưu ý

Cách tối ưu hiện tại tập trung vào tốc độ I/O, chuyển đổi dữ liệu dùng phương pháp朴素, chưa tận dụng phần cứng. Hầu hết CPU x86 hỗ trợ AVX2, có thể dùng SIMD tăng tốc chuyển đổi. STL không dùng SIMD; ví dụ libstdc++ 实现 chuyển 2 chữ số và tra bảng. Tối ưu chuyển đổi có thể有益, nhưng trong thi, các method ở đây已 đủ cho đa số场景.

Tối ưu đọc

Mỗi số nguyên gồm dấu và phần số; dấu luôn trước phần số. Với dấu, + thường bỏ qua và không ảnh hưởng giá trị; - không được bỏ, cần判定. Nếu input không chứa số âm, có thể bỏ判定.

Phần số chỉ gồm 0..9; khi đọc đến ký tự không phải số (thường là khoảng trắng), kết thúc số.

Vì đọc từ trái sang phải, có thể dùng秦九韶 để chuyển đổi trong lúc đọc.

Khi đọc, cần kiểm tra ký tự có phải số: ch >= '0' && ch <= '9', hoặc dùng isdigit().

Tối ưu ghi

Ghi số thường chuyển sang chuỗi bằng phương pháp朴素: lấy từng chữ số từ thấp lên cao rồi đảo.

Chi tiết triển khai

Vấn đề tràn số

Cần注意 tràn số. Ví dụ lấy đối số âm của min int gây tràn; có thể dẫn đến output sai. Đọc min int cũng có thể tràn, nhưng có thể không sai do giá trị tràn trùng input.

Tràn số có dấu là UB; có thể利用 tính chất chia số âm của C (làm tròn về 0) để tránh. Nếu không cần âm, hoặc không可能 gặp min int, vấn đề không出现.

Tăng tính通用

Nếu dùng nhiều kiểu số nguyên, cần nhiều hàm I/O khác kiểu nhưng logic giống nhau. Có thể dùng C++ template. Ví dụ C++11:

1
2
3
4
template <typename T>
typename std::enable_if<std::is_integral<T>::value &&
                        std::is_signed<T>::value>::type
read(T &x);

Hoặc C++20:

1
2
template <std::signed_integral T>
void read(T &x);

Để tiện đọc, phần sau giả định chỉ cần int; các implementation đủ cho đa số题.

实现

Các implementation khác nhau ở hàm đọc/ghi, logic chuyển đổi giống nhau.

Dùng getchar và putchar

Core:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void read(int &x) {
  bool neg = false;
  x = 0;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') neg = true;
    ch = getchar();
  }
  if (neg) {
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + ('0' - ch);
      ch = getchar();
    }
  } else {
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + (ch - '0');
      ch = getchar();
    }
  }
}

void write(int x) {
  bool neg = false;
  if (x < 0) {
    neg = true;
    putchar('-');
  }
  static int sta[40];
  int top = 0;
  do {
    sta[top++] = x % 10;
    x /= 10;
  } while (x);
  if (neg)
    while (top) putchar('0' - sta[--top]);
  else
    while (top) putchar('0' + sta[--top]);
}

Dùng fread và fwrite

fread/fwrite có thể nhanh hơn. Hàm signature:

1
2
3
4
std::size_t fread(void* buffer, std::size_t size, std::size_t count,
                  std::FILE* stream);
std::size_t fwrite(const void* buffer, std::size_t size, std::size_t count,
                   std::FILE* stream);

Ví dụ fread(Buf, 1, SIZE, stdin) đọc SIZE byte vào Buf, trả số byte đọc được.

fread/fwrite đọc/ghi theo block, nhanh hơn getchar/putchar. Nếu buffer đủ lớn, có thể đọc cả file một lần; nếu không, cần đọc nhiều lần. Để实现, chỉ cần redefinition getchar.

1
2
3
4
5
char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)

Ghi tương tự:先把 output vào buffer, cuối cùng fwrite một lần.

Core:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  char gc() {
#if DEBUG  // 调试，可显示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }

  void read(int &x) {
    bool neg = false;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') neg = true;
    if (neg)
      for (; isdigit(ch); ch = gc()) x = x * 10 + ('0' - ch);
    else
      for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
  }

  void read(char *s) {
    char ch = gc();
    for (; isspace(ch); ch = gc());
    for (; !isspace(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }

  void read(char &c) { for (c = gc(); isspace(c); c = gc()); }

  void push(const char &c) {
#if DEBUG  // 调试，可显示字符
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }

  void write(int x) {
    bool neg = false;
    if (x < 0) {
      neg = true;
      push('-');
    }
    static int sta[40];
    int top = 0;
    do {
      sta[top++] = x % 10;
      x /= 10;
    } while (x);
    if (neg)
      while (top) push('0' - sta[--top]);
    else
      while (top) push('0' + sta[--top]);
  }

  void write(int x, char lastChar) { write(x), push(lastChar); }
} io;

Lưu ý:

  • Khi tắt debug dùng fread()/fwrite(); khi mở debug dùng getchar()/putchar() để dễ debug.
  • Nếu đọc/ghi file, cần freopen() trước mọi đọc/ghi.

Dùng mmap

mmap là system call Linux, ánh xạ file vào memory, có thể nhanh hơn. Hàm signature:

1
2
void *mmap(void addr[.length], size_t length, int prot, int flags, int fd,
           off_t offset);

Lưu ý

mmap không dùng được trên Windows (Codeforces/HDU), và không khuyến nghị dùng trong thi. Thực tế fread đã đủ nhanh; nếu dùng mmap lặp đọc file nhỏ, chi phí映射 + page fault có thể lớn hơn fread.

Cần lấy fd, dùng fstat lấy size, rồi mmap lấy pointer *pc. Sau đó dùng *pc++ thay getchar() để đọc.

Nếu đọc từ stdin, có thể dùng fd=0. Nhưng mmap stdin rất nguy hiểm, và không thể nhập từ terminal; có thể redirect file vào stdin.

Ví dụ：洛谷 P10815【模板】快速读入

Đọc \(n\) số trong \([-n, n]\), tính tổng. \(n \leq 10^8\). Dữ liệu đảm bảo với mọi prefix, tổng nằm trong phạm vi 32-bit signed.

Code tham khảo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#include <cstdio>

char *pc;

void rd(int &x) {
  bool neg = false;
  x = 0;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') neg = true;
    ch = *pc++;
  }
  if (neg) {
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + ('0' - ch);
      ch = *pc++;
    }
  } else {
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + (ch - '0');
      ch = *pc++;
    }
  }
}

int main() {
  int fd = 0;  // 从 stdin 读入
  // int fd = open("xxx.in", O_RDONLY); // 从文件读入
  struct stat state;
  fstat(fd, &state);  // 获取文件大小
  pc = (char *)mmap(NULL, state.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
  int n, x, sum = 0;
  rd(n);
  while (n--) {
    rd(x);
    sum += x;
  }
  printf("%d\n", sum);
}

参考

cin.tie 与 sync_with_stdio 加速输入输出 - 码农场

C++ 高速化 - Heavy Watal

'Re: mmap/mlock performance versus read' - MARC

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Marcythm, YZircon, Chaigidel, Tiger3018, voidge, H-J-Granger, ouuan, Enter-tainer, lcfsih, Xeonacid, Ir1d
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply