Warum `(Karte digitToInt). show` ist so schnell?

StackOverflow https://stackoverflow.com/questions/4841078

Frage

Konvertieren von nicht-negativen Integer auf die Liste der Stellen häufig wie dies geschehen ist: 

import Data.Char

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

Ich habe versucht, einen direkteren Weg zu finden, um die Aufgabe auszuführen, ohne eine String Umwandlung beteiligt, aber ich bin nicht in der Lage, mit etwas schneller zu entwickeln.

Dinge, die ich habe bisher versucht:

Die Basislinie: 

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

Got dieser von einer anderen Frage auf Stackoverflow: 

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

Der Versuch, meine eigene Rolle: 

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

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

Dieses von showInt in Numeric inspiriert wurde: 

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

Nun ist die Benchmark. . Hinweis: Ich zwinge die Auswertung filter mit 

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

Dies ist die Referenz. Jetzt für digits2: 

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

Das 3,46 mal länger. 

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

digits3 heißt 4,89 Zeit langsamer. Just for fun, habe ich versucht, nur revDigits3 verwenden und die reverse zu vermeiden. 

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

Seltsam, das ist noch langsamer, 5,24 mal langsamer.

Und die letzte: 

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

Dies ist 10,43 Zeit langsamer.

Ich habe den Eindruck, dass nur Arithmetik und Nachteile mit etwas würde übertrifft eine Zeichenfolge Umwandlung beteiligt ist. Offenbar gibt etwas kann ich nicht begreifen.

Also, was ist der Trick? Warum ist digits so schnell?

Ich bin mit GHC 6.12.3.

War es hilfreich?

Lösung

Da ich Kommentare noch nicht hinzufügen können, ich werde ein wenig tun, etwas mehr Arbeit und nur alle von ihnen analysieren. Ich stelle die Analyse an der Spitze; Jedoch werden die entsprechenden Daten unten. (Anmerkung:. All dies wird auch in 6.12.3 getan - keine Magie GHC 7 noch)

Analyse:

Version 1: Show ist ziemlich gut für ints, vor allem diejenigen, so kurz wie wir haben. Herstellung von Saiten neigt eigentlich anständig in GHC zu sein; aber das Lesen in Strings und große Strings, um Dateien zu schreiben (oder stdout, obwohl Sie das nicht tun wollen), wo der Code absolut kriechen. Ich würde vermuten, dass viele der Details hinter warum dies so schnell durch sind clevere Optimierungen innerhalb Show für Ints.

Version 2: Dieser war der langsamste des Bundes, wenn zusammengestellt. Einige Probleme: Reverse ist streng in seiner Argumentation. das bedeutet, was ist, dass Sie nicht von der Möglichkeit profitieren ausführen Berechnungen auf dem ersten Teil der Liste, während Sie die nächsten Elemente sind die Berechnung; Sie haben sie alle, drehen sie, zu berechnen und dann Berechnungen tun (nämlich ( `mod` 10)) auf den Elementen der Liste. Während diese klein erscheinen mag, kann es zu einer größeren Speichernutzung (beachten Sie die 5 GB Heap-Speicher auch hier zugeordnet) führen und langsamer Berechnungen. (Lange Rede kurzer Sinn:. Nicht umgekehrt verwenden)

Version 3: Denken Sie daran, wie ich gerade gesagt habe nicht umgekehrt verwenden? Es stellte sich heraus, wenn man es aus, dieses ein Tropfen auf 1.79s Gesamtausführungszeit - kaum langsamer als die Basislinie. Das einzige Problem dabei ist, dass, wie Sie tiefer in die Zahl gehen, ich ist das Rückgrat der Liste in der falschen Richtung Aufbau (im Wesentlichen sind Sie „in“ die Liste mit Rekursion consing, im Gegensatz zu consing „auf“ die folgende Liste).

Version 4: Dies ist eine sehr kluge Umsetzung. Sie profitieren von mehreren schönen Dingen: Zum einen, quotRem den euklidischen Algorithmus verwendet werden soll, die in seinem größeren Argumente logarithmisch ist. (Vielleicht ist es schneller, aber ich glaube nicht, dass es etwas gibt, das mehr ist als ein konstanter Faktor schneller als Euklid.) Des Weiteren Sie cons auf der Liste wie besprochen letzte Mal, so dass Sie keine Liste Thunks nicht, wie Sie lösen müssen gehen - wird die Liste bereits vollständig aufgebaut, wenn Sie zurückkommen, um es zu analysieren. Wie Sie sehen können, von dieser die Leistungsvorteile.

