Perché `(map digitToInt). show` è così veloce?

Question

Conversione non negativo Integer alla sua lista di cifre è comunemente fatto in questo modo:

import Data.Char 

digits :: Integer -> [Int] 
digits = (map digitToInt) . show 

stavo cercando di trovare un modo più diretto per eseguire l'operazione, senza coinvolgere una conversione stringa, ma non riesco per inventare qualcosa di più veloce.

Le cose che ho cercato finora:

La linea di base:

digits :: Int -> [Int] 
digits = (map digitToInt) . show 

ottenuto questo uno da un'altra domanda su StackOverflow:

digits2 :: Int -> [Int] 
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10) 

Cercando di rotolare il mio:

digits3 :: Int -> [Int] 
digits3 = reverse . revDigits3 

revDigits3 :: Int -> [Int] 
revDigits3 n = case divMod n 10 of 
       (0, digit) -> [digit] 
       (rest, digit) -> digit:(revDigits3 rest) 

Questo è stato ispirato da showInt in Numeric:

digits4 n0 = go n0 [] where 
    go n cs 
     | n < 10 = n:cs 
     | otherwise = go q (r:cs) 
     where 
     (q,r) = n `quotRem` 10 

Ora il punto di riferimento. Nota: sto forzando la valutazione usando filter.

λ>:set +s 
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000] 
2400000 
(1.58 secs, 771212628 bytes) 

Questo è il riferimento. Ora, per digits2:

λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000] 
2400000 
(5.47 secs, 1256170448 bytes) 

Ecco 3,46 tempi più lunghi.

λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000] 
2400000 
(7.74 secs, 1365486528 bytes) 

digits3 è 4.89 tempo più lento. Solo per divertimento, ho provato a utilizzare solo revDigits3 ed evitare lo reverse.

λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000] 
2400000 
(8.28 secs, 1277538760 bytes) 

Stranamente, questo è ancora più lento, 5.24 volte più lento.

E l'ultimo:

λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000] 
2400000 
(16.48 secs, 1779445968 bytes) 

Questo è 10.43 tempo più lento.

Ho avuto l'impressione che solo l'utilizzo di aritmetica e contro avrebbe superato qualsiasi cosa implicasse una conversione di stringhe. Apparentemente, c'è qualcosa che non riesco a capire.

Quindi, qual è il trucco? Perché lo digits è così veloce?

Sto usando GHC 6.12.3.

Answer 1

Visto che non posso ancora aggiungere commenti, farò un po 'più di lavoro e analizzerò tutti. Sto mettendo l'analisi in cima; tuttavia, i dati rilevanti sono di seguito. (Nota: tutto questo è fatto anche in 6.12.3 - non ancora GHC 7 magic.)

---

Analisi:

Versione 1: spettacolo è abbastanza buona per interi, in particolare quelli più breve che abbiamo. Rendere le stringhe in realtà tende a essere decente in GHC; tuttavia, la lettura di stringhe e la scrittura di stringhe di grandi dimensioni su file (o stdout, anche se non si vorrebbe farlo) sono il punto in cui il codice può assolutamente eseguire la scansione. Avrei il sospetto che molti dei dettagli alla base del perché questo sia così veloce sono dovuti a intelligenti ottimizzazioni in mostra per Ints.

Versione 2: Questo era il più lento del gruppo quando compilato. Alcuni problemi: il contrario è rigido nel suo argomento. Ciò significa che non si è in grado di eseguire calcoli sulla prima parte dell'elenco mentre si calcolano gli elementi successivi; devi calcolarli tutti, girarli e poi fare i tuoi calcoli (cioè (`mod` 10)) sugli elementi della lista. Anche se questo può sembrare piccolo, può portare a un maggiore utilizzo della memoria (notare anche i 5 GB di memoria heap allocati qui) e calcoli più lenti. (Per farla breve: non utilizzare il contrario.)

