Ketika menemukan elemen terakhir tetapi kedua dari daftar, mengapa menggunakan `last` yang tercepat di antara ini?

10

Ada 3 fungsi yang diberikan di bawah ini yang menemukan elemen terakhir tetapi kedua dalam daftar. Yang menggunakan last . inittampaknya jauh lebih cepat daripada yang lain. Sepertinya saya tidak tahu mengapa.

Untuk pengujian, saya menggunakan daftar input [1..100000000](100 juta). Yang terakhir berjalan hampir secara instan sedangkan yang lain membutuhkan waktu beberapa detik.

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init
haskell storm125
sumber
5
inittelah dioptimalkan untuk menghindari "membongkar" daftar beberapa kali.
Willem Van Onsem
1
@ WillemVanOnsem tetapi mengapa myButLastjauh lebih lambat? Tampaknya tidak membongkar daftar apa pun, tetapi hanya melewatinya seperti initfungsinya ...
lsmor
1
@ Irsmor: ini [x, y]adalah kependekan dari (x:(y:[])), jadi membongkar kontra luar, kontra kedua, dan memeriksa apakah ekor yang kedua consadalah []. Selanjutnya klausa kedua akan membongkar daftar lagi di (x:xs). Ya itu membongkar cukup efisien, tetapi tentu saja jika itu terjadi sangat sering, itu akan memperlambat proses.
Willem Van Onsem
1
Melihat di hackage.haskell.org/package/base-4.12.0.0/docs/src/… , optimasi tampaknya inittidak berulang kali memeriksa apakah argumennya adalah daftar tunggal atau daftar kosong. Setelah rekursi dimulai, itu hanya mengasumsikan bahwa elemen pertama akan ditempelkan ke hasil panggilan rekursif.
chepner
2
@ WillemVanOnsem Saya pikir membongkar mungkin bukan masalah di sini: GHC melakukan spesialisasi pola panggilan yang seharusnya memberi Anda versi yang dioptimalkan myButLastsecara otomatis. Saya pikir itu lebih mungkin daftar fusi yang harus disalahkan untuk percepatan.
oisdk

Jawaban:

9

Saat mempelajari kecepatan dan pengoptimalan, sangat mudah untuk mendapatkan hasil yang sangat salah . Secara khusus, Anda tidak dapat benar-benar mengatakan bahwa satu varian lebih cepat daripada yang lain tanpa menyebutkan versi kompiler dan mode pengoptimalan pengaturan pembandingan Anda. Bahkan kemudian, prosesor modern sangat canggih untuk fitur prediktor cabang berbasis jaringan saraf, belum lagi semua jenis cache, sehingga, bahkan dengan pengaturan yang hati-hati, hasil pembandingan akan buram.

Yang telah dibilang...

Benchmarking adalah teman kita.

criterionadalah paket yang menyediakan alat pembandingan lanjutan. Saya dengan cepat membuat tolok ukur seperti ini:

module Main where

import Criterion
import Criterion.Main

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

