Как случайно написать самый быстрый CSV-парсер на C#

На рождественских каникулах 2025 года автор библиотеки FourLambda.Csv ехал в автобусе и читал про UTF-8. Обнаружив, что все ASCII-символы в UTF-8 занимают ровно один байт, он начал экспериментировать с подсчётом символов на максимальной скорости. Через несколько дней у него был готовый CSV-парсер на C#, который обогнал все существующие библиотеки в большинстве бенчмарков. Вот как это произошло.

Ключевые выводы
- SIMD-инструкции (SSE2, AVX2) позволяют обрабатывать 16-32 байта за одну операцию
- В UTF-8 все управляющие символы CSV (запятая, кавычка, перенос строки) занимают ровно один байт и совпадают с ASCII
- Минималистичный код (16 КБ) побеждает оптимизированный, но раздутый (163 КБ) за счёт давления на L1-кэш процессора
- Компилятор и рантайм умеют оптимизировать лучше, если им не мешать микрооптимизациями

Наивная реализация — считаем запятые

Прежде чем строить парсер, поставим простую задачу: как быстрее всего подсчитать, сколько раз символ , встречается в большом UTF-8-файле? Тестируем на CSV-файле размером 500 МБ.

Базовая реализация: 135,305 мс

			const byte findByte = (byte)',';

static int CountSoftware(ReadOnlySpan<byte> data)
{
  int count = 0;

  for (int i = 0; i < data.Length; i++)
  {
    if (data[i] == findByte)
      count++;
  }

  return count;
}
		

Простейший вариант: перебираем каждый байт и сравниваем с искомым. Можно ли лучше?

Unsafe-указатели: 128,683 мс

			static unsafe int CountSoftwareUnsafe(ReadOnlySpan<byte> data)
{
  int count = 0;
  int length = data.Length;

  fixed (byte* ptr = data)
    for (int i = 0; i < length; i++)
    {
      if (ptr[i] == findByte)
        count++;
    }

  return count;
}
		

Каждый раз, когда вы обращаетесь к массиву через data[i], рантайм .NET выполняет проверку границ (bounds checking) — убеждается, что индекс не выходит за пределы массива. Если вместо этого использовать unsafe-указатели, мы обещаем рантайму, что не выйдем за границы. Экономия — 7 мс.

Развёртка цикла (unrolling 4x): 105,320 мс

			static unsafe int CountSoftwareUnsafeUnrolled4x(ReadOnlySpan<byte> data)
{
  int count = 0;
  int length = data.Length;

  fixed (byte* ptr = data)
  {
    int i = 0;

    for (; i + 3 < length; i += 4)
    {
      if (ptr[i] == findByte)
        count++;
      if (ptr[i + 1] == findByte)
        count++;
      if (ptr[i + 2] == findByte)
        count++;
      if (ptr[i + 3] == findByte)
        count++;
    }

    for (; i < length; i++)
    {
      if (ptr[i] == findByte)
        count++;
    }
  }

  return count;
}
		

Механика цикла for обманчиво дорога: на каждой итерации нужно проверить условие выхода и выполнить переход в начало. Если обрабатывать по 4 элемента за итерацию, накладные расходы снижаются в четыре раза. «Хвост» данных, не кратный четырём, обрабатывается обычным побайтовым циклом.

Проблема — UTF-8 и Unicode ломают всё

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

Наименьшая единица данных — байт (числа 0-255). Но человечество использует гораздо больше 256 символов. Ранние системы решали это через кодовые страницы — у каждого региона была своя таблица. Японские системы использовали Shift-JIS, в Китае по закону обязателен GB 18030. Если открыть файл в неправильной кодировке, вы увидите «крокозябры» (mojibake) — бессмысленный набор символов.

Так выглядит mojibake — результат открытия файла в неправильной кодировке

Unicode решил эту проблему в 90-х: каждому символу присваивается номер (codepoint), а разные кодировки (UTF-8, UTF-16, UTF-32) определяют, как эти номера записываются в байты.

Вот как UTF-8 кодирует символы в зависимости от количества байтов:

			Кол-во байтов  Диапазон кодпоинтов  Двоичная структура
