На рождественских каникулах я ехал на автобусах из одного штата в другой, и мне нужно было как-то убить 24 часа. Я читал об UTF-8 и узнал об этой кодировке нечто интересное: все традиционные символы ASCII сохранены в ней в их исходном однобайтовом представлении, поэтому их можно сканировать крайне быстро. Я решил поэкспериментировать с кодом, максимально быстро подсчитывающим такие символы, в результате получив готовый парсер CSV, который вполне сравним с предыдущими парсерами, а то и быстрее них.

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

Преамбула: что такое кодировки символов

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

(Если вы знаете, как работает Unicode и UTF-8/16, то можете и пропустить эту главу. Но можете и остаться, если вам хочется узнать любопытные факты.)

Ещё с самых ранних этапов развития компьютеров хранение и обработка текстовых данных были очень сложным процессом. Это вызвано всего лишь двумя причинами:

  • Наименьшая значимая единица данных в компьютере — это байт, принимающий любые значения в интервале от 0 до 255.

  • Если взять все языки вместе, человечество пользуется гораздо большим количеством символов, чем 256.

Поэтому разработчикам компьютеров нужно было ответить на два вопроса: как описать больше 256 символов и как делать это эффективно?

Если вы занимались преобразованием текстовых символов из байтов и обратно, то наверняка видели подобную таблицу ASCII:

Setting binding redirect error
S

Это и есть кодировка символов. Она определяет соответствие между байтами и человекочитаемыми текстовыми символами. Эта таблица была создана в 1970-х годах и её применяли везде, куда поставлялись американские компьютеры (буква A в ASCII означает «American»).

Важным исключением из этого правила стали страны, в языках которых не используется латиница. У них есть собственные наборы символов (в контексте операционных систем также называемые кодовыми страницами), имеющие свои соответствия для каждого символа. В большинстве из них под символы латиницы зарезервирована та же область, что и в ASCII, а в области после 0x7F располагаются их собственные символы. Некоторым нужно даже больше места, поэтому они определяют некоторые символы, как последовательности из нескольких байтов.

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

Mojibake
Mojibake

Unicode: одна кодировка, чтобы править всеми

Разработчиков компьютеров такая ситуация утомила. Существуют сотни уникальных специализированных кодировок. Представьте, каково это — обрабатывать их все, не говоря уже о том, чтобы выполнять преобразования между ними.

На сцене появляется кодировка Unicode, созданная в 90-х. Смысл её был очень прост: каждому символу присваивается число (называемое также кодовой точкой), и вместо того, чтобы пытаться привязать символы к байтам, мы проводим соответствия между присвоенными числами и байтами.

В реальности всё не так просто. Некоторые символы используются гораздо чаще остальных, к тому же Unicode должна была иметь обратную совместимость с кодировками символов на основе ASCII (именно поэтому символы ASCII полностью соответствуют символам UTF-8; если ограничиться только этими символами, то можно использовать любую из этих кодировок).

Кроме того, для одного и того же списка символов Unicode существуют множественные кодировки символов, также называемые UTF.

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

Постепенно Unicode начали использовать практически повсюду, и практически невозможно найти текст в кодировке, не основанной на ней. За исключением двух примечательных локалей:

  • В японских компьютерных системах заимствование Unicode шло гораздо менее быстрыми темпами, вместо неё использовалась собственная кодировка Shift-JIS. Сегодня ситуация не так плоха, как когда-то, но даже в 2010 году 50% японоязычных веб-сайтов имели только Shift-JIS, а 38% использовали Unicode.

  • В китайских компьютерных системах (и в операционных системах, и в приложениях) законодательно утверждена поддержка GB 18030 — китайской кодировки символов, частично основанной на Unicode. Это «официальный набор символов Китайской Народной Республики». Конвертация между Unicode и этой кодировкой очень сложна, и она даже ломает совместимость с Unicode в отношении того, какие кодовые точки соответствуют каким символам, несмотря на то, что кодировка задумывалась, как полностью поддерживаемая альтернатива UTF.

Можете в это поверить? Государство требует использования конкретного набора символов. Именно это я и имел в виду, когда говорил об интересных фактах. Впрочем, мы отклонились от темы.

UTF-8, UTF-16 и UTF-32

