Space leak

Space leak adalah kebocoran memori yang terjadi karena data yang seharusnya bisa dilepas tetap ditahan oleh thunk yang belum dihitung. Kebocoran semacam ini tidak memunculkan pesan error apa pun, melainkan tampak sebagai memori yang terus bertambah dan program yang melambat. Topik ini membahas akumulasi thunk pada foldl sebagai pola penyebab yang umum, perbaikannya dengan varian strict, serta cara mendiagnosis keberadaannya dengan alat pengukuran yang tersedia.

Penumpukan thunk pada akumulator#

Fungsi foldl memperbarui akumulator tanpa memaksanya, sehingga setiap langkah hanya menambah satu lapisan perhitungan tertunda. Setelah list habis dipindai, akumulator berubah menjadi rantai penjumlahan sepanjang list, dan seluruh rantai itu baru dihitung ketika hasilnya diminta. Penyimpanan yang diperlukan tumbuh sebanding dengan panjang list, yaitu $O(n)$, meskipun nilai akhirnya hanyalah satu bilangan.

Program berikut membuktikan urutan itu dengan trace. Fungsi langkah mencatat elemen yang diproses, dan waktu kemunculan pesannya menunjukkan kapan penjumlahan benar-benar dilakukan.

import Debug.Trace (trace)
import System.IO (BufferMode (..), hSetBuffering, stdout)

-- langkah mencatat elemennya tanpa memaksa akumulatornya
langkah :: Int -> Int -> Int
langkah acc x = trace ("langkah " ++ show x) (acc + x)

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  let hasil = foldl langkah 0 [1, 2, 3]
  putStrLn "foldl sudah selesai dipanggil"
  print hasil

foldl sudah selesai dipanggil
langkah 3
langkah 2
langkah 1
6

Baris pertama tercetak lebih dahulu karena pemanggilan foldl selesai dengan segera, yaitu mengembalikan thunk tanpa memindai list sama sekali. Ketiga pesan langkah baru muncul ketika print hasil memaksa thunk tersebut, dimulai dari lapisan terluar sehingga urutannya terbalik. Pada list yang panjang, kejadian yang sama menyimpan jutaan lapisan sekaligus di memori sebelum satu nilai pun siap.

Perbaikan dengan foldl'#

Fungsi foldl' dari Data.List memaksa akumulator pada setiap langkah, sehingga lapisan tertunda tidak pernah menumpuk. Akumulator selalu berupa nilai yang sudah dihitung sebelum elemen berikutnya diproses, dan memori yang digunakan tetap kecil sepanjang pemindaian.

