¿Cómo determinar si el rango de numba realmente funciona correctamente?

En otra Q + A ( ¿Puedo realizar una acumulación dinámica de filas en pandas? ) Hice un comentario sobre la corrección de usar el prange de este código (de esta respuesta ):

 from numba import njit, prange @njit def dynamic_cumsum(seq, index, max_value): cumsum = [] running = 0 for i in prange(len(seq)): if running > max_value: cumsum.append([index[i], running]) running = 0 running += seq[i] cumsum.append([index[-1], running]) return cumsum 

El comentario fue:

No recomendaría paralelizar un bucle que no sea puro. En este caso la variable de running hace impura. Hay 4 resultados posibles: (1) numba decide que no puede paralelizarlo y simplemente procesa el bucle como si fuera una cumsum lugar de prange (2) puede elevar la variable fuera del bucle y usar la paralelización en el rest (3) numba la inserción incorrecta de la sincronización entre las ejecuciones paralelas y el resultado puede ser falso (4) el numba inserta las sincronizaciones necesarias en la ejecución, lo que puede generar más sobrecarga de la que se obtiene al paralelizarla en primer lugar

Y la adición posterior:

Por supuesto, tanto la variable de running como la variable de cumsum hacen que el bucle sea “impuro”, no solo la variable de ejecución como se indicó en el comentario anterior

    Entonces me preguntaron:

    Esto puede parecer una pregunta tonta, pero ¿cómo puedo averiguar cuál de las 4 cosas hizo y mejorarlo? Realmente me gustaría ser mejor con numba!

    Dado que podría ser útil para futuros lectores, decidí crear una Q + A auto respondida aquí. Spoiler: Realmente no puedo responder a la pregunta cuál de los 4 resultados se produce (o si numba produce un resultado totalmente diferente), por lo que recomiendo encarecidamente otras respuestas.

    TL; DR: Primero: prange en idéntico al range , excepto cuando se agrega paralelo al jit , por ejemplo njit(parallel=True) . Si lo intenta, verá una excepción acerca de una “reducción no prange , ya que Numba limita el scope del prange de prange a los bucles “puros” y los “bucles impuros” con reducciones soportadas por numba y pone la responsabilidad de asegurarse de que caiga. en cualquiera de estas categorías en el usuario.

    Esto se indica claramente en la documentación de numbas prange (versión 0.42) :

    1.10.2. Bucles paralelos explícitos

    Otra característica de este paso de transformación de código es la compatibilidad con bucles paralelos explícitos. Se puede usar el prange de prange lugar del range para especificar que un bucle se puede paralelizar. Se requiere que el usuario se asegure de que el bucle no tenga dependencias de iteración cruzada, a excepción de las reducciones compatibles.

    A lo que los comentarios se refieren como “impuro” se le llama “dependencias de iteración cruzada” en esa documentación. Tal “dependencia de iteración cruzada” es una variable que cambia entre bucles. Un ejemplo simple sería:

     def func(n): a = 0 for i in range(n): a += 1 return a 

    Aquí, la variable a depende del valor que tenía antes de que comenzara el ciclo y de cuántas iteraciones se habían ejecutado. Eso es lo que se entiende por una “dependencia de iteración cruzada” o un bucle “impuro”.

    El problema al paralelizar explícitamente dicho bucle es que las iteraciones se realizan en paralelo, pero cada iteración necesita saber qué están haciendo las otras iteraciones. De lo contrario, se obtendría un resultado incorrecto.

    Supongamos por un momento que prange generaría 4 trabajadores y pasamos 4 como n a la función. ¿Qué haría una implementación completamente ingenua?

     Worker 1 starts, gets ai = 1 from `prange`, and reads a = 0 Worker 2 starts, gets ai = 2 from `prange`, and reads a = 0 Worker 3 starts, gets ai = 3 from `prange`, and reads a = 0 Worker 1 executed the loop and sets `a = a + 1` (=> 1) Worker 3 executed the loop and sets `a = a + 1` (=> 1) Worker 4 starts, gets ai = 4 from `prange`, and reads a = 2 Worker 2 executed the loop and sets `a = a + 1` (=> 1) Worker 4 executed the loop and sets `a = a + 1` (=> 3) => Loop ended, function return 3 

    El orden en que los diferentes trabajadores leen, ejecutan y escriben en a puede ser arbitrario, esto fue solo un ejemplo. ¡También podría producir (por accidente) el resultado correcto! Eso generalmente se llama condición de raza .

    ¿Qué haría un progtwig más sofisticado que reconozca que existe tal dependencia de iteraciones cruzadas?

    Hay tres opciones:

    • Simplemente no lo paralelice.
    • Implementar un mecanismo donde los trabajadores compartan la variable. Los ejemplos típicos aquí son los lockings (esto puede incurrir en una gran sobrecarga).
    • Reconoce que es una reducción que puede ser paralelizada.

    Dado mi entendimiento de la documentación numba (repetida de nuevo):

    Se requiere que el usuario se asegure de que el bucle no tenga dependencias de iteración cruzada, a excepción de las reducciones compatibles.

    Numba hace:

    • Si se trata de una reducción conocida, utilice patrones para paralelizarla.
    • Si no es una reducción conocida lanzar una excepción.

    Desafortunadamente, no está claro qué son las “reducciones apoyadas”. Pero la documentación sugiere que los operadores binarios operan con el valor anterior en el cuerpo del bucle:

    Una reducción se infiere automáticamente si una función / operador binario actualiza una variable utilizando su valor anterior en el cuerpo del bucle. El valor inicial de la reducción se deduce automáticamente para los operadores += y *= . Para otras funciones / operadores, la variable de reducción debe mantener el valor de identidad justo antes de ingresar al ciclo de prange . Las reducciones de esta manera se admiten para escalares y para matrices de dimensiones arbitrarias.

    El código en el OP utiliza una lista como dependencia de iteración cruzada y llama a list.append en el cuerpo del bucle. Personalmente no llamaría a list.append que no es un operador binario, por lo que list.append que es muy probable que no sea compatible . En cuanto a la otra dependencia de iteración cruzada que se está running : está usando la sum en el resultado de la iteración anterior (que estaría bien), pero también se restablece condicionalmente a cero si supera un umbral (que probablemente no esté bien).

    Numba proporciona formas de inspeccionar el código intermedio (LLVM y ASM):

     dynamic_cumsum.inspect_types() dynamic_cumsum.inspect_llvm() dynamic_cumsum.inspect_asm() 

    Pero incluso si tuviera la comprensión requerida de los resultados para hacer una statement sobre la corrección del código emitido, en general es altamente no trivial “probar” que el código de proceso / multiproceso funciona correctamente. Dado que aún carezco del conocimiento de LLVM y ASM para ver si incluso intenta paralelizarlo, no puedo responder a su pregunta específica qué resultado produce.

    De vuelta al código, como se mencionó, arroja una excepción (reducción no admitida) si uso parallel=True , así que asumo que numba no paraliza nada en el ejemplo:

     from numba import njit, prange @njit(parallel=True) def dynamic_cumsum(seq, index, max_value): cumsum = [] running = 0 for i in prange(len(seq)): if running > max_value: cumsum.append([index[i], running]) running = 0 running += seq[i] cumsum.append([index[-1], running]) return cumsum dynamic_cumsum(np.ones(100), np.arange(100), 10) 
     AssertionError: Invalid reduction format During handling of the above exception, another exception occurred: LoweringError: Failed in nopython mode pipeline (step: nopython mode backend) Invalid reduction format File "<>", line 7: def dynamic_cumsum(seq, index, max_value):  running = 0 for i in prange(len(seq)): ^ [1] During: lowering "id=2[LoopNest(index_variable = parfor_index.192, range = (0, seq_size0.189, 1))]{56:  (10)>, 24:  (7)>, 34:  (8)>}Var(parfor_index.192, <> (7))" at <> (7) 

    Entonces, lo que queda por decir: prange no proporciona ninguna ventaja de velocidad en este caso en un range normal (porque no se ejecuta en paralelo). Entonces, en ese caso, no “arriesgaría” problemas potenciales y / o confundiría a los lectores, dado que no se admite de acuerdo con la documentación numba.

     from numba import njit, prange @njit def p_dynamic_cumsum(seq, index, max_value): cumsum = [] running = 0 for i in prange(len(seq)): if running > max_value: cumsum.append([index[i], running]) running = 0 running += seq[i] cumsum.append([index[-1], running]) return cumsum @njit def dynamic_cumsum(seq, index, max_value): cumsum = [] running = 0 for i in range(len(seq)): # <-- here is the only change if running > max_value: cumsum.append([index[i], running]) running = 0 running += seq[i] cumsum.append([index[-1], running]) return cumsum 

    Solo una sincronización rápida que admite la statement “no más rápida que” que hice anteriormente:

     import numpy as np seq = np.random.randint(0, 100, 10_000_000) index = np.arange(10_000_000) max_ = 500 # Correctness and warm-up assert p_dynamic_cumsum(seq, index, max_) == dynamic_cumsum(seq, index, max_) %timeit p_dynamic_cumsum(seq, index, max_) # 468 ms ± 12.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) %timeit dynamic_cumsum(seq, index, max_) # 470 ms ± 9.49 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)