Теперь возьмёмся за реальные технические подробности Unicode. Эта кодировка рассчитана на 1,1 миллиона символов (чего, надеюсь, хватит всем). В результате этого, с учётом прочих структурных частей Unicode, кодовые точки можно считать 32-битными целыми числами.

Значит ли это, что на каждый символ мы будем тратить 4 байта? Разумеется, нет. Именно потому существует множество разных способов преобразования кодовых точек Unicode в байты и обратно. Для этого применяется кодирование переменной длины: первый байт каждого символа заранее определяет, сколько байт за ним следует.

Например вот как выглядит общая структура UTF-8 при кодировании числа в зависимости от того, сколько байт для этого требуется:

Нужное количество байт

Интервал кодовых точек

Двоичная структура

1 байт

С U+0000 по U+0080

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

С точки зрения обработки всё просто: мы проверяем биты в первом байте, чтобы понять, насколько длинной будет последовательность, и считываем/записываем значение кодовой точки в свободное место, обозначенное в таблице символами «x». Кроме того, такая система автоматически синхронизируется: если часть данных будет повреждена, то остальные данные после них не будут потеряны и не придётся гадать, где начинается следующий символ. Достаточно найти следующую допустимую начальную последовательность битов и от него двигаться дальше. Ещё одна очень удобная особенность UTF-8 заключается в том, что байты 0×00 — 0×7F соответствуют их эквивалентам в ASCII, благодаря чему они обратно совместимы со всеми файлами ASCII.

В UTF-16 происходит нечто подобное, только ширина «единицы кодирования» равна не одному, а двум байтам (отсюда и 16, то есть 16 бит). Она тоже сохраняет возможность присоединения в конец ещё одной единицы кодирования, называемой суррогатом, но происходит это не так изящно, как в системе UTF-8.

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

Вот несколько примеров того, как это выглядит на практике:

Текстовый символ

Кодовая точка (шестнадцатеричная)

Описание в UTF-8

Описание в UTF-16

Описание в UTF-32

E

U+0045

0x45

0x00 0x45

0x00 0x00 0x00 0x45

Ж

U+0416

0xD0 0x96

0x04 0x16

0x00 0x00 0x04 0x16

ぁ

U+3041

0xE3 0x81 0x81

0x30 0x41

0x00 0x00 0x30 0x41

😎

U+1F60E

0xF0 0x9F 0x98 0x8E

0xD8 0x3D 0xDE 0x0E

0x00 0x01 0xF6 0x0E

Для содержимого нашей статьи актуальными будут лишь несколько фактов:

  • Так как все форматы UTF — это, по сути, различные способы кодирования списка номеров кодовых точек, проще всего выполнять преобразования между ними, извлекая каждую кодовую точку из исходной последовательности и перезаписывая её в целевой формат.

  • При считывании можно проверить, состоит ли символ из нескольких байтов, посмотрев на первый бит его первого байта: если он равен 0, то это однобайтный символ, если 1, то многобайтный.

  • Что ещё более важно, все символы в диапазоне ASCII всегда будут иметь длину ровно один байт для обеспечения обратной совместимости с ASCII.

Считаем символы как можно быстрее

Отлично, наконец, мы со всем этим разобрались. Я начал весь свой проект лишь благодаря тому, что узнал о последнем пункте: если символы ASCII имеют длину один байт, то для парсинга CSV-файла можно придумать множество очень крутых трюков, потому что все управляющие символы CSV относятся к ASCII.

Но для начала давайте поставим более простую цель и будем отталкиваться от неё. Как быстрее всего посчитать, сколько раз один символ встречается в большом текстовом файле UTF-8?

В качестве отправной точки мы будем выполнять сканирование в поисках символа , в CSV-файле размером 500 МБ.

const byte findByte = (byte)',';

Программная реализация: 135,305 мс

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 будет выполнять так называемую «проверку границ», то есть проверку, что индекс (i) находится в интервале от нуля до длины массива, чтобы можно было выбросить IndexOutOfRangeException, если он выходит на интервал.

Когда мы используем небезопасные (unsafe) указатели для доступа к содержимому массива, то обещаем среде исполнения, что не будем получать доступ к данным вне диапазона массива, потому что в противном случае можем столкнуться с AccessViolationException, или хуже того — с отсутствием исключений, после чего будем обрабатывать невалидные данные (отсюда и термин «небезопасные»).

Благодаря этому мы сэкономили 7 мс.

