Input/Output Optimization

This article will introduce how to optimize stream-based I/O and C-style I/O.

Note

The actual speed of stream-based I/O and C-style I/O may vary depending on the environment (such as compiler, operating system, and hardware specifications). For more detailed analysis, please refer to experimental results. However, it is important to control variables in experiments to avoid erroneous conclusions due to multiple influencing factors.

Stream-based I/O

For stream-based I/O (such as std::cin and std::cout), the most common optimization methods are disabling synchronization with C streams and unbinding input and output streams.

Disabling Synchronization

Use the std::ios::sync_with_stdio(false) function to disable synchronization with C streams. To maintain compatibility with C, C++ synchronizes these two types of streams to prevent confusion when a program uses both printf and std::cout. Synchronized C++ streams guarantee thread safety.

This is a conservative measure taken by C++ for compatibility. If synchronization is enabled, during each I/O operation, the C++ stream immediately applies the operation to the corresponding C buffer. However, if the code does not involve C-style I/O, this operation is redundant. Therefore, synchronization with C streams can be disabled before performing I/O operations. However, after doing so, note that subsequent code must not use std::cin and scanf simultaneously, nor std::cout and printf simultaneously. However, std::cin and printf can be used together, as can scanf and std::cout.

Unbinding Streams

Use the tie() function to unbind input and output streams.

By default, std::cin is tied to &std::cout, so each formatted input operation calls std::cout.flush() to clear the output buffer, which increases I/O overhead. You can unbind them with std::cin.tie(nullptr) to further improve execution efficiency.

Note

When using it, you cannot omit the parameter and write std::cin.tie(), as this will not unbind the streams but return the output stream tied to std::cin. Also, there is no need for std::cout.tie(nullptr), as by default no other output stream is tied to std::cout.

Code Implementation

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

Note

After performing both operations above, you must manually flush in the program to ensure that the content displayed by std::cout appears before std::cin. This is because in this case, std::cout will not automatically flush the buffer when std::cin is called. For example:

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << "Please input your name: "
          << std::flush;  // Or: std::endl;
                          // Because each call to std::endl flushes the output buffer, while \n
                          // does not.
// If std::flush is omitted, the prompt will not be displayed before inputting the name
std::cin >> name;

C-style I/O

scanf and printf still have room for efficiency improvement, with methods based on conversion between integers and strings.

Note

The read and output optimizations introduced on this page are specifically for integer data. Floating-point read and output optimizations are very complex. For read-related optimizations, refer to the Bellerophon algorithm. For output-related optimizations, refer to the Ryū algorithm.

Implementation Design

Note

Current optimization methods focus on faster I/O, using naive methods for data conversion without fully utilizing hardware features. Nowadays, most x86 architecture CPUs support the AVX2 instruction set, which can use SIMD to accelerate conversion between integers and strings. Standard library functions do not utilize SIMD optimization. For example, the implementation in libstdc++ converts two consecutive digits at a time and converts them to characters via a lookup table. Therefore, optimizing the data conversion process may also bring benefits. However, within the scope of competitive programming, the optimization methods mentioned in this article are sufficient for most scenarios.

Read Optimization

Each integer consists of a sign part and a digit part, with the sign always preceding the digit part, so the sign part is read first. For the sign part, the + for positive integers is usually omitted and does not affect the value represented by the following digits, while - cannot be omitted, so it must be checked. If the input does not contain negative integers, this check can be omitted. For the digit part, it only contains digits from 0 to 9, so when a character that should not exist in an integer (usually a space) is read, it can be determined that the integer has been fully read.

During reading, since digits are read from left to right, Horner's method can be used for integer conversion. Therefore, the entire conversion process can be combined with input.

During the digit reading process, it is necessary to determine whether the read character is a decimal digit character. This can be simply checked with ch >= '0' && ch <= '9', or by using the isdigit() function.

Output Optimization

