Jejak memori dari tipe data Haskell

124

Bagaimana saya dapat menemukan jumlah memori sebenarnya yang diperlukan untuk menyimpan nilai beberapa tipe data di Haskell (kebanyakan dengan GHC)? Apakah mungkin untuk mengevaluasinya pada saat runtime (misalnya dalam GHCi) atau mungkinkah untuk memperkirakan kebutuhan memori tipe data gabungan dari komponennya?

Secara umum, jika kebutuhan memori tipe adan bdiketahui, apa yang merupakan overhead memori tipe data aljabar seperti:

data Uno = Uno a
data Due = Due a b

Misalnya, berapa banyak byte dalam memori yang ditempati oleh nilai-nilai ini?

1 :: Int8
1 :: Integer
2^100 :: Integer
\x -> x + 1
(1 :: Int8, 2 :: Int8)
[1] :: [Int8]
Just (1 :: Int8)
Nothing

Saya memahami bahwa alokasi memori sebenarnya lebih tinggi karena pengumpulan sampah tertunda. Ini mungkin berbeda secara signifikan karena evaluasi malas (dan ukuran thunk tidak terkait dengan ukuran nilai). Pertanyaannya adalah, berdasarkan tipe data, berapa banyak memori yang dibutuhkan nilainya ketika dievaluasi sepenuhnya?

Saya menemukan ada :set +sopsi di GHCi untuk melihat statistik memori, tetapi tidak jelas bagaimana memperkirakan jejak memori dari satu nilai.

haskell memory-management ghc algebraic-data-types sastanin
sumber

Jawaban:

156

(Hal berikut ini berlaku untuk GHC, kompiler lain mungkin menggunakan konvensi penyimpanan yang berbeda)

Aturan praktis: biaya konstruktor satu kata untuk tajuk, dan satu kata untuk setiap bidang . Pengecualian: konstruktor tanpa bidang (seperti Nothingatau True) tidak membutuhkan ruang, karena GHC membuat satu contoh konstruktor ini dan membagikannya di antara semua penggunaan.

Sebuah kata berukuran 4 byte pada mesin 32-bit, dan 8 byte pada mesin 64-bit.

Jadi mis 

data Uno = Uno a
data Due = Due a b

an Unomembutuhkan 2 kata, dan a Duemembutuhkan 3.

The Intjenis didefinisikan sebagai

data Int = I# Int#

sekarang, Int#ambil satu kata, jadi Intambil total 2. Kebanyakan tipe unboxed mengambil satu kata, pengecualiannya adalah Int64#,, Word64#dan Double#(pada mesin 32-bit) yang mengambil 2. GHC sebenarnya memiliki cache dengan nilai tipe yang kecil Intdan Char, jadi dalam banyak kasus ini tidak membutuhkan ruang heap sama sekali. A Stringhanya membutuhkan spasi untuk sel daftar, kecuali Anda menggunakan Chars> 255.

An Int8memiliki representasi yang identik dengan Int. Integerdidefinisikan seperti ini:

data Integer
  = S# Int#                            -- small integers
  | J# Int# ByteArray#                 -- large integers

jadi kecil Integer( S#) membutuhkan 2 kata, tetapi bilangan bulat besar membutuhkan jumlah variabel ruang tergantung pada nilainya. A ByteArray#membutuhkan 2 kata (header + size) ditambah spasi untuk array itu sendiri.

Perhatikan bahwa konstruktor yang didefinisikan dengan newtypegratis . newtypeadalah murni gagasan waktu kompilasi, dan tidak membutuhkan ruang dan tidak memerlukan instruksi pada waktu berjalan.

Lebih detail dalam Tata Letak Objek Heap di Komentar GHC .

Simon Marlow
sumber
1
Terima kasih, Simon. Inilah yang sebenarnya ingin saya ketahui.
sastanin
2
Bukankah tajuknya dua kata? Satu untuk tag, dan satu lagi untuk penunjuk penerusan untuk digunakan selama GC atau evaluasi? Jadi, bukankah itu menambahkan satu kata ke total Anda?
Edward KMETT
5
@Edward: Thunks ditimpa oleh tipuan (yang kemudian dihapus oleh GC), tetapi itu hanya 2 kata, dan setiap objek heap dijamin setidaknya berukuran dua 2 kata. Tanpa fitur profil atau debugging yang dihidupkan, header sebenarnya hanya satu kata. Dalam GHC, implementasi lain mungkin melakukan sesuatu secara berbeda.
nominolo
3
nominolo: ya, tetapi dari Closure.h: / * Thunk memiliki kata padding untuk mengambil nilai yang diperbarui. Ini agar pembaruan tidak menimpa payload, jadi kita dapat menghindari keharusan mengunci thunk selama entri dan pembaruan. Catatan: ini tidak berlaku untuk THUNK_STATICs, yang tidak memiliki payload. Catatan: kami meninggalkan kata padding ini dengan segala cara, bukan hanya SMP, sehingga kami tidak perlu mengkompilasi ulang semua perpustakaan kami untuk SMP. * / Muatan tidak ditimpa selama tipu muslihat. Indirection ditulis di lokasi terpisah di Header.
Edward KMETT
6
Ya, tapi perhatikan ini hanya untuk thunks . Ini tidak berlaku untuk konstruktor. Memperkirakan ukuran thunk agak sulit - Anda harus menghitung variabel bebas.
nominolo