Recentemente, estou aprendendo alguns tópicos de HPC e descobri que os compiladores C/C++ modernos são capazes de detectar locais onde a otimização é necessária e conduzi-la usando técnicas correspondentes, como SIMD, desdobramento de loop, etc., especialmente sob o sinalizador -O3
, com uma compensação entre desempenho de tempo de execução versus tempo de compilação e tamanho do arquivo de objeto.
Então, imediatamente me ocorreu que o CPython interpreta e executa em tempo real, então presumo que ele não pode se dar ao luxo de conduzir esses recursos do compilador porque o tempo de compilação para ele é equivalente ao tempo de execução, então fiz um experimento de brinquedo abaixo:
import time, random
n = 512
A = [[random.random() for _ in range(n)] for _ in range(n)]
B = [[random.random() for _ in range(n)] for _ in range(n)]
C = [[0] * n for _ in range(n)]
def matMul( A, B, C ):
""" C = A .* B """
for i in range(0, n - 4, 4):
for j in range(0, n - 4, 4):
for k in range(0, n - 4, 4):
C[i][j] = A[i][k] * B[k][j]
C[i + 1][j + 1] = A[i + 1][k + 1] * B[k + 1][j + 1]
C[i + 2][j + 2] = A[i + 2][k + 2] * B[k + 2][j + 2]
C[i + 3][j + 3] = A[i + 3][k + 3] * B[k + 3][j + 3]
C[i + 4][j + 4] = A[i + 4][k + 4] * B[k + 4][j + 4]
# return C
start = time.time()
matMul( A, B, C )
end = time.time()
print( f"Elapsed {end - start}" )
Com o loop se desenrolando, o programa termina em 3 segundos, sem ele, leva até quase 20 segundos.
Isso significa que é preciso prestar atenção e implementar manualmente essas técnicas opt ao escrever código Python? Ou o Python oferece a otimização em alguma configuração especial?
O desenrolamento do loop é útil porque pode (1) reduzir a sobrecarga gasta no gerenciamento do loop e (2) no nível de montagem, permite que o processador funcione mais rápido, eliminando penalidades de ramificação, mantendo o pipeline de instruções cheio, etc.
(2) não se aplica realmente a uma implementação de linguagem interpretada como Python - ela já está fazendo muitas ramificações e tomadas de decisão no nível de assembly. Pode ganhar com (1), mas meu pressentimento é que esse tempo é frequentemente ofuscado pela sobrecarga do interpretador. A regra de ouro da otimização de desempenho é primeiro medir e confirmar que o gargalo está onde você acha que está.
A propósito, seu código tem um bug:
Ele processa as células (0, 0), (1, 1), (2, 2), (3, 3) e (4, 4) (embora (4, 4) também seja processado na próxima iteração), mas não (0, 1), (0, 2), (1, 0)... (Essa é a outra razão para a regra de ouro da otimização de desempenho: é fácil cometer erros ao otimizar código que não precisa disso.)
Como @Mat disse, a abordagem padrão para Python em particular é usar NumPy , que usa uma implementação C otimizada.
Tudo o que foi dito acima se aplica ao CPython, a implementação padrão do Python. Há outras implementações do Python como o Cython que oferecem suas próprias otimizações; estou menos familiarizado com elas.
(Veja os comentários para saber por que seu código não está funcionando, já que essa não é a verdadeira questão).
Como Josh já disse, CPython não faz otimização. Então, desdobrar loops pode ser útil (sob a suposição de que simplesmente não usar os loops em python, por exemplo, deixando
numpy
fazer isso por você, não é a solução).Mas gostaria de salientar que você está errado sobre o interpretador fazer as coisas "na hora" e, portanto, não ser capaz de otimizar o código.
Intérpretes nunca apenas interpretam o texto; mesmo os mais antigos, e muito menos os modernos. Eles funcionam um pouco como compiladores, com diferentes estágios: tokenização, depois análise sintática, que transforma o texto em árvores de tokens, depois análise semântica que, por exemplo, vincula identificadores à sua definição (a razão pela qual, mesmo em um interpretador, ao contrário do que às vezes lemos aqui, realmente não importa, em termos de desempenho, se os nomes de suas variáveis têm 1 caractere ou 1000. O nome desapareceu do código antes mesmo de a execução ser iniciada), faz alguma verificação de digitação ou avaliação, se a linguagem é uma linguagem tipada, etc.
Nesse estágio, seria possível para um interpretador desenrolar os loops: ele poderia ver que o contador de loops não é usado fora do loop (portanto, não há necessidade de mantê-lo) e decidir transformar a árvore para substituir a
for
por uma repetição das instruções).E mesmo o único estágio que diferencia um compilador de um interpretador, o estágio de geração de código, hoje em dia é frequentemente executado por interpretadores também, já que a maioria dos interpretadores modernos compila primeiro para uma máquina virtual e então executa o código da máquina virtual. Então, neste estágio também é possível executar algumas otimizações, como fatoração de resultados intermediários e o tipo.
Então, isso não muda a resposta: não, CPython não otimiza realmente, e sim, com CPython, não é surpreendente que desenrolar os loops, às vezes, ganhe tempo (isso, claro, depende do que está no loop. Se o custo de aumentar um contador e compará-lo a um intervalo é insignificante antes do que está dentro do loop, então desenrolá-lo é um pouco inútil). Mas a razão não é "porque python é um interpretador, e interpretadores, ao contrário de compiladores, não poderiam fazer otimização". Interpretadores modernos são basicamente compiladores e máquinas virtuais. E mesmo os mais tradicionais interpretam uma árvore representando o programa, não o código de texto, e alguma otimização, como desenrolar loops, poderia ser feita diretamente na fase em que eles constroem essa árvore (isto é, assim que o
.py
arquivo é lido, mesmo que não seja executado). É apenas porque CPython escolhe não fazer.(E o CPython opta por não fazer isso, porque o ponto python não é para ser o ideal. Se você precisa de um código rápido, não deve codificá-lo em python. Você deve confiar no numpy ou similares, que não são codificados em python. Ou usar suas próprias extensões, com Python/C Api, ou ctypes, ou numba, ou cython, ou...)