solo - javascript regex test

¿Por qué agregar una alternativa más hace que mi expresión regular sea 600 veces más lenta?

Question

Me di cuenta de algo raro mientras probaba un simple script de Perl que se supone que filtra los nombres de archivo que comienzan con ciertos prefijos.

Básicamente, estoy construyendo una expresión regular como esta:

my $regex = join "|", map quotemeta, @prefixes;
$regex = qr/^($regex)/;   # anchor the regex and precompile it

Aquí, en el escenario que probé originalmente, @prefixes consta de cadenas hexadecimales de 32 caracteres. Lo que encontré es que todo funcionó bien y sin problemas hasta 6,552 prefijos, pero tan pronto como probé 6,553, el tiempo de ejecución de la secuencia de comandos aumentó en un factor de más de 25 (de 1,8 segundos a 51 segundos).

Jugué con eso y construí el siguiente punto de referencia. Originalmente utilicé cadenas hexagonales de 32 caracteres, como en mi programa original, pero descubrí que si reduje la longitud de las cuerdas a solo 8 caracteres, el valor umbral se movió más alto, a 16,383, de hecho, mientras el factor de desaceleración aumentó drásticamente. más alto aún: ¡la expresión regular con 16,383 alternativas es casi 650 veces más lenta que la que tiene solo 16,382!

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(timethese cmpthese);

my $count = shift || 10;

our @items = map unpack("H8", pack "V", $_), 0..99999;

our $nA = 16382; our $reA = join "|", @items[1 .. $nA];
our $nB = 16383; our $reB = join "|", @items[1 .. $nB];

$_ = qr/^($_)/ for $reA, $reB;  # anchor and compile regex

my $results = timethese( $count, {
    $nA => q{ our (@items, $nA, $reA); $nA == grep /$reA/, @items or die; },
    $nB => q{ our (@items, $nB, $reB); $nB == grep /$reB/, @items or die; },
} );
cmpthese( $results );

Aquí están los resultados de ejecutar este benchmark en mi computadora portátil, usando Perl (v5.18.2):

Benchmark: timing 10 iterations of 16382, 16383...
     16382:  2 wallclock secs ( 1.79 usr +  0.00 sys =  1.79 CPU) @  5.59/s (n=10)
     16383: 1163 wallclock secs (1157.28 usr +  2.70 sys = 1159.98 CPU) @  0.01/s (n=10)
      s/iter  16383  16382
16383    116     --  -100%
16382  0.179 64703%     --

Tenga en cuenta la diferencia de velocidad del 64,703%.

Mi corazonada original, basada en la coincidencia numérica de 6553 ≈ 2 16/10, era que esto podría haber sido algún tipo de límite arbitrario dentro del motor de expresiones regulares de Perl, o tal vez que podría haber algún tipo de matriz de 10 -Estructuras de bytes limitadas a 64 kB o algo así. Pero el hecho de que el número mínimo de alternativas depende de su longitud hace que las cosas sean más confusas.

(Por otro lado, claramente no solo se trata de la longitud de la expresión regular, la expresión regular original con 6,553 alternativas de 32 bytes fue 2 + 6,553 × 33 = 216,251 bytes de largo, mientras que la que tiene 16,383 alternativas de 8 bytes es solo 2 + 16,383 × 9 = 147,450 bytes de largo)

¿Qué está causando este extraño salto en el tiempo de coincidencia de expresiones regulares, y por qué sucede en ese punto específico?

Answer 1

Durante mucho tiempo, la optimización TRIE de perl no se aplicó cuando la compilación inicial de la expresión regular produce instrucciones longjmp en lugar de jmp (creo) (que depende del número de alternancias y las longitudes totales de las cadenas involucradas y qué más es ( anteriormente?) en la expresión regular).

Vea la diferencia entre:

perl -we''use re "debug"; qr/@{[join"|","a".."afhd"]}/''

y

perl -we''use re "debug"; qr/@{[join"|","a".."afhe"]}/''

Puede dividir su alternancia en trozos más pequeños y precompilarlos por separado y hacer, por ejemplo, (??{$rxa})|(??{$rxb})|(??{$rxc}) .