una - ¿Por qué la comparación de cadenas es tan rápida en Python?

eliminar caracteres de una cadena python (2)

Sentí curiosidad por comprender los aspectos internos de cómo funciona la comparación de cadenas en python cuando estaba resolviendo el siguiente problema de algoritmo de ejemplo:

Dadas dos cadenas, devuelve la longitud del prefijo común más largo

Solución 1: charByChar

Mi intuición me dijo que la solución óptima sería comenzar con un cursor al comienzo de ambas palabras e iterar hacia adelante hasta que los prefijos ya no coincidan. Algo como

def charByChar(smaller, bigger): assert len(smaller) <= len(bigger) for p in range(len(smaller)): if smaller[p] != bigger[p]: return p return len(smaller)

Para simplificar el código, la función asume que la longitud de la primera cuerda, smaller , siempre es menor o igual a la longitud de la segunda cuerda, bigger .

Solución 2: búsqueda binaria

Otro método es dividir en dos las cadenas para crear dos subcadenas de prefijo. Si los prefijos son iguales, sabemos que el punto de prefijo común es al menos tan largo como el punto medio. De lo contrario, el punto de prefijo común es al menos no más grande que el punto medio. Entonces podemos recurse para encontrar la longitud del prefijo.

Aka búsqueda binaria.

def binarySearch(smaller, bigger): assert len(smaller) <= len(bigger) lo = 0 hi = len(smaller) # binary search for prefix while lo < hi: # +1 for even lengths mid = ((hi - lo + 1) // 2) + lo if smaller[:mid] == bigger[:mid]: # prefixes equal lo = mid else: # prefixes not equal hi = mid - 1 return lo

Al principio asumí que binarySearch sería más lento porque la comparación de cadenas compararía todos los caracteres varias veces en lugar de solo los caracteres de prefijo como en charByChar .

Sorprendentemente, binarySearch resultó ser mucho más rápido después de algunos benchmarking preliminares.

Figura A

Lo anterior muestra cómo se ve afectado el rendimiento a medida que aumenta la longitud del prefijo. La longitud del sufijo permanece constante en 50 caracteres.

Este gráfico muestra dos cosas:

Como se esperaba, ambos algoritmos tienen un desempeño lineal peor a medida que aumenta la longitud del prefijo.
El rendimiento de charByChar degrada a un ritmo mucho más rápido.

¿Por qué es binarySearch mucho mejor? Creo que es porque

La comparación de cadenas en binarySearch es presumiblemente optimizada por el intérprete / CPU detrás de escena.
charByChar realmente crea nuevas cadenas para cada carácter al que se accede y esto produce una sobrecarga significativa.

Para validar esto, comparé el rendimiento de la comparación y el corte de una cadena, etiquetados como cmp y slice respectivamente, a continuación.

Figura B

Este gráfico muestra dos cosas importantes:

Como se esperaba, la comparación y el corte aumentan linealmente con la longitud.
El costo de comparar y cortar aumenta muy lentamente con la longitud en relación con el rendimiento del algoritmo, Figura A. Observe que ambas figuras van a cadenas de longitud de 1 mil millones de caracteres. Por lo tanto, el costo de comparar 1 carácter 1 billón de veces es mucho mayor que comparar 1 billón de caracteres una vez. Pero esto todavía no responde por qué ...

Cpython

En un esfuerzo por descubrir cómo el intérprete de cpython optimiza la comparación de cadenas, generé el código de bytes para la siguiente función.

In [9]: def slice_cmp(a, b): return a[0] == b[0] In [10]: dis.dis(slice_cmp) 0 LOAD_FAST 0 (a) 2 LOAD_CONST 1 (0) 4 BINARY_SUBSCR 6 LOAD_FAST 1 (b) 8 LOAD_CONST 1 (0) 10 BINARY_SUBSCR 12 COMPARE_OP 2 (==) 14 RETURN_VALUE

Busqué el código de cpython y encontré las two pieces de código siguientes, pero no estoy seguro de que sea aquí donde se produce la comparación de cadenas.