Программная реализация (unsafe, четырёхкратное раскручивание): 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 могут быть обманчиво затратными. В предыдущих функциях при каждом сравнении байта нужно было проверять, находимся ли мы в конце массива, и выполнять затратный переход в начало цикла, если нет. В результате возникает большой оверхед, поэтому следующая оптимизация заключается в выполнении сравнений блоками по четыре. Чтобы обеспечить наилучшую производительность, можно подбирать подходящее количество, но это будет зависеть от целевой системы.

Стоит отметить, что у нас по-прежнему есть более медленное сравнение байта во временном цикле в конце функции. Он нужен исключительно потому, что не все данные будут кратными четырём, поэтому нужно обрабатывать конец данных отдельно.

SIMD: Single Instruction, Multiple Data

Прежде, чем мы перейдём к следующей серии оптимизаций, нужно объяснить ещё одну концепцию.

Пока мы обрабатывали по одному байту за раз. Например, давайте посмотрим, как выглядит сложение двух байт одновременно из array1 и array2 в array3:

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

=

54

..

..

..

..

..

..

..

Для суммирования всех элементов в массивах нам нужно итеративно обходить каждый элемент по отдельности и выполнить 8 отдельных команд сложения. Этот процесс можно ускорить при помощи многопоточности — назначить каждому потоку свой срез и обрабатывать их параллельно:

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

=

54

..

97

..

55

..

51

..

В этом примере каждому потоку назначается срез из двух элементов. Хотя в теории это может ускорить работу в четыре раза, на практике управление несколькими потоками запутанно и создаёт большой оверхед. Кроме того, это не более эффективно, потому что выполняется тот же объём работы, только распределённый по разным ядрам CPU. Как можно улучшить ситуацию?

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

Проще это представить на примере сложения столбиком. Сложить два одноразрядных числа наподобие 8 + 2 легко, это делается мгновенно. Но если нужно сложить два больших числа, например, 4672345 + 3782147, то придётся работать с каждым разрядом по отдельности, в конечном итоге получив общую сумму. Представьте, что вместо этого мы можем посмотреть на эти два числа и сразу же определить сумму, приложив те же мыслительные усилия, что и при сложении одноразрядных чисел. Вот в этом и заключается сила SIMD.

Вернёмся к нашему примеру: если бы мы использовали команду SIMD, выполняющую суммирование четырёх элементов одновременно, то одно вычисление выглядело бы так:

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

=

54

30

97

51

..

..

..

..

Мы выполняем четырёхкратную работу за тот же объём усилий. Лично я считаю, что это одно из самых замечательных свойств современных CPU.

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

Вот первая реализация функции с использованием SIMD. SSE2, появившийся в процессорах x86 в 2000 году, имеет ширину 128 бит/16 байт; именно поэтому основной цикл теперь работает с блоками по 16 байт.

Команды SIMD требуют, чтобы данные помещались в специальные регистры CPU; они не умеют напрямую работать с массивами, поэтому мы управляем данными в регистрах при помощи структуры Vector128. Вот, как выглядит процесс работы для строки «Hello, I, like, commas» (я урезал его до первых 9 байт, чтобы таблица уместилась в статью):

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

dataVector

H

e

l

l

o

,

I

,

l

i

k

e

,

c

o

m

m

a

s

.

compareVector

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

equalVector

Sse2.CompareEqual

0

0

0

0

0

255

0

0

255

0

0

0

0

0

255

0

mask

Sse2.MoveMask

0

0

0

0

0

1

0

0

1

0

0

0

0

0

1

0

Sse2.CompareEqual выводит 255 в каждый слот, где совпадают два байта, а Sse2.MoveMask извлекает из каждого слота старший бит, сжимая всё это до 16-битного integer. В результате мы получаем маску, в которой каждый бит 1 соответствует местоположению совпадения; после этого можем всё обработать. Изящно.

Но можно ли это улучшить?

SIMD AVX2: 42,220 мс

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

Вместо SSE2 давайте используем AVX2. Это расширение, появившееся в CPU x86 в 2011 году, имеет ширину уже 32 байта.

В отличие от большого скачка скорости, обеспеченного SSE2, здесь прирост оказался очень скромным, поэтому, похоже, следующее узкое место находится где-то ещё. В данном случае это цикл, преобразующий маску в счислимое число. Давайте посмотрим, что с этим можно сделать.

