Fast input and output

The problem: read numbers and find the records. The solution is one pass, O(n). We submit it and get time limit exceeded on the test with a million numbers. The algorithm has nothing to do with it: on this test almost all the time goes on reading the input. Below is the same work, read and printed in different ways, with times measured on the site’s server.

In Python input() is several times slower than reading the whole input at once, and in Go fmt.Scan straight from standard input is tens of times slower. The difference is not in parsing the numbers, which is the same everywhere, but in what each request for the next portion costs.

The idea

Every call to input or output has a fixed price: a function call, checks, and sometimes a system call, a request to the operating system that costs hundreds of nanoseconds or more. If you pay it for every number or every byte, over a million numbers the price adds up to seconds. Fast reading and writing pay it rarely: they read a lot at once and write what has piled up in one piece.

This is the same amortisation as in a dynamic array: the expensive action, a call to the system, is done rarely and in large portions, and per number it becomes almost free. A 4096-byte buffer divides the number of system calls by four thousand.

Python: what input() does

If you spy on what input() calls, by putting objects that count calls in place of the standard streams, it turns out that on every call it asks standard input for its file number to check whether it is a terminal, flushes the buffers of standard output and standard error, and only then reads a line. In an interactive program this is right: the prompt must appear on the screen before a person starts typing. But over a million lines from a file these checks and flushes cost more than the reading itself.

• sys.stdin.readline() reads a line from the same buffer, without the checks. It is several times faster than input(); if the method is saved in a variable (readline = sys.stdin.readline), a little faster still.
• sys.stdin.buffer.read().split() takes the whole input in one piece and splits it on whitespace once. buffer gives bytes without decoding them to text; int can read bytes. This is the fastest way when the input fits in memory.
• Output: print for every number is a function call with argument parsing and a write to the buffer. Building a string and writing it once, sys.stdout.write("\n".join(map(str, xs)) + "\n"), is several times faster.

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
xs = list(map(int, data[1:n + 1]))
# … the solution …
sys.stdout.write("\n".join(map(str, answer)) + "\n")

Go: a system call per byte

In Go the reason is different. os.Stdin is not buffered: every read from it is a system call. And fmt.Scan reads input one character at a time so as not to take too much, so if you give it os.Stdin directly, every byte of input costs a separate system call. A million numbers is several million bytes and as many calls to the system. In the site’s sandbox, where programs run under gVisor, a system call is even more expensive than on an ordinary machine.

• fmt.Fscan(bufio.NewReader(os.Stdin), &x): one extra line of code removes the system calls, but fmt parses its arguments through reflection, and that is still noticeable.
• bufio.Scanner with ScanWords and strconv.Atoi is several times faster. Note: by default a scanner’s line is at most 64 KB; long lines need sc.Buffer.
• Parsing numbers straight from a bufio.Reader byte by byte is the fastest: no strings, no reflection. This is how the reference solution of the problem below is written.
• Output: fmt.Println writes to the unbuffered os.Stdout, a system call for every line. bufio.NewWriter(os.Stdout) and defer w.Flush() collect the output in a buffer. A forgotten Flush is a classic mistake: the program silently loses the end of its output.

in := bufio.NewReaderSize(os.Stdin, 1<<16)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n) // fmt is fine for a couple of numbers, for a million use readInt
// … the solution …
fmt.Fprintln(out, answer)

Code

How many times does a program call the system with different ways of reading? A model of a file counts the read calls: a byte at a time, like fmt.Scan without a buffer; through a 4096-byte buffer, like bufio and Python’s files; and all at once.

Forty-two thousand calls against twelve, three and a half thousand times fewer. And here is the measurement the race is built from: each way is a separate program given the file on standard input, as in a judge. Separate, because in the site’s sandbox input() is replaced and asks the page for input.

What it costs

All the ways are O(size of the input): every byte is read and parsed one way or another. What differs is the constant factor, and it is huge: in the race above the ways within one language differ several times over and tens of times over. On an input of a hundred numbers it is invisible; on a megabyte of input it is the difference between “accepted” and “time limit exceeded”. The price is memory: reading it all holds the whole input, and gigabyte files are read in pieces, through the same buffer.

Before speeding up input, it is worth estimating: if there are up to 10⁵ numbers, the difference is milliseconds, and input() will do. From 10⁶ and up it is worth writing fast input straight away. And if the program is slow while the input is small, the input is not the problem; then a profiler will help.

Problems

A problem in which only fast input is needed: a million days of temperatures, records of heat and cold. One of the tests is the real 85 years of Almaty weather.