La pregunta

¿Dónde en el cpython ocurre la comparación de cadenas?
¿Hay una optimización de la CPU? ¿Hay una instrucción especial x86 que haga una comparación de cadenas? ¿Cómo puedo ver qué instrucciones de ensamblaje genera cpython? Puede suponer que estoy usando python3 más reciente, Intel Core i5, OS X 10.11.6.
¿Por qué comparar una cadena larga es mucho más rápido que comparar cada uno de sus caracteres?

Pregunta de bonificación: ¿Cuándo es más eficaz charByChar?

Si el prefijo es lo suficientemente pequeño en comparación con el resto de la longitud de la cadena, en algún punto el costo de crear subcadenas en charByChar es menor que el costo de comparar las subcadenas en binarySearch .

Para describir esta relación profundicé en el análisis del tiempo de ejecución.

Análisis de tiempo de ejecución

Para simplificar las ecuaciones siguientes, supongamos que las smaller y las bigger tienen el mismo tamaño, y me referiré a ellas como s1 y s2 .

charByChar

charByChar(s1, s2) = costOfOneChar * prefixLen

Donde el

costOfOneChar = cmp(1) + slice(s1Len, 1) + slice(s2Len, 1)

Donde cmp(1) es el costo de comparar dos cadenas de longitud 1 char.

slice es el costo de acceder a un char, el equivalente de charAt(i) . Python tiene cadenas inmutables y el acceso a un char realmente crea una nueva cadena de longitud 1. slice(string_len, slice_len) es el costo de cortar una cadena de longitud string_len a una porción de tamaño slice_len .

Asi que

charByChar(s1, s2) = O((cmp(1) + slice(s1Len, 1)) * prefixLen)

búsqueda binaria

binarySearch(s1, s2) = costOfHalfOfEachString * log_2(s1Len)

log_2 es el número de veces para dividir las cuerdas a la mitad hasta alcanzar una cuerda de longitud 1. Donde

costOfHalfOfEachString = slice(s1Len, s1Len / 2) + slice(s2Len, s1Len / 2) + cmp(s1Len / 2)

Así que el big-O de binarySearch crecerá de acuerdo a

binarySearch(s1, s2) = O((slice(s2Len, s1Len) + cmp(s1Len)) * log_2(s1Len))

En base a nuestro análisis previo del costo de

Si asumimos que costOfHalfOfEachString es aproximadamente el costOfComparingOneChar entonces podemos referirnos a ambos como x .

charByChar(s1, s2) = O(x * prefixLen) binarySearch(s1, s2) = O(x * log_2(s1Len))

Si los equiparamos

O(charByChar(s1, s2)) = O(binarySearch(s1, s2)) x * prefixLen = x * log_2(s1Len) prefixLen = log_2(s1Len) 2 ** prefixLen = s1Len