Versione 3: Ricordare come ho appena detto di non utilizzare il contrario? Risulta, se lo estrai, questo scende a 1.79s tempo di esecuzione totale - appena più lento della linea di base. L'unico problema qui è che mentre approfondisci il numero, stai costruendo la colonna vertebrale dell'elenco nella direzione sbagliata (essenzialmente, stai andando "nella" lista con la ricorsione, invece che con "accedervi"). la lista).

Versione 4: Questa è un'implementazione molto intelligente. Beneficiate di molte cose carine: per esempio, quotRem dovrebbe usare l'algoritmo euclideo, che è logaritmico nel suo argomento più ampio. (Forse è più veloce, ma non credo che ci sia qualcosa che è più di un fattore costante più veloce di Euclid.) Inoltre, cons off sulla lista come discusso l'ultima volta, in modo che non devi risolvere alcun thunks di lista come vai - la lista è già interamente costruita quando torni indietro per analizzarla. Come puoi vedere, le prestazioni ne traggono vantaggio.

Questo codice era probabilmente il più lento in GHCi perché molte delle ottimizzazioni eseguite con il flag -O3 in GHC si occupavano di creare elenchi più velocemente, mentre GHCi non avrebbe fatto nulla di tutto ciò.

Lezioni: contro il modo in cui a destra in una lista, orologio per severità intermedia che può rallentare calcoli, e fare qualche noia nel guardare le statistiche a grana fine delle prestazioni del codice. Compilati anche con le bandiere -O3: ogni volta che non lo fai, tutte quelle persone che impiegano molte ore a fare in modo che GHC super veloce ottenga grandi occhi da cucciolo.

---

dati:

Ho appena preso tutte le quattro funzioni, li bloccato in un unico .hs file, quindi cambiato, se necessario, in modo da riflettere la funzione in uso. Inoltre, ho superato il limite fino a 5e6, perché in alcuni casi il codice compilato veniva eseguito in meno di mezzo secondo su 1e6 e questo può iniziare a causare problemi di granularità con le misurazioni che stiamo facendo.

Opzioni del compilatore: utilizzare ghc --make -O3 [nome file] .hs per fare in modo che GHC esegua l'ottimizzazione. Effettueremo il dump delle statistiche sull'errore standard usando le cifre + RTS -sstderr.

Dumping a -sstderr ci dà in uscita che assomiglia a questo, nel caso di digits1:

