Perché log2 e log1p sono molto più veloci di log e log10?

Question

Mentre giocare con this question ho notato qualcosa che non potevo spiegare per quanto riguarda la performance relativa np.log2, np.log e np.log10:

In [1]: %%timeit x = np.random.rand(100000) 
    ....: np.log2(x) 
    ....: 
1000 loops, best of 3: 1.31 ms per loop 

In [2]: %%timeit x = np.random.rand(100000) 
np.log(x) 
    ....: 
100 loops, best of 3: 3.64 ms per loop 

In [3]: %%timeit x = np.random.rand(100000) 
np.log10(x) 
    ....: 
100 loops, best of 3: 3.93 ms per loop 

np.log2 è circa 3 volte più veloce di np.log e np.log10. Forse ancor più contro-intuitivo, np.log1p(x), che calcola ln (x + 1), è alla pari con np.log2:

In [4]: %%timeit x = np.random.rand(100000) 
np.log1p(x) 
    ....: 
1000 loops, best of 3: 1.46 ms per loop 

ho ottenuto quasi identiche in tempi v1.10.1 NumPy e v1.8.2.

Esiste una spiegazione intuitiva per queste discrepanze nelle prestazioni di runtime?

Answer 1

Questa è solo una nota, ma più lunga di un commento. A quanto pare questo ha a che fare con la vostra particolare installazione:

import numpy as np 
import numexpr as ne 
x = np.random.rand(100000) 

ottengo lo stesso timing con NumPy 1.10 da Conda e una versione compilata con ICC:

%timeit np.log2(x) 
1000 loops, best of 3: 1.24 ms per loop 

%timeit np.log(x) 
1000 loops, best of 3: 1.28 ms per loop 

ho pensato che potrebbe avere qualcosa a che con la cattura il pacchetto MKL VML, ma sembra che questo è un no:

%timeit ne.evaluate('log(x)') 
1000 loops, best of 3: 218 µs per loop 

sembra che il tuo NumPy installazione è afferrare la sua attuazione log/log2 da due luoghi diversi che è strano.

Answer 2

Ho trovato la tua domanda estremamente interessante, quindi ho trascorso alcune ore a fare un po 'di ricerca; Credo di aver trovato una spiegazione per la differenza di prestazioni come si applica a numeri interi (si Matteo Italia ringraziamo per il messaggio) - Non è chiaro come che il ragionamento può essere esteso ad galleggianti però:

computer utilizzano base 2 - Secondo agli articoli collegati in riferimento, il calcolo di log2 è un processo a 4 processori - quello di log10 richiede di moltiplicare log2 (val) per 1/log2 (10) che aggiunge altri 5 cicli.

L'individuazione di log2 è una questione di finding the index of the least significant bit of a value.(video all'incirca al 23esimo minuto in avanti).

hack bit: Find integer log base 10 of an integer

hack bit: Find the log base 2 of an N-bit integer in O(lg(N))

Il registro numero intero di base 10 viene calcolato prima utilizzando uno dei tecniche sopra per trovare il logaritmo in base 2. In relazione log10 (v) = log2 (v)/log2 (10), dobbiamo moltiplicarlo per 1/log2 (10), che è approssimativamente 1233/4096, o 1233 seguito da uno spostamento a destra di 12. Aggiungere uno è necessario perché IntegerLogBase2 si arrotonda. Infine, poiché il valore t è solo un'approssimazione che può essere disattivata da uno , il valore esatto viene rilevato sottraendo il risultato di v < PowersOf10 [t].

Questo metodo richiede 6 operazioni diverse da IntegerLogBase2. Potrebbe essere accelerato (su macchine con accesso rapido alla memoria) modificando il metodo di ricerca tabella di base di base 2 in modo che le voci contengano ciò che è calcolato per t (ovvero, pre-aggiunta, -mulitply e - cambio). Così facendo, richiederebbe un totale di sole 9 operazioni per trovare la base di log 10, assumendo 4 tabelle (una per ogni byte di v).

Da segnalare: l'uso di sequenze deBruijn Lookup & tecniche bit spostando per calcolare log2 in questo MIT video: Lec 2 | MIT 6.172 Performance Engineering of Software Systems, Fall 2010(video a segno 36 ° minuto in poi).

Da segnalare questo post StackOverflow che dimostra a method to make efficient log2 calculations truly cross platform with C++

Caveat: Non ho controllato il codice sorgente NumPy per verificare che implementa infatti tecniche simili, ma sarebbe sorprendente che non ha fatto. Infatti, dai commenti sotto postale del PO, Fermion Portal hanno controllato:

l'utilizza NumPy math.h da glibc, vedrete la stessa differenza in C/C++, se si utilizza math.h/cmath .h. È possibile trovare il codice sorgente ben commentato per le due funzioni, ad es. ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/… e ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/… - Fermion Portal [9]

Answer 3

Disclaimer: io non sono né credibile né una fonte ufficiale.

Sono quasi certo che qualsiasi implementazione del log sulla funzione base e può essere eseguita alla stessa velocità della funzione log2, perché per convertire uno all'altro è necessaria una singola divisione per una costante. Questo naturalmente presuppone che una singola operazione di divisione sia una piccola frazione degli altri calcoli; che in accurate implementazioni dei logaritmi è vero.

Nella maggior parte dei casi, NumPy utilizza math.h da glibc, vedrete la stessa differenza in C/C++, se si utilizza math.h/cmath.h. Nei commenti, alcune persone osservano le stesse velocità per np.log e np.log2; Sospetto che ciò possa provenire da diverse build/piattaforme.

È possibile trovare il codice sorgente ben commentato per le due funzioni nei file e_log.c, e_log2.c, e_logf.c, e_log2f.c nelle dbl-64/ e flt-32/ sottodirectory di this GitHub repo.

Per doppia precisione, in glibc, la funzione log sta attuando un algo completamente diverso (rispetto al log2) da IBM dal ~ 2001 che è stata inclusa nella loro biblioteca libultim. Mentre log2 è di Sun Microsystems dal 1993 circa. Solo guardando il codice si possono vedere due diverse approssimazioni in fase di implementazione. Al contrario, per la precisione singola, entrambe le funzioni log e log2 sono uguali a prescindere dalla divisione di ln2 nel caso log2, quindi la stessa velocità.

Per ulteriori informazioni sugli algoritmi, le alternative e le discussioni sottostanti su cui includere in glibc in futuro, vedere here.