¿Por qué las expresiones regulares compiladas de C# son más rápidas que los métodos de cadenas equivalentes?

Question

Cada vez que tengo que realizar operaciones simples de contención o reemplazo en strings, donde el término que estoy buscando es un valor fijo, me parece que si tomo mi entrada de muestra y hago algún perfil sobre ella, usando un compilado regular la expresión es casi * siempre más rápida que usar el método equivalente de la clase String.

He intentado comparar una variedad de métodos (. hs es el "pajar" para buscar, ndl es la "aguja" para buscar, repl es el valor de reposición regex siempre se crea con la opción RegexOptions.Compiled):

• hs.Replace(ndl, repl) vs regex.Replace(hs, repl)
• hs.Contains(ndl) vs regex.IsMatch(hs)

tengo se encuentran bastantes discusiones centradas en cuales de las dos técnicas son más rápidas (1, 2, 3, y un montón de otros), pero esas discusiones siempre parecen centrarse en:

1. Utilice la versión de cadena para simples operaciones y expresiones regulares para operaciones complejas (que, desde una perspectiva de rendimiento en bruto, ni siquiera parece ser una buena idea), o
2. Ejecute una prueba y compare los dos (y para pruebas equivalentes, la versión de expresiones regulares parece siempre funciona mejor).

No entiendo cómo puede ser este el caso: ¿cómo compara el motor de expresiones regex dos cadenas para las cadenas de subcadenas más rápido que la versión de cadena equivalente? Esto parece ser cierto para los espacios de búsqueda que son muy pequeños o muy grandes, o los términos de búsqueda que son pequeños o grandes, o si el término de búsqueda ocurre temprano o tarde en el espacio de búsqueda.

Entonces, ¿por qué son expresiones regulares más rápidas?

---

* De hecho, la única caso se ha logrado demostrar que la versión de cadena es más rápido que una expresión regular compilada está en la búsqueda de una cadena vacía! Cualquier otro caso, desde cadenas de caracteres individuales hasta cadenas muy largas, se procesa más rápido mediante una expresión regular compilada que con el método de cadena equivalente.

---

Actualización: añadido una cláusula para aclarar que estoy mirando a los casos en que el término de búsqueda se conoce en tiempo de compilación. Para operaciones dinámicas o de una sola vez, la sobrecarga de compilar la expresión regular tenderá a sesgar los resultados a favor de los métodos de cadena.

Answer 1

No entiendo cómo puede ser este el caso: ¿cómo compara el motor de expresiones regex dos cadenas para las coincidencias de subcadenas más rápido que la versión de cadena equivalente?

puedo pensar en dos razones:

1. la expresión regular está utilizando algún algoritmo inteligente como Boyer Moore (O (M/N)), mientras que la operación de cadena sencilla simplemente compara la aguja para cada posición en la pajar (O (N * M)).
2. No están haciendo exactamente lo mismo. Por ejemplo, uno podría hacer coincidir invariante con la cultura mientras que el otro haría emparejamiento dependiente de la cultura, lo que podría hacer una diferencia en el rendimiento.

Answer 2

medida que el equipo de biblioteca de clases base wrote:

En [el caso de RegexOptions.Compiled], lo primero que hacen el trabajo de analizar en códigos de operación. Entonces también hacemos más trabajo para convertir esos códigos de operación en IL real usando Reflection.Emit.Como se puede imaginar, este modo opera , un tiempo de inicio aumentado para un tiempo de ejecución más rápido: en la práctica, la compilación tarda aproximadamente un orden de magnitud más en arrancar, pero rinde un 30% mejor rendimiento en tiempo de ejecución.

Pero, estás overloking una cosa importante: patrón se fija. Tenga en cuenta que este no es siempre el caso. ¡No puedes cambiarlo en tiempo de ejecución! Habrá casos en que la flexibilidad disminuirá por más del 30% de la ganancia de rendimiento.

Answer 3

Desde mi propia experiencia, cada vez que comparé las soluciones regex con los analizadores personalizados con operaciones de cadena simples, la solución de expresiones regulares es un poco más lenta. Eso es porque a menudo sufren retrocesos.

Pero por curiosidad escribí una pequeña prueba para ver si lo que dices es verdad en los ejemplos más simples.

Aquí está mi prueba ...

private static Regex RegexSearch = new Regex("Audi A4", RegexOptions.Compiled); 

    static void Main(string[] args) 
    {    
     // warm up the JIT compiler 
     FoundWithRegexIsMatch(); 
     FoundWithStringContains(); 
     FoundWithStringIndexOf(); 
     // done warming up 

     int iterations = 100; 
     var sw = new Stopwatch(); 

     sw.Restart(); 
     for (int i = 0; i < iterations; i++) 
     { 
      FoundWithRegexIsMatch(); 
     } 
     sw.Stop(); 
     Console.WriteLine("Regex.IsMatch: " + sw.ElapsedMilliseconds + " ms"); 


     sw.Restart(); 
     for (int i = 0; i < iterations; i++) 
     { 
      FoundWithStringIndexOf(); 
     } 
     sw.Stop(); 
     Console.WriteLine("String.IndexOf: " + sw.ElapsedMilliseconds + " ms"); 


     sw.Restart(); 
     for (int i = 0; i < iterations; i++) 
     { 
      FoundWithStringContains(); 
     } 
     sw.Stop(); 
     Console.WriteLine("String.Contains: " + sw.ElapsedMilliseconds + " ms"); 
    } 

    private static bool FoundWithStringContains() 
    { 
     return Resource2.csv.Contains("Audi A4"); 
    } 

    private static bool FoundWithStringIndexOf() 
    { 
     return Resource2.csv.IndexOf("Audi A4") >= 0; 
    } 

    private static bool FoundWithRegexIsMatch() 
    { 
     return RegexSearch.IsMatch(Resource2.csv); 
    } 

estoy probando con un archivo CSV que tengo que es de aproximadamente 1,2 MB. Y aquí están los resultados:

• Regex.IsMatch: 172 ms
• String.indexOf: 172 ms
• String.Contains: 185 ms

De hecho estás en lo correcto. Cuando no está haciendo nada sofisticado en la expresión regular, la expresión regular es un poco más rápida que una operación String.Contains. Sin embargo, encontré que hay un tiny bit of overhead in String.Contains y llamar al String.IndexOf es más rápido y en realidad coincide con el tiempo de Regex.IsMatch al milisegundo.

Estos tiempos idénticos son sospechosos. Me pregunto si durante la compilación se determina que esto realmente no necesita pasar por el motor Regex (ya que no hay instrucciones específicas de expresiones regulares en el patrón que utilicé anteriormente). En su lugar, se puede simplificar para que Regex.IsMatch haga la misma llamada a FindNLSString desde kernel32.dll como IndexOf. Eso es solo una suposición.