Entonces O(charByChar(s1, s2)) > O(binarySearch(s1, s2) cuando

2 ** prefixLen = s1Len

Por lo tanto, al conectar las pruebas de fórmula I regeneradas anteriores para la Figura A pero con cadenas de longitud total 2 ** prefixLen espera que el rendimiento de los dos algoritmos sea aproximadamente igual.

Sin embargo, claramente charByChar funciona mucho mejor. Con un poco de prueba y error, el rendimiento de los dos algoritmos es aproximadamente igual cuando s1Len = 200 * prefixLen

¿Por qué la relación es 200x?

Esto depende tanto de la implementación como del hardware. Sin conocer su máquina objetivo y su distribución específica, no podría asegurarlo. Sin embargo, sospecho fuertemente que el hardware subyacente, como la mayoría, tiene instrucciones de bloqueo de memoria. Entre otras cosas, esto puede comparar un par de cadenas arbitrariamente largas (hasta límites de direccionamiento) en forma paralela y canalizada. Por ejemplo, puede comparar segmentos de 8 bytes en una porción por ciclo de reloj. Esto es mucho más rápido que jugar con índices de nivel de bytes.

TL: DR : una comparación de memcmp es una sobrecarga de Python + un memcmp altamente optimizado (a menos que exista el procesamiento UTF-8?). Idealmente, use las comparaciones de sectores para encontrar la primera discrepancia en menos de 128 bytes o algo así, luego realice un ciclo de char a la vez.

O si se trata de una opción y el problema es importante, realice una copia modificada de un memcmp optimizado para memcmp que devuelve la posición de la primera diferencia, en lugar de igual / no igual; se ejecutará tan rápido como un solo == de las cadenas completas. Python tiene formas de llamar a funciones C / asm nativas en bibliotecas.

Es una limitación frustrante que la CPU pueda hacer esto increíblemente rápido, pero Python no (AFAIK) le da acceso a un bucle de comparación optimizado que le indica la posición de falta de coincidencia en lugar de solo igual / mayor / menor.

Es totalmente normal que la sobrecarga del intérprete domine el costo del trabajo real en un simple bucle de Python, con CPython . La construcción de un algoritmo a partir de bloques de construcción optimizados vale la pena, incluso si esto significa hacer más trabajo total. Esta es la razón por la que NumPy es bueno, pero pasar por encima de una matriz elemento por elemento es terrible. La diferencia de velocidad podría ser algo así como un factor de 20 a 100, para CPython frente a un bucle C (asm) compilado para comparar un byte a la vez (números compuestos, pero probablemente dentro de un orden de magnitud).

La comparación de los bloques de memoria para la igualdad es probablemente una de las mayores incongruencias entre los bucles de Python frente a los que operan en una lista / división completa. Es un problema común con las soluciones altamente optimizadas (por ejemplo, la mayoría de las implementaciones de libc (incluido OS X) tienen un memcmp asm codificado a mano y vectorizado manualmente que utiliza SIMD para comparar 16 o 32 bytes en paralelo, y se ejecuta mucho más rápido que un byte-at -un bucle de tiempo en C o ensamblado). Así que hay otro factor de 16 a 32 (si el ancho de banda de la memoria no es un cuello de botella) multiplicando el factor de la diferencia de velocidad de 20 a 100 entre los bucles de Python y C. O dependiendo de qué tan optimizado memcmp su memcmp , tal vez "solo" 6 u 8 bytes por ciclo.

Con datos activos en caché L2 o L1d para los buffers medianos, es razonable esperar 16 o 32 bytes por ciclo para memcmp en una CPU Haswell o posterior. (El nombramiento de i3 / i5 / i7 comenzó con Nehalem; i5 por sí solo no es suficiente para decirnos mucho sobre su CPU).

No estoy seguro de si una o ambas de sus comparaciones tienen que procesar UTF-8 y verificar las clases de equivalencia o las diferentes formas de codificar el mismo carácter. El peor de los casos es si el bucle Char-at-a-time de Python tiene que buscar caracteres potencialmente de múltiples bytes, pero su comparación de rebanadas solo puede usar memcmp .

Escribir una versión eficiente en Python:

Estamos luchando totalmente contra el lenguaje para obtener eficiencia: su problema es casi exactamente el mismo que el de la función de biblioteca estándar C memcmp , excepto que desea la posición de la primera diferencia en lugar del resultado - / 0 / + que le indica qué cadena es mayor. El bucle de búsqueda es idéntico, es solo una diferencia en lo que hace la función después de encontrar el resultado.

Su búsqueda binaria no es la mejor manera de usar un bloque de construcción de comparación rápida. Una comparación de rebanadas todavía tiene un costo de O(n) , no O(1) , solo que con un factor constante mucho menor. Puede y debe evitar volver a comparar los inicios de los búferes de forma repetida mediante el uso de sectores para comparar fragmentos grandes hasta que encuentre una discrepancia, luego vuelva sobre ese último fragmento con un tamaño de fragmento más pequeño.

# I don''t actually know Python; consider this pseudo-code # or leave an edit if I got this wrong :P chunksize = min(8192, len(smaller)) # possibly round chunksize down to the next lowest power of 2? start = 0 while start+chunksize < len(smaller): if smaller[start:start+chunksize] == bigger[start:start+chunksize]: start += chunksize else: if chunksize <= 128: return char_at_a_time(smaller[start:start+chunksize], bigger[start:start+chunksize]) else: chunksize /= 8 # from the same start # TODO: verify this logic for corner cases like string length not a power of 2 # and/or a difference only in the last character: make sure it does check to the end

Elegí 8192 porque su CPU tiene un caché L1d de 32 kB, por lo que la huella total de caché de dos porciones de 8k es 16k, la mitad de su L1d. Cuando el ciclo encuentra una discrepancia, volverá a escanear los últimos 8kiB en trozos de 1k, y estas comparaciones recorrerán los datos que todavía están calientes en L1d. (Tenga en cuenta que si == encontró una falta de coincidencia, es probable que solo haya tocado datos hasta ese punto, no los 8k completos. Pero la captación previa de HW continuará un poco más allá de eso).

Un factor de 8 debe ser un buen equilibrio entre el uso de grandes segmentos para localizar rápidamente en lugar de no necesitar muchos pases sobre los mismos datos. Este es un parámetro ajustable, por supuesto, junto con el tamaño del fragmento. Cuanto mayor es la falta de correspondencia entre Python y asm, menor debe ser este factor para reducir las iteraciones de bucle de Python).

