Быстрый консольный ввод на .NET

Во времена, когда .NET был закрытой технологией только для Windows, за ним и языком C# закрепилась репутация платформы, которая отлично подходит для решения бизнес-задач, но непригодна для соревновательного программирования и написания высокопроизводительного кода.

Часто приходится слышать, что «шарпы медленные», особенно в контексте алгоритмических задач, например с timus.online и codeforces.com. И, увы, не только слышать, но и сталкиваться с реальными проблемами, связанными с особенностями платформы, получая Wrong Answer, Runtime Error, Memory Limit, Time Limit при корректном алгоритме.

Большинство этих проблем кроется в особенностях консольного ввода и вывода. Да и часто куда проще написать cin >> nили sc.nextInt(), чем int.Parse(Console.ReadLine()) или Console.ReadLine().Split().Select(int.Parse).ToArray(), из-за чего выбор падает на другой язык.

Далее я расскажу о распространённых проблемах с консольным вводом-выводом в .NET, и о том, как сделать ввод быстрым и удобным.

Плавающая запятая

Иногда требуется считать или вывести число с плавающей точкой. Но легко забыть, что плавающие точки в .NET бывают запятыми, в зависимости от локали. Об этом особенно легко забыть, если пользоваться английской локалью в своей операционной системе.

Варианта решения два:

• задать локаль потока: Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
• передавать CultureInfo.InvariantCulture явно в такие методы, как (Try)Parse и ToString

Также в современном .NET есть параметр рантайма InvariantGlobalization, позволяющий избежать подобных проблем.

Ввод и вывод

Представим, что нам дана простая задача: нужно считать строк по 4 числа int в каждой , числа разделёны пробелами. Требуется вывести сумму чисел для каждой строки.

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

Может ли в этом коде что-то привести к вердикту, отличному от Accepted? Запросто.

Особенности форматирования

В условии ничего не сказано про количество пробелов, которыми разделены числа. И в итоге, если где-то пробелов больше одного, Console.ReadLine().Split() вернёт массив, содержащий пустые строки. А int.Parse упадёт с исключением, что приведёт к вердикту Runtime Error. Может показаться, что такого не бывает на контестах, но увы, случай вполне реальный.

Исправляем код:

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

Неприятный нюанс, о котором надо помнить. Кстати, если раньше код обрабатывал все пробельные символы как разделители, то теперь только пробелы. Исправить можно, но будет чуть длиннее.

Проблема возникает только при построчном чтении ввода. В языках, где есть готовые способы для считывания с консоли чисел (например int n; cin >> n), проблемы не возникает вообще.

Console Flush

Потоки ввода и вывода stdin/stdout/stderr устроены на основе буфера в памяти, в который один процесс может записать данные, а другой — прочитать. Обращаться к этому буферу ради нескольких байт — дорого, поэтому для эффективности каждый процесс может дополнительно буферизовать ввод/вывод. Продвижение данных в буфер потока происходит либо при заполнении локального, либо при вызове .Flush().

Вызов .Flush() имеет большой смысл для интерактивных консольных приложений — пользователю нужно показать вывод в терминале сразу, а не копить его в памяти. Большинство платформ изначально адаптированы под этот сценарий и вызывают .Flush() автоматически после каждой записи.

Обратите внимание, что бывают и задачи, в которых требуется интерактивный ввод-вывод (request-response семантика). Например задачи, в которых требуется вычислить ответ, задавая «вопросы» проверяющей системе (простейший пример — программа, угадывающее слово в условном «Поле чудес», «общающаяся» с программой-ведущим)

Чтобы сэкономить на Flush, в C++ iostreams пишут:

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

А в C# можно использовать StreamWriter для stdout вместо 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); }

Проверим, оказывает ли .Flush() влияние на производительность замерами. Версия с Console.WriteLine отрабатывает на моём компьютере за ~490ms, а с использованием StreamWriter — за 105ms. Т.е. причина плохой производительности оказалась вовсе не в LINQ. В проверяющей системе c более медленным железом можно запросто получить Time Limit Exceed, если не учитывать автоматический .Flush(). Кстати, на заметку, в энтерпрайз приложениях проблема тоже встречается — в логировании.

