Alat untuk menganalisis kinerja program Haskell

Saat menyelesaikan beberapa Masalah Project Euler untuk mempelajari Haskell (jadi saat ini saya seorang pemula) saya menemukan Masalah 12 . Saya menulis solusi (naif) ini:

--Get Number of Divisors of n
numDivs :: Integer -> Integer
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

--Generate a List of Triangular Values
triaList :: [Integer]
triaList =  [foldr (+) 0 [1..n] | n <- [1..]]

--The same recursive
triaList2 = go 0 1
  where go cs n = (cs+n):go (cs+n) (n+1)

--Finds the first triangular Value with more than n Divisors
sol :: Integer -> Integer
sol n = head $ filter (\x -> numDivs(x)>n) triaList2

Solusi untuk n=500 (sol 500)ini sangat lambat (berjalan selama lebih dari 2 jam sekarang), jadi saya bertanya-tanya bagaimana cara mengetahui mengapa solusi ini sangat lambat. Apakah ada perintah yang memberitahu saya di mana sebagian besar waktu komputasi dihabiskan sehingga saya tahu bagian mana dari program haskell saya yang lambat? Sesuatu seperti profiler sederhana.

Untuk membuatnya jelas, aku tidak meminta untuk solusi yang lebih cepat tetapi untuk cara untuk menemukan solusi ini. Bagaimana Anda memulai jika Anda tidak memiliki pengetahuan haskell?

Saya mencoba menulis dua triaListfungsi tetapi tidak menemukan cara untuk menguji mana yang lebih cepat, jadi di sinilah masalah saya dimulai.

Terima kasih

bagaimana mencari tahu mengapa solusi ini sangat lambat. Apakah ada perintah yang memberi tahu saya di mana sebagian besar waktu komputasi dihabiskan sehingga saya tahu bagian mana dari program haskell saya yang lambat?

Tepat! GHC menyediakan banyak alat yang sangat baik, termasuk:

• statistik runtime
• pembuatan profil waktu
• profil tumpukan
• analisis benang
• analisis inti.
• pembandingan komparatif
• Penyetelan GC

Tutorial tentang penggunaan profil ruang dan waktu adalah bagian dari Real World Haskell .

Statistik GC

Pertama, pastikan Anda melakukan kompilasi dengan ghc -O2. Dan Anda mungkin memastikan ini adalah GHC modern (misalnya GHC 6.12.x)

Hal pertama yang dapat kita lakukan adalah memeriksa bahwa pengumpulan sampah bukanlah masalahnya. Jalankan program Anda dengan + RTS -s