Con suerte, 8k es lo suficientemente grande como para ocultar la sobrecarga de loop / slice de Python; La memcmp hardware debería seguir funcionando durante la sobrecarga de Python entre memcmp llamadas de memcmp del intérprete, por lo que no necesitamos que la granularidad sea enorme. Pero para cadenas realmente grandes, si 8k no satura el ancho de banda de la memoria, entonces puede que sea de 64k (su caché L2 es de 256 kB; i5 nos dice mucho).

¿Cómo es exactamente `memcmp` tan rápido?

Estoy ejecutando esto en Intel Core i5 pero me imagino que obtendría los mismos resultados en la mayoría de las CPU modernas.

Incluso en C, ¿Por qué memcmp es mucho más rápido que una verificación de bucle for? memcmp es más rápido que un ciclo de comparación de byte a la vez, porque incluso los compiladores de C no son geniales (o totalmente incapaces de) auto-vectorizar los bucles de búsqueda.

Incluso sin soporte de hardware SIMD, un memcmp optimizado podría verificar 4 u 8 bytes a la vez (tamaño de palabra / ancho de registro) incluso en una CPU simple sin SIMD de 16 bytes o 32 bytes.

Pero la mayoría de las CPU modernas, y todas las x86-64, tienen instrucciones SIMD. SSE2 es la línea base para x86-64 , y está disponible como una extensión en el modo de 32 bits.

