PyPy 17x más rápido que Python. ¿Se puede acelerar Python?

Resolviendo un problema reciente de Adviento de Código , encontré que mi Python predeterminado era ~ 40 veces más lento que PyPy. Pude hacer eso hasta aproximadamente 17x con este código limitando las llamadas a len y limitando las búsquedas globales ejecutándolo en una función.

En este momento, e.py ejecuta en 5.162 segundos en Python 3.6.3 y .297 segundos en PyPy en mi máquina.

Mi pregunta es: ¿es esta la aceleración irreducible de JIT, o hay alguna manera de acelerar la respuesta de CPython? (sin medios extremos: ¿podría ir a Cython / Numba o algo así?) ¿Cómo puedo convencerme de que no hay nada más que pueda hacer?


Vea el gist para la lista de archivos de entrada de números.

Como se describe en la statement del problema , representan compensaciones de salto. position += offsets[current] , e incrementa el offset actual en 1. Ha terminado cuando un salto lo lleva fuera de la lista.

Aquí está el ejemplo dado (la entrada completa que toma 5 segundos es mucho más larga y tiene números más grandes):

 (0) 3 0 1 -3 - before we have taken any steps. (1) 3 0 1 -3 - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1. 2 (3) 0 1 -3 - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2. 2 4 0 1 (-3) - jump all the way to the end; leave a 4 behind. 2 (4) 0 1 -2 - go back to where we just were; increment -3 to -2. 2 5 0 1 -2 - jump 4 steps forward, escaping the maze. 

El código:

 def run(cmds): location = 0 counter = 0 while 1: try: cmd = cmds[location] if cmd >= 3: cmds[location] -= 1 else: cmds[location] += 1 location += cmd if location < 0: print(counter) break counter += 1 except: print(counter) break if __name__=="__main__": text = open("input.txt").read().strip().split("\n") cmds = [int(cmd) for cmd in text] run(cmds) 

edición: Compilé y ejecuté el código con Cython, que redujo el tiempo de ejecución a 2.53s, pero eso es casi un orden de magnitud más lento que PyPy.

Edición: Numba me pone dentro de 2x

Edición: El mejor Cython que pude escribir se redujo a 1.32s, un poco más de 4x pypy

edit: mover la variable cmd a un cdef, como lo sugiere @viraptor, ¡bajó el Cython a .157 segundos! Casi un orden de magnitud completo más rápido, y no muy lejos de la python normal. Sin embargo, salgo de esto muy impresionado con el PyPy JIT, que hizo todo esto de forma gratuita.

Como una línea de base para Python, escribí esto en C (y luego decidí usar C ++ para una E / S de matriz más conveniente). Se comstack eficientemente para x86-64 con clang ++. Esto se ejecuta 82 veces más rápido que CPython3.6.2 con el código en la pregunta, en un Skylake x86 , por lo que incluso sus versiones más rápidas de Python aún están a un par de factores para mantenerse al día con el código de máquina casi óptimo. (Sí, miré la salida de asm del comstackdor para comprobar que hizo un buen trabajo).

Dejar que un buen JIT o un comstackdor adelantado vea la lógica del bucle es clave para el rendimiento aquí. La lógica del problema es inherentemente serial, por lo que no hay posibilidad de que Python ejecute C ya comstackdo para hacer algo en toda la matriz (como NumPy), porque no se comstackrá C para este problema específico a menos que uses Cython o algo así. . Hacer que cada paso del problema regrese al intérprete de CPython es muerte para el desempeño, cuando su lentitud no está oculta por cuellos de botella en la memoria ni nada.


Actualización: transformar el conjunto de compensaciones en un conjunto de punteros lo acelera en otro factor de 1.5x (modo de direccionamiento simple + eliminación de un add de la cadena de dependencia de bucle de ruta crítica, reduciéndolo solo a la carga L1D de 4 ciclos use la latencia para un modo de direccionamiento simple ( cuando el puntero proviene de otra carga ), no 6c = 5c + 1c para un modo de direccionamiento indexado + add latencia).

Pero creo que podemos ser generosos con Python y no esperar que continúe con las transformaciones de algoritmos para adaptarse a las CPU modernas: P (Especialmente porque usé punteros de 32 bits incluso en el modo de 64 bits para asegurar que la matriz de 4585 elementos aún era única 18kiB, por lo que cabe en la memoria caché L1D de 32kiB. Al igual que la ABI de Linux x32 o la ABI de ILP32 de AArch64).