$ time ./A +RTS -s
./A +RTS -s 
749700
   9,961,432,992 bytes allocated in the heap
       2,463,072 bytes copied during GC
          29,200 bytes maximum residency (1 sample(s))
         187,336 bytes maximum slop
               **2 MB** total memory in use (0 MB lost due to fragmentation)

  Generation 0: 19002 collections,     0 parallel,  0.11s,  0.15s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   13.15s  ( 13.32s elapsed)
  GC    time    0.11s  (  0.15s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   13.26s  ( 13.47s elapsed)

  %GC time       **0.8%**  (1.1% elapsed)

  Alloc rate    757,764,753 bytes per MUT second

  Productivity  99.2% of total user, 97.6% of total elapsed

./A +RTS -s  13.26s user 0.05s system 98% cpu 13.479 total

Yang sudah memberi kita banyak informasi: Anda hanya memiliki tumpukan 2 juta, dan GC membutuhkan waktu 0,8%. Jadi tidak perlu khawatir alokasi itu masalahnya.

Profil Waktu

Mendapatkan profil waktu untuk program Anda sangatlah mudah: kompilasi dengan -prof -auto-all

 $ ghc -O2 --make A.hs -prof -auto-all
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

Dan, untuk N = 200:

$ time ./A +RTS -p                   
749700
./A +RTS -p  13.23s user 0.06s system 98% cpu 13.547 total

yang membuat file, A.prof, berisi:

    Sun Jul 18 10:08 2010 Time and Allocation Profiling Report  (Final)

       A +RTS -p -RTS

    total time  =     13.18 secs   (659 ticks @ 20 ms)
    total alloc = 4,904,116,696 bytes  (excludes profiling overheads)

COST CENTRE          MODULE         %time %alloc

numDivs            Main         100.0  100.0

Menunjukkan bahwa semua waktu Anda dihabiskan di numDivs, dan ini juga merupakan sumber dari semua alokasi Anda.

Profil Heap

Anda juga bisa mendapatkan rincian alokasi tersebut, dengan menjalankan + RTS -p -hy, yang membuat A.hp, yang dapat Anda lihat dengan mengonversinya menjadi file postscript (hp2ps -c A.hp), menghasilkan:

yang memberi tahu kita bahwa tidak ada yang salah dengan penggunaan memori Anda: ia mengalokasikan dalam ruang yang konstan.

Jadi masalah Anda adalah kompleksitas algoritmik numDivs:

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

Perbaiki itu, yang 100% dari waktu berjalan Anda, dan yang lainnya mudah.

Optimasi

Ekspresi ini adalah kandidat yang baik untuk pengoptimalan fusi aliran , jadi saya akan menulis ulang untuk menggunakan Data.Vector , seperti ini:

numDivs n = fromIntegral $
    2 + (U.length $
        U.filter (\x -> fromIntegral n `rem` x == 0) $
        (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))

Yang harus digabungkan menjadi satu loop tanpa alokasi heap yang tidak perlu. Artinya, versi tersebut akan memiliki kompleksitas yang lebih baik (berdasarkan faktor konstan) daripada versi daftar. Anda dapat menggunakan alat ghc-core (untuk pengguna tingkat lanjut) untuk memeriksa kode perantara setelah pengoptimalan.

Menguji ini, ghc -O2 --make Z.hs

$ time ./Z     
749700
./Z  3.73s user 0.01s system 99% cpu 3.753 total

Jadi itu mengurangi waktu berjalan untuk N = 150 sebesar 3,5x, tanpa mengubah algoritme itu sendiri.

Kesimpulan

Masalah Anda adalah numDivs. Ini adalah 100% dari waktu berjalan Anda, dan memiliki kerumitan yang mengerikan. Pikirkan tentang numDivs, dan bagaimana, misalnya, untuk setiap N Anda menghasilkan [2 .. n div2 + 1] N kali. Cobalah mengingatnya, karena nilainya tidak berubah.

Untuk mengukur fungsi mana yang lebih cepat, pertimbangkan untuk menggunakan kriteria , yang akan memberikan informasi yang kuat secara statistik tentang peningkatan sub-mikrodetik dalam waktu berjalan.

Tambahan

Karena numDivs adalah 100% waktu berjalan Anda, menyentuh bagian lain dari program tidak akan membuat banyak perbedaan, namun, untuk tujuan pedagogis, kami juga dapat menulis ulang menggunakan fusi aliran.

Kami juga dapat menulis ulang trialList, dan mengandalkan fusion untuk mengubahnya menjadi loop yang Anda tulis dengan tangan di trialList2, yang merupakan fungsi "pemindaian awalan" (alias scanl):

triaList = U.scanl (+) 0 (U.enumFrom 1 top)
    where
       top = 10^6

Demikian pula untuk sol:

sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList

Dengan waktu berjalan keseluruhan yang sama, tetapi kode yang sedikit lebih bersih.

Jawaban Don sangat bagus tanpa menjadi spoiler dengan memberikan solusi langsung untuk masalah tersebut.
Disini saya ingin menyarankan sedikit alat yang saya tulis baru-baru ini. Ini menghemat waktu Anda untuk menulis anotasi SCC secara manual saat Anda menginginkan profil yang lebih detail daripada default ghc -prof -auto-all. Selain itu warna-warni!

Berikut contoh kode yang Anda berikan (*), hijau tidak masalah, merah lambat:

Sepanjang waktu berjalan dalam membuat daftar pembagi. Ini menyarankan beberapa hal yang dapat Anda lakukan:
1. Percepat pemfilteran n rem x == 0, tetapi karena ini adalah fungsi bawaan, mungkin sudah cepat.
2. Buat daftar yang lebih pendek. Anda telah melakukan sesuatu ke arah itu dengan memeriksa hanya sampai n quot 2.
3. Buang pembuatan daftar sepenuhnya dan gunakan beberapa matematika untuk mendapatkan solusi yang lebih cepat. Ini adalah cara yang biasa untuk masalah proyek Euler.

(*) Saya mendapatkan ini dengan meletakkan kode Anda dalam file bernama eu13.hs, menambahkan fungsi utama main = print $ sol 90. Lalu lari visual-prof -px eu13.hs eu13dan hasilnya masuk eu13.hs.html.

Catatan terkait Haskell: triaList2tentu saja lebih cepat daripada triaListkarena yang terakhir melakukan banyak perhitungan yang tidak perlu. Ini akan membutuhkan waktu kuadrat untuk menghitung n elemen pertama triaList, tapi linier untuk triaList2. Ada cara lain yang elegan (dan efisien) untuk menentukan daftar nomor segitiga malas yang tak terbatas:

triaList = 1 : zipWith (+) triaList [2..]

Catatan terkait matematika: tidak perlu memeriksa semua pembagi hingga n / 2, cukup memeriksa hingga akar (n).

Anda dapat menjalankan program Anda dengan tanda untuk mengaktifkan pembuatan profil waktu. Sesuatu seperti ini:

./program +RTS -P -sprogram.stats -RTS

Itu harus menjalankan program dan menghasilkan file bernama program.stats yang akan memiliki berapa banyak waktu yang dihabiskan di setiap fungsi. Anda dapat menemukan informasi lebih lanjut tentang membuat profil dengan GHC di panduan pengguna GHC . Untuk pembandingan, ada pustaka Kriteria. Saya menemukan entri blog ini memiliki pengantar yang berguna.