Qual è il modo più veloce per scorrere i singoli caratteri in una stringa in C#?

Question

Il titolo è la domanda. Di seguito è il mio tentativo di rispondere attraverso la ricerca. Ma non mi fido delle mie ricerche disinformate, quindi pongo ancora la domanda (qual è il modo più veloce per scorrere i singoli caratteri in una stringa in C#?).

Occasionalmente, desidero scorrere i caratteri di una stringa uno alla volta, ad esempio durante l'analisi di token annidati, cosa che è cannot be done with regular expressions. Mi chiedo quale sia il modo più veloce per scorrere i singoli caratteri di una stringa, in particolare stringhe molto grandi.

Ho fatto un po 'di test me stesso ei miei risultati sono sotto. Tuttavia ci sono molti lettori con una conoscenza molto più approfondita del compilatore .NET CLR e C# quindi non so se mi manca qualcosa di ovvio, o se ho fatto un errore nel mio codice di test. Quindi sollecito la tua risposta collettiva. Se qualcuno ha un'idea di come funziona realmente l'indicizzatore di stringhe, sarebbe molto utile. (È una caratteristica del linguaggio C# compilata in qualcos'altro dietro le quinte o qualcosa di integrato nel CLR?).

Il primo metodo che utilizza un flusso è stata presa direttamente dalla risposta accettata dal thread: how to generate a stream from a string?

Test

longString è una stringa di 99,1 milioni di caratteri composto di 89 copie della versione di solo testo delle specifiche del linguaggio C#. I risultati mostrati sono per 20 iterazioni. Dove c'è un tempo di "avvio" (come per la prima iterazione dell'array implicitamente creato nel metodo # 3), l'ho testato separatamente, ad esempio interrompendo il ciclo dopo la prima iterazione.

Risultati

Dalle mie prove, la memorizzazione nella cache la stringa in un array di caratteri utilizzando il metodo ToCharArray() è il più veloce per iterare su l'intera stringa. Il metodo ToCharArray() è una spesa anticipata e il successivo accesso ai singoli caratteri è leggermente più rapido dell'accessorio incorporato nell'indice.

          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 

Aggiornamento: Per @ commento di Eric, ecco i risultati per 100 iterazioni su una più normale 1.1 M stringa char (una copia del C# spec). Gli indicizzatori e gli array di char sono ancora più veloci, seguiti da foreach (char in string), seguiti dai metodi di streaming.

          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  

codice usato (testato separatamente; mostrato insieme per brevità)

//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) { } 

risposta accettata:

ho interpretato @CodeInChaos e le note di Ben come segue:

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

Esecuzione per 100 iterazioni sul corto la stringa era di 4,4 ms, con < 0,1 ms st dev.

Answer 1

La risposta più veloce è quello di utilizzare C++/CLI: How to: Access Characters in a System::String

Questo approccio consente di scorrere i caratteri sul posto nella stringa utilizzando l'aritmetica dei puntatori . Non ci sono copie, assegni di intervallo impliciti e chiamate di funzioni per elemento.

È probabile che sia possibile ottenere (quasi, C++/CLI non richiede il blocco) le stesse prestazioni di C# scrivendo una versione C# non sicura di PtrToStringChars.

Qualcosa di simile:

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

ricordo di chiamare GCHandle.Free dopo.

commento di CodeInChaos sottolinea che C# fornisce uno zucchero sintattico per questo:

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

Answer 2

Qualsiasi motivo per non includere foreach?

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

È questo davvero sarà il vostro collo di bottiglia, a proposito? Qual è la proporzione del tempo totale di esecuzione che fa l'iterazione stessa?

Answer 3

Se la velocità è importante for è più veloce di foreach

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

Answer 4

Questo tipo di test artificiali sono piuttosto pericoloso. Notevole è che le tue // 2 e // 3 versioni del codice non indicizzano mai effettivamente la stringa. Il jitter optimizer getta via il codice dato che la variabile c non viene utilizzata affatto. Stai solo misurando quanto dura il ciclo for(). Non puoi davvero vederlo a meno che non guardi il codice macchina generato.

Sostituirlo con c += longString[i]; per forzare l'uso dell'indicizzatore di array.

Ovviamente è assurdo. Solo profilo codice reale.

Answer 5

Se la micro ottimizzazione è molto importante per te, prova questo. (Ho assunto la lunghezza della stringa di input per essere multiplo di 8 per semplicità)

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

Sto scherzando, non usare mai questo codice :)

Answer 6

TL; DR: un semplice foreach è il modo più veloce per iterare una stringa .

Per le persone che ritornano a questo: i tempi cambiano!

Con l'ultimo .NET JIT a 64 bit, la versione non sicura è effettivamente la più lenta.

Di seguito è riportata un'implementazione di benchmark per BenchmarkDotNet. Da questi, ho ottenuto i seguenti risultati:

  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 | 

I più interessanti sono quelli che non funzionano su una copia in serie.Questo dimostra che l'indicizzazione e foreach sono molto simili nelle prestazioni, con una differenza del 5%, foreach essendo più veloce. L'utilizzo di unsafe è in realtà del 28% più lento rispetto all'utilizzo di foreach.

In passato unsafe potrebbe essere stata l'opzione più veloce, ma JIT è sempre più veloce e più intelligente.

Come riferimento, il codice di riferimento:

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

Il codice ha alcune piccole variazioni rispetto al codice offerto. I caratteri che vengono recuperati dalla stringa originale sono | -ed con la variabile che viene restituita e restituiamo il valore. La ragione di ciò è che dobbiamo effettivamente fare qualcosa con il risultato. In caso contrario, se avessimo solo essere iterare sulla stringa del tipo:

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

JIT è libero di rimuovere questo perché potrebbe dedurre che non si è in realtà osservando i risultati del iterazione. Con | -anciando i caratteri nella matrice e restituendo ciò, BenchmarkDotNet si assicurerà che il JIT non possa eseguire questa ottimizzazione.