Dieser Code wurde wahrscheinlich das langsamste in GHCi, weil viele der Optimierungen mit dem O3-Flag in GHC Deal durchgeführt Listen mit schneller zu machen, während GHCi würde irgendetwas davon nicht tun.

Lektionen: Nachteile der richtige Weg, auf eine Liste, Uhr für die Zwischen Strenge, die Berechnungen verlangsamen kann, und einige Lauferei tun in Blick auf die feinkörnig Spiel Leistung Ihres Codes. kompiliert auch mit den O3 Fahnen:., wenn Sie dies nicht tun, all jenen Menschen, die viele Stunden setzten in der Herstellung GHC superschnelle große ol‘Welpen Augen, die Sie bekommen

Daten:

Ich habe gerade alle vier Funktionen, steckte sie in eine .hs Datei und dann geändert, wie notwendig, um die Funktion in Gebrauch zu reflektieren. Außerdem stieß ich Ihr Limit 5E6, denn in einigen Fällen Code kompiliert in weniger als einer halben Sekunde auf 1e6 laufen würde, und dies auf Grund Granularität Probleme mit den Messungen machen wir beginnen können.

Compiler-Optionen: Verwendung ghc --make O3 [Dateiname] .hs haben GHC einige Optimierungen tun. Wir werden Dump Statistiken Standardfehler mit Ziffern + RTS -sstderr .

zu -sstderr Dumping gibt uns Ausgabe, dass wie folgt aussieht, im Fall von 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

Es gibt drei wichtige Statistiken hier:

  1. Gesamtspeicher im Einsatz:. Nur 1MB bedeutet, diese Version ist sehr platzspar
  2. Gesamtzeit:. 1.61s Mittel nichts mehr, aber wir werden sehen, wie es aussieht, gegen die anderen Implementierungen
  3. Effizienz: Dies ist nur 100% minus Mülleinsammlungs; da wir bei 96,3% sind this bedeutet, dass wir nicht eine Menge von Objekten zu schaffen, dass wir im Speicher liegen lassen ..

In Ordnung, lassen Sie uns bewegen auf Version 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

In Ordnung, so dass wir ein interessantes Muster sind zu sehen.

  1. Same Menge des verwendeten Speichers. Dies bedeutet, dass es sich um eine ziemlich gute Umsetzung, obwohl es könnte bedeuten, dass wir zu Test auf höheren Proben Eingänge müssen zu sehen, ob wir einen Unterschied finden.
  2. Es dauert doppelt so lang. Wir werden zu einem gewissen Spekulationen zurückkommen, warum dies später ist.
  3. Es ist eigentlich etwas produktive, aber wenn man bedenkt, dass GC ist nicht ein großer Teil von jedem Programm das uns nicht helfen, etwas von Bedeutung.

Version 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

In Ordnung, so dass wir einige seltsame Muster sind zu sehen.

  1. Wir sind immer noch auf 1 MB Gesamtspeicher im Einsatz. Also wir haben nichts speicher ineffizient getroffen, was gut ist.
  2. Wir sind nicht ganz auf digits1, aber wir haben digits2 Beat ziemlich leicht einsehen.
  3. Sehr wenig GC. (Beachten Sie, dass etwas mehr als 95% der Produktivität ist sehr gut, so dass wir nicht wirklich mit etwas zu groß hier zu tun.)

Und schließlich, Version 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! Lassen Sie uns brechen sie:

  1. Wir sind immer noch auf 1 MB insgesamt. Dies ist fast sicher ein Merkmal dieser Implementierungen, wie sie bei 1MB an den Eingängen von 5e5 und 5E7 bleiben. Ein Beweis für Faulheit, wenn man so will.
  2. Wir schneiden etwa 32% unserer ursprünglichen Zeit ab, was ziemlich beeindruckend ist.
  3. Ich vermute, dass die hier Prozentsätze die Granularität reflektieren in -sstderr ist die Überwachung eher als jede Berechnung auf superluminal Partikel.

Andere Tipps

Die Beantwortung der Frage „warum rem statt mod?“ in den Kommentaren. Wenn mit positiven Werten rem x y === mod x y so die einzige Überlegung Banknoten- Umgang Leistung: 

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

Also, was ist die Leistung? Es sei denn, Sie einen guten Grund, nicht zu (und faul ist kein guter Grund, weder ist nicht Criterion zu wissen) haben dann eine gute Benchmark-Tool verwenden, habe ich Kriterium: 

$ 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)
        ]

Ausführen dieses zeigt rem ist messbar besser als mod (mit -O2 kompiliert): 

$ ./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
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top