import Data.List (foldl')
import Debug.Trace (trace)
import System.IO (BufferMode (..), hSetBuffering, stdout)

-- langkah mencatat elemennya tanpa memaksa akumulatornya
langkah :: Int -> Int -> Int
langkah acc x = trace ("langkah " ++ show x) (acc + x)

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  let hasil = foldl' langkah 0 [1, 2, 3]
  putStrLn "foldl' sudah selesai dipanggil"
  print hasil

foldl' sudah selesai dipanggil
langkah 1
langkah 2
langkah 3
6

Perbedaannya terlihat pada urutan pesan. Ketiga pesan langkah kini tercetak berurutan dari 1 sampai 3, artinya penjumlahan pada setiap langkah selesai dihitung sebelum langkah berikutnya diproses, sebab foldl' memaksa akumulator pada setiap langkah pemindaiannya. Pemanggilan foldl' sendiri tetap selesai dengan segera, sehingga seluruh pemindaian beserta pesannya baru berlangsung ketika print hasil memaksa thunk-nya. Nilai akhirnya sama, tetapi lapisan perhitungan tertunda tidak pernah menumpuk, dan itulah perbedaan yang menentukan kebutuhan memorinya.

Memaksa sampai ke dalam dengan force#

Fungsi seq hanya memaksa sampai WHNF, sehingga komponen di dalam sebuah struktur tetap tertunda. Apabila seluruh isi harus dihitung, pustaka deepseq menyediakan force, yaitu fungsi yang memaksa argumennya sampai normal form penuh sebelum mengembalikan nilainya. Fungsi itu berguna ketika struktur seperti tuple atau list yang menyimpan hasil perhitungan perlu dijamin selesai dihitung.

import Control.DeepSeq (force)
import Debug.Trace (trace)
import System.IO (BufferMode (..), hSetBuffering, stdout)

-- kuadrat mencatat setiap perhitungan yang benar-benar dijalankan
kuadrat :: Int -> Int
kuadrat n = trace ("menghitung " ++ show n) (n * n)

main :: IO ()
main = do
  hSetBuffering stdout LineBuffering
  let pasangan = (kuadrat 2, kuadrat 3)
  pasangan `seq` putStrLn "seq: komponen pasangan masih tertunda"
  let paksa = force pasangan
  paksa `seq` putStrLn "force: keduanya kini benar-benar dihitung"
  print paksa

seq: komponen pasangan masih tertunda
menghitung 2
menghitung 3
force: keduanya kini benar-benar dihitung
(4,9)

Baris pertama keluaran menunjukkan bahwa seq pada pasangan tidak memaksa satu pun komponennya, sedangkan force memaksa keduanya sebelum pesan kedua tercetak. Pemanggilan print paksa kemudian tidak mencetak pesan apa pun karena kedua komponen sudah dihitung pada saat force. Perbedaan ini menegaskan bahwa memaksa sampai batas terluar dan memaksa sampai ke dalam adalah dua pekerjaan yang berbeda.

Mendiagnosis dengan statistik RTS#

Gejala space leak dikenali dari perilaku program, yaitu memori yang terus tumbuh dan porsi waktu yang makin besar habis untuk garbage collection (pembersihan memori otomatis), meskipun hasil akhir program kecil. Penelusuran pertama dilakukan dengan membaca kode dan mencari akumulator yang tidak dipaksa, sebagaimana pola foldl di atas. Penelusuran berikutnya dilakukan dengan mengukur, dan alat bawaan GHC untuk itu adalah opsi statistik runtime system (RTS), yaitu bagian yang mengelola memori dan waktu berjalan program. Pada GHCi, perintah :sprint juga dapat digunakan untuk melihat seberapa jauh sebuah definisi sudah dihitung.

Program berikut menjumlahkan satu juta bilangan pertama dengan dua cara, yaitu foldl yang membocorkan memori dan foldl' yang tidak. Kompilasinya memerlukan -rtsopts agar opsi RTS dapat diberikan saat program dijalankan.

-- Penjumlahan list panjang: foldl menumpuk thunk, foldl' menghitung seketika
import Data.List (foldl')

main :: IO ()
main = do
  let lambat = foldl (+) 0 [1 .. 1000000]
      cepat  = foldl' (+) 0 [1 .. 1000000]
  print lambat
  print cepat

500000500000
500000500000

Perintah berikut mengompilasi program tersebut lalu menjalankannya dengan ringkasan statistik di akhir.

# kompilasi dengan izin opsi RTS
ghc -rtsopts leak.hs
# jalankan program beserta ringkasan statistik runtime-nya
./leak +RTS -s

    36,169,392 bytes allocated in the heap
     4,057,632 bytes copied during GC
     1,065,272 bytes maximum residency (2 sample(s))
        54,312 bytes maximum slop
             3 MB total memory in use (0 MB lost due to fragmentation)

Ringkasan lengkapnya memuat pula jumlah garbage collection dan rincian waktu, sedangkan lima baris di atas adalah bagian memorinya sebagaimana tercantum pada panduan GHC. Angka bytes allocated in the heap menyatakan total alokasi selama program berjalan, sedangkan bytes maximum residency menyatakan data hidup (residency) terbesar yang pernah diperiksa garbage collector. Membandingkan dua program yang masing-masing hanya menjalankan salah satu varian memperlihatkan perbedaannya secara langsung, yaitu residency varian foldl tumbuh sebanding dengan panjang list, sedangkan varian foldl' tetap kecil di tingkat kilobyte. Apabila distribusi memori per bagian program diperlukan, GHC menyediakan profil heap melalui opsi -hT yang dijelaskan pada panduan profiling.

Kesalahan umum#

Kesalahan pertama adalah memaksa di tempat yang tidak menyentuh penumpukannya. Menambahkan seq pada hasil akhir foldl tidak mengurangi puncak memori, karena penumpukan terjadi selama pemindaian berlangsung dan sudah selesai terbentuk ketika hasilnya dipaksa. Titik pemaksaan yang benar ada di dalam langkah pemindaian, dan foldl' memang menerapkan hal itu.

Kesalahan kedua adalah menganggap semua akumulator perlu dipaksa. foldr yang lazy bergantung pada penundaan agar dapat berhenti lebih awal pada list tak hingga, sehingga mengganti seluruh fold menjadi varian strict justru merusak penggunaan tersebut. Ketentuan praktisnya, akumulator yang selalu dipindai habis, seperti penjumlahan, dipaksa lebih awal, sedangkan akumulator yang mungkin tidak diminta dibiarkan tertunda.

Ringkasan#

• foldl menumpuk satu lapisan thunk per elemen pada akumulatornya, sehingga kebutuhan memori tumbuh seiring panjang list.
• foldl' memaksa akumulator di setiap langkah, sedangkan force dari deepseq memaksa seluruh isi struktur sampai normal form penuh.
• Opsi +RTS -s menampilkan total alokasi dan residency puncak yang menjadi indikator utama space leak, sedangkan :sprint pada GHCi memperlihatkan seberapa jauh sebuah definisi sudah dihitung.
• Pemaksaan diterapkan secara selektif, karena foldr justru bergantung pada evaluasi tertunda untuk list tak hingga.

Referensi#

• GHC Users Guide: RTS options to produce runtime statistics — haskell.org — Bentuk keluaran +RTS -s yang dikutip pada topik ini.
• Data.List — Hackage — Dokumentasi foldl' beserta catatan strictness-nya.
• Control.DeepSeq — Hackage — Kelas NFData dan fungsi force untuk memaksa evaluasi sampai normal form penuh.
• GHC Users Guide: Profiling — haskell.org — Opsi heap profiling untuk menelusuri alokasi memori per bagian program.