Un memcmp SSE2 o AVX2 puede usar pcmpeqb / pmovmskb para comparar 16 o 32 bytes en paralelo. (No voy a entrar en detalles sobre cómo escribir memcmp en x86 asm o con C intrínsecos. Busque en Google por separado y / o busque esas instrucciones de asm en una referencia de conjunto de instrucciones de x86, como http://felixcloutier.com/x86/index.html . Consulte también la etiqueta wiki x86 para asm y enlaces de rendimiento. Por ejemplo, ¿ por qué Skylake es mucho mejor que Broadwell-E para el rendimiento de la memoria de un solo hilo? tiene información sobre las limitaciones de ancho de banda de la memoria de un solo núcleo.

Encontré una versión anterior de 2005 del memcmp x86-64 de memcmp (en el lenguaje ensamblador de sintaxis de AT & T) en su sitio web opensource. Definitivamente podría ser mejor; para los búferes grandes, debe alinear un puntero de origen y solo usar movdqu para el otro, permitiendo movdqu luego pcmpeqb con un operando de memoria en lugar de 2x movdqu , incluso si las cadenas están desalineadas entre sí. xorl $0xFFFF,%eax / jnz tampoco es óptimo en CPU donde cmp/jcc puede fusionarse macro pero xor / jcc no.

Desenrollar para verificar toda una línea de caché de 64 bytes a la vez también ocultaría la sobrecarga del ciclo. (Esta es la misma idea de un trozo grande y luego regresa sobre él cuando encuentras un golpe). La versión movbe movbe de movbe hace esto con vpand para combinar los resultados de la comparación en el bucle principal del búfer grande, con la combinación final siendo un vptest que también establece indicadores del resultado. (Tamaño de código más pequeño, pero no menos uops que vpand / vpmovmskb / cmp / jcc ; pero sin inconveniente y, tal vez, menor latencia para reducir las penalizaciones por error de rama en la salida del bucle). Glibc realiza el envío dinámico de CPU en tiempo de enlace dinámico; elige esta versión en las CPU que lo soportan.

Con suerte, el memcmp de Apple es mejor en estos días; Libc embargo, no veo el origen en absoluto en el directorio Libc más reciente. Esperemos que se despachen en tiempo de ejecución a una versión AVX2 para las CPUs Haswell y posteriores.

El ciclo LLoopOverChunks en la versión I linked solo se ejecutará en 1 iteración (16 bytes desde cada entrada) por ~ 2.5 ciclos en Haswell; 10 uops de dominio fusionado. Pero eso es aún mucho más rápido que 1 byte por ciclo para un ciclo C ingenuo, o mucho peor que para un ciclo de Python.

El bucle L(loop_4x_vec): Glibc es de 18 uops de dominio fusionado y, por lo tanto, puede ejecutarse a solo un poco menos de 32 bytes (de cada entrada) por ciclo de reloj, cuando los datos están activos en el caché L1d. De lo contrario se producirá un cuello de botella en el ancho de banda L2. Podrían haber sido 17 uops si no hubieran usado una instrucción adicional dentro del ciclo, disminuyendo un contador de ciclo separado, y calcularon un puntero final fuera del ciclo.

Encontrar instrucciones / puntos calientes en el propio código del intérprete de Python

¿Cómo podría profundizar para encontrar las instrucciones C y las instrucciones de la CPU que mi código llama?

En Linux, puede ejecutar el perf record python ... luego el perf report -Mintel para ver las funciones en las que la CPU pasaba más tiempo y qué instrucciones de esas funciones eran las más atractivas. Obtendrás resultados como los que publiqué aquí: ¿Por qué float () es más rápido que int ()? . (Desplácese hacia abajo en cualquier función para ver las instrucciones reales de la máquina que se ejecutaron, que se muestran como lenguaje ensamblador porque perf tiene un desarmador incorporado).

Para obtener una vista más matizada que muestree el gráfico de llamadas en cada evento, consulte la sección de rendimiento de Linux: cómo interpretar y encontrar zonas interactivas .

(Cuando realmente busca optimizar un programa, desea saber qué función son caras para poder evitarlas en primer lugar. La creación de perfiles para el tiempo "propio" encontrará los puntos calientes, pero no lo hará). siempre sabrá qué diferentes emisores causaron que un bucle determinado ejecute la mayor parte de las iteraciones. Consulte la respuesta de Mike Dunlavey sobre esa pregunta de rendimiento).

Pero para este caso específico, el perfil del intérprete que ejecuta una versión de comparación de segmentos en grandes cadenas debería encontrar el bucle de memcmp donde creo que pasará la mayor parte del tiempo. (O para la versión char-at-a-time, encuentre el código del intérprete que es "hot").

Luego puede ver directamente qué instrucciones de asm están en el ciclo. A partir de los nombres de funciones, asumiendo que su binario tiene algún símbolo, probablemente pueda encontrar la fuente. O si tiene una versión de Python construida con información de depuración, puede acceder a la fuente directamente desde la información del perfil. (No es una creación de depuración con la optimización deshabilitada, solo con símbolos completos).