Por que o retorno antecipado é mais lento do que outro?

179

Esta é uma pergunta de acompanhamento para uma resposta que eu dei alguns dias atrás . Edit: parece que o OP dessa pergunta já usou o código que eu postei para ele para fazer a mesma pergunta , mas eu não sabia disso. Desculpas. As respostas fornecidas são diferentes!

Substancialmente, observei que:

>>> def without_else(param=False):
...     if param:
...         return 1
...     return 0
>>> def with_else(param=False):
...     if param:
...         return 1
...     else:
...         return 0
>>> from timeit import Timer as T
>>> T(lambda : without_else()).repeat()
[0.3011460304260254, 0.2866089344024658, 0.2871549129486084]
>>> T(lambda : with_else()).repeat()
[0.27536892890930176, 0.2693932056427002, 0.27011704444885254]
>>> T(lambda : without_else(True)).repeat()
[0.3383951187133789, 0.32756996154785156, 0.3279120922088623]
>>> T(lambda : with_else(True)).repeat()
[0.3305950164794922, 0.32186388969421387, 0.3209099769592285]

... ou em outras palavras: ter a elsecláusula é mais rápido, independentemente da ifcondição ser acionada ou não.

Suponho que tenha a ver com diferentes bytecodes gerados pelos dois, mas alguém é capaz de confirmar / explicar em detalhes?

Edição: Parece que nem todo mundo é capaz de reproduzir meus horários, então eu pensei que poderia ser útil dar algumas informações sobre o meu sistema. Estou executando o Ubuntu 11.10 de 64 bits com o python padrão instalado. pythongera as seguintes informações de versão:

Python 2.7.2+ (default, Oct  4 2011, 20:06:09) 
[GCC 4.6.1] on linux2

Aqui estão os resultados da desmontagem no Python 2.7:

>>> dis.dis(without_else)
  2           0 LOAD_FAST                0 (param)
              3 POP_JUMP_IF_FALSE       10

  3           6 LOAD_CONST               1 (1)
              9 RETURN_VALUE        

  4     >>   10 LOAD_CONST               2 (0)
             13 RETURN_VALUE        
>>> dis.dis(with_else)
  2           0 LOAD_FAST                0 (param)
              3 POP_JUMP_IF_FALSE       10

  3           6 LOAD_CONST               1 (1)
              9 RETURN_VALUE        

  5     >>   10 LOAD_CONST               2 (0)
             13 RETURN_VALUE        
             14 LOAD_CONST               0 (None)
             17 RETURN_VALUE        
Mac
fonte
1
havia uma pergunta idêntica no SO que não consigo encontrar agora. Eles verificaram o código de código gerado e houve uma etapa adicional. As diferenças observadas eram muito dependentes do testador (máquina, SO ..), às vezes encontrando apenas diferenças muito pequenas.
joaquin
3
No 3.x, ambos produzem bytecode idêntico, exceto por algum código inacessível ( LOAD_CONST(None); RETURN_VALUE- mas como afirmado, nunca é alcançado) no final de with_else. Eu duvido muito que o código morto torne a função mais rápida. Alguém poderia fornecer um disno 2.7?
4
Não pude reproduzir isso. Funciona com elsee Falsefoi o mais lento de todos (152ns). O segundo mais rápido foi Truesem else(143ns) e dois outros eram basicamente os mesmos (137ns e 138ns). Eu não usei o parâmetro padrão e o medi %timeitno iPython.
rplnt
Eu não posso reproduzir esses horários, às vezes o with_else é mais rápido, por vezes, esta é a versão without_else, parece que eles são bastante semelhantes para mim ...
Cédric Julien
1
Resultados adicionados de desmontagem. Estou usando o Ubuntu 11.10, 64 bits, estoque Python 2.7 - mesma configuração do @mac. Também concordo que with_elseé notavelmente mais rápido.
Chris Morgan

Respostas:

387

Este é um palpite puro, e não descobri uma maneira fácil de verificar se está certo, mas tenho uma teoria para você.

Eu tentei o seu código e obtive o mesmo resultado, without_else()é repetidamente um pouco mais lento que with_else():