digits1 +RTS -sstderr 
12000000 
    2,885,827,628 bytes allocated in the heap 
     446,080 bytes copied during GC 
      3,224 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 5504 collections,  0 parallel, 0.06s, 0.03s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.61s ( 1.66s elapsed) 
    GC time 0.06s ( 0.03s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 1.67s ( 1.69s elapsed) 

    %GC time  3.7% (1.5% elapsed) 

    Alloc rate 1,795,998,050 bytes per MUT second 

    Productivity 96.3% of total user, 95.2% of total elapsed 

Ci sono tre statistiche chiave qui:

1. memoria totale in uso: solo 1MB mezzi questa versione è molto efficiente in termini di spazio.
2. Tempo totale: 1,61s non significa nulla ora, ma vedremo come appare rispetto alle altre implementazioni.
3. Produttività: questo è solo il 100% meno raccolta dei rifiuti; visto che siamo al 96,3%, ciò significa che non stiamo creando un sacco di oggetti che lasciamo in giro in memoria ..

Va bene, passiamo alla versione 2.

digits2 +RTS -sstderr 
12000000 
    5,512,869,824 bytes allocated in the heap 
     1,312,416 bytes copied during GC 
      3,336 bytes maximum residency (1 sample(s)) 
      13,048 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 10515 collections,  0 parallel, 0.06s, 0.04s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 3.20s ( 3.25s elapsed) 
    GC time 0.06s ( 0.04s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 3.26s ( 3.29s elapsed) 

    %GC time  1.9% (1.2% elapsed) 

    Alloc rate 1,723,838,984 bytes per MUT second 

    Productivity 98.1% of total user, 97.1% of total elapsed 

Bene, quindi stiamo vedendo uno schema interessante.

1. Stessa quantità di memoria utilizzata. Ciò significa che questa è un'implementazione piuttosto buona, anche se potrebbe significare che dobbiamo testare su input di campioni più alti per vedere se possiamo trovare una differenza.
2. Ci vuole il doppio del tempo. Torneremo ad alcune speculazioni sul motivo per cui questo è più tardi.
3. In realtà è leggermente più produttivo, ma dato che GC non è una porzione enorme di entrambi i programmi, questo non ci aiuta in alcun modo significativo.

Versione 3:

digits3 +RTS -sstderr 
12000000 
    3,231,154,752 bytes allocated in the heap 
     832,724 bytes copied during GC 
      3,292 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 6163 collections,  0 parallel, 0.02s, 0.02s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 2.09s ( 2.08s elapsed) 
    GC time 0.02s ( 0.02s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 2.11s ( 2.10s elapsed) 

    %GC time  0.7% (1.0% elapsed) 

    Alloc rate 1,545,701,615 bytes per MUT second 

    Productivity 99.3% of total user, 99.3% of total elapsed 

Va bene, quindi stiamo vedendo alcuni modelli strani.

1. Siamo ancora a 1 MB di memoria totale in uso. Quindi non abbiamo colpito nulla di memoria-inefficiente, che è buono.
2. Non siamo abbastanza a cifre1, ma abbiamo digits2 battere abbastanza facilmente.
3. GC molto piccolo. (Tenete a mente che tutto ciò che oltre il 95% la produttività è molto buono, quindi non siamo in realtà si tratta di qualcosa di troppo importante qui.)

E, infine, la versione 4:

digits4 +RTS -sstderr 
12000000 
    1,347,856,636 bytes allocated in the heap 
     270,692 bytes copied during GC 
      3,180 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 2570 collections,  0 parallel, 0.00s, 0.01s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.09s ( 1.08s elapsed) 
    GC time 0.00s ( 0.01s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 1.09s ( 1.09s elapsed) 

    %GC time  0.0% (0.8% elapsed) 

    Alloc rate 1,234,293,036 bytes per MUT second 

    Productivity 100.0% of total user, 100.5% of total elapsed 

Wowza! Scopriamolo:

1. Siamo ancora a 1 MB totale. Questa è quasi certamente una caratteristica di queste implementazioni, poiché rimangono a 1 MB sugli ingressi di 5e5 e 5e7. Una testimonianza di pigrizia, se vuoi.
2. Abbiamo tagliato circa il 32% del tempo originale, il che è piuttosto impressionante.
3. Sospetto che le percentuali qui riflettano la granularità nel monitoraggio di -sstderr piuttosto che qualsiasi calcolo su particelle superluminali.

Answer 2

Rispondere alla domanda "perché rem invece di mod?" nei commenti.Quando si tratta di valori positivi rem x y === mod x y così l'unica considerazione di nota è la prestazione:

> import Test.QuickCheck 
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y) 

Allora, qual è la performance? Se non avete una buona ragione per non farlo (e di essere pigro non è una buona ragione, né è non sapere Criterion) quindi utilizzare un buon strumento di riferimento, ho usato Criterio:

$ cat useRem.hs 
import Criterion 
import Criterion.Main 

list :: [Integer] 
list = [1..10000] 

main = defaultMain 
     [ bench "mod" (nf (map (`mod` 7)) list) 
     , bench "rem" (nf (map (`rem` 7)) list) 
     ] 

L'esecuzione di questo dimostra rem è misurabile migliore di mod (compilato con -O2):

$ ./useRem 
... 
benchmarking mod 
... 
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950 

benchmarking rem 
... 
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950