1 байт         U+0000 .. U+007F     0xxxxxxx
2 байта        U+0080 .. U+07FF     110xxxxx 10xxxxxx
3 байта        U+0800 .. U+FFFF     1110xxxx 10xxxxxx 10xxxxxx
4 байта        U+10000 .. U+10FFFF  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
		

Таблица ASCII-символов: все они кодируются в UTF-8 ровно одним байтом

Ключевой факт: байты 0x00-0x7F в UTF-8 полностью совпадают с ASCII. Это значит, что управляющие символы CSV — запятая (,), кавычка ("), перевод строки (\n) — всегда занимают ровно один байт, независимо от того, какие Unicode-символы находятся в данных. И это можно использовать для невероятно быстрого сканирования.

SIMD — ускорение через параллельные инструкции

До сих пор мы обрабатывали по одному байту за раз. Представьте сложение двух массивов по 8 элементов — нужно 8 отдельных операций сложения. Можно распараллелить это по потокам, но управление потоками создаёт накладные расходы и не добавляет эффективности.

Скалярная операция: процессор обрабатывает по одному элементу

SIMD (Single Instruction, Multiple Data) — это набор процессорных инструкций, которые выполняют одну операцию сразу над несколькими элементами данных. Вся магия происходит в железе, поэтому результат приходит за то же время, что и обычная операция над одним элементом.

SIMD: четыре операции сложения за одну инструкцию

Аналогия: сложить два однозначных числа (8 + 2) — просто. Сложить два семизначных — нужно перебирать разряды. А теперь представьте, что вы можете «увидеть» сумму двух семизначных чисел мгновенно, с той же лёгкостью, что и однозначных. Это и есть SIMD.

Более широкие регистры позволяют обрабатывать больше элементов за такт

Вот как выглядит SIMD-сложение 4 элементов за одну операцию:

			Индексы        0    1    2    3    4    5    6    7
array1       [ 4] [ 8] [43] [29] [12] [61] [50] [58]
array2     + [48] [22] [54] [22] [43] [36] [ 1] [56]
             ---- ---- ---- ----
array3     = [52] [30] [97] [51]  ..   ..   ..   ..
             ^^^^^^^^^^^^^^^^^^^^^^^^
             Одна SIMD-инструкция обработала 4 элемента
		

Мы делаем в 4 раза больше работы за то же усилие.

SSE2: 46,663 мс

			static int CountSSE2(ReadOnlySpan<byte> data)
{
  var compareVector = Vector128.Create(findByte);

  int count = 0;
  int i = 0;

  for (i = 0; i + 15 < data.Length; i += 16)
  {
    var dataVector = Vector128.Create(data.Slice(i, 16));
    var equal = Sse2.CompareEqual(compareVector, dataVector);
    var mask = (uint)Sse2.MoveMask(equal);
    while (mask != 0)
    {
      count += (int)(mask & 0x1);
      mask >>= 1;
    }
  }

  for (; i < data.Length; i++)
  {
    if (data[i] == findByte)
      count++;
  }

  return count;
}
		

SSE2 (появился в x86-процессорах в 2000 году) работает с 128-битными регистрами — 16 байтов за раз. Алгоритм такой:

1. Загрузить 16 байтов данных в SIMD-вектор
2. Сравнить каждый байт с искомым (Sse2.CompareEqual) — на позициях совпадений появятся байты 255, на остальных — 0
3. Извлечь старшие биты из каждого байта (Sse2.MoveMask) — получаем 16-битное число, где каждый установленный бит означает совпадение
4. Подсчитать установленные биты

Для строки "Hello, I, like, commas." это выглядит так:

			Индексы        0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
dataVector   [ H  e  l  l  o  ,     I  ,     l  i  k  e  ,    ]
compareVector[ ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , ]
               ↓ CompareEqual
equalVector  [ 0  0  0  0  0  *  0  0  *  0  0  0  0  0  *  0]
   (* = 255)    ↓ MoveMask
mask         [ 0  0  0  0  0  1  0  0  1  0  0  0  0  0  1  0]

Результат: найдено 3 запятые за одну итерацию SIMD-цикла
		

SIMD-поиск запятых: сравнение вектора данных с вектором разделителей

Поиск разделителей в строке с Unicode-символами

AVX2: 42,220 мс

AVX2 (с 2011 года) расширяет регистры до 256 битов — 32 байта за итерацию. Код аналогичен SSE2, но с Vector256 вместо Vector128.

			static int CountAvx2(ReadOnlySpan<byte> data)
{
  var compareVector = Vector256.Create(findByte);

  int count = 0;
  int i = 0;

  for (i = 0; i + 31 < data.Length; i += 32)
  {
    var dataVector = Vector256.Create(data.Slice(i, 32));

    var equal = Avx2.CompareEqual(compareVector, dataVector);
    var mask = (uint)Avx2.MoveMask(equal);

    while (mask != 0)
    {
      count += (int)(mask & 0x1);
      mask >>= 1;
    }
  }

  for (; i < data.Length; i++)
  {
    if (data[i] == findByte)
      count++;
  }

  return count;
}
		

Прирост скромный — значит, узкое место сместилось на цикл обработки маски. Нужно ускорить подсчёт битов.

AVX2 + TZCNT: 16,630 мс

BitOperations.TrailingZeroCount — аппаратная инструкция TZCNT, которая мгновенно находит позицию младшего установленного бита. Вместо того чтобы перебирать биты маски по одному, мы прыгаем сразу к следующему совпадению и сбрасываем его.

			while (mask != 0)
{
  count++;
  int bIndex = BitOperations.TrailingZeroCount(mask);
  mask ^= 1u << bIndex;
}
		

AVX2 + POPCNT: 13,673 мс

А есть ещё лучше. BitOperations.PopCount — аппаратная инструкция POPCNT, которая за одну операцию считает количество установленных битов в числе. Именно то, что нам нужно:

			// Вместо цикла — одна инструкция
count += BitOperations.PopCount(mask);
		

Мы достигли потолка производительности для подсчёта символов. Ускорение в 10 раз по сравнению с наивной реализацией — отличный результат. Пора применить это к парсингу CSV.

Поиск разделителей через SIMD

При парсинге CSV нас интересуют три управляющих символа: запятая (,), кавычка (") и перевод строки (\n). Правила обработки:

• Запятая — конец текущего поля
• Перевод строки — конец текущей строки
• Кавычка — начало или конец экранированного блока (внутри которого запятые и переносы игнорируются). Две кавычки подряд — это экранированная кавычка в значении

Парсинг разбивается на два этапа. Первый — определение позиций и длин полей через SIMD (функция DetermineFields). Второй — фактическое извлечение и дeкодирование значений, только когда пользователь их запрашивает.

Вот упрощённый код первого этапа (без обработки краевых случаев):

			private readonly Vector256<byte> separatorVector = Vector256.Create((byte)',');
private readonly Vector256<byte> escapeVector = Vector256.Create((byte)'"');
private readonly Vector256<byte> newlineVector = Vector256.Create((byte)'\n');

private readonly (int offset, int length, bool isEscaped)[] fieldInfo = new[256];

protected override int DetermineFields(ReadOnlySpan<byte> buffer)
{
  int endChar = -1;
  int fieldStart = 0;
  bool wasOnceEscaped = false;
  bool isEscaped = false;
  fieldCount = 0;

  int i = 0;

  for (; i + 31 < buffer.Length; i += 32)
  {
    // загружаем следующий блок данных
    Vector256<byte> dataVector = Vector256.Create(buffer.Slice(i));

    uint separatorMask = (uint)Avx2.MoveMask(
        Avx2.CompareEqual(dataVector, separatorVector));
    uint escapeMask = (uint)Avx2.MoveMask(
        Avx2.CompareEqual(dataVector, escapeVector));
    uint newlineMask = (uint)Avx2.MoveMask(
        Avx2.CompareEqual(dataVector, newlineVector));

    // объединяем маски
    var combinedMask = separatorMask | escapeMask | newlineMask;

    while (combinedMask != 0)
    {
      int index = BitOperations.TrailingZeroCount(combinedMask);
      uint bit = (1u << index);

      if ((escapeMask & bit) != 0) // кавычка
      {
        isEscaped = !isEscaped;
        wasOnceEscaped = true;
        goto continueLoop;
      }

      if (isEscaped)
        goto continueLoop;

      if ((separatorMask & bit) != 0) // запятая
      {
        fieldInfo[fieldCount++] = (
            fieldStart, i + index - fieldStart, wasOnceEscaped);
        fieldStart = i + index + 1;
        wasOnceEscaped = false;
      }
      else if ((newlineMask & bit) != 0) // перевод строки
      {
        endChar = i + index;
        goto exit;
      }

      continueLoop:
      combinedMask &= ~bit; // сбрасываем обработанный бит
    }
  }

  // (побайтовый цикл для остатка опущен для краткости)

  exit:

  fieldInfo[fieldCount++] = (
      fieldStart, endChar - fieldStart, wasOnceEscaped);

  return endChar;
}
		

Несколько важных деталей:

• Здесь используется TrailingZeroCount вместо PopCount, потому что нам важна позиция каждого найденного символа, а не только их количество
• Одна и та же схема CompareEqual + MoveMask применяется для каждого управляющего символа, а затем маски объединяются через OR. Отдельные маски сохраняются, чтобы потом определить тип найденного символа
• Мы не касаемся содержимого полей — если пользователю нужен только один столбец, незачем декодировать остальные

Обработка кавычек и экранирования

Когда поле содержит кавычки, нужно выполнить декодирование вручную — убрать обрамляющие кавычки и заменить двойные кавычки на одинарные. Кроме того, C# внутри использует UTF-16 для всех строк (char — это 16-битная единица кода), поэтому при чтении UTF-8 приходится конвертировать.

Если кавычек в поле нет, используется быстрая встроенная конвертация Encoding.UTF8.GetChars. Но если кавычки есть, быстрее выполнить конвертацию и удаление кавычек за один проход:

			private int UnescapeField(
    Span<char> destination,
    (int offset, int length, bool isEscaped) info)
{
  if (!info.isEscaped)
  {
    // без кавычек — используем быструю встроенную конвертацию
    return Encoding.UTF8.GetChars(
        new Span<byte>(bufferPtr + info.offset, info.length),
        destination);
  }

  // есть кавычки — собственная конвертация UTF-8 → UTF-16
  int idx = 0;
  int rawLength = info.offset + info.length;

  for (int i = info.offset; i < rawLength; i++)
  {
    byte c = bufferPtr[i];
    if (c == (byte)'"')
    {
      if (i != info.offset && i + 1 < rawLength)
      {
        var nextC = bufferPtr[i + 1];
        if ((nextC & 0x80) == 0)
        {
          destination[idx++] = (char)nextC;
          i++;
        }
      }
    }
    else if ((c & 0x80) != 0) // многобайтовая последовательность
    {
      var encodedLength =
          BitOperations.LeadingZeroCount(
              (uint)(~c & 0xFF)) - 24;
      uint codePoint;

      if (encodedLength == 2)
      {
        codePoint = (uint)(
            (c & 0b0001_1111) << 6 |
            (bufferPtr[i + 1] & 0b0011_1111));
        destination[idx++] = (char)codePoint;
        i += 1;
      }
      else if (encodedLength == 3)
      {
        codePoint = (uint)(
            (c & 0b0000_1111) << 12 |
            (bufferPtr[i + 1] & 0b0011_1111) << 6 |
            (bufferPtr[i + 2] & 0b0011_1111));
        destination[idx++] = (char)codePoint;
        i += 2;
      }
      else // 4 байта — суррогатная пара UTF-16
      {
        codePoint = (uint)(
            (c & 0b0000_0111) << 18 |
            (bufferPtr[i + 1] & 0b0011_1111) << 12 |
            (bufferPtr[i + 2] & 0b0011_1111) << 6 |
            (bufferPtr[i + 3] & 0b0011_1111));
        codePoint -= 0x10000;
        destination[idx++] =
            (char)(ushort)((codePoint >> 10) + 0xD800);
        destination[idx++] =
            (char)(ushort)((codePoint & 0x3FF) + 0xDC00);
        i += 3;
      }
    }
    else // ASCII — просто расширяем до 16 бит
    {
      destination[idx++] = (char)c;
    }
  }

  return idx;
}
		

Хитрость здесь в том, что 2- и 3-байтовые UTF-8-последовательности всегда дают одну единицу кода UTF-16, поэтому кодпоинт можно просто привести к char. Четырёхбайтовые символы (эмодзи и редкие иероглифы) требуют суррогатных пар.

Для UTF-16-строк (внутренний формат C#) парсер использует трюк с Avx2.PackUnsignedSaturate: два 256-битных вектора 16-битных символов «сжимаются» в один 256-битный вектор 8-битных байтов. ASCII-символы сохраняются как есть, а все не-ASCII насыщаются до 255 (или 0 для отрицательных при знаковой интерпретации). После перестановки блоков через Avx2.Permute4x64 можно применять ту же маску, что и для UTF-8.

Бенчмарки — результаты

Существующие бенчмарки CSV-парсеров на C# тестируют только один файл — по сути, они измеряют не парсинг CSV, а производительность на одном конкретном сценарии. Поэтому автор создал собственный набор тестов с разными типами данных:

• Реальные данные Reddit — широкий датасет с разными типами данных и большим количеством текста (из Reddit ArcticShift)
• Международный текст — CSV с названиями предметов из Pokemon на множестве языков (кириллица, японский, корейский)
• Финансовые данные — числа с минимумом текста
• Синтетические тесты — числовые поля, короткие файлы (50 строк), файлы с обязательным экранированием, «стресс-тест» с массой кавычек

Полные результаты опубликованы на bepis.io/csv-benchmark.

Итог: FourLambda.Csv оказался самым быстрым в 41 из 70 тестов. Не абсолютная победа, но убедительное лидерство.

Для сравнения, вот как менялась скорость подсчёта символов на файле 500 МБ по мере оптимизации:

			Реализация                     Время (мс)   Ускорение
────────────────────────────────────────────────────────
Базовая (for + bounds check)    135,305       1,0x
Unsafe-указатели                128,683       1,05x
Unsafe + unrolling 4x           105,320       1,28x
SSE2 (128 бит)                   46,663       2,90x
AVX2 (256 бит)                   42,220       3,20x
AVX2 + TZCNT                     16,630       8,14x
AVX2 + POPCNT                    13,673       9,90x
		

Почему FourLambda.Csv быстрее Sep

До этого самым быстрым CSV-парсером на C# считалась библиотека Sep. Вот несколько причин, почему FourLambda.Csv выигрывает:

UTF-8 без промежуточной конвертации. Sep внутри конвертирует UTF-8 в UTF-16 даже если данные не нужны пользователю. FourLambda.Csv работает напрямую с UTF-8.

Давление на кэш. L1-кэш процессора — около 32-64 КБ, и он хранит не только данные, но и исполняемый код. FourLambda.Csv весит ~16 КБ, а Sep — ~163 КБ. Разница в 10 раз означает, что Sep может вытеснять данные из L1-кэша, вызывая медленные обращения к памяти.

Переоптимизация. Sep тщательно контролирует, как данные перемещаются между регистрами. Теоретически это быстрее, но на практике может мешать оптимизациям рантайма. Компилятор и процессор умеют оптимизировать код, если им не указывают точный способ выполнения. Чрезмерная микрооптимизация «связывает руки» и мешает автоматическим улучшениям в новых версиях .NET.

Зависимость от оборудования. Результаты могут отличаться на разных машинах. Например, Sse.Prefetch0 (предзагрузка данных в L1) давала +10-20% на ноутбуке с DDR3, но почти нулевой эффект на десктопе с DDR5. На системах с AVX-512 и ARM у Sep есть аппаратные оптимизации, которых пока нет в FourLambda.Csv.

Выводы

История этого проекта — хороший пример того, как глубокое понимание низкоуровневых деталей (кодировки, устройство кэша, SIMD-инструкции) может привести к результатам, которые превосходят годы целенаправленных оптимизаций в существующих библиотеках.

Главные уроки:

• SIMD — не магия для избранных. В C# интринсики доступны из коробки и дают кратный прирост на задачах поиска и сравнения
• UTF-8-совместимость ASCII — мощное свойство, которое можно эксплуатировать для быстрого парсинга
• Минимализм побеждает сложность: меньше кода — меньше давления на кэш — быстрее выполнение
• Не мешайте компилятору: иногда лучшая оптимизация — не оптимизировать вручную

Библиотека доступна на GitHub: bbepis/FourLambda.Csv.

Перевод и адаптация статьи How I accidentally made the fastest C# CSV parser с разрешения автора.