When outputting, integers need to be converted to strings. The naive algorithm is generally used, which directly calculates each digit of the integer from low to high, converts it to a character, and outputs in reverse order.

Implementation Details

Integer Overflow Issues

Care must be taken to avoid integer overflow in implementations. For example, improperly taking the opposite number in output optimization may cause the minimum value of an integer type to become a number that exceeds the maximum value representable by that type after negation, potentially leading to incorrect output. Similar overflow may occur when reading the minimum value of an integer type, but this may not cause data read errors because the overflowed value might equal the actual input value.

Signed integer overflow is undefined behavior. In implementation, the property of C language's integer division rounding toward zero for negative numbers can be used to avoid the above issues. However, if negative numbers are not required for input/output, or if the minimum value of the integer type cannot be input/output, this problem will not occur.

Improving Implementation Generality

If the program uses multiple types of integer variables, it may be necessary to implement multiple input/output functions that are logically the same but differ in type. In this case, C++ template can be used to implement input/output optimizations for all integer types. For example, under the C++11 standard, use

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

or under the C++20 standard, use

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

to define the function.

For ease of reading, the implementations in the following sections assume that only int type integers need to be read. These implementations are sufficient for most contest problems.

Implementations

Mainstream implementations differ only in the read/write functions used, with the same logic for integer conversion. They are introduced below according to the read/write functions used.

Implementation Using getchar and putchar

The core code is as follows.

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]);
}

Implementation Using fread and fwrite

Faster read and output can be achieved via fread and fwrite. Their function signatures are as follows.

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);

For example, fread(Buf, 1, SIZE, stdin) means reading SIZE data blocks of size 1 byte from standard input into Buf. The return value indicates how many bytes were successfully read.

Since fread and fwrite read and write in whole segments, they are faster than getchar() and putchar(). If the buffer is large enough, the entire file can be read at once. However, if the buffer is not large enough, multiple reads are needed to ensure all input content is read. To achieve this, simply redefine getchar.

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

Output is similar to input: first place the output content into a buffer, and finally output the buffer content at once via fwrite.

The core code is as follows.

// #define DEBUG 1  // Debug switch
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  // Debug mode, characters are visible
    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  // Debug mode, characters are visible
    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;

When using this method, note:

• When the debug switch is off, use fread(), fwrite(), and automatically destruct to execute fwrite() upon exit. When the debug switch is on, use getchar(), putchar() for easier debugging.
• If file read/write is required, add freopen() before any read/write operations.

Implementation Using mmap

mmap is a Linux system call that can map a file into memory at once, similar to a memory region that can be referenced by pointers, offering better speed in some scenarios. Its function signature is:

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

Note

mmap cannot be used in Windows environments (such as CodeForces and HDU's judging systems), and it is also not recommended for use in official contests. In fact, using fread is already fast enough. Moreover, if mmap is used to repeatedly read a small piece of a file, the overhead of one memory mapping and kernel handling page faults will be much greater than using fread.

First, obtain the file descriptor fd, then get the file size via fstat, and thereafter obtain the pointer *pc to the file mapped in memory via mmap. After that, *pc++ can be used directly instead of getchar() for file reading.

If reading from standard input is needed, set fd to 0. However, using mmap on standard input is extremely dangerous and cannot be used with terminal input. You can choose to redirect a file to standard input.

Example Problem: Luogu P10815【Template】Fast Read

Read \(n\) integers in the range \([-n, n]\), sum them, and output the result. Here \(n \leq 10^8\). The data guarantees that for any prefix of the sequence, the sum of that prefix is within the storage range of a 32-bit signed integer.

Reference code is as follows.

#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;  // Read from stdin
  // int fd = open("xxx.in", O_RDONLY); // Read from file
  struct stat state;
  fstat(fd, &state);  // Get file size
  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);
}

References

cin.tie and sync_with_stdio Accelerate Input and Output - Code Farm

C++ Speed Optimization - Heavy Watal

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

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用