>>> T(lambda : without_else()).repeat()
[0.42015745017874906, 0.3188967452567226, 0.31984281521812363]
>>> T(lambda : with_else()).repeat()
[0.36009842032996175, 0.28962249392031936, 0.2927151355828528]
>>> T(lambda : without_else(True)).repeat()
[0.31709728471076915, 0.3172671387005721, 0.3285821242644147]
>>> T(lambda : with_else(True)).repeat()
[0.30939889008243426, 0.3035132258429485, 0.3046679117038593]

Considerando que o bytecode é idêntico, a única diferença é o nome da função. Em particular, o teste de temporização faz uma pesquisa no nome global. Tente renomear without_else()e a diferença desaparecerá:

>>> def no_else(param=False):
    if param:
        return 1
    return 0

>>> T(lambda : no_else()).repeat()
[0.3359846013948413, 0.29025818923918223, 0.2921801513879245]
>>> T(lambda : no_else(True)).repeat()
[0.3810395594970828, 0.2969634408842694, 0.2960104566362247]

Meu palpite é que without_elsehá uma colisão de hash com outra coisa, globals()portanto a pesquisa de nome global é um pouco mais lenta.

Editar : um dicionário com 7 ou 8 teclas provavelmente possui 32 slots, portanto, nessa base, without_elsehá uma colisão de hash com __builtins__:

>>> [(k, hash(k) % 32) for k in globals().keys() ]
[('__builtins__', 8), ('with_else', 9), ('__package__', 15), ('without_else', 8), ('T', 21), ('__name__', 25), ('no_else', 28), ('__doc__', 29)]

Para esclarecer como o hash funciona:

__builtins__ hashes para -1196389688, o que reduziu o tamanho do módulo da mesa (32) significa que ele é armazenado no slot nº 8 da tabela.

without_elsehashes para 505688136 que reduziu o módulo 32 é 8, então há uma colisão. Para resolver este Python calcula:

Começando com:

j = hash % 32
perturb = hash

Repita isso até encontrarmos um espaço livre:

j = (5*j) + 1 + perturb;
perturb >>= 5;
use j % 2**i as the next table index;

o que dá 17 para usar como o próximo índice. Felizmente, isso é gratuito, então o loop se repete apenas uma vez. O tamanho da tabela de hash é uma potência de 2, assim 2**icomo o tamanho da tabela de hash, ié o número de bits usados ​​no valor de hash j.

Cada sonda na tabela pode encontrar um destes:

  • O slot está vazio; nesse caso, a análise é interrompida e sabemos que o valor não está na tabela.

  • O slot não foi usado, mas foi usado no passado; nesse caso, vamos tentar o próximo valor calculado como acima.

  • O slot está cheio, mas o valor total do hash armazenado na tabela não é o mesmo que o da chave que estamos procurando (é o que acontece no caso de __builtins__vs without_else).

  • O slot está cheio e tem exatamente o valor de hash que queremos, então o Python verifica se a chave e o objeto que estamos procurando são o mesmo objeto (que nesse caso serão porque as cadeias curtas que poderiam ser identificadores são armazenadas, portanto identificadores idênticos usam exatamente a mesma string).

  • Finalmente, quando o slot está cheio, o hash corresponde exatamente, mas as chaves não são o objeto idêntico, e só então o Python tentará compará-las em termos de igualdade. Isso é comparativamente lento, mas no caso de pesquisas de nome não devem realmente acontecer.

Duncan
fonte
9
@ Chris, não, o comprimento da string não deve ser significativo. Na primeira vez que você faz o hash de uma string, isso leva um tempo proporcional ao comprimento da string, mas o hash calculado é armazenado em cache no objeto string, para que os hashes subsequentes sejam O (1).
Duncan
1
Ah ok, eu não estava ciente do cache, mas que faz sentido
Chris Eberle
9
Fascinante! Posso te chamar de Sherlock? ;) De qualquer forma, espero não esquecer de lhe dar alguns pontos adicionais com uma recompensa assim que a pergunta for elegível.
Voo
4
@mac, não exatamente. Vou acrescentar um pouco sobre a resolução de hash (iria incluí-lo no comentário, mas é mais interessante do que eu pensava).
Duncan
6
@ Duncan - Muito obrigado por dedicar um tempo para ilustrar o processo de hash. Resposta de primeira qualidade! :)
mac