Además, una expresión alternativa para la actualización hace que gcc compile sin ramificación, como lo hace clang. (En esta respuesta, se comentó el resultado original y el rendimiento original, ya que es interesante ver el efecto de sin ramificaciones en comparación con ramificaciones con predicciones erróneas).

 unsigned jumps(int offset[], unsigned size) { unsigned location = 0; unsigned counter = 0; do { //location += offset[location]++; // simple version // >=3 conditional version below int off = offset[location]; offset[location] += (off>=3) ? -1 : 1; // branchy with gcc // offset[location] = (off>=3) ? off-1 : off+1; // branchless with gcc and clang. location += off; counter++; } while (location < size); return counter; } #include  #include  #include  int main() { std::ios::sync_with_stdio(false); // makes cin faster std::istream_iterator begin(std::cin), dummy; std::vector values(begin, dummy); // construct a dynamic array from reading stdin unsigned count = jumps(values.data(), values.size()); std::cout << count << '\n'; } 

Con clang4.0.1 -O3 -O3 -march=skylake , el bucle interno no tiene sucursales; usa un movimiento condicional para la condición >=3 . Yo utilicé ? : ? : porque eso es lo que esperaba que hiciera el comstackdor. Fuente + asm en el explorador del comstackdor Godbolt

 .LBB1_4: # =>This Inner Loop Header: Depth=1 mov ebx, edi ; silly compiler: extra work inside the loop to save code outside mov esi, dword ptr [rax + 4*rbx] ; off = offset[location] cmp esi, 2 mov ecx, 1 cmovg ecx, r8d ; ecx = (off>=3) ? -1 : 1; // r8d = -1 (set outside the loop) add ecx, esi ; off += -1 or 1 mov dword ptr [rax + 4*rbx], ecx ; store back the updated off add edi, esi ; location += off (original value) add edx, 1 ; counter++ cmp edi, r9d jb .LBB1_4 ; unsigned compare against array size 

Aquí está la salida de perf stat ./a.out < input.txt (para la versión de Clang), en mi CPU i7-6700k Skylake:

 21841249 # correct total, matches Python Performance counter stats for './a.out': 36.843436 task-clock (msec) # 0.997 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 119 page-faults # 0.003 M/sec 143,680,934 cycles # 3.900 GHz 245,059,492 instructions # 1.71 insn per cycle 22,654,670 branches # 614.890 M/sec 20,171 branch-misses # 0.09% of all branches 0.036953258 seconds time elapsed 

El promedio de instrucciones por reloj es mucho menor que 4 debido a la dependencia de los datos en el bucle. La dirección de carga para la siguiente iteración depende de la carga + adición para esta iteración, y la ejecución fuera de orden no puede ocultar eso. Sin embargo, puede superponer todo el trabajo de actualizar el valor de la ubicación actual.

Cambiar de int a short no tiene ningún inconveniente en el rendimiento (como se esperaba; movsx tiene la misma latencia que mov en Skylake ), pero reduce el consumo de memoria a la mitad, por lo que una matriz más grande podría caber en el caché L1D si fuera necesario.

Intenté comstackr la matriz en el progtwig (ya que int offsets[] = { file contents with commas added }; por lo que no es necesario leerlo ni analizarlo. También hizo que el tamaño fuera una constante de tiempo de comstackción. Esto redujo la ejecución el tiempo hasta ~ 36.2 +/- 0.1 milisegundos, por debajo de ~ 36.8, por lo que la versión que se lee de un archivo todavía pasaba la mayor parte de su tiempo en el problema real, no analizando la entrada (a diferencia de Python, C ++ tiene una sobrecarga de inicio insignificante y mi CPU Skylake aumenta hasta la velocidad máxima del reloj en menos de un milisegundo gracias a la administración del estado P del hardware en Skylake.)


Como se describió anteriormente, la búsqueda de punteros con un modo de direccionamiento simple como [rdi] lugar de [rdi + rdx*4] tiene 1c de latencia más baja, y evita la add (el index += offset vuelve current = target ). Intel, ya que IvyBridge tiene un movimiento de enteros de latencia cero entre registros, por lo que no alarga la ruta crítica. Aquí está la fuente (con comentarios) + asm para esta optimización hacky . Una ejecución típica (con el análisis de texto en un std::vector ): 23.26 +- 0.05 ms , 90.725 M ciclos (3.900 GHz), 288.724 M instructions (3.18 IPC). Curiosamente, en realidad son instrucciones más completas, pero se ejecutan mucho más rápido debido a la menor latencia de la cadena de dependencia transmitida por el bucle.


gcc usa una twig y es aproximadamente 2x más lento. (El 14% de las sucursales se predicen erróneamente de acuerdo con las perf stat de perf stat de todo el progtwig. Solo se ramifica como parte de la actualización de los valores, pero la twig no se detiene, por lo que también afecta la ruta crítica, de manera que las dependencias de datos no lo hacen aquí. . Esto parece una mala decisión por parte del optimizador.)

Reescribiendo el condicional como offset[location] = (off>=3) ? off-1 : off+1; offset[location] = (off>=3) ? off-1 : off+1; convence a gcc para ir sin sucursales con asm que se ve bien.

gcc7.1.1 -O3 -march = skylake (para la fuente original que comstack con una twig para (off <= 3) ? : -1 : +1 ).

 Performance counter stats for './ec-gcc': 70.032162 task-clock (msec) # 0.998 CPUs utilized 0 context-switches # 0.000 K/sec 0 cpu-migrations # 0.000 K/sec 118 page-faults # 0.002 M/sec 273,115,485 cycles # 3.900 GHz 255,088,412 instructions # 0.93 insn per cycle 44,382,466 branches # 633.744 M/sec 6,230,137 branch-misses # 14.04% of all branches 0.070181924 seconds time elapsed 

vs. CPython (Python3.6.2 en Arch Linux) :

 perf stat python ./orig-v2.e.py 21841249 Performance counter stats for 'python ./orig-v2.e.py': 3046.703831 task-clock (msec) # 1.000 CPUs utilized 10 context-switches # 0.003 K/sec 0 cpu-migrations # 0.000 K/sec 923 page-faults # 0.303 K/sec 11,880,130,860 cycles # 3.899 GHz 38,731,286,195 instructions # 3.26 insn per cycle 8,489,399,768 branches # 2786.421 M/sec 18,666,459 branch-misses # 0.22% of all branches 3.046819579 seconds time elapsed 

No tengo PyPy u otras implementaciones de Python instaladas, lo siento.

Puedes mejorar las cosas pequeñas, pero pypy (lo más probable) siempre será más rápido en esta tarea.

Para ambos CPython y Cython:

  • No lea todo el archivo a la vez. Puede iterar en las líneas a medida que avanza, lo que le ahorra costos de (re) asignación. Sin embargo, esto requiere que asignes previamente la matriz.
  • Tal vez cambiar de una lista a una matriz .

Para Cython:

  • Marque los tipos de variables . Especialmente los contadores como int s y los comandos como una matriz de int s para omitir la mayoría de las comprobaciones de tipo.