Замерял на Linux, рантайм .NET 7 NativeAOT — так достигается минимальный оверхед на старте программы, порядка 1.5 ms. На Windows как минимум старт процесса был бы порядка 10 ms, даже для C++.

Для чтения также можно использовать StreamReader вместо Console. Это позволяет сэкономить на проверке, не переопределён ли Console.In при каждом чтении и использовать увеличенный буфер, но выигрыш куда менее впечатляющий — единицы миллисекунд

Обратите внимание, что задавать размер буфера консольному стриму нет смысла — параметр попросту игнорируется

Задача на ввод: аллокации

Задача 1510 с Тимуса. Для этой задачи есть два решения — за линию и с сортировкой. Её все сдают легко на том же C++, но на C# даже с умным алгоритмом из-за особенностей стандартного ввода будет Memory Limit Exceed. Почему?

В задаче установлен Memory Limit в 16 MB. Зачем? Не знаю, сохранить все числа в памяти и отсортировать он никак не мешает, ведь 500000 чисел по 4 байта — всего лишь 2 MB. Но в C# чтение ввода через Console.ReadLine приводит к аллокации строк. А строка с числом из 10 цифр, это не 4 байта, а, как минимум:

• 16 байт на заголовок объекта и указатель на Method Table
• 4 байта на хранение длины
• 20 байт на 10 символов в UTF-16
• 2 байта на null terminator для совместимости с нативным кодом, его ожидающим

Т.е. уже 42 байта на 10 символов. А 500000 раз по 42 байта — это уже 21 MB.

Но они же короткоживущие?! Читаем строку, сразу парсим, GC как-нибудь соберёт. Но срабатывание GC — не гарантированно, освобождение памяти обратно в ОС — тоже, а принудительный вызов через GC.Collect() может привести уже к Time Limit Exceed.

Как же быть? Писать ввод самостоятельно

Кастомный ввод

Дедовское решение

По C++ вспоминается решение с посимвольным чтением чисел.

Перепишем его на C# с использованием Console.Read(), а лучше — StreamReader.Read(). В этом случае использовать StreamReader оправдано, потому что обращаться к Console на каждый символ гораздо дороже, чем на каждую строку при использовании ReadLine.

После этого задача не представляет никакой сложности. На моём компьютере посимвольное чтение отрабатывает в 3 раза быстрее, чем с 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; }

Решение, однако, не идеально. Этот метод подходит для целых чисел, а сделать корректный парсинг чисел с плавающей точкой нетривиально, легко попасть на граничные случаи и ошибиться с точностью. Чтобы это понять, достаточно посмотреть Pull Request.

Тиктокерское решение

В современном .NET есть перегрузки методов Parse и TryParse принимающие ReadOnlySpan<char> вместо строки. Вместо ручного парсинга чисел, можно записать фрагмент символов с числом в буфер и вызвать стандартный метод для парсинга.

Это решит проблему с парсингом чисел с плавающей точкой «дедовского» решения, а также сделает ввод кода удобнее, избавив от необходимости писать конструкции вида Console.ReadLine().Split().Select(int.Parse).ToArray(). Сам код настолько прост, что может быть легко написан прямо во время контеста (но не учитывает, например, переполнение буфера, если вам это важно):

class Scanner {   StreamReader input = new(Console.OpenStandardInput(), bufferSize: 16384);   char[] buffer = new char[4096];    public int ReadInt()   {     var length = PrepareToken();     return int.Parse(buffer.AsSpan(0, length));   }    private int PrepareToken()   {     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 length;   } }

Да, работает медленнее «дедовского» варианта, но на уровне с общепринятыми способами ввода, не аллоцирует memory traffic, и уж точно не станет причиной попадания в Time или Memory Limit.

На C++ и других языках можно написать и более эффективные варианты консольного ввода. scanf и cin взяты только для того, чтобы ориентироваться на способы чтения ввода, которые обычно укладываются в пределы Time Limit

Для .NET 7 и C# 11 можно сделать generic версию на основе статического метода интерфейса ISpanParsable<TSelf>. Правда, в проверяющих системах C# 11 ещё не поддерживается.

