Por que algumas comparações float <integer são quatro vezes mais lentas que outras?

Ao comparar flutuações com números inteiros, alguns pares de valores levam muito mais tempo para serem avaliados do que outros valores de magnitude semelhante.

Por exemplo:

>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742

Mas se o número flutuante ou número inteiro for menor ou maior em uma certa quantidade, a comparação será executada muito mais rapidamente:

>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956

Alterar o operador de comparação (por exemplo, usar ==ou >não) não afeta os horários de maneira perceptível.

Isso não está relacionado apenas à magnitude, porque a escolha de valores maiores ou menores pode resultar em comparações mais rápidas, então eu suspeito que esteja relacionado a alguma maneira infeliz de alinhar os bits.

Claramente, comparar esses valores é mais do que rápido o suficiente para a maioria dos casos de uso. Estou simplesmente curioso para saber por que o Python parece lutar mais com alguns pares de valores do que com outros.

Um comentário no código-fonte Python para objetos float reconhece que:

Comparação é praticamente um pesadelo

Isso é especialmente verdadeiro quando se compara um float a um número inteiro, porque, diferentemente dos floats, os números inteiros no Python podem ser arbitrariamente grandes e sempre exatos. Tentar converter o número inteiro em um flutuador pode perder precisão e tornar a comparação imprecisa. Tentar converter o float em um número inteiro também não funcionará porque qualquer parte fracionária será perdida.

Para contornar esse problema, o Python executa uma série de verificações, retornando o resultado se uma delas for bem-sucedida. Ele compara os sinais dos dois valores e, em seguida, se o número inteiro é "muito grande" para ser um ponto flutuante, compara o expoente do ponto flutuante com o comprimento do número inteiro. Se todas essas verificações falharem, é necessário construir dois novos objetos Python para comparar, a fim de obter o resultado.

Ao comparar um float vcom um número inteiro / comprimento w, o pior caso é o seguinte:

• ve wtem o mesmo sinal (positivo ou negativo),
• o número inteiro wtem poucos bits suficientes para ser retido no size_ttipo (normalmente 32 ou 64 bits),
• o número inteiro wtem pelo menos 49 bits,
• o expoente do flutuador vé o mesmo que o número de bits w.

E é exatamente isso que temos para os valores da pergunta:

>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49

Vemos que 49 é o expoente da flutuação e o número de bits no número inteiro. Ambos os números são positivos e, portanto, os quatro critérios acima são atendidos.

A escolha de um dos valores para ser maior (ou menor) pode alterar o número de bits do número inteiro ou o valor do expoente, e assim o Python é capaz de determinar o resultado da comparação sem realizar a verificação final cara.

Isso é específico para a implementação do CPython da linguagem.

A comparação em mais detalhes

A float_richcomparefunção lida com a comparação entre dois valores ve w.

Abaixo está uma descrição passo a passo das verificações que a função executa. Os comentários na fonte do Python são realmente muito úteis ao tentar entender o que a função faz, então eu os deixei onde relevantes. Também resumi essas verificações em uma lista no pé da resposta.

A idéia principal é mapear os objetos Python ve wduas duplicatas C apropriadas, ie j, que podem ser facilmente comparadas para fornecer o resultado correto. Tanto o Python 2 quanto o Python 3 usam as mesmas idéias para fazer isso (o primeiro apenas manipula inte longdigita separadamente).

A primeira coisa a fazer é verificar se vé definitivamente um flutuador Python e mapeá-lo para um C duplo i. Em seguida, a função examina se wtambém é um flutuador e o mapeia para um C duplo j. Este é o melhor cenário para a função, pois todas as outras verificações podem ser ignoradas. A função também verifica se vé infou nan:

static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
    double i, j;
    int r = 0;
    assert(PyFloat_Check(v));       
    i = PyFloat_AS_DOUBLE(v);       

    if (PyFloat_Check(w))           
        j = PyFloat_AS_DOUBLE(w);   

    else if (!Py_IS_FINITE(i)) {
        if (PyLong_Check(w))
            j = 0.0;
        else
            goto Unimplemented;
    }

