Optimalisasi apa yang diharapkan GHC lakukan dengan andal?

GHC memiliki banyak optimasi yang dapat dilakukan, tetapi saya tidak tahu apa itu semua, atau seberapa besar kemungkinan mereka akan dilakukan dan dalam keadaan apa.

Pertanyaan saya adalah: transformasi apa yang dapat saya harapkan untuk diterapkan setiap waktu, atau hampir seperti itu? Jika saya melihat sepotong kode yang akan sering dieksekusi (dievaluasi) dan pikiran pertama saya adalah "hmm, mungkin saya harus mengoptimalkan itu", dalam hal mana seharusnya pikiran kedua saya menjadi, "bahkan tidak memikirkannya, GHC mendapatkan ini "?

Saya sedang membaca makalah Stream Fusion: Dari Daftar ke Streaming ke Nothing at All , dan teknik yang mereka gunakan untuk menulis ulang pemrosesan daftar ke dalam bentuk berbeda yang optimalisasi normal GHC kemudian andalkan dioptimalkan menjadi loop sederhana adalah hal baru bagi saya. Bagaimana saya bisa tahu ketika program saya sendiri memenuhi syarat untuk optimasi semacam itu?

Ada beberapa informasi dalam manual GHC, tetapi hanya sebagian dari jalan menuju menjawab pertanyaan.

EDIT: Saya mulai hadiah. Apa yang saya inginkan adalah daftar transformasi tingkat rendah seperti lambda / let / case-floating, tipe / konstruktor / fungsi argumen spesialisasi, analisis ketat dan unboxing, pekerja / pembungkus, dan apa pun GHC signifikan yang tidak saya tinggalkan , bersama dengan penjelasan dan contoh kode input dan output, dan ilustrasi idealnya situasi ketika efek total lebih dari jumlah bagian-bagiannya. Dan idealnya disebutkan kapan transformasi tidakterjadi. Saya tidak mengharapkan penjelasan panjang novel dari setiap transformasi, beberapa kalimat dan contoh kode satu-baris sebaris bisa cukup (atau tautan, jika tidak sampai dua puluh halaman makalah ilmiah), selama gambaran besarnya adalah jelas pada akhir itu. Saya ingin dapat melihat sepotong kode dan dapat membuat tebakan yang baik tentang apakah itu akan dikompilasi ke loop ketat, atau mengapa tidak, atau apa yang harus saya ubah untuk membuatnya. (Saya tidak terlalu tertarik di sini dalam kerangka kerja optimasi besar seperti aliran fusi (saya baru saja membaca makalah tentang itu); lebih pada jenis pengetahuan yang dimiliki orang-orang yang menulis kerangka kerja ini.)

Halaman GHC Trac ini juga menjelaskan lintasan dengan cukup baik. Halaman ini menjelaskan urutan pengoptimalan, seperti mayoritas Wiki Trac, sudah ketinggalan zaman.

