0002.plain_text_io_performance_theory.md

Plain-text IO performance

In the previous post, I discussed the usability flaws of plain-text input parsing in .NET platform. In this post, we will focus on performance issues related to plain-text input and output.

Plain-text IO performance is a big issue for competitive programming. If the input or output is too large, the solution may get Time Limit or Memory Limit exceeded verdict due to inefficient IO. IO will be a bottleneck.

Consider the problem Timus: 1510. Even a tricky C# solution with optimal $O(n)$ complexity got Memory Limit Exceeded verdict due to inefficient input parsing. But nonoptimal C++ solution with $O(nlog(n))$ complexity easily got Accepted. The choice of language is a game changer in this case.

Which affects plain text IO performance

Many things affects plain text IO performance. Let's discuss some of this things in theory to set up a correct benchmark.

Data source and target

Before reach the program, input data should be loaded from disk or generated by another program. Thus, speed of the disk or efficiency of the generator program may affect benchmark result.

If the output stream is piped to a slow application, like terminals, there also will be an issue. Both input and output streams are implemented over bounded buffers, thus our application will be blocked when the terminal app renders old text.

Note that redirecting the output e.g. to > nul on Windows will lead to false benchmark results because no output will be generated at all (the stdout pipe will not be created at all).

I will get around these issues in the benchmarks by storing input and output data in memory.

Operating system

IO streams (pipes) are a tool to pass data from one process to another, managed by the operating system. So, the operating system is responsible for the efficiency of APIs, used to access the internal pipe's buffer.

Also blocking may happen where the pipe's buffer is full on write or empty on reading. In this case, the OS thread scheduler is involved.

Language runtime

Programming languages and frameworks abstract the hardware and OS from a programmer, providing an abstraction layer over platform-specific implementation details. The transformation from raw STD_INPUT_HANDLE to nice TextReader may require hard CPU and memory bus work, like converting, copying, and additional buffering of the data.

Language runtime is also responsible for encoding, decoding, and parsing text data.

Even for single language, runtime behavior may differ. For C++ we should test against different compilers, and for C# against .NET Framework and modern .NET like 6 and 7.

Encoding

No text is just plain. The stdin/stdout content is a sequence of bytes, and it is a program's responsibility to interpret it with some encoding. The most common encodings for files are ASCII and UTF-8 (which is the same in range 0-127), but .NET strings use UTF-16. So, the input stream reading to string will require data re-encoding.

ascii("-13") = 2d 31 33
utf8 ("-13") = 2d 31 33
utf16("-13") = 2d 00 31 00 33 00

Allocations

As I mentioned in the previous post, all popular methods for input parsing, like Console.Readline(), string.Split(), .Select(int.Parse).ToArray() will copy data and allocate new objects. This allocations take some time and memory. Then if the garbage collector will be triggered, it will also take some time to process and clean up these objects.

The worst case for .NET is a long single-line input. Console.ReadLine() will read all the input in memory, even if it's unnecessary.

Parsing

The transformations from char sequence to number or backward may be tricky. I recommend you to look at this Pull Request from dotnet/runtime about double parsing for more information.

In some cases, it is worth reimplementing some things, like string to integer conversions, outperforming standard functions. For example, integer parsing may be implemented like this. Of course, this code is not suitable for all cases, but for some it is faster.

int fastscan()
{
    bool negative = false;
    bool read_start = false;
  
    int number = 0;
  
    while (true)
    {
        int c = _getchar_nolock(); // Windows
        int c = getchar_unlocked(); // Linux

        if (c=='-')
        {
            negative = true;
            read_start = true;
            continue;
        }
  
        if ('0' <= c && c <= '9')
        {
            number = number * 10 + (c - '0');
            read_start = true;
            continue;
        }

        if (read_start)
            break;
    }

    return negative ? -number : number;
}

Flushing

There are two scenarios for output writing:

• Interactive console applications, where the following input may depend on output. E.g. a chess program which plays with humans or another programs
• Non-interactive applications, which may print output after reading all the input.

The interactive output should be propagated to the STDOUT buffer as early as possible, typically line-by-line. But for non-interactive apps, it is not efficient to flush a small amount of data because it will wake the reader application thread only to process this small output and then block on waiting again. Instead, we want to accumulate the output in the own buffer and flush it to STDOUT rarely.

Many language runtimes are configured for interactive apps by default. So for fast output, we should reconfigure this behavior.

.NET methods like Console.WriteLine, Console.Write synchronizes access to the output stream and flush it. So you may improve C# output performance by writing to the buffered output stream:

using var output = new StreamWriter(Console.OpenStandardOutput());
output.WriteLine(...);

Announce

In the next post I'll set up benchmarks to check these concerns on practice and discuss the results.

In the following we will discuss:

• How to improve C#/.NET plain-text IO speed
• Number parsing algorithms
• Efficient plain-text input reading implementation on C#

Homework

Solve the Timus: 1510 problem on C#.