class Scanner {   StreamReader input = new(Console.OpenStandardInput(), bufferSize: 16384);   char[] buffer = new char[4096];    public T Read<T>() where T : ISpanParsable<T>   {     var length = PrepareToken();     return T.Parse(buffer.AsSpan(0, length), CultureInfo.InvariantCulture);   }    private int PrepareToken()   {     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 length;   } }

Также я подготовил более эффективный вариант кода на основе TryParse(ReadOnlySpan<char>), но он слишком длинный, чтобы поместиться здесь. Он разгоняется в моём тесте до 24 мс за счёт чтения данных блоками.

Отказываемся от StreamReader

StreamReader — прослойка между Console Stream, в который обычно попадают ASCII-символы и .NET-строками в кодировке UTF-16. Переделаем код для работы со Stream напрямую.

Метод для парсинга, принимающий ReadOnlySpan<char> уже не подойдёт. К счастью, в .NET есть класс под названием Utf8Parser— наследие разработки библиотеки System.Text.Json, решающее ту же задачу для спана байтов. Не обманывайтесь тем, что в названии есть Utf8 — парсить все 100500 цифр, которые есть в Unicode он не умеет. Зато с обычными ASCII-цифрами справляется на ура!

Достоинство Utf8Parser.TryParse в сравнении с T.TryParse— возможность парсить значение с префикса, без заранее подготовленного токена. Сравните:

bool TryParse(ReadOnlySpan<char> span, out int value, IFormatProvider provider); bool TryParse(ReadOnlySpan<byte> span, out int value, out int bytesConsumed, char format='\0')

Первый метод заставляет заранее заглянуть вперёд и найти разделитель. Затем данные читаются снова для парсинга.

Второй же умеет останавливаться при парсинге токена сам, позволяя распарсить данные за один проход по буферу.

Т.к. Utf8Parser — достаточно узкоспециализированный класс, он не поддерживает IFormatProvider и локали. Но нам это только в радость — десятичная запятая нам здесь никак не помешает.

При использовании Utf8Parser нужно учитывать, что если данных в буфере осталось мало — результат может оказаться неверным. Если какой-то из текстовых токенов разобьётся на два разных чтения из потока данных, например [.........12][34...........], то Utf8Parser прочитает этот токен как два разных числа — 12 и 34. Или же для [........1e][7.......] вернётся false для 1e, и придётся делать дополнительную проверку: или это невалидный double или же просто не хватило данных.

Для упрощения реализации, буду требовать наличия в буфере некоторого минимального количества данных или признака окончания потока данных. Сам код тоже довольно прост и занимается только загрузкой данных из потока и пропуском разделителей, которыми здесь считаются все символы по пробел включительно. По желанию можно также пропускать символы, например, с кодами >= 128, на случай если в поток данных попадёт мусор.

Но во время контеста я бы лучше использовал предыдущий вариант на основе StreamReader и Span — он всё же гораздо проще

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

Замеры

В качестве тестовых данных использовался файл с 200000 строками шестизначных чисел по 4 числа в каждой (~5MB). Каждая программа считала XOR каждой из колонок и выводила ответ в конце. Таким образом, тестировалась только производительность ввода рассмотренными способами, с возможностью проверить корректность при тестировании. Входные данные предварительно загружались в память программы, производящей запуск тестируемых программ и подавались на stdin.

В качестве рантайма использовался .NET 7 NativeAOT на Linux. Этот вариант даёт меньше всего оверхеда на старте программы. C JIT на Windows оверхед составил ~36 мс, на Linux — ~70. Очерёдность по скорости для .NET-программ на Windows не отличается.

Тест не претендует на максимальную корректность, ставилась лишь цель оценить порядок разницы между способами чтения ввода.

Выводы

• На .NET можно писать программы с интенсивным консольным IO.
• Для достижения максимальной производительности рекомендуется:
  
  • не использовать статические методы Console.Write/WriteLine, а писать в stdout через StreamWriter
  • для чтения большого количества чисел с консоли (или просто для удобства написания кода) использовать описанные способы: например с дополнительным буфером и неаллоцирующим TryParse(ReadOnlySpan<char>)
  • правильно оценивать задачу и не переусложнять код без необходимости

Ссылки

• API Proposal о новом консольном вводе