programming - python vs c++




Python vs CPP: Por que a diferença de velocidade é tão grande? (2)

def main():
    i = 2
    sum = 1
    while i < 100000:
        j = 2
        while j < i:
            if i%j == 0:
                sum += 1
                break
            j += 1
        i += 1

    print(sum)


if __name__ == "__main__":
    main()
#include<iostream>

using namespace std;

int main() {
    int sum = 1;
    for (int i=2; i<100000; i++) {
        for (int j=2; j<i; j++) {
            if (i%j == 0) {
                sum++;
                break;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

C ++

Executar com: g++ -std=c++11 x.cpp -ox && time ./x

Tempo: ./x 1.36s user 0.00s system 99% cpu 1.376 total

Python

Executar com: python x.py

Tempo: python x.py 32.10s user 0.21s system 98% cpu 32.854 total

Alguém pode explicar a enorme diferença entre o tempo gasto pelos dois programas? E o que pode ser feito para acelerar o python?


Aqui está um exemplo simples da diferença:

i++ em C ++ compila para (em máquinas x86-64) uma simples instrução inc REGISTER . Leva uma fração de um ciclo para executar.

i += 1 no Python pode ser desmontado com o módulo dis via dis.dis('i += 1') que nos informa que o bytecode envolvido é:

  1           0 LOAD_NAME                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_NAME               0 (i)
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE

Experimente online!

Tecnicamente, todas as instruções que terminam em _NAME tornam-se _FAST em uma função (desmontamos uma instrução isolada, de modo que ela se comportou de maneira ligeiramente diferente) e o LOAD_CONST (None) / RETURN_VALUE não existirá para a expressão em uma função real. função tem que fazê-lo, mas não para cada expressão), mas perto o suficiente. Na prática, o bytecode real dentro de uma função seria mais parecido com:

  1           0 LOAD_FAST                0 (i)
              2 LOAD_CONST               0 (1)
              4 INPLACE_ADD
              6 STORE_FAST               0 (i)

Cada uma dessas instruções requer uma execução através de uma instrução switch ou um goto computado (dependendo de como o CPython foi compilado), carregando a próxima instrução e atualizando as informações de posição do código (também envolve verificar repetidamente para assegurar que nenhum outro thread esteja solicitando o GIL) ). LOAD_FAST instruções LOAD_FAST e LOAD_CONST envolvem uma pesquisa de matriz C e ajuste de contagem de referência (um único ajuste de contagem de referência é equivalente ao i++ de antes, exceto que ele precisa mudar a memória, não um registrador, portanto é mais lento). STORE_FAST similarmente envolve uma pesquisa de matriz C, ajuste de contagem de referência (para diminuir o valor existente) e, freqüentemente, liberando memória (se o decref removeu a última referência ao valor). INPLACE_ADD tem que procurar dinamicamente e chamar um ponteiro de função para executar a adição (e faz isso através de algumas camadas de função indireta em primeiro lugar), que por si só precisa extrair o valor C subjacente de cada Python int para fazer o trabalho ( e se os números são grandes o suficiente, isso envolve matemática baseada em array, que fica feia), (geralmente) cria um novo objeto int Python, e também faz mais ajustes de contagem de referência.

Basicamente, para obter o equivalente ao que o C / C ++ faz em uma instrução de montagem barata e barata em um registrador, o Python precisava executar (estimar) meia dúzia de chamadas de função (incluindo uma através de um ponteiro de função), dezenas de pesquisas de memória, cerca de uma dúzia de ajustes de contagem de referência, etc. Francamente, o mais surpreendente é que o Python leva apenas 24x mais do que o C ++.

Vou observar que o custo relativo aqui é maior para operações matemáticas simples; quanto mais trabalho um único bytecode faz, menos a sobrecarga do interpretador é importante. Infelizmente para este caso, seu código não é nada além de matemática simples, então Python (pelo menos, CPython) está no pior dos casos aqui.

Quanto à aceleração, as principais regras são:

  1. Escreva código Python, não código C Você está mantendo manualmente seus contadores, quando o range do Python pode fazer o trabalho para você (e salvar muitas instruções individuais de bytecode). Como eu mencionei, são as operações mais simples e baratas onde a sobrecarga do interpretador é maior, mas essas operações normalmente são coisas que você não precisa fazer muito, porque geralmente há uma maneira melhor de fazê-las (por exemplo, for loops over range em vez de loops while com ajuste manual do contador).
  2. Para operações matemáticas em massa, use módulos de extensão que podem fazer o trabalho em massa, por exemplo, numpy . Toda essa sobrecarga para uma única adição é ruim; pagá-lo por 1000 adições é bem trivial.
  3. Tente intérpretes alternativos (por exemplo, PyPy)
  4. Use o Cython para compilar o C ++ a partir do seu código Python (requer a adição de declarações apropriadas do cdef )
  5. Use ctypes para chamar bibliotecas C existentes e / ou escrever extensões brutas do Python C (quando o Cython não puder lidar com o que você deseja)

Além disso, você só precisa aceitar que as linguagens interpretadas com digitação dinâmica sempre terão uma sobrecarga que uma linguagem compilada e estaticamente tipada não terá.

Para abordar o ponto 1, uma versão Python do seu código seria semelhante a:

def main():
    sum = 1
    for i in range(2, 100000):
        for j in range(2, i):
            if i%j == 0:
                sum += 1
                break

    print(sum)

if __name__ == "__main__":
    main()

Você pode até mesmo substituir o loop interno com:

    sum += any(i % j == 0 for j in range(2, i))

embora seja improvável que isso traga benefícios de desempenho, apenas um pouco de simplificação de código. Os benefícios de desempenho vêm do uso do range , que agrupa toda a matemática básica de incremento e teste em uma única função dedicada, reduzindo significativamente a sobrecarga.

Para demonstrar a diferença na complexidade do bytecode, considere uma função que não faz nada além de executar um loop com while e um contador manual ou for and range :

def whileloop(n):
    i = 0
    while i < n:
        i += 1

def forloop(n):
    for i in range(n):
        pass

Desmontando cada função mostra:

  3           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (i)

  4           4 SETUP_LOOP              20 (to 26)
        >>    6 LOAD_FAST                1 (i)
              8 LOAD_FAST                0 (n)
             10 COMPARE_OP               0 (<)
             12 POP_JUMP_IF_FALSE       24

  5          14 LOAD_FAST                1 (i)
             16 LOAD_CONST               2 (1)
             18 INPLACE_ADD
             20 STORE_FAST               1 (i)
             22 JUMP_ABSOLUTE            6
        >>   24 POP_BLOCK
        >>   26 LOAD_CONST               0 (None)
             28 RETURN_VALUE

para whileloop e:

  8           0 SETUP_LOOP              16 (to 18)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                 4 (to 16)
             12 STORE_FAST               1 (i)

  9          14 JUMP_ABSOLUTE           10
        >>   16 POP_BLOCK
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

Experimente online!

para forloop . O corpo do loop (o material executado uma vez por passagem, incluindo o teste da condição de finalização) durante o while é executado a partir do LOAD_FAST seguindo o SETUP_LOOP para o JUMP_ABSOLUTE , englobando nove instruções por loop; para o for , ele é executado a partir do FOR_ITER para o JUMP_ABSOLUTE , abrangendo apenas três instruções. Como o trabalho feito para todas essas instruções é bastante trivial, é fácil ver como a sobrecarga do próprio loop seria significativamente maior para o contador gerenciado manualmente com um loop while.


Você está calculando algo como os números não-primos até algum n . Fazê-lo com uma peneira é muito mais rápido:

def count_primes(n):
    count = 0
    w = [False]*n
    for m in range(2,n):
        if not w[m]:
            w[m*m::m] = [True] * ((n+m-m*m-1)//m)
            count+=1
    return count

print(99999 - sieve(100000))

Isso é executado em milissegundos, mesmo com o python.





performance