Agora sabemos que, se wessas verificações falharem, não é um flutuador Python. Agora a função verifica se é um número inteiro Python. Se for esse o caso, o teste mais fácil é extrair o sinal de ve o sinal de w(retornar 0se zero, -1se negativo, 1se positivo). Se os sinais forem diferentes, essas são todas as informações necessárias para retornar o resultado da comparação:

    else if (PyLong_Check(w)) {
        int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
        int wsign = _PyLong_Sign(w);
        size_t nbits;
        int exponent;

        if (vsign != wsign) {
            /* Magnitudes are irrelevant -- the signs alone
             * determine the outcome.
             */
            i = (double)vsign;
            j = (double)wsign;
            goto Compare;
        }
    }   

Se esta verificação falhar, em seguida, ve wtêm o mesmo sinal.

A próxima verificação conta o número de bits no número inteiro w. Se tiver muitos bits, não poderá ser mantido como um flutuador e, portanto, deve ser maior em magnitude do que o flutuador v:

    nbits = _PyLong_NumBits(w);
    if (nbits == (size_t)-1 && PyErr_Occurred()) {
        /* This long is so large that size_t isn't big enough
         * to hold the # of bits.  Replace with little doubles
         * that give the same outcome -- w is so large that
         * its magnitude must exceed the magnitude of any
         * finite float.
         */
        PyErr_Clear();
        i = (double)vsign;
        assert(wsign != 0);
        j = wsign * 2.0;
        goto Compare;
    }

Por outro lado, se o número inteiro wtiver 48 ou menos bits, ele pode transformar com segurança um C duplo je comparar:

    if (nbits <= 48) {
        j = PyLong_AsDouble(w);
        /* It's impossible that <= 48 bits overflowed. */
        assert(j != -1.0 || ! PyErr_Occurred());
        goto Compare;
    }

Desse ponto em diante, sabemos que wpossui 49 ou mais bits. Será conveniente tratar wcomo um número inteiro positivo; portanto, altere o sinal e o operador de comparação conforme necessário:

    if (nbits <= 48) {
        /* "Multiply both sides" by -1; this also swaps the
         * comparator.
         */
        i = -i;
        op = _Py_SwappedOp[op];
    }

Agora a função olha para o expoente do flutuador. Lembre-se de que um float pode ser gravado (sinal de ignição) como ^expoente significand * 2 e que o significand representa um número entre 0,5 e 1:

    (void) frexp(i, &exponent);
    if (exponent < 0 || (size_t)exponent < nbits) {
        i = 1.0;
        j = 2.0;
        goto Compare;
    }

Isso verifica duas coisas. Se o expoente for menor que 0, o flutuador será menor que 1 (e, portanto, menor em magnitude que qualquer número inteiro). Ou, se o expoente for menor que o número de bits, wentão temos que, v < |w|já que o significante * 2 ^expoente é menor que 2 ^nbits .

Na falta dessas duas verificações, a função procura ver se o expoente é maior que o número de bits w. Isso mostra que o significante * 2 ^expoente é maior que 2 ^nbits e, portanto v > |w|:

    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

Se essa verificação não for bem-sucedida, sabemos que o expoente da flutuação vé o mesmo que o número de bits no número inteiro w.

A única maneira de comparar os dois valores agora é construir dois novos inteiros Python a partir de ve w. A idéia é descartar a parte fracionária de v, dobrar a parte inteira e adicionar uma. wtambém é duplicado e esses dois novos objetos Python podem ser comparados para fornecer o valor de retorno correto. Usando um exemplo com valores pequenos, 4.65 < 4seria determinado pela comparação (2*4)+1 == 9 < 8 == (2*4)(retornando false).

    {
        double fracpart;
        double intpart;
        PyObject *result = NULL;
        PyObject *one = NULL;
        PyObject *vv = NULL;
        PyObject *ww = w;

        // snip

        fracpart = modf(i, &intpart); // split i (the double that v mapped to)
        vv = PyLong_FromDouble(intpart);

        // snip

        if (fracpart != 0.0) {
            /* Shift left, and or a 1 bit into vv
             * to represent the lost fraction.
             */
            PyObject *temp;

            one = PyLong_FromLong(1);

            temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
            ww = temp;

            temp = PyNumber_Lshift(vv, one);
            vv = temp;

            temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
            vv = temp;
        }
        // snip
    }
}

