python troncare - Perché alcuni confronti in virgola mobile sono quattro volte più lenti di altri?




1 Answers

Un commento nel codice sorgente Python per oggetti float riconosce che:

Il confronto è praticamente un incubo

Questo è particolarmente vero quando si confronta un float con un intero, perché, a differenza dei float, gli interi in Python possono essere arbitrariamente grandi e sono sempre esatti. Provare a convertire il numero intero in un oggetto mobile potrebbe perdere precisione e rendere il confronto impreciso. Provare a lanciare il float su un numero intero non funzionerà perché qualsiasi parte frazionale andrà persa.

Per aggirare questo problema, Python esegue una serie di controlli, restituendo il risultato se uno dei controlli ha esito positivo. Confronta i segni dei due valori, quindi se il numero intero è "troppo grande" per essere un float, quindi confronta l'esponente del float con la lunghezza del numero intero. Se tutti questi controlli falliscono, è necessario costruire due nuovi oggetti Python da confrontare per ottenere il risultato.

Quando si confronta un float v con un intero / lungo w , il caso peggiore è che:

  • v e w hanno lo stesso segno (sia positivo che negativo),
  • il numero intero w ha pochi bit sufficienti da poter essere contenuto nel tipo size_t (tipicamente 32 o 64 bit),
  • il numero intero w ha almeno 49 bit,
  • l'esponente del float v è uguale al numero di bit in w .

E questo è esattamente ciò che abbiamo per i valori nella domanda:

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

Vediamo che 49 è sia l'esponente del float sia il numero di bit nel numero intero. Entrambi i numeri sono positivi e quindi i quattro criteri sopra riportati sono soddisfatti.

La scelta di uno dei valori più grandi (o più piccoli) può modificare il numero di bit del numero intero o il valore dell'esponente e quindi Python è in grado di determinare il risultato del confronto senza eseguire il costoso controllo finale.

Questo è specifico per l'implementazione CPython della lingua.

Il confronto più in dettaglio

La funzione float_richcompare gestisce il confronto tra due valori v e w .

Di seguito è riportata una descrizione dettagliata dei controlli eseguiti dalla funzione. I commenti nel sorgente Python sono in realtà molto utili quando si cerca di capire cosa fa la funzione, quindi li ho lasciati in caso di pertinenza. Ho anche riassunto questi assegni in una lista in fondo alla risposta.

L'idea principale è quella di mappare gli oggetti Python v w due doppi C, i e j appropriati, che possono quindi essere facilmente confrontati per fornire il risultato corretto. Sia Python 2 che Python 3 usano le stesse idee per fare ciò (il primo tratta solo i tipi int e long separatamente).

La prima cosa da fare è controllare che v sia definitivamente un float Python e mapparlo a un doppio C. Successivamente la funzione controlla se w è anche un float e lo mappa su un doppio C C. Questo è lo scenario migliore per la funzione in quanto è possibile saltare tutti gli altri controlli. La funzione controlla anche se v è inf o 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;
    }

Ora sappiamo che se w non ha superato questi controlli, non è un float Python. Ora la funzione controlla se si tratta di un intero Python. Se questo è il caso, il test più semplice è estrarre il segno di v e il segno di w (restituisce 0 se zero, -1 se negativo, 1 se positivo). Se i segni sono diversi, queste sono tutte le informazioni necessarie per restituire il risultato del confronto:

    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 questo controllo fallisce, allora w hanno lo stesso segno.

Il prossimo controllo conta il numero di bit nel numero intero w . Se ha troppi bit allora non può essere considerato come un float e quindi deve essere di dimensioni maggiori rispetto al float 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;
    }

D'altra parte, se il numero intero w ha 48 o meno bit, può tranquillamente trasformarsi in un C double j e confrontato:

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

Da questo punto in poi, sappiamo che w ha 49 o più bit. Sarà conveniente trattare w come numero intero positivo, quindi cambia il segno e l'operatore di confronto secondo necessità:

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

Ora la funzione guarda l'esponente del float. Ricorda che un float può essere scritto (ignorando il segno) come significante e * 2 esponente e che il significato e rappresenta un numero compreso tra 0,5 e 1:

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

