php - subcadena - ¿Por qué mb_strpos() es considerablemente más lento que strpos()?
si existe una cadena dentro de otra php (4)
Razón de la lentitud
Echando un vistazo a los archivos fuente PHP 5.5.6, el retraso parece surgir en su mayor parte en mbfilter.c , donde, como hakre supuso , tanto el pajar como la aguja deben validarse y convertirse, cada vez que mb_strpos (o, Supongo que la mayoría de la familia mb_* se llama:
A menos que el pajar esté en el formato predeterminado, codifíquelo al formato predeterminado :
if (haystack->no_encoding != mbfl_no_encoding_utf8) {
mbfl_string_init(&_haystack_u8);
haystack_u8 = mbfl_convert_encoding(haystack, &_haystack_u8, mbfl_no_encoding_utf8);
if (haystack_u8 == NULL) {
result = -4;
goto out;
}
} else {
haystack_u8 = haystack;
}
A menos que la aguja esté en el formato predeterminado, codifíquelo al formato predeterminado :
if (needle->no_encoding != mbfl_no_encoding_utf8) {
mbfl_string_init(&_needle_u8);
needle_u8 = mbfl_convert_encoding(needle, &_needle_u8, mbfl_no_encoding_utf8);
if (needle_u8 == NULL) {
result = -4;
goto out;
}
} else {
needle_u8 = needle;
}
De acuerdo con una verificación rápida con valgrind , la conversión de codificación representa una gran parte del tiempo de ejecución de mb_strpos , aproximadamente el 84% del total, o cinco sextos:
218,552,085 ext/mbstring/libmbfl/mbfl/mbfilter.c:mbfl_strpos [/usr/src/php-5.5.6/sapi/cli/php]
183,812,085 ext/mbstring/libmbfl/mbfl/mbfilter.c:mbfl_convert_encoding [/usr/src/php-5.5.6/sapi/cli/php]
que parece ser consistente con los tiempos del OP de mb_strpos versus strpos .
La codificación no se considera, mb_strpos una cadena es exactamente igual a la de un string un poco más largo . De acuerdo, una cadena de hasta cuatro veces más larga si tiene cadenas realmente incómodas, pero incluso así, obtendría un retraso por un factor de cuatro, no por un factor de veinte. La ralentización adicional de 5-6X surge de los tiempos de codificación.
Acelerando mb_strpos ...
¿Entonces que puedes hacer? Puede omitir esos dos pasos asegurándose de tener internamente las cadenas en el formato "básico" en el que mbfl* do conversion and compare, que es mbfl_no_encoding_utf8 (UTF-8):
- Mantenga sus datos en UTF-8.
- Convierta la entrada del usuario a UTF-8 tan pronto como sea práctico.
- Convertir, si es necesario, volver a la codificación del cliente si es necesario.
Entonces su pseudo-código:
$haystack = "...";
$needle = "...";
$res = mb_strpos($haystack, $needle, 0, $Encoding);
se convierte en:
$haystack = "...";
$needle = "...";
mb_internal_encoding(''UTF-8'') or die("Cannot set encoding");
$haystack = mb_convert_encoding($haystack, ''UTF-8'' [, $SourceEncoding]);
$needle = mb_convert_encoding($needle, ''UTF-8'', [, $SourceEncoding]);
$res = mb_strpos($haystack, $needle, 0);
... cuando vale la pena
Por supuesto, esto solo es conveniente si el "tiempo de configuración" y el mantenimiento de una base UTF-8 completa son considerablemente menores que el "tiempo de ejecución" de realizar conversiones implícitamente en cada función mb_* .
He criticado una respuesta que sugiere preg_match over === al encontrar las compensaciones de subcadenas para evitar la falta de coincidencia de tipos.
Sin embargo, más tarde, el autor de la respuesta descubrió que preg_match es en realidad significativamente más rápido que mb_strpos operación de múltiples bytes. Los strpos normales son más rápidos que las dos funciones, pero, por supuesto, no pueden manejar cadenas multibyte.
Entiendo que mb_strpos necesita hacer algo más que strpos . Sin embargo, si regex puede hacerlo casi tan rápido como strpos , ¿qué es lo que mb_strpos hace que toma tanto tiempo?
Tengo una fuerte sospecha de que es un error de optimización. ¿Podrían, por ejemplo, las extensiones de PHP ser más lentas que sus funciones nativas?
mb_strpos($str, "颜色", 0 ,"GBK"): 15.988190889 (89%)
preg_match("/颜色/", $str): 1.022506952 (6%)
strpos($str, "dh"): 0.934401989 (5%)
Las funciones se ejecutaron 10 6 veces. El tiempo (s) absoluto (s) representa la suma del tiempo de 10 6 ejecuciones de una función, en lugar del promedio para una.
La cadena de prueba es $str = "代码dhgd颜色代码"; . La prueba se puede ver aquí (desplácese hacia abajo para omitir la clase de prueba).
Nota: De acuerdo con uno de los comentaristas (y el sentido común), preg_match tampoco usa multi-byte cuando se compara, ya que está sujeto al mismo riesgo de errores que los strpos .
Los problemas con el rendimiento de mb_ pueden ser causados por la instalación de un paquete php-mbstring desordenado (en un linux). Instalarlo explícitamente para la versión exacta de la instalación de php me ayudó.
sudo apt-get install php7.1-mbstring
...
Before: Time: 16.17 seconds, Memory: 36.00MB OK (3093 tests, 40272 assertions)
After: Time: 1.81 seconds, Memory: 36.00MB OK (3093 tests, 40272 assertions)
Para comprender por qué las funciones tienen un tiempo de ejecución diferente, debe comprender lo que realmente hacen. Porque resumirlos como "buscan una aguja en un pajar " no es suficiente.
strpos
Si nos fijamos en la implementación de strpos , usa zend_memstr internamente , lo que implementa un algoritmo bastante ingenuo para buscar la aguja en el pajar : básicamente, usa memchr para encontrar el primer byte de la aguja en el pajar y luego usa memcmp para verificar si todo La aguja comienza en esa posición. Si no, repite la búsqueda del primer byte de la aguja desde la posición de la coincidencia anterior del primer byte.
Sabiendo esto, podemos decir que strpos solo busca una secuencia de bytes en una secuencia de bytes usando un algoritmo de búsqueda ingenuo.
mb_strpos
Esta función es la contraparte de múltiples bytes para strpos . Esto hace que la búsqueda sea un poco más compleja, ya que no puede simplemente mirar los bytes sin saber a qué carácter pertenecen.
mb_strpos usa mbfl_strpos , que hace mucho más en comparación con el algoritmo simple de zend_memstr , es como 200 líneas de código complejo ( mbfl_strpos ) en comparación con 30 líneas de código pulido ( zend_memstr ).
Podemos omitir la parte donde tanto la aguja como el pajar se convierten a UTF-8 si es necesario , y llegar a la parte principal del código .
Primero tenemos dos bucles de configuración y luego está el que avanza el puntero de acuerdo con el desplazamiento dado, donde puede ver que conocen los caracteres reales y cómo omiten los caracteres UTF-8 codificados completos: ya que UTF-8 es una variable la codificación de caracteres de ancho donde el primer byte de cada carácter codificado denota la longitud completa del carácter codificado. Esta información se almacena en la matriz u8_tbl .
Finalmente, el bucle donde se realiza la búsqueda real . Y aquí tenemos algo interesante, porque la prueba de la aguja en una cierta posición en el pajar se prueba a la inversa. Y si un byte no coincide, la tabla de salto jtbl se usa para encontrar la siguiente posición posible para la aguja en el pajar . Esta es en realidad una implementación del algoritmo de búsqueda de cadenas Boyer-Moore .
Así que ahora sabemos que mb_strpos ...
- convierte las cadenas a UTF-8, si es necesario
- es consciente de los personajes reales
- utiliza el algoritmo de búsqueda de Boyer-Moore
preg_match
En cuanto a preg_match , utiliza la librería PCRE . Su algoritmo de coincidencia estándar utiliza un autómata finito no determinístico (NFA) para encontrar una coincidencia que realice una búsqueda en profundidad del árbol de patrones. Esto es básicamente un enfoque de búsqueda ingenua.
Estoy preg_match para que el análisis sea más puntuado.
Teniendo en cuenta que mb_strpos es relativamente más lento en comparación con strpos , te lleva a suponer que, debido al tiempo consumido, mb_strpos hace más que strpos .
Creo que esta observación es correcta.
Luego preguntó qué es ese "más" que está causando la diferencia horaria.
Intento dar una respuesta simple: "más" se debe a que strpos funciona con cadenas binarias (un carácter = 8 bits = 1 octeto = 1 byte). mb_strpos opera en secuencias de caracteres codificados (como lo hacen casi todas las funciones mb_* ) que pueden ser X bits, quizás incluso en longitud variable para cada carácter.
Como siempre se trata de una codificación de caracteres específica, tanto el pajar como la cadena de la aguja (probablemente) deben validarse primero para esa codificación, y luego toda la operación para encontrar la posición de la cadena debe realizarse en esa codificación de caracteres específica .
Eso es trabajo de traducción y, dependiendo de la codificación, también requiere un algoritmo de búsqueda específico.
Además de eso, la extensión mb también debe tener algunas estructuras en la memoria para organizar las diferentes codificaciones de caracteres, ya sean tablas de traducción y / o algoritmos específicos. Vea el parámetro adicional que inyecta, por ejemplo, el nombre de la codificación.
Es mucho más trabajo que hacer simples comparaciones byte por byte.
Por ejemplo, la codificación de caracteres GBK es bastante interesante cuando necesitas codificar o decodificar un determinado carácter. La función mb string en este caso debe tener en cuenta todos estos detalles para averiguar si y en qué posición se encuentra el personaje. Como PHP solo tiene cadenas binarias en la zona de usuario desde la que llamaría a esa función, todo el trabajo debe hacerse en cada llamada de función.
Para ilustrar esto aún más, si observa la lista de codificaciones admitidas ( mb_list_encodings ), también puede encontrar algunas como BASE64 , UUENCODE , HTML-ENTITIES y Quoted-Printable . Como puedes imaginar, todos estos se manejan de manera diferente.
Por ejemplo, una sola entidad HTML numérica puede tener un tamaño de hasta 1024 bytes, si no es incluso mayor. Un ejemplo extremo que conozco y amo es este . Sin embargo, para esa codificación, tiene que ser manejado por el algoritmo mb_strpos .