Fast console input in .NET
Back when .NET was a proprietary Windows-only technology, it and C# gained a reputation as a platform that is great for solving business problems, but unsuitable for competitive programming and writing high-performance code.
One often hears that “sharps are slow”, especially in the context of algorithmic tasks on platforms such as timus.online and codeforces.com. And, alas, not only to hear, but also to face real problems related to the features of the platform, getting Wrong Answer, Runtime Error, Memory Limit, Time Limit with the correct algorithm.
Most of these problems lie in the peculiarities of console input and output. And it’s often easier to write cin >> n
or sc.nextInt()
how int.Parse(Console.ReadLine())
or Console.ReadLine().Split().Select(int.Parse).ToArray()
because of which the choice falls on another language.
Next, I will talk about common problems with console I/O in .NET, and how to make input fast and convenient.
floating point
Sometimes you need to read or output a floating point number. But it’s easy to forget that floating points in .NET are commas, depending on the locale. This is especially easy to forget if you use an English locale on your operating system.
There are two solution options:
- set stream locale:
Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
- transfer
CultureInfo.InvariantCulture
explicitly into methods like(Try)Parse
andToString
Also in modern .NET there is runtime parameter InvariantGlobalization
to avoid such problems.
Input and output
Imagine that we are given a simple task: we need to calculate lines of 4 numbers
int
in each , numbers separated by spaces. It is required to display the sum of numbers for each line.
int n = int.Parse(Console.ReadLine());
for (int i = 0; i < n; ++i)
{
var result = Console.ReadLine().Split().Select(int.Parse).Sum();
Console.WriteLine(result);
}
Could anything in this code lead to a verdict other than Accepted? Easy.
Formatting Features
The condition does not say anything about the number of spaces that separate the numbers. And in the end, if somewhere there are more than one gap, Console.ReadLine().Split()
will return an array containing empty strings. BUT int.Parse
will fail with an exception, resulting in a verdict runtime error. It may seem that this does not happen in contests, but alas, the case is quite real.
Fixing the code:
int n = int.Parse(Console.ReadLine());
for (int i = 0; i < n; ++i)
{
var result = Console.ReadLine()
.Split(' ', StringSplitOptions.RemoveEmptyEntries)
.Select(int.Parse)
.Sum();
Console.WriteLine(result);
}
An unpleasant nuance that must be remembered. By the way, if earlier the code treated all whitespace characters as separators, now only spaces. You can fix it, but it will be a little longer.
The problem occurs only when reading input line by line. In languages where there are ready-made ways to read numbers from the console (for example int n; cin >> n
), there is no problem at all.
Console Flush
The input and output streams stdin/stdout/stderr are based on an in-memory buffer that one process can write to and another can read. Accessing this buffer for a few bytes is expensive, so each process can additionally buffer I/O for efficiency. Data is promoted into the stream buffer either by filling the local one or by calling .Flush()
.
Call .Flush()
makes a lot of sense for interactive console applications – the user needs to show the output in the terminal right away, and not save it in memory. Most platforms are natively adapted to this scenario and call .Flush()
automatically after each entry.
Note that there are also tasks that require interactive I/O (request-response semantics). For example, tasks in which it is required to calculate the answer by asking “questions” to the checking system (the simplest example is a program that guesses the word in the conditional “Field of Miracles”, “communicating” with the host program)
To save on Flush, in C++ iostreams write:
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
And in C# you can use StreamWriter
for stdout
instead of Console
:
const int bufferSize = 16384;
using var input = new StreamReader(
Console.OpenStandardInput(), bufferSize: bufferSize);
using var output = new StreamWriter(
Console.OpenStandardOutput(), bufferSize: bufferSize);
int n = int.Parse(input.ReadLine());
for (int i = 0; i < n; ++i)
{
var result = input.ReadLine()
.Split(' ', StringSplitOptions.RemoveEmptyEntries)
.Select(int.Parse)
.Sum();
output.WriteLine(result);
}
Let’s check if it does .Flush()
impact on metering performance. Version from Console.WriteLine
works on my computer for ~490msand using StreamWriter
– per 105ms. Those. the reason for poor performance was not at all in LINQ. In a testing system with slower hardware, you can easily get Time Limit Exceedif you do not take into account the automatic .Flush()
. By the way, for the record, in enterprise applications, the problem also occurs – in logging.
Measured on Linux, .NET 7 NativeAOT runtime – this is how the minimum overhead is achieved at the start of the program, about 1.5 ms. On Windows, at least the start of the process would be on the order of 10 ms, even for C++.
You can also use to read StreamReader
instead of Console
. This saves you the hassle of checking to see if the Console.In
on each read and use an increased buffer, but the gain is much less impressive – a few milliseconds
Please note that it makes no sense to set the buffer size for the console stream – the parameter is simply ignored
Input task: allocations
A task 1510 from the Timus. There are two solutions for this problem – behind the line and with sorting. Everyone passes it easily in the same C ++, but in C # even with a smart algorithm, due to the peculiarities of the standard input, it will be Memory Limit Exceeded. Why?
The task has a Memory Limit of 16 MB. What for? I don’t know, it doesn’t interfere with storing all the numbers in memory and sorting, because 500,000 numbers of 4 bytes are only 2 MB. But in C# reading input via Console.ReadLine
leads to string allocation. BUT line with a number of 10 digits, this is not 4 bytes, but at least:
- 16 bytes for the object header and a pointer to the Method Table
- 4 bytes per length storage
- 20 bytes per 10 characters in UTF-16
- 2 bytes per null terminator for compatibility with native code that expects it
Those. already 42 bytes per 10 characters. And 500,000 times 42 bytes is already 21 MB.
But are they short lived? We read the line, immediately parse it, GC will somehow collect it. But the operation of the GC is not guaranteed, the release of memory back to the OS is also, and the forced call through GC.Collect()
may already lead to Time Limit Exceed.
How to be? Write input yourself
Custom input
grandfather’s decision
In C++, the solution comes to mind with character-by-character by reading numbers.
Let’s rewrite it in C# using Console.Read()
and better – StreamReader.Read()
. In this case use StreamReader
justified, because to refer to Console
per character is much more expensive than per line when using ReadLine
.
After that, the task is not difficult. On my computer, character-by-character reading is 2 times faster than with Console.ReadLine()
.
StreamReader reader = new StreamReader(Console.OpenStandardInput(), bufferSize: 32768);
int fastscan()
{
bool negative = false;
bool read_start = false;
int number = 0;
while (true)
{
int c = reader.Read();
if (c=='-')
{
negative = true;
read_start = true;
continue;
}
if (c>47 && c<58)
{
number = number * 10 + (c - 48);
read_start = true;
continue;
}
if (read_start)
break;
}
if (negative)
number *= -1;
return number;
}
The solution, however, is not ideal. This method is suitable for integers, and it is not trivial to parse floating point numbers correctly, it is easy to fall into edge cases and make mistakes with precision. To understand this, just look Pull Request.
Tiktoker solution
Modern .NET has method overloads Parse
and TryParse
host ReadOnlySpan
instead of a string. Instead of manually parsing numbers, you can write a character fragment with a number to the buffer and call the standard method for parsing.
This will solve the problem of parsing floating-point numbers of the “grandfather” solution, and also make code entry more convenient, eliminating the need to write constructions like Console.ReadLine().Split().Select(int.Parse).ToArray()
. The code itself is so simple that it can be easily written right during the contest (but does not take into account, for example, a buffer overflow, if this is important to you):
class Scanner
{
StreamReader input = new(Console.OpenStandardInput(), bufferSize: 16384);
char[] buffer = new char[4096];
public int ReadInt()
{
int length = 0;
bool readStart = false;
while (true)
{
int ch = input.Read();
if (ch == -1)
break;
if (char.IsWhiteSpace((char)ch))
{
if (readStart) break;
continue;
}
readStart = true;
buffer[length++] = (char)ch;
}
return int.Parse(buffer.AsSpan(0, length), CultureInfo.InvariantCulture);
}
}
Yes, it works slower than the “grandfather” version, but at the level with generally accepted input methods, it does not allocate memory traffic, and certainly will not cause Time or Memory limit.
In C++ and other languages, you can write more efficient versions of console input.
scanf
andcin
taken only to focus on ways to read input, which usually fit within the Time Limit
For .NET 7 and C# 11, you can make a generic version based on a static interface method ISpanParsable<TSelf>
. True, C # 11 is not yet supported in checking systems.
class Scanner
{
StreamReader input = new(Console.OpenStandardInput(), bufferSize: 16384);
char[] buffer = new char[4096];
public T Read<T>() where T : ISpanParsable<T>
{
int length = 0;
bool readStart = false;
while (true)
{
int ch = input.Read();
if (ch == -1)
break;
if (char.IsWhiteSpace((char)ch))
{
if (readStart) break;
continue;
}
readStart = true;
buffer[length++] = (char)ch;
}
return T.Parse(buffer.AsSpan(0, length), CultureInfo.InvariantCulture);
}
}
I also prepared a more efficient version of the code based on TryParse(ReadOnlySpan<char>)
but he too longto fit here. It accelerates in my test to 24 ms by reading data in blocks.
Ditching the StreamReader
StreamReader
– a layer between the Console Stream, which usually includes ASCII characters and .NET strings encoded in UTF-16. Let’s change the code to work with Stream
directly.
Method for parsing, accepting ReadOnlySpan<char>
won’t fit anymore. Luckily, .NET has a class called Utf8Parser
– Legacy of library development System.Text.Json
, which solves the same problem for a span of bytes. Don’t be fooled by what’s in the title Utf8
– parse everything 100500 digits, which are in Unicode, he does not know how. But with the usual ASCII-digits copes with a bang!
Dignity Utf8Parser.TryParse
compared to T.TryParse
– the ability to parse a value from a prefix, without a pre-prepared token. Compare:
bool TryParse(ReadOnlySpan<char> span, out int value, IFormatProvider provider);
bool TryParse(ReadOnlySpan<byte> span, out int value, out int bytesConsumed, char format="\0")
The first method forces you to look ahead in advance and find the separator. The data is then read again for parsing.
The second one can stop itself while parsing the token, allowing you to parse the data in one pass through the buffer.
Because Utf8Parser
– a rather highly specialized class, it does not support IFormatProvider
and locales. But this is only a joy for us – the decimal point does not interfere with us here.
Using Utf8Parser
keep in mind that if there is not enough data left in the buffer, the result may turn out to be incorrect. If any of the text tokens breaks into two different readings from the data stream, for example [.........12][34...........]
then Utf8Parser
will read this token as two different numbers – 12 and 34. Or for [........1e][7.......]
will return false
for 1e
and you will have to do an additional check: or is it invalid double
or simply not enough data.
To simplify the implementation, I will require the presence in the buffer of a certain minimum amount of data or a sign of the end of the data stream. The code itself is also quite simple and only deals with loading data from the stream and skipping delimiters, which here are considered to be all characters up to and including the space. Optionally, you can also skip characters, for example, with codes >= 128
in case garbage gets into the data stream.
But during the contest, I would rather use the previous option based on StreamReader
and Span
– it’s much easier
class Scanner
{
private const int MaxTokenLength = 1200;
Stream? input = Console.OpenStandardInput();
byte[] buffer = new byte[32768];
Span<byte> Fragment => buffer.AsSpan(offset, length - offset);
int offset;
int length;
public int ReadInt()
{
while (input != null && length - offset < MaxTokenLength)
{
if (offset != 0)
{
var remaining = Fragment.Length;
Fragment.CopyTo(buffer);
offset = 0;
length = remaining;
}
var count = input.Read(buffer, length, buffer.Length - length);
if (count <= 0)
{
input = null;
break;
}
length += count;
while (offset < length && buffer[offset] <= ' ') offset++;
}
while (offset < length && buffer[offset] <= ' ') offset++;
var parsed = Utf8Parser.TryParse(Fragment, out int value, out int bytesConsumed);
if (!parsed)
Throw();
offset += bytesConsumed;
return value;
}
void Throw() => throw new Exception();
}
measurements
A file with 200,000 lines of six-digit numbers, 4 numbers each (~5MB) was used as test data. Each program XORed each of the columns and printed the answer at the end. Thus, only input performance was tested by the considered methods, with the ability to check the correctness during testing. The input data was preloaded into the memory of the program that launches the tested programs and fed to stdin.
.NET 7 NativeAOT on Linux was used as a runtime. This option gives the least overhead at the start of the program. With JIT on Windows, the overhead was ~36 ms, on Linux – ~70. The order of speed for .NET programs on Windows is the same.
The test does not pretend to be the most correct, the only goal was to evaluate the order of difference between the ways of reading the input.
conclusions
- You can write programs with intensive console IO on .NET.
- For maximum performance, we recommend:
- don’t use static methods
Console.Write/WriteLine
and write instdout
throughStreamReader
- to read a large number of numbers from the console (or just for the convenience of writing code), use the described methods: for example, with an additional buffer and a non-allocating
TryParse(ReadOnlySpan<char>
- correctly evaluate the task and not overcomplicate the code unnecessarily
- don’t use static methods