Какой самый быстрый способ перебора отдельных символов в строке в C #?

Question

Название вопроса. Ниже моя попытка ответить на это через исследование. Но я не доверяю своим неинформированным исследованиям, поэтому я все еще задаю вопрос (Какой самый быстрый способ перебрать отдельные символы в строке в C #?).

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

Я сам провел несколько испытаний, и мои результаты приведены ниже. Однако, есть много читателей с гораздо более глубокими знаниями компилятора .NET CLR и C #, поэтому я не знаю, упустил ли я что-то очевидное или допустил ошибку в своем тестовом коде. Поэтому я прошу ваш коллективный ответ. Если у кого-то есть понимание того, как на самом деле работает индексатор строк, это было бы очень полезно. (Это функция языка C #, скомпилированная во что-то другое за кулисами? Или что-то встроенное в CLR?).

Первый метод, использующий поток, был взят непосредственно из принятого ответа от потока: как генерировать поток из строки?

Тесты

longString - строка длиной 99,1 миллиона символов, состоящая из 89 копий текстовой версии спецификации языка C # в виде простого текста. Результаты показаны за 20 итераций. Там, где есть время запуска (например, для первой итерации неявно созданного массива в методе № 3), я тестировал это отдельно, например, прерывая цикл после первой итерации.

Результаты

Из моих тестов кэширование строки в массиве char с использованием метода ToCharArray () является самым быстрым для итерации по всей строке. Метод ToCharArray () является предоплатным, и последующий доступ к отдельным символам несколько быстрее, чем встроенный индексатор.

                                           milliseconds
                                ---------------------------------
 Method                         Startup  Iteration  Total  StdDev
------------------------------  -------  ---------  -----  ------
 1 index accessor                     0        602    602       3
 2 explicit convert ToCharArray     165        410    582       3
 3 foreach (c in string.ToCharArray)168        455    623       3
 4 StringReader                       0       1150   1150      25
 5 StreamWriter => Stream           405       1940   2345      20
 6 GetBytes() => StreamReader       385       2065   2450      35
 7 GetBytes() => BinaryReader       385       5465   5850      80
 8 foreach (c in string)              0        960    960       4

Обновление: В соответствии с комментарием Эрика, здесь приведены результаты для 100 итераций по более обычной 1,1-миллиметровой строке символов (одна копия спецификации C #). Индексатор и массив символов по-прежнему самые быстрые, за ними следует foreach (char в строке), а затем потоковые методы.

                                           milliseconds
                                ---------------------------------
 Method                         Startup  Iteration  Total  StdDev
------------------------------  -------  ---------  -----  ------
 1 index accessor                     0        6.6    6.6    0.11
 2 explicit convert ToCharArray     2.4        5.0    7.4    0.30
 3 for(c in string.ToCharArray)     2.4        4.7    7.1    0.33
 4 StringReader                       0       14.0   14.0    1.21
 5 StreamWriter => Stream           5.3       21.8   27.1    0.46
 6 GetBytes() => StreamReader       4.4       23.6   28.0    0.65
 7 GetBytes() => BinaryReader       5.0       61.8   66.8    0.79
 8 foreach (c in string)              0       10.3   10.3    0.11     

Используемый код (проверено отдельно; для краткости показано вместе)

//1 index accessor
int strLength = longString.Length;
for (int i = 0; i < strLength; i++) { c = longString[i]; }

//2 explicit convert ToCharArray
int strLength = longString.Length;
char[] charArray = longString.ToCharArray();
for (int i = 0; i < strLength; i++) { c = charArray[i]; }

//3 for(c in string.ToCharArray)
foreach (char c in longString.ToCharArray()) { } 

//4 use StringReader
int strLength = longString.Length;
StringReader sr = new StringReader(longString);
for (int i = 0; i < strLength; i++) { c = Convert.ToChar(sr.Read()); }

//5 StreamWriter => StreamReader 
int strLength = longString.Length;
MemoryStream stream = new MemoryStream();
StreamWriter writer = new StreamWriter(stream);
writer.Write(longString);
writer.Flush();
stream.Position = 0;
StreamReader str = new StreamReader(stream);
while (stream.Position < strLength) { c = Convert.ToChar(str.Read()); } 

//6 GetBytes() => StreamReader
int strLength = longString.Length;
MemoryStream stream = new MemoryStream(Encoding.Unicode.GetBytes(longString));
StreamReader str = new StreamReader(stream);
while (stream.Position < strLength) { c = Convert.ToChar(str.Read()); }

//7 GetBytes() => BinaryReader 
int strLength = longString.Length;
MemoryStream stream = new MemoryStream(Encoding.Unicode.GetBytes(longString));
BinaryReader br = new BinaryReader(stream, Encoding.Unicode);
while (stream.Position < strLength) { c = br.ReadChar(); }

//8 foreach (c in string)
foreach (char c in longString) { } 

Принятый ответ:

Я интерпретировал записи @CodeInChaos и Бена следующим образом:

fixed (char* pString = longString) {
    char* pChar = pString;
    for (int i = 0; i < strLength; i++) {
        c = *pChar ;
        pChar++;
    }
}

Выполнение за 100 итераций по короткой строке составило 4,4 мс, с <0,1 мсек. Дев. </p>

Answer 1

Любая причина не включать foreach?

foreach (char c in text)
{
    ...
}

Кстати, действительно ли это станет вашим узким местом в производительности?Какую долю от общего времени выполнения занимает сама итерация?

Answer 2

Подобные искусственные тесты довольно опасны. Примечательно, что ваши версии кода // 2 и // 3 никогда не индексируют строку. Оптимизатор джиттера просто выбрасывает код, поскольку переменная c вообще не используется. Вы просто измеряете, сколько времени занимает цикл for (). Вы не сможете увидеть это, если не посмотрите на сгенерированный машинный код.

Измените его на c += longString[i];, чтобы использовать индексатор массива.

Что, конечно, глупость. Только профиль реальный код.

Answer 3

Самый быстрый ответ - использовать C ++ / CLI: Как: получить доступ к символам в системе :: String

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

Вероятно, можно получить (почти что C ++ / CLI не требует закрепления) ту же производительность от C #, написав небезопасную версию C # PtrToStringChars.

Что-то вроде:

unsafe char* PtrToStringContent(string s, out GCHandle pin)
{
    pin = GCHandle.Alloc(s, GCHandleType.Pinned);
    return (char*)pin.AddrOfPinnedObject().Add(System.Runtime.CompilerServices.RuntimeHelpers.OffsetToStringData).ToPointer();
}

Не забудьте позвонить GCHandle.Free впоследствии.

Комментарий CodeInChaos указывает, что C # предоставляет синтаксический сахар для этого:

fixed(char* pch = s) { ... }

Answer 4

TL; DR: простой foreach - это самый быстрый способ перебора строки.

Для людей, возвращающихся к этому: времена меняются!

С последней 64-битной JIT .NET небезопасная версия на самом деле самая медленная.

Ниже приведена сравнительная реализация BenchmarkDotNet. Из них я получил следующие результаты:

          Method |      Mean |     Error |    StdDev |
---------------- |----------:|----------:|----------:|
        Indexing | 5.9712 us | 0.8738 us | 0.3116 us |
 IndexingOnArray | 8.2907 us | 0.8208 us | 0.2927 us |
  ForEachOnArray | 8.1919 us | 0.6505 us | 0.1690 us |
         ForEach | 5.6946 us | 0.0648 us | 0.0231 us |
          Unsafe | 7.2952 us | 1.1050 us | 0.3941 us |

Интересными являются те, которые не работают с копией массива. Это показывает, что индексирование и foreach очень похожи по производительности, с разницей в 5%, foreach быстрее . Использование unsafe на самом деле на 28% медленнее, чем использование foreach.

В прошлом unsafe, возможно, был самым быстрым вариантом, но JIT все быстрее и умнее.

Для справки, код теста:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Configs;
using BenchmarkDotNet.Horology;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

namespace StringIterationBenchmark
{
    public class StringIteration
    {
        public static void Main(string[] args)
        {
            var config = new ManualConfig();

            config.Add(DefaultConfig.Instance);

            config.Add(Job.Default
                .WithLaunchCount(1)
                .WithIterationTime(TimeInterval.FromMilliseconds(500))
                .WithWarmupCount(3)
                .WithTargetCount(6)
            );

            BenchmarkRunner.Run<StringIteration>(config);
        }

        private readonly string _longString = BuildLongString();

        private static string BuildLongString()
        {
            var sb = new StringBuilder();
            var random = new Random();

            while (sb.Length < 10000)
            {
                char c = (char)random.Next(char.MaxValue);
                if (!Char.IsControl(c))
                    sb.Append(c);
            }

            return sb.ToString();
        }

        [Benchmark]
        public char Indexing()
        {
            char c = '\0';
            var longString = _longString;
            int strLength = longString.Length;

            for (int i = 0; i < strLength; i++)
            {
                c |= longString[i];
            }

            return c;
        }

        [Benchmark]
        public char IndexingOnArray()
        {
            char c = '\0';
            var longString = _longString;
            int strLength = longString.Length;
            char[] charArray = longString.ToCharArray();

            for (int i = 0; i < strLength; i++)
            {
                c |= charArray[i];
            }

            return c;
        }

        [Benchmark]
        public char ForEachOnArray()
        {
            char c = '\0';
            var longString = _longString;

            foreach (char item in longString.ToCharArray())
            {
                c |= item;
            }

            return c;
        }

        [Benchmark]
        public char ForEach()
        {
            char c = '\0';
            var longString = _longString;

            foreach (char item in longString)
            {
                c |= item;
            }

            return c;
        }

        [Benchmark]
        public unsafe char Unsafe()
        {
            char c = '\0';
            var longString = _longString;
            int strLength = longString.Length;

            fixed (char* p = longString)
            {
                var p1 = p;

                for (int i = 0; i < strLength; i++)
                {
                    c |= *p1;
                    p1++;
                }
            }

            return c;
        }
    }
}

В коде есть несколько незначительных изменений по сравнению с предложенным кодом. Символы, полученные из исходной строки, | -ed с возвращаемой переменной, и мы возвращаем значение. Причина этого в том, что нам действительно нужно что-то делать с результатом. Иначе, если бы мы просто перебирали строку вроде:

//8 foreach (c in string)
foreach (char c in longString) { } 

JIT может удалить это, поскольку это может означать, что вы фактически не наблюдаете результаты итерации. | -символяя символы в массиве и возвращая его, BenchmarkDotNet убедится, что JIT не может выполнить эту оптимизацию.

Answer 5

Если микрооптимизация очень важна для вас, попробуйте это.(Я предположил, что длина входной строки кратна 8 для простоты)

unsafe void LoopString()
{
    fixed (char* p = longString)
    {
        char c1,c2,c3,c4;
        Int64 len = longString.Length;
        Int64* lptr = (Int64*)p;
        Int64 l;
        for (int i = 0; i < len; i+=8)
        {
            l = *lptr;
            c1 = (char)(l & 0xffff);
            c2 = (char)(l >> 16);
            c3 = (char)(l >> 32);
            c4 = (char)(l >> 48);
            lptr++;
        }
    }
}

Шучу, никогда не используйте этот код:)

Answer 6

Если скорость действительно имеет значение, for быстрее, чем foreach

for (int i = 0; i < text.Length; i++) {
   char ch = text[i];
   ...
}