Por uma questão de brevidade, deixei de lado a verificação de erros e o rastreamento de lixo adicionais que o Python precisa fazer quando cria esses novos objetos. Escusado será dizer que isso adiciona uma sobrecarga adicional e explica por que os valores destacados na pergunta são significativamente mais lentos em comparação do que outros.

Aqui está um resumo das verificações que são executadas pela função de comparação.

Let vSer um float e lançá-lo como um C duplo. Agora, se wtambém é um float:

• Verifique se wé nanou inf. Nesse caso, lide com este caso especial separadamente, dependendo do tipo de w.

• Caso contrário, compare ve wdiretamente por suas representações, enquanto C dobra.

Se wé um número inteiro:

• Extraia os sinais de ve w. Se são diferentes, sabemos ve wsomos diferentes e qual é o maior valor.

• ( Os sinais são os mesmos. ) Verifique se whá bits demais para ser um flutuador (mais que size_t). Se sim, wtem uma magnitude maior que v.

• Verifique se wpossui 48 ou menos bits. Nesse caso, ele pode ser convertido com segurança em um duplo C sem perder a precisão e comparado com v.

• ( wpossui mais de 48 bits. Agora, trataremos wcomo um número inteiro positivo depois de alterar a comparação, conforme apropriado. )

• Considere o expoente do flutuador v. Se o expoente for negativo, vserá menor que 1e, portanto, menor que qualquer número inteiro positivo. Caso wcontrário , se o expoente for menor que o número de bits , deverá ser menor que w.

• Se o expoente de vfor maior que o número de bits, wentão vserá maior que w.

• ( O expoente é igual ao número de bits w. )

• A verificação final. Divida vem partes inteiras e fracionárias. Dobre a parte inteira e adicione 1 para compensar a parte fracionária. Agora dobre o número inteiro w. Compare esses dois novos números inteiros para obter o resultado.

Usando gmpy2 com flutuadores de precisão arbitrários e números inteiros, é possível obter um desempenho de comparação mais uniforme:

~ $ ptipython
Python 3.5.1 |Anaconda 4.0.0 (64-bit)| (default, Dec  7 2015, 11:16:01) 
Type "copyright", "credits" or "license" for more information.

IPython 4.1.2 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: import gmpy2

In [2]: from gmpy2 import mpfr

In [3]: from gmpy2 import mpz

In [4]: gmpy2.get_context().precision=200

In [5]: i1=562949953421000

In [6]: i2=562949953422000

In [7]: f=562949953420000.7

In [8]: i11=mpz('562949953421000')

In [9]: i12=mpz('562949953422000')

In [10]: f1=mpfr('562949953420000.7')

In [11]: f<i1
Out[11]: True

In [12]: f<i2
Out[12]: True

In [13]: f1<i11
Out[13]: True

In [14]: f1<i12
Out[14]: True

In [15]: %timeit f<i1
The slowest run took 10.15 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 441 ns per loop

In [16]: %timeit f<i2
The slowest run took 12.55 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 152 ns per loop

In [17]: %timeit f1<i11
The slowest run took 32.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 269 ns per loop

In [18]: %timeit f1<i12
The slowest run took 36.81 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 231 ns per loop

In [19]: %timeit f<i11
The slowest run took 78.26 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 156 ns per loop

In [20]: %timeit f<i12
The slowest run took 21.24 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 194 ns per loop

In [21]: %timeit f1<i1
The slowest run took 37.61 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 275 ns per loop

In [22]: %timeit f1<i2
The slowest run took 39.03 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 259 ns per loop