Questo controlla due cose. Se l'esponente è minore di 0 allora il float è più piccolo di 1 (e quindi più piccolo di grandezza di qualsiasi intero). Oppure, se l'esponente è inferiore al numero di bit in w allora abbiamo v < |w| dal momento che il significato e * 2 esponente è inferiore a 2 nbits .

In mancanza di questi due controlli, la funzione cerca di vedere se l'esponente è maggiore del numero di bit in w . Questo dimostra che significante e * 2 esponente è maggiore di 2 nbits e quindi v > |w| :

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

Se questo controllo non ha avuto successo, sappiamo che l'esponente del float v è lo stesso del numero di bit nel numero intero w .

L'unico modo in cui i due valori possono essere confrontati ora è di costruire due nuovi numeri interi Python da w . L'idea è di scartare la parte frazionaria di v , raddoppiare la parte intera e quindi aggiungerne una. w è anche raddoppiato e questi due nuovi oggetti Python possono essere confrontati per fornire il valore di ritorno corretto. Usando un esempio con valori piccoli, 4.65 < 4 sarebbe determinato dal confronto (2*4)+1 == 9 < 8 == (2*4) (restituendo falso).

    {
        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
    }
}

Per brevità ho omesso il controllo degli errori aggiuntivo e il tracciamento dei rifiuti che Python deve fare quando crea questi nuovi oggetti. Inutile dire che questo aggiunge un sovraccarico aggiuntivo e spiega perché i valori evidenziati nella domanda sono significativamente più lenti da confrontare rispetto ad altri.

Ecco un riepilogo dei controlli eseguiti dalla funzione di confronto.

Sia v un float e lo lanci come un doppio C. Ora, se w è anche un float:

  • Controlla se w è nan o inf . In tal caso, gestire questo caso speciale separatamente in base al tipo di w .

  • In caso contrario, confrontare w direttamente con le loro rappresentazioni come C raddoppia.

Se w è un numero intero:

  • Estrai i segni di v e w . Se sono diversi allora sappiamo che w sono diversi e quale è il valore maggiore.

  • ( I segni sono gli stessi ) . Controlla se w ha troppi bit per essere un float (più di size_t ). Se è così, w ha una magnitudine maggiore di v .

  • Controlla se w ha 48 o meno bit. Se è così, può essere castato in modo sicuro in una doppia C senza perdere la sua precisione e confrontato con v .

  • ( w ha più di 48 bit. Ora considereremo w come un numero intero positivo dopo aver modificato l'ops di confronto come appropriato ) .

  • Considera l'esponente del float v . Se l'esponente è negativo, v è inferiore a 1 e quindi inferiore a qualsiasi numero intero positivo. Altrimenti, se l'esponente è inferiore al numero di bit in w allora deve essere inferiore a w .

  • Se l'esponente di v è maggiore del numero di bit in w allora v è maggiore di w .

  • ( L'esponente è uguale al numero di bit in w . )

  • Il controllo finale Suddividi v nelle sue parti intere e frazionarie. Raddoppia la parte intera e aggiungi 1 per compensare la parte frazionaria. Ora raddoppiare il numero intero w . Confronta questi due nuovi numeri interi invece per ottenere il risultato.

decimali convertitore

Quando si confrontano i float con gli interi, alcune coppie di valori richiedono molto più tempo per essere valutate rispetto ad altri valori di grandezza simile.

Per esempio:

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

Ma se il float o il numero intero viene reso più piccolo o più grande di una certa quantità, il confronto viene eseguito molto più rapidamente:

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

Cambiare l'operatore di confronto (es. Usando == o > invece) non influenza i tempi in alcun modo evidente.

Questo non è solo legato alla magnitudine, perché il prelievo di valori più grandi o più piccoli può portare a confronti più veloci, quindi sospetto che sia in qualche modo sfortunato il modo in cui i bit si allineano.

Chiaramente, confrontare questi valori è più che abbastanza veloce per la maggior parte dei casi d'uso. Sono semplicemente curioso di sapere perché Python sembra lottare di più con alcune coppie di valori rispetto ad altri.




Related

python performance floating-point cpython python-internals