Untuk spesifiknya, hal terbaik yang harus dilakukan mungkin adalah dengan melihat bagaimana suatu program spesifik dikompilasi. Cara terbaik untuk melihat optimasi apa yang sedang dilakukan adalah mengkompilasi program secara lisan, menggunakan -vflag. Sebagai contoh, potongan Haskell pertama yang dapat saya temukan di komputer saya:

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
         ms_mod = main:Main,
         ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
                            import Control.Concurrent, import System.Environment]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting: 
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
   [DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

Melihat dari yang pertama *** Simplifier:ke yang terakhir, di mana semua fase optimasi terjadi, kami melihat cukup banyak.

Pertama-tama, Simplifier berjalan di antara hampir semua fase. Ini membuat menulis banyak lintasan lebih mudah. Misalnya, ketika menerapkan banyak optimasi, mereka hanya membuat aturan penulisan ulang untuk menyebarkan perubahan daripada harus melakukannya secara manual. Penyederhanaan mencakup sejumlah optimasi sederhana, termasuk inlining dan fusi. Keterbatasan utama dari ini yang saya tahu adalah bahwa GHC menolak untuk sebaris fungsi rekursif, dan bahwa segala sesuatu harus dinamai dengan benar agar fusi bekerja.

Selanjutnya, kami melihat daftar lengkap semua optimasi yang dilakukan:

• Mengkhususkan

  Ide dasar spesialisasi adalah untuk menghapus polimorfisme dan kelebihan dengan mengidentifikasi tempat-tempat di mana fungsi dipanggil dan membuat versi fungsi yang bukan polimorfik - mereka khusus untuk jenis yang mereka panggil. Anda juga dapat memberi tahu kompiler untuk melakukan ini dengan SPECIALISEpragma. Sebagai contoh, ambil fungsi faktorial:

  fac :: (Num a, Eq a) => a -> a
  fac 0 = 1
  fac n = n * fac (n - 1)

  Karena kompiler tidak mengetahui properti dari perkalian yang akan digunakan, kompiler tidak dapat mengoptimalkan ini sama sekali. Namun, jika melihat bahwa itu digunakan pada Int, sekarang dapat membuat versi baru, hanya berbeda dalam jenis:

  fac_Int :: Int -> Int
  fac_Int 0 = 1
  fac_Int n = n * fac_Int (n - 1)

  Selanjutnya, aturan yang disebutkan di bawah ini dapat diaktifkan, dan Anda berakhir dengan sesuatu yang bekerja pada kotak un Int, yang jauh lebih cepat daripada yang asli. Cara lain untuk melihat spesialisasi adalah aplikasi parsial pada kamus tipe kelas dan variabel tipe.

  The sumber di sini memiliki beban catatan di dalamnya.

• Mengapung

  EDIT: Saya rupanya salah paham tentang ini sebelumnya. Penjelasan saya telah sepenuhnya berubah.

  Ide dasar dari ini adalah untuk memindahkan perhitungan yang tidak boleh diulang dari fungsi. Sebagai contoh, misalkan kita memiliki ini:

  \x -> let y = expensive in x+y

  Dalam lambda di atas, setiap kali fungsi dipanggil, ydihitung ulang. Fungsi yang lebih baik, yang menghasilkan mengambang, adalah

  let y = expensive in \x -> x+y

  Untuk memfasilitasi proses, transformasi lain dapat diterapkan. Misalnya, ini terjadi:

   \x -> x + f 2
   \x -> x + let f_2 = f 2 in f_2
   \x -> let f_2 = f 2 in x + f_2
   let f_2 = f 2 in \x -> x + f_2

  Sekali lagi, perhitungan berulang disimpan.

  The sumber sangat mudah dibaca dalam kasus ini.

  Saat ini ikatan antara dua lambda yang berdekatan tidak melayang. Misalnya, ini tidak terjadi:

  \x y -> let t = x+x in ...

  pergi ke

   \x -> let t = x+x in \y -> ...

• Mengapung ke dalam

  Mengutip kode sumber,

  Tujuan utama floatInwardsmelayang ke cabang-cabang kasing, sehingga kami tidak mengalokasikan barang-barang, menyimpannya di tumpukan, dan kemudian menemukan bahwa mereka tidak diperlukan di cabang yang dipilih.

  Sebagai contoh, misalkan kita memiliki ungkapan ini:

  let x = big in
      case v of
          True -> x + 1
          False -> 0

  Jika vdievaluasi False, kemudian dengan mengalokasikan x, yang mungkin merupakan pukulan besar, kami telah membuang-buang waktu dan ruang. Mengambang ke dalam memperbaiki ini, menghasilkan ini:

  case v of
      True -> let x = big in x + 1
      False -> let x = big in 0

  , yang kemudian diganti oleh penyederhanaan dengan

  case v of
      True -> big + 1
      False -> 0

  Makalah ini , meskipun membahas topik lain, memberikan pengantar yang cukup jelas. Perhatikan bahwa terlepas dari nama mereka, mengambang di dan mengambang tidak masuk dalam loop tak terbatas karena dua alasan:

  1. Float in floats memungkinkan casepernyataan, sementara float out berkaitan dengan fungsi.
  2. Ada urutan berlalu yang pasti, jadi mereka tidak boleh bergantian tanpa batas.

• Analisis permintaan

  Analisis permintaan, atau analisis ketat kurang dari transformasi dan lebih, seperti namanya, dari sebuah jalur pengumpulan informasi. Kompiler menemukan fungsi yang selalu mengevaluasi argumen mereka (atau setidaknya beberapa di antaranya), dan meneruskan argumen tersebut menggunakan nilai-panggilan-alih-alih, panggilan-berdasarkan-kebutuhan. Karena Anda dapat menghindari biaya overhead thunks, ini seringkali jauh lebih cepat. Banyak masalah kinerja di Haskell muncul dari kegagalan pass ini, atau kode tidak cukup ketat. Contoh sederhana adalah perbedaan antara menggunakan foldr,foldl danfoldl'untuk menjumlahkan daftar bilangan bulat - yang pertama menyebabkan stack overflow, yang kedua menyebabkan overflow tumpukan, dan yang terakhir berjalan dengan baik, karena ketatnya. Ini mungkin yang termudah untuk dipahami dan didokumentasikan dengan baik dari semua ini. Saya percaya bahwa polimorfisme dan kode CPS sering mengalahkan ini.

• Bungkus pekerja terikat

  Ide dasar transformasi pekerja / pembungkus adalah melakukan loop ketat pada struktur sederhana, mengubah ke dan dari struktur itu di ujungnya. Misalnya, ambil fungsi ini, yang menghitung faktorial suatu angka.

  factorial :: Int -> Int
  factorial 0 = 1
  factorial n = n * factorial (n - 1)

  Menggunakan definisi Intdalam GHC, kami punya

  factorial :: Int -> Int
  factorial (I# 0#) = I# 1#
  factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
      I# down# -> down#)

  Perhatikan bagaimana kode ini tercakup dalam I#s? Kami dapat menghapusnya dengan melakukan ini:

  factorial :: Int -> Int
  factorial (I# n#) = I# (factorial# n#)
  
  factorial# :: Int# -> Int#
  factorial# 0# = 1#
  factorial# n# = n# *# factorial# (n# -# 1#)

  Meskipun contoh spesifik ini bisa juga dilakukan oleh SpecConstr, transformasi pekerja / pembungkus sangat umum dalam hal-hal yang dapat dilakukannya.

• Sub-ekspresi umum

  Ini adalah optimasi lain yang sangat sederhana yang sangat efektif, seperti analisis ketat. Ide dasarnya adalah bahwa jika Anda memiliki dua ekspresi yang sama, mereka akan memiliki nilai yang sama. Misalnya, jika fibmerupakan kalkulator angka Fibonacci, CSE akan berubah

  fib x + fib x

  ke

  let fib_x = fib x in fib_x + fib_x

  yang memotong perhitungan menjadi dua. Sayangnya, ini kadang-kadang dapat menghalangi optimisasi lainnya. Masalah lain adalah bahwa kedua ekspresi harus berada di tempat yang sama dan bahwa keduanya harus sama secara sintaksis , tidak sama dengan nilainya. Misalnya, CSE tidak akan menjalankan kode berikut tanpa sejajar dengan sekelompok:

  x = (1 + (2 + 3)) + ((1 + 2) + 3)
  y = f x
  z = g (f x) y

  Namun, jika Anda mengkompilasi melalui llvm, Anda mungkin mendapatkan beberapa dari ini, karena pass Penomoran Nilai Global-nya.

• Kasus pembebasan

  Ini tampaknya merupakan transformasi yang sangat terdokumentasi, selain fakta bahwa hal itu dapat menyebabkan ledakan kode. Ini adalah versi kecil dari dokumentasi kecil yang saya temukan: diformat ulang (dan sedikit ditulis ulang):

  Modul ini berjalan Core, dan mencari casevariabel gratis. Kriterianya adalah: jika ada casevariabel bebas pada rute ke panggilan rekursif, maka panggilan rekursif diganti dengan pembukaan. Misalnya, dalam

  f = \ t -> case v of V a b -> a : f t

  bagian dalam fdiganti. untuk membuat

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t

  Perhatikan perlunya membayangi. Menyederhanakan, kita dapatkan

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)

  Ini adalah kode yang lebih baik, karena agratis di dalam batin letrec, daripada perlu proyeksi dari v. Perhatikan bahwa ini berkaitan dengan variabel bebas , tidak seperti SpecConstr, yang berkaitan dengan argumen yang bentuknya diketahui.

  Lihat di bawah untuk informasi lebih lanjut tentang SpecConstr.

• SpecConstr - ini mengubah program seperti

  f (Left x) y = somthingComplicated1
  f (Right x) y = somethingComplicated2

  ke

  f_Left x y = somethingComplicated1
  f_Right x y = somethingComplicated2
  
  {-# INLINE f #-}
  f (Left x) = f_Left x
  f (Right x) = f_Right x

  Sebagai contoh tambahan, ambil definisi ini dari last:

  last [] = error "last: empty list"
  last (x:[]) = x
  last (x:x2:xs) = last (x2:xs)

  Kami pertama-tama mengubahnya menjadi

  last_nil = error "last: empty list"
  last_cons x [] = x
  last_cons x (x2:xs) = last (x2:xs)
  
  {-# INLINE last #-}
  last [] = last_nil
  last (x : xs) = last_cons x xs

  Selanjutnya, penyederhanaan berjalan, dan kita miliki

  last_nil = error "last: empty list"
  last_cons x [] = x
  last_cons x (x2:xs) = last_cons x2 xs
  
  {-# INLINE last #-}
  last [] = last_nil
  last (x : xs) = last_cons x xs

  Perhatikan bahwa program sekarang lebih cepat, karena kita tidak berulang kali bertinju dan menghapus kotak bagian depan daftar. Perhatikan juga bahwa inlining sangat penting, karena memungkinkan definisi baru yang lebih efisien digunakan, serta membuat definisi rekursif menjadi lebih baik.

  SpecConstr dikendalikan oleh sejumlah heuristik. Yang disebutkan di koran adalah sebagai berikut:

  1. Lambda itu eksplisit dan aritynya a.
  2. Sisi kanan adalah "cukup kecil," sesuatu yang dikendalikan oleh sebuah bendera.
  3. Fungsi ini bersifat rekursif, dan panggilan khusus digunakan di sisi kanan.
  4. Semua argumen ke fungsi hadir.
  5. Setidaknya salah satu argumen adalah aplikasi konstruktor.
  6. Argumen itu dianalisis kasus di suatu tempat dalam fungsi.

  Namun, heuristik hampir pasti berubah. Bahkan, makalah ini menyebutkan heuristik keenam alternatif:

  Mengkhususkan diri pada argumen xhanya jika xini hanya diteliti oleh case, dan tidak diteruskan ke fungsi biasa, atau dikembalikan sebagai bagian dari hasilnya.

Ini adalah file yang sangat kecil (12 baris) dan jadi mungkin tidak memicu banyak optimasi (meskipun saya pikir itu semua). Ini juga tidak memberi tahu Anda mengapa ia mengambil lintasan itu dan mengapa ia menempatkannya dalam urutan itu.

Kemalasan

Ini bukan "optimisasi kompiler", tetapi ini sesuatu yang dijamin oleh spesifikasi bahasa, sehingga Anda selalu dapat mengandalkannya. Pada dasarnya, ini berarti bahwa pekerjaan tidak dilakukan sampai Anda "melakukan sesuatu" dengan hasilnya. (Kecuali jika Anda melakukan salah satu dari beberapa hal untuk mematikan kemalasan dengan sengaja.)

Ini, jelas, adalah seluruh topik dalam dirinya sendiri, dan SO sudah punya banyak pertanyaan dan jawaban tentang hal itu.

Dalam pengalaman saya yang terbatas, membuat kode Anda terlalu malas atau terlalu ketat memiliki penalti kinerja yang jauh lebih besar (dalam waktu dan ruang) daripada hal-hal lain yang akan saya bicarakan ...

Analisis keketatan

Kemalasan adalah tentang menghindari pekerjaan kecuali jika itu perlu. Jika kompilator dapat menentukan bahwa hasil yang diberikan akan "selalu" diperlukan, maka tidak akan repot menyimpan perhitungan dan melakukannya nanti; itu hanya akan melakukannya secara langsung, karena itu lebih efisien. Ini disebut "analisis ketat".

Gotcha, jelas, adalah bahwa kompiler tidak selalu dapat mendeteksi kapan sesuatu dapat dibuat ketat. Terkadang Anda perlu memberi sedikit kompiler petunjuk. (Saya tidak mengetahui cara mudah untuk menentukan apakah analisis ketelitian telah melakukan apa yang Anda pikirkan, selain mengarungi keluaran Core.)

Sebaris

Jika Anda memanggil suatu fungsi, dan kompiler dapat mengetahui fungsi mana yang Anda panggil, ia mungkin mencoba untuk "inline" fungsi itu - yaitu, untuk mengganti panggilan fungsi dengan salinan fungsi itu sendiri. Overhead panggilan fungsi biasanya cukup kecil, tetapi inlining sering memungkinkan optimisasi lain terjadi yang tidak akan terjadi sebaliknya, sehingga inlining bisa menjadi kemenangan besar.

Fungsi hanya diuraikan jika "cukup kecil" (atau jika Anda menambahkan pragma yang secara khusus meminta inlining). Selain itu, fungsi hanya dapat digarisbawahi jika kompiler dapat mengetahui fungsi apa yang Anda panggil. Ada dua cara utama yang tidak bisa diketahui oleh kompiler:

• Jika fungsi yang Anda panggil diteruskan dari tempat lain. Misalnya, ketika filterfungsi dikompilasi, Anda tidak dapat menyamakan predikat filter, karena itu argumen yang disediakan pengguna.

• Jika fungsi yang Anda panggil adalah metode kelas dan kompiler tidak tahu jenis apa yang terlibat. Misalnya, ketika sumfungsi dikompilasi, kompiler tidak dapat menyejajarkan +fungsi, karena sumberfungsi dengan beberapa tipe angka yang berbeda, masing-masing memiliki +fungsi yang berbeda .

Dalam kasus terakhir, Anda dapat menggunakan {-# SPECIALIZE #-}pragma untuk menghasilkan versi fungsi yang dikodekan secara keras ke tipe tertentu. Misalnya, {-# SPECIALIZE sum :: [Int] -> Int #-}akan mengkompilasi versi sumhard-coded untuk Inttipe tersebut, artinya +dapat digarisbawahi dalam versi ini.

Namun, perlu diketahui bahwa sumfungsi khusus baru kami hanya akan dipanggil ketika kompiler dapat mengetahui bahwa kami sedang bekerja dengannya Int. Kalau tidak yang asli, polimorfik sumakan dipanggil. Sekali lagi, overhead panggilan fungsi sebenarnya cukup kecil. Optimalisasi tambahan inilah yang memungkinkan inlining dapat memberikan manfaat.

Penghapusan subekspresi umum

Jika suatu blok kode tertentu menghitung nilai yang sama dua kali, kompilator dapat menggantikannya dengan satu instance dari perhitungan yang sama. Misalnya, jika Anda melakukannya

(sum xs + 1) / (sum xs + 2)

maka kompiler dapat mengoptimalkan ini untuk

let s = sum xs in (s+1)/(s+2)

Anda mungkin berharap bahwa kompiler akan selalu melakukan ini. Namun, ternyata dalam beberapa situasi ini dapat menghasilkan kinerja yang lebih buruk, tidak lebih baik, sehingga GHC tidak selalu melakukan ini. Terus terang, saya tidak begitu mengerti detail di balik yang ini. Tetapi intinya adalah, jika transformasi ini penting bagi Anda, tidak sulit untuk melakukannya secara manual. (Dan jika itu tidak penting, mengapa kamu mengkhawatirkannya?)

Ekspresi kasus

Pertimbangkan yang berikut ini:

foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo (  []) = "end"

Tiga persamaan pertama semua memeriksa apakah daftar tersebut tidak kosong (antara lain). Tetapi memeriksa hal yang sama tiga kali sia-sia. Untungnya, sangat mudah bagi kompiler untuk mengoptimalkan ini menjadi beberapa ekspresi kasus bersarang. Dalam hal ini, sesuatu seperti

foo xs =
  case xs of
    y:ys ->
      case y of
        0 -> "zero"
        1 -> "one"
        _ -> foo ys
    []   -> "end"

Ini agak kurang intuitif, tetapi lebih efisien. Karena kompiler dapat dengan mudah melakukan transformasi ini, Anda tidak perlu khawatir tentang hal itu. Cukup tulis pencocokan pola Anda dengan cara yang paling intuitif; kompiler sangat pandai mengatur ulang dan mengatur ulang ini untuk membuatnya secepat mungkin.

Fusi

Idi standar Haskell untuk pemrosesan daftar adalah untuk menyatukan fungsi-fungsi yang mengambil satu daftar dan menghasilkan daftar baru. Contoh kanonik adalah

map g . map f

Sayangnya, sementara kemalasan menjamin melewatkan pekerjaan yang tidak perlu, semua alokasi dan alokasi untuk kinerja menengah daftar getah. "Fusion" atau "penggundulan hutan" adalah tempat penyusun mencoba menghilangkan langkah-langkah perantara ini.

Masalahnya adalah, sebagian besar fungsi ini bersifat rekursif. Tanpa rekursi, itu akan menjadi latihan dasar dalam inlining untuk memadatkan semua fungsi menjadi satu blok kode besar, menjalankan penyederhanaan di atasnya dan menghasilkan kode yang benar-benar optimal tanpa daftar perantara. Tetapi karena rekursi, itu tidak akan berhasil.

Anda dapat menggunakan {-# RULE #-}pragma untuk memperbaikinya. Sebagai contoh,

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

Sekarang setiap kali GHC melihat mapditerapkan map, itu squishes menjadi satu pass di atas daftar, menghilangkan daftar perantara.

Masalahnya adalah, ini hanya berfungsi untuk mapdiikuti oleh map. Ada banyak kemungkinan lain - mapdiikuti oleh filter, filterdiikuti olehmap , dll. Daripada menggunakan kode tangan solusi untuk masing-masing dari mereka, apa yang disebut "aliran fusi" diciptakan. Ini adalah trik yang lebih rumit, yang tidak akan saya uraikan di sini.

Panjang dan pendeknya adalah: Ini semua adalah trik optimasi khusus yang ditulis oleh programmer . GHC sendiri tidak tahu apa-apa tentang fusi; itu semua ada di daftar perpustakaan dan perpustakaan kontainer lainnya. Jadi optimasi apa yang terjadi tergantung pada bagaimana perpustakaan kontainer Anda ditulis (atau, lebih realistis, perpustakaan mana yang Anda pilih untuk digunakan).

Misalnya, jika Anda bekerja dengan array Haskell '98, jangan mengharapkan fusi dalam bentuk apa pun. Tetapi saya mengerti bahwa vectorperpustakaan memiliki kemampuan fusi yang luas. Ini semua tentang perpustakaan; kompiler hanya menyediakan RULESpragma. (Omong-omong, ini sangat kuat. Sebagai penulis perpustakaan, Anda dapat menggunakannya untuk menulis ulang kode klien!)

Meta:

• Saya setuju dengan orang-orang yang mengatakan "kode pertama, profil kedua, optimalkan ketiga".

• Saya juga setuju dengan orang-orang yang mengatakan "akan bermanfaat untuk memiliki model mental untuk berapa banyak biaya keputusan desain yang diberikan".

Seimbangkan semua hal, dan semua itu ...

Jika let binding v = rhs hanya digunakan di satu tempat, Anda dapat mengandalkan kompiler untuk memasukkannya, bahkan jika rhs besar.

Pengecualian (yang hampir tidak satu dalam konteks pertanyaan saat ini) adalah lambdas yang berisiko duplikasi pekerjaan. Mempertimbangkan:

let v = rhs
    l = \x-> v + x
in map l [1..100]

ada inlining v akan berbahaya karena penggunaan satu (sintaksis) akan diterjemahkan ke dalam 99 evaluasi tambahan rhs. Namun, dalam hal ini, Anda juga tidak mungkin ingin memasukkannya secara manual. Jadi intinya Anda bisa menggunakan aturan:

Jika Anda ingin memasukkan nama yang hanya muncul sekali, kompiler tetap akan melakukannya.

Sebagai akibat wajar yang bahagia, menggunakan pengikatan let hanya untuk menguraikan pernyataan panjang (dengan harapan mendapatkan kejelasan) pada dasarnya gratis.

Ini berasal dari community.haskell.org/~simonmar/papers/inline.pdf yang mencakup lebih banyak informasi tentang inlining.