butLast2 :: [a] -> a
butLast2 (x :     _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"

setupEnv = do
  let xs = [1 .. 10^7] :: [Int]
  return xs

benches xs =
  [ bench "slow?"   $ nf myButLast   xs
  , bench "decent?" $ nf myButLast'  xs
  , bench "fast?"   $ nf myButLast'' xs
  , bench "match2"  $ nf butLast2    xs
  ]

main = defaultMain
    [ env setupEnv $ \ xs -> bgroup "main" $ let bs = benches xs in bs ++ reverse bs ]

Seperti yang Anda lihat, saya menambahkan varian yang secara eksplisit cocok dengan dua elemen sekaligus, tetapi sebaliknya itu adalah kode yang sama kata demi kata. Saya juga menjalankan tolok ukur secara terbalik, agar menyadari bias karena caching. Jadi, mari kita lari dan lihat!

% ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.6.5


% ghc -O2 -package criterion A.hs && ./A
benchmarking main/slow?
time                 54.83 ms   (54.75 ms .. 54.90 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.86 ms   (54.82 ms .. 54.93 ms)
std dev              94.77 μs   (54.95 μs .. 146.6 μs)

benchmarking main/decent?
time                 794.3 ms   (32.56 ms .. 1.293 s)
                     0.907 R²   (0.689 R² .. 1.000 R²)
mean                 617.2 ms   (422.7 ms .. 744.8 ms)
std dev              201.3 ms   (105.5 ms .. 283.3 ms)
variance introduced by outliers: 73% (severely inflated)

benchmarking main/fast?
time                 84.60 ms   (84.37 ms .. 84.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 84.46 ms   (84.25 ms .. 84.77 ms)
std dev              435.1 μs   (239.0 μs .. 681.4 μs)

benchmarking main/match2
time                 54.87 ms   (54.81 ms .. 54.95 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.85 ms   (54.81 ms .. 54.92 ms)
std dev              104.9 μs   (57.03 μs .. 178.7 μs)

benchmarking main/match2
time                 50.60 ms   (47.17 ms .. 53.01 ms)
                     0.993 R²   (0.981 R² .. 0.999 R²)
mean                 60.74 ms   (56.57 ms .. 67.03 ms)
std dev              9.362 ms   (6.074 ms .. 10.95 ms)
variance introduced by outliers: 56% (severely inflated)

benchmarking main/fast?
time                 69.38 ms   (56.64 ms .. 78.73 ms)
                     0.948 R²   (0.835 R² .. 0.994 R²)
mean                 108.2 ms   (92.40 ms .. 129.5 ms)
std dev              30.75 ms   (19.08 ms .. 37.64 ms)
variance introduced by outliers: 76% (severely inflated)

benchmarking main/decent?
time                 770.8 ms   (345.9 ms .. 1.004 s)
                     0.967 R²   (0.894 R² .. 1.000 R²)
mean                 593.4 ms   (422.8 ms .. 691.4 ms)
std dev              167.0 ms   (50.32 ms .. 226.1 ms)
variance introduced by outliers: 72% (severely inflated)

benchmarking main/slow?
time                 54.87 ms   (54.77 ms .. 55.00 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 54.95 ms   (54.88 ms .. 55.10 ms)
std dev              185.3 μs   (54.54 μs .. 251.8 μs)

Sepertinya versi "lambat" kami sama sekali tidak lambat! Dan seluk-beluk pencocokan pola tidak menambahkan apa pun. (Sedikit mempercepat kita melihat antara dua kali berturut-turut match2saya menganggap efek caching.)

Ada cara untuk mendapatkan lebih banyak data "ilmiah" : kita dapat -ddump-simpldan melihat cara kompiler melihat kode kita.

Inspeksi struktur menengah adalah teman kita.

"Core" adalah bahasa internal GHC. Setiap file sumber Haskell disederhanakan menjadi Core sebelum diubah menjadi grafik fungsional akhir untuk dijalankan oleh sistem waktu. Jika kita melihat tahap menengah ini, ia akan memberi tahu kita myButLastdan butLast2setara. Memang butuh melihat, karena, pada tahap penggantian nama, semua pengenal baik kami acak-acakan.

% for i in `seq 1 4`; do echo; cat A$i.hs; ghc -O2 -ddump-simpl A$i.hs > A$i.simpl; done

module A1 where

-- slow
myButLast :: [a] -> a
myButLast [x, y] = x
myButLast (x : xs) = myButLast xs
myButLast _ = error "List too short"

module A2 where

-- decent
myButLast' :: [a] -> a
myButLast' = (!! 1) . reverse

module A3 where

-- fast
myButLast'' :: [a] -> a
myButLast'' = last . init

module A4 where

butLast2 :: [a] -> a
butLast2 (x :     _ : [ ] ) = x
butLast2 (_ : xs@(_ : _ ) ) = butLast2 xs
butLast2 _ = error "List too short"

% ./EditDistance.hs *.simpl
(("A1.simpl","A2.simpl"),3866)
(("A1.simpl","A3.simpl"),3794)
(("A2.simpl","A3.simpl"),663)
(("A1.simpl","A4.simpl"),607)
(("A2.simpl","A4.simpl"),4188)
(("A3.simpl","A4.simpl"),4113)

Tampaknya A1dan A4yang paling mirip. Pemeriksaan menyeluruh akan menunjukkan bahwa memang struktur kode A1dan A4identik. Itu A2dan A3sama juga masuk akal karena keduanya didefinisikan sebagai komposisi dua fungsi.

Jika Anda akan memeriksa coreoutput secara luas, masuk akal juga untuk menyediakan flag seperti -dsuppress-module-prefixesdan -dsuppress-uniques. Mereka membuatnya jauh lebih mudah dibaca.

Daftar pendek musuh kita juga.

Jadi, apa yang bisa salah dengan pembandingan dan pengoptimalan?

  • ghci, yang dirancang untuk permainan interaktif dan iterasi cepat, mengkompilasi sumber Haskell ke rasa kode byte tertentu, daripada dieksekusi akhir, dan menghindari optimasi mahal demi pemuatan ulang yang lebih cepat.
  • Profiling sepertinya alat yang bagus untuk melihat kinerja bit-bit individual dari sebuah program yang kompleks, tetapi itu dapat merusak optimisasi kompiler dengan sangat buruk, hasilnya akan menjadi urutan besarnya dari basis.
    • Perlindungan Anda adalah membuat profil setiap bit kecil kode sebagai executable terpisah, dengan runner benchmark sendiri.
  • Pengumpulan sampah bisa dijamah. Baru hari ini fitur utama baru dirilis. Penundaan pengumpulan sampah akan memengaruhi kinerja dengan cara yang tidak mudah diprediksi.
  • Seperti yang saya sebutkan, versi kompiler yang berbeda akan membangun kode yang berbeda dengan kinerja yang berbeda, jadi Anda harus tahu versi apa yang akan digunakan oleh pengguna kode Anda untuk membuatnya, dan membandingkannya dengan itu, sebelum Anda membuat janji.

Ini mungkin terlihat sedih. Tetapi sebenarnya bukan hal yang harus menjadi perhatian seorang programmer Haskell, sebagian besar waktu. Kisah nyata: Saya punya teman yang baru saja mulai belajar Haskell. Mereka telah menulis sebuah program untuk integrasi numerik, dan itu lambat sekali. Jadi kami duduk bersama dan menulis deskripsi kategoris dari algoritma, dengan diagram dan sebagainya. Ketika mereka menulis ulang kode untuk menyelaraskan dengan deskripsi abstrak, secara ajaib menjadi, seperti, cheetah cepat, dan langsing pada memori juga. Kami menghitung π dalam waktu singkat. Pesan moral dalam cerita? Struktur abstrak yang sempurna, dan kode Anda akan mengoptimalkan dirinya sendiri.

Ignat Insarov
sumber
Sangat informatif, dan juga sedikit membingungkan bagi saya pada tahap ini. Dalam hal ini, semua "pembandingan" yang saya lakukan adalah menjalankan semua fungsi untuk 100 juta daftar item dan perhatikan bahwa yang satu lebih lama dari yang lain. Benchmark dengan kriteria tampaknya agak bermanfaat. Selain itu, ghcitampaknya memberikan hasil yang berbeda (dalam hal kecepatan) dibandingkan dengan membuat exe terlebih dahulu, seperti yang Anda katakan.
storm125