Início / coding / Perguntas / 79570163
Accepted
Ξένη Γήινος
Asked: 2025-04-12 15:38:21 +0800 CST

Por que essas funções quase idênticas funcionam de forma tão diferente?

  • 772

Eu escrevi quatro funções que modificam uma matriz quadrada 2D no local, ela reflete metade da matriz quadrada delimitada por dois lados que se encontram e a diagonal correspondente de 45 graus, para a outra metade separada pela mesma diagonal.

Eu escrevi uma função para cada um dos quatro casos possíveis, para product(('upper', 'lower'), ('left', 'right'))refletir product(('lower', 'upper'), ('right', 'left')).

Eles usam o Numba para compilar Just-In-Time e são paralelizados usando numba.prangee, portanto, são muito mais rápidos que os métodos fornecidos pelo NumPy:

In [2]: sqr = np.random.randint(0, 256, (1000, 1000), dtype=np.uint8)

In [3]: %timeit x, y = np.tril_indices(1000); sqr[x, y] = sqr[y, x]
9.16 ms ± 30.9 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Como você pode ver, o código acima leva muito tempo para ser executado.

import numpy as np
import numba as nb


@nb.njit(cache=True, parallel=True, nogil=True)
def triangle_flip_LL2UR(arr: np.ndarray) -> None:
    height, width = arr.shape[:2]
    if height != width:
        raise ValueError("argument arr must be a square")

    for i in nb.prange(height):
        arr[i, i:] = arr[i:, i]


@nb.njit(cache=True, parallel=True, nogil=True)
def triangle_flip_UR2LL(arr: np.ndarray) -> None:
    height, width = arr.shape[:2]
    if height != width:
        raise ValueError("argument arr must be a square")

    for i in nb.prange(height):
        arr[i:, i] = arr[i, i:]


@nb.njit(cache=True, parallel=True, nogil=True)
def triangle_flip_LR2UL(arr: np.ndarray) -> None:
    height, width = arr.shape[:2]
    if height != width:
        raise ValueError("argument arr must be a square")

    last = height - 1
    for i in nb.prange(height):
        arr[i, last - i :: -1] = arr[i:, last - i]


@nb.njit(cache=True, parallel=True, nogil=True)
def triangle_flip_UL2LR(arr: np.ndarray) -> None:
    height, width = arr.shape[:2]
    if height != width:
        raise ValueError("argument arr must be a square")

    last = height - 1
    for i in nb.prange(height):
        arr[i:, last - i] = arr[i, last - i :: -1]

In [4]: triangle_flip_LL2UR(sqr)

In [5]: triangle_flip_UR2LL(sqr)

In [6]: triangle_flip_LR2UL(sqr)

In [7]: triangle_flip_UL2LR(sqr)

In [8]: %timeit triangle_flip_LL2UR(sqr)
194 μs ± 634 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [9]: %timeit triangle_flip_UR2LL(sqr)
488 μs ± 3.26 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [10]: %timeit triangle_flip_LR2UL(sqr)
196 μs ± 501 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [11]: %timeit triangle_flip_UL2LR(sqr)
486 μs ± 855 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Por que eles têm tempos de execução tão diferentes? Dois deles levam cerca de 200 microssegundos para serem executados, os outros dois, cerca de 500 microssegundos, apesar de serem quase idênticos.

Descobri uma coisa. triangle_flip_UR2LL(arr)é o mesmo que triangle_flip_LL2UR(sqr.T)e vice-versa.

Agora, se eu transpor o array antes de chamar as funções, a tendência de desempenho se inverte:

In [109]: %timeit triangle_flip_UR2LL(sqr.T)
196 μs ± 1.15 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [110]: %timeit triangle_flip_LL2UR(sqr.T)
490 μs ± 1.24 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Por que isso está acontecendo?

python

1 respostas

  1. Best Answer

    isso é uma mistura de compartilhamento falso e gargalo de largura de banda de memória, removendo a paralelização ao converter nb.prange -> rangevocê obtém tempos iguais para todas as 4 funções.

    o primeiro é escrever uma única linha por vez, que é contígua na memória, o segundo é escrever uma coluna por vez. esta coluna não é contígua.

    o computador não trabalha com bytes, ele trabalha com linhas de cache, uma linha de cache é um conjunto contíguo de 64 bytes de memória na maioria dos sistemas. quando uma thread grava em uma linha de cache, ela marca toda a linha de cache como suja e outras threads precisam atualizar sua versão dessa linha de cache suja antes de lerem ou gravarem nos outros valores nela. isso é basicamente compartilhamento falso.

    Na segunda versão, como cada thread está gravando uma coluna por vez, ela está marcando muitas linhas de cache como sujas por vez, ignorando assim outras threads que tentarão lê-las.

    Por fim, preciso ressaltar que a paralelização desse código introduz condições de corrida em todas as versões. Você precisa ter matrizes separadas para entrada e saída, ou fazer com que cada thread trabalhe em um bloco quadrado por vez, em vez de uma linha ou coluna inteira. A maioria das implementações otimizadas de transposição de matriz evita esse falso compartilhamento ao fazer isso.

    • 4

relate perguntas