Input and Output Optimization

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

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 untieing input and output streams.

Disabling Synchronization

Use the std::ios::sync_with_stdio(false) function to disable synchronization with C streams. For compatibility with C—that is, to ensure that no confusion occurs when printf and std::cout are used at the same time—C++ synchronizes these two types of streams. Synchronized C++ streams are guaranteed to be thread-safe.

This is actually a conservative measure adopted by C++ for compatibility. When synchronization is enabled, at every I/O operation, the C++ stream immediately applies the operation to the corresponding C buffer. 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, but note that after doing so, std::cin and scanf cannot be used at the same time in subsequent code, nor can std::cout and printf; however, std::cin and printf can be used together, as can scanf and std::cout.

Untieing Streams

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

By default, std::cin is tied to &std::cout, so std::cout.flush() must be called every time formatted input is performed to clear the output buffer, which increases the I/O overhead. You can untie them with std::cin.tie(nullptr) to further improve execution efficiency.

Implementation

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

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 removed, the prompt will not be displayed before the name is input.
std::cin >> name;

C-Style I/O

There is still room to improve the efficiency of scanf and printf; the improvements are all based on conversion between integers and strings.

Design

Input Optimization

Each integer consists of a sign and a digit part, and the sign always comes before the digit part, so the sign part is read first. For the sign part, the + sign of a positive integer is usually omitted and does not affect the value represented by the following digits, whereas - cannot be omitted and therefore needs to be checked. If the input contains no negative integers, this check can be omitted. The digit part contains only digits from 0 to 9, so when a character that cannot occur in an integer (usually a space) is read, it can be determined that this integer has finished being read.

When reading, because the digits are read from left to right, the Qin Jiushao algorithm can be used for integer conversion. Thus, the entire conversion process can be combined with input.

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

Output Optimization

When outputting, an integer must be converted into a string. The usual approach is the naive algorithm: directly calculate each digit of the integer from low to high, convert it to a character, and output the result in reverse order.

Implementation Details

Integer Overflow

Integer overflow must be considered in the implementation. For example, improperly taking the opposite number in output optimization can cause the minimum integer value to exceed the maximum value representable by that integer type after being negated, which may lead to incorrect output. Similar overflow may occur when reading the minimum integer value, but in this case it may not cause an error in the input data, because the value obtained through overflow may equal the actual input value.

Signed integer overflow is undefined behavior. In an implementation, the above problems can be avoided by using the property of integer division of negative numbers in C that it rounds toward zero. However, this issue does not arise if negative numbers do not need to be input or output, or if the minimum value of this integer type cannot be input or output.

Improving Generality

If a program uses integer variables of multiple types, it may be necessary to implement multiple input and output functions with different types but the same logic. In this case, C++ template can be used to implement input and output optimization 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 readability, the implementations later in this article assume that only integers of type int need to be read. These implementations are sufficient for most problems.

Implementation

Mainstream implementations differ only in the input and output functions they use; their logic for integer conversion is the same. The following sections introduce them according to the input and output functions used by each 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]);
}

Using fread and fwrite

Faster input and output can be implemented with 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 of data were successfully read.

Because fread and fwrite read and write an entire block at a time, they are faster than getchar() and putchar(). If the buffer is large enough, the entire file can be read at once. If the buffer is not large enough, however, multiple reads are needed to ensure that all input is read. To implement this functionality, only getchar needs to be redefined.

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 in a buffer, and finally output the buffer's contents at once with 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  // Debugging; characters can be displayed
    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  // Debugging; characters can be displayed
    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 the following:

• When the debug switch is disabled, fread() and fwrite() are used, and fwrite() is automatically executed during destruction on exit. When the debug switch is enabled, getchar() and putchar() are used to facilitate debugging.
• To perform file I/O, add freopen() before all reading and writing operations.

Using mmap

mmap is a Linux system call that can map an entire file into memory, similar to a memory region that can be referenced by a pointer, and can be faster in some scenarios. Its function signature is as follows:

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

First obtain the file descriptor fd, then obtain the file size through fstat, and finally use mmap to obtain the pointer *pc to the file mapped in memory. After that, *pc++ can directly replace getchar() for reading the file.

When reading from standard input, fd can be set to 0. However, using mmap on standard input is extremely dangerous, and input cannot be entered in a terminal; you can redirect a file to standard input instead.

The 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 a file
  struct stat state;
  fstat(fd, &state);  // Obtain the 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

Accelerating input and output with cin.tie and sync_with_stdio - Coder's Field

C++ optimization - Heavy Watal

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