AVX2 + TZCNT: 16,630 мс

static int CountAvx2Tzcnt(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 bIndex = BitOperations.TrailingZeroCount(mask); 
      mask ^= 1u << bIndex; 
    }
  }

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

  return count;
}

Теперь вместо постоянного сдвига маски вниз и считывания младшего бита можно использовать TrailingZeroCount, чтобы напрямую найти следующий бит 1 и обратить его, поэтому нам не нужно тратить усилия на обнуление битов в маске.

Если бы мы реализовывали это программно, TrailingZeroCount, то был бы слишком медленным и не обеспечил никаких преимуществ. Однако в данном случае это ещё одна операция, реализуемая в CPU аппаратно: вместо итераций по каждому отдельному биту операция происходит мгновенно.

Впрочем, сюда может лучше подойти другая операция:

AVX2 + POPCNT: 13,673 мс

static int CountAvx2Tzcnt(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);

    count += BitOperations.PopCount(mask); 
  }

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

  return count;
}

PopCount фактически разрабатывался именно под этот сценарий. Мы берём маску, а он возвращает количество битов, равных 1 во входном integer. Кроме того, он реализован аппаратно, так что это происходит очень быстро.

По сути, здесь мы зашли в тупик с точки зрения производительности. Да, можно сделать кое-что ещё, выжимая крохи скорости, но это даст нам улучшение меньше одной миллисекунды. Но надо признать, что ускорение в 10 раз само по себе крайне хорошо.

Используем это для создания CSV-парсера

При парсинге CSV-файла для вычисления структуры файла и позиций значений важны три символа: , (запятая), " (кавычка) и \n (символ новой строки).

И здесь нам пригодятся наши предыдущие эксперименты. Для создания высокопроизводительного CSV-парсера важнее всего как можно быстрее обнаруживать эти структурные символы, а затем применять следующие правила:

  • Запятая обозначает конец поля.

  • Символ новой строки обозначает конец строки.

  • Кавычка заставляет игнорировать все структурные символы, пока не встретится ещё один символ кавычек.

    • Если подряд идут две кавычки, то в выводе должна оставаться только одна.

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

Вот, как это выглядит в сильно упрощённом виде (удалены пограничные случаи и микрооптимизации):

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; // Сброс этого бита
    }
  }

  // (Вариант цикла без SIMD удалён ради краткости)

  exit:

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

  return endChar;
}

Нужно отметить следующее:

  • Вместо BitOperations.PopCount мы используем немного более медленный BitOperations.TrailingZeroCount, потому что нам важны данные позиций, а PopCount не сохраняет их.

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

  • Мы вообще не касаемся значений полей. Если пользователю важен только один столбец, то мы должны начать обрабатывать содержимое только тогда, когда пользователь это запросит.

Ещё одна неочевидная задача заключается в обработке экранированных полей. Нам нужно обрабатывать и удалять дополнительные кавычки из всех полей, где они есть. Как лучше подойти к решению этой задачи?

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

  // Мы обнаружили кавычку, поэтому нужно выполнять специализированное преобразование в 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) // Длина 2 байта - всегда один символ utf16
      {
        codePoint = (uint)((c & 0b0001_1111) << 6 | (bufferPtr[i + 1] & 0b0011_1111));
        
        destination[idx++] = (char)codePoint;
        i += 1;
      }
      else if (encodedLength == 3) // Длина 3 байта - всегда один символ utf16
      {
        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 байта - всегда два символа utf16 как пара суррогатов. Преобразование UTF8 -> UTF32 -> UTF16
      {
        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
    {
      destination[idx++] = (char)c;
    }
  }

  return idx;
}

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

Если поле вообще не экранировано кавычками, то мы можем передать реализацию методу Encoding.UTF8.GetChars. В нём используется много чёрной магии и особенностей среды исполнения, которые я не понимаю и к которым у меня нет доступа; он стабильно оказывается быстрее всего, что мы могли бы создать сами. Но в случае, когда у нас есть кавычки, быстрее будет просто неуклюже реализовать всё самим, а не пользоваться Encoding.UTF8.GetChars для помещения данных во временной буфер с последующим сканированием обработки для удаления кавычек.

Единственная сложная часть этой функции — преобразование из UTF-8 в UTF-16. Символы ASCII нужно расширить до 16 бит (преобразовав их в char), но перед преобразованием необходимо извлечь кодовые точки многобайтных последовательностей. Также мы можем воспользоваться тем, что любые 2 или 3 байта последовательностей UTF-8 всегда будут превращаться в одну кодовую единицу UTF-16, поэтому представление — это сама кодовая точка, обрезанная до младших 16 бит.

Проблема с UTF-16

Итак, это практически и есть основа для достаточно хорошего CSV-парсера UTF-8. А поскольку почти все создаваемые сегодня текстовые файлы хранятся в UTF-8, то этого должно хватать для всего, ведь так?..

Ну, не совсем. Как я сказал выше, внутри C# для хранения всего, что связано с char и string, используется UTF-16. То есть наш парсер даже не сможет читать строки, созданные на C#!

Надо это исправить. Основная часть кода останется неизменной, но требуются некоторые изменения в сканировании двухбайтных символов (потому что теперь у нас нет совместимости с ASCII). Изначально я думал, что добиться схожей производительности не удастся ни в коем случае, но потратив на это какое-то время, я нашёл достаточно близкое решение.

Основное изменение произошло в цикле сканирования:

// ...

Vector256<short> dataVector1 = Avx.LoadVector256((short*)bufferPtr + i);
Vector256<short> dataVector2 = Avx.LoadVector256((short*)bufferPtr + i + 16);

// Значения 256 -> 32767 будут корректно преобразовываться и дополняться до 255.
// Значения 32768 -> 65535 будут интерпретироваться как отрицательные и дополняться до 0.
// Это идеально для нас, потому что ASCII остаётся неизменным
Vector256<byte> packedData = Avx2.PackUnsignedSaturate(dataVector1, dataVector2);

Vector256<byte> dataVector = Avx2.Permute4x64(packedData.AsUInt64(), 0b11_01_10_00).AsByte();

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

uint combinedMask = separatorMask | escapeMask | newlineMask;

// ...

Изначально это была просто копия версии с UTF-8, в которой мы сравнивали по 2 байта за раз, то есть пропускная способность была в два раза меньше, и это было довольно медленно. Но здесь решение чуть более умное.

Avx2.PackUnsignedSaturate получает два вектора AVX2, интерпретирует входные данные как 16-битные integer, а затем сворачивает их до одной 8-битной последовательности integer, как в цикле UTF-8. В процессе происходит дополнение, то есть значения больше 255 превращаются в 255, а значения меньше 0 превращаются в 0. Так как интересующие нас символы находятся в интервале ASCII 0-128, они сохраняются, и это просто замечательно.

Однако это не совсем идеально для наших нужд, потому что против нас работает два аспекта:

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

  • Выходные данные чередуются блоками по 8 байт.

Обе эти проблемы можно решить. Первую можно полностью игнорировать: хоть мы и преобразуем беззнаковые числа в числа со знаком и получаем отрицательные числа там, где их быть не должно, благодаря дополнению они дополняются до 0, а не до 255. Вторую проблему можно решить при помощи Avx2.Permute4x64, который можно использовать для сдвига блоков по 8 байт так, как нам нужно. А затем можно применить маску тем же образом, что и раньше.

Вот расширенная схема для строки cat,猫,mačka,мачка,mačka,chatte,katė, позволяющая понаблюдать за происходящим:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

dataVector1dataVector2

c(99)

a(97)

t(116)

,(44)

猫(29483)

,(44)

m(109)

a(97)

č(269)

k(107)

a(97)

,(44)

м(1084)

а(1072)

ч(1095)

к(1082)

а(1072)

,(44)

m(109)

a(97)

č(269)

k(107)

a(97)

,(44)

c(99)

h(104)

a(97)

t(116)

t(116)

e(101)

,(44)

k(107)

a(97)

t(116)

ė(279)

packedData

Avx2.PackUnsignedSaturate

c(99)

a(97)

t(116)

,(44)

ÿ(255)

,(44)

m(109)

a(97)

ÿ(255)

,(44)

m(109)

a(97)

ÿ(255)

k(107)

a(97)

,(44)

ÿ(255)

k(107)

a(97)

,(44)

ÿ(255)

ÿ(255)

ÿ(255)

ÿ(255)

c(99)

h(104)

a(97)

t(116)

t(116)

e(101)

,(44)

k(107)

dataVector

Avx2.Permute4x64

c(99)

a(97)

t(116)

,(44)

ÿ(255)

,(44)

m(109)

a(97)

ÿ(255)

k(107)

a(97)

,(44)

ÿ(255)

ÿ(255)

ÿ(255)

ÿ(255)

ÿ(255)

,(44)

m(109)

a(97)

ÿ(255)

k(107)

a(97)

,(44)

c(99)

h(104)

a(97)

t(116)

t(116)

e(101)

,(44)

k(107)

separatorVector

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

Avx2.CompareEqual

0

0

0

255

0

255

0

0

0

0

0

255

0

0

0

0

0

255

0

0

0

0

0

255

0

0

0

0

0

0

255

0

separatorMask

Avx2.MoveMask

0

0

0

1

0

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

1

0

С другой стороны, поскольку мы уже работаем с UTF-16, код для избавления от экранирования крайне прост:

private int UnescapeField(Span<char> destination, (int offset, int length, byte escapedCount) info)
{
  int rawLength = info.offset + info.length;
  int idx = 0;

  for (int i = info.offset; i < rawLength; i++)
  {
    char c = bufferPtr[i];
    if (c == '"')
    {
      if (i != info.offset && i + 1 < rawLength)
      {
        destination[idx++] = bufferPtr[i + 1];
        i++;
      }
    }
    else
      destination[idx++] = c;
  }

  return idx;
}

Создаём исчерпывающий бенчмарк

Итак, потратив несколько дней на совершенствование кода, мы получили настоящий CSV-парсер. Как нам сравнить его с другими высокопроизводительными библиотеками?

Есть готовые бенчмарки для CSV-парсинга на C#:

Однако лично я не считаю их особо хорошими исключительно из-за того, что все они выполняют тест на одном CSV-файле. То есть может оказаться, что они и не замеряют парсинг CSV, а измеряют производительность в одном конкретном сценарии. 

Давайте создадим собственный набор бенчмарков. На каких данных мы хотим проводить тестирование?

  • Широкий датасет, содержащий множество разных типов данных и большой объём человеческого текста. Я бы сказал, что это «идеальный» датасет, поскольку он наиболее сбалансирован по каждому из аспектов и его легко можно встретить в реальной жизни. В качестве него взял большой фрагмент RC_2008-01.ndjson из дампов Reddit ArcticShift и преобразовал его в формат CSV.

  • Данные, содержащие много символов Unicode не из латиницы, для отражения обработки международного неанглийского теста. Я выбрал item_flavor_text.csv из датасета Veekun pokedex, содержащий имена и описания всех предметов из всех игр Pokemon.

  • Финансовые данные с большим количеством чисел и малым объёмом текста. Я выбрал данные exelbianalytics, потому что они отвечают этому требованию и к тому же использовались в бенчмарке MarkPflug/Benchmarks.

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

  • Файл с четырьмя столбцами и числами от 0 до 2000 в каждом поле в качестве точки отсчёта.

  • То же самое, но очень короткий, длиной 50 строк, чтобы мы могли протестировать общий оверхед каждой библиотеки.

  • Ещё один похожий файл, но с числами, обёрнутыми в кавычки, чтобы проверить, будут ли какие-нибудь изменения в производительности, если каждое поле закавычено.

  • И, наконец, очень сложный для парсинга CSV-файл с огромным количеством кавычек и других структурных символов, который поставит на колени любой парсер. 

В конечном итоге я всё это собрал, несколько раз прогнал тесты и опубликовал результаты: https://bepis.io/csv-benchmark/

Если вкратце: моя библиотека оказалась самой быстрой в 41 из 70 тестов. Не абсолютный победитель, но она над той планкой, выше которой, как мне кажется, находятся лидеры.

Почему мой парсер в большинстве бенчмарков оказался быстрее Sep

Может быть, вы не знаете, но раньше самым быстрым CSV-парсером на C# считался Sep. Как мой парсер победил его в таком количестве сценариев?

В процессе его совершенствования у меня было несколько идей, но чем дольше я тестировал и экспериментировал, тем меньше понимал. У меня есть лишь несколько теорий:

UTF-8

Гораздо быстрее обрабатывать данные в UTF-8, чем в UTF-16, поэтому некоторые бенчмарки в результате этого искажают показатели в пользу моей библиотеки. В Sep нет кода для работы с данными UTF-8; внутри она сначала выполняет преобразование в UTF-16, то есть ей приходится тратить время и энергию на эти преобразования, даже если пользователь в конечном итоге не хочет использовать данные.

Давление на кэш

В чипы CPU встроена собственная память, называющаяся кэшами L1/L2/L3. При такой быстрой обработке данных чем ближе память к CPU, тем лучше, поэтому в идеале в этих кэшах должно храниться как можно больше данных.

Однако эти кэши крайне малы: кэш L1 имеет размер 32-64 КБ на одно ядро CPU. Кроме того, эта память предназначается не только для данных, но и для исполняемого кода. Поэтому если у нас есть достаточно большой горячий цикл, то он может создать высокое давление на этот кэш или даже вызвать его переполнение.

Моя библиотека имеет размер примерно 16 КБ, в то время как Sep почти в 10 раз больше (163 КБ). Из-за этого в кэше L1 остаётся меньше места для передачи по конвейеру данных CSV и происходит гораздо больше операций доступа вне кэша.

Чрезмерная оптимизация

При работе над этой библиотекой я не хотел изучать реализации других библиотек, потому что иначе не мог бы получить удовольствие от внесения оптимизаций. Однако для написания этого раздела я изучил Sep и, похоже, могу показать одну область, в которой возникают проблемы.

Файл, который ближе всего к нашему циклу обработки, находится здесь: https://github.com/nietras/Sep/blob/main/src/Sep/Internals/SepParserAvx2PackCmpOrMoveMaskTzcnt.cs. Он гораздо более длинно и подробно объясняет, как нужно перемещать данные в CPU и в памяти. Теоретически это быстрее, потому что мы выполняем микро-оптимизацию каждого аспекта, но в двух случаях может привести к проблемам:

  • Можно очень легко зайти в локальный минимум, при котором другой путь быстрее, но мы не видим его, потому что гора слишком высока, чтобы дойти до более оптимального пути при микробенчмаркинге.

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

Наши компиляторы и машины — не тупые строительные блоки, просто преобразующие код и слепо исполняющие команды, как это было больше двадцати лет назад. Если они знают, что могут ускорить код, не вызывая проблем, то они сделают это. Особенно если при этом будет казаться, что CPU быстрее, чем на самом деле. Например, фиаско Spectre и Meltdown было вызвано тем, что CPU пытался оптимизировать ветвления, не выполняя при этом санацию получающихся данных.

Верно это и на стороне ПО: каждый раз, когда выходит новая версия .NET, мне нравится читать информацию об изменениях в среде исполнения и узнавать о новых оптимизациях. Эти оптимизации происходят внутри среды исполнения, поэтому разработчики получают выгоду, даже ничего не делая, но только в случае, если среда может понять, что вы хотите сделать, и не особо беспокоится о том, как это будет сделано.

Поэтому необходим баланс между объяснениями компилятору, что вы хотите сделать, и объяснениями, как вы хотите это сделать. Да, возникает желание запланировать и подробно описать всё, что вы хотите оптимизировать в коде, но если есть платформа или ситуация, в которой лучше выполнять это как-то ещё, или даже если более новая версия среды исполнения может ускорить определённый паттерн, её руки связаны, потому что вы заставляете её поступать определённым образом.

Оборудование

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

Могу привести пример: изначально в моём коде использовался Sse.Prefetch0, чтобы сообщать CPU, что я собираюсь сканировать блок данных; благодаря этому он заранее подготавливал эти данные в кэше L1. На моём ноутбуке с DDR3 высокие задержки памяти, поэтому это увеличивало скорости на 10-20%. Однако на моём гораздо более быстром десктопе с DDR5 разницы практически не было.

При всём при этому должен сказать, что существуют платформы, на которых Sep в любом случае будет быстрее моей библиотеки, особенно в системах AVX-512 и ARM, для которых у неё есть аппаратная оптимизация. Я не могу реализовать их сам, потому что у меня нет этих машин для тестирования.

Эпилог

Если вы хотите сами пользоваться библиотекой и изучить её код, то её можно найти здесь:

https://github.com/bbepis/FourLambda.Csv

Спасибо за прочтение моей статьи! Я планирую выпускать больше подобных библиотек; сейчас я продолжаю работать над библиотекой для JSON-парсинга и ещё над одной, которую я улучшаю для кода Рида — Соломона.

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