Efisiensi memori Haskell - yang merupakan pendekatan yang lebih baik?

Kami menerapkan pustaka kompresi matriks berdasarkan sintaksis tata bahasa dua dimensi yang dimodifikasi. Sekarang kami memiliki dua pendekatan untuk tipe data kami - yang mana akan lebih baik jika menggunakan memori? (kami ingin mengompresi sesuatu;)).

Tata bahasa mengandung NonTerminals dengan tepat 4 Productions atau Terminal di sisi kanan. Kami akan membutuhkan nama Productions untuk pemeriksaan kesetaraan dan minimalisasi tata bahasa.

Pertama:

-- | Type synonym for non-terminal symbols
type NonTerminal = String

-- | Data type for the right hand side of a production
data RightHandSide = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal Int

-- | Data type for a set of productions
type ProductionMap = Map NonTerminal RightHandSide

data MatrixGrammar = MatrixGrammar {
    -- the start symbol
    startSymbol :: NonTerminal,
    -- productions
    productions :: ProductionMap    
    } 

Di sini data RightHandSide kami hanya menyimpan nama String untuk menentukan produksi berikutnya, dan apa yang tidak kami ketahui di sini adalah bagaimana Haskell menyimpan string ini. Misalnya matriks [[0, 0], [0, 0]] memiliki 2 produksi:

a = Terminal 0
aString = "A"
b = DownStep aString aString aString aString
bString = "B"
productions = Map.FromList [(aString, a), (bString, b)]

Jadi pertanyaannya di sini adalah seberapa sering String "A" benar-benar disimpan? Sekali dalam aString, 4 kali dalam b dan sekali dalam produksi atau hanya sekali dalam aString dan yang lain hanya memegang referensi "lebih murah"?

Kedua:

data Production = NonTerminal String Production Production Production Production
                | Terminal String Int 

type ProductionMap = Map String Production

di sini istilah "Terminal" agak menyesatkan karena sebenarnya produksi yang memiliki terminal sebagai sisi kanan. Matriks yang sama:

a = Terminal "A" 0
b = NonTerminal "B" a a a a
productions = Map.fromList [("A", a), ("B", b)]

dan pertanyaan serupa: seberapa sering produksi diselamatkan secara internal oleh Haskell? Mungkin kami akan memasukkan nama-nama di dalam produksi jika kami tidak membutuhkannya, tetapi kami tidak yakin sekarang tentang ini.

Jadi katakanlah kita memiliki tata bahasa dengan sekitar 1000 produksi. Pendekatan mana yang akan mengkonsumsi lebih sedikit memori?

Akhirnya pertanyaan tentang bilangan bulat di Haskell: Saat ini kami berencana memiliki nama sebagai Strings. Tetapi kita dapat dengan mudah beralih ke nama integer karena dengan 1000 produksi kita akan memiliki nama dengan lebih dari 4 karakter (yang saya anggap 32 bit?). Bagaimana Haskell menangani ini. Apakah Int selalu 32 Bit dan Integer mengalokasikan memori yang benar-benar dibutuhkan?

Saya juga membaca ini: Merancang tes nilai / referensi semantik Haskell - tapi saya tidak tahu apa artinya sebenarnya bagi kita - saya lebih dari anak java imperatif kemudian programmer fungsional yang baik: P

Anda dapat memperluas tata bahasa matriks Anda menjadi ADT dengan berbagi sempurna dengan sedikit tipu daya:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import Data.Map
import Data.Foldable
import Data.Functor
import Data.Traversable

-- | Type synonym for non-terminal symbols
type NonTerminal = String

-- | Data type for the right hand side of a production
data RHS a = DownStep NonTerminal NonTerminal NonTerminal NonTerminal | Terminal a
  deriving (Eq,Ord,Show,Read,Functor, Foldable, Traversable)

data G a = G NonTerminal (Map NonTerminal (RHS a))
  deriving (Eq,Ord,Show,Read,Functor)

data M a = Q (M a) (M a) (M a) (M a) | T a
  deriving (Functor, Foldable, Traversable)

tabulate :: G a -> M a
tabulate (G s pm) = loeb (expand <$> pm) ! s where
  expand (DownStep a11 a12 a21 a22) m = Q (m!a11) (m!a12) (m!a21) (m!a22)
  expand (Terminal a)               _ = T a

loeb :: Functor f => f (f b -> b) -> f b
loeb x = xs where xs = fmap ($xs) x

Di sini saya menggeneralisasikan tata bahasa Anda untuk memungkinkan tipe data apa pun, tidak hanya Int, dan tabulateakan mengambil tata bahasa dan memperluasnya dengan melipatnya sendiri loeb.

loebdijelaskan dalam sebuah artikel oleh Dan Piponi

Ekspansi yang dihasilkan sebagai ADT secara fisik tidak membutuhkan lebih banyak memori daripada tata bahasa asli - pada kenyataannya dibutuhkan sedikit lebih sedikit, karena tidak memerlukan faktor log tambahan untuk tulang punggung Peta, dan tidak perlu menyimpan string sama sekali.

Berbeda dengan ekspansi naif, menggunakan loebmemungkinkan saya 'mengikat simpul' dan berbagi thunks untuk semua kejadian dari non-terminal yang sama.

Jika Anda ingin mencelupkan lebih ke dalam teori semua ini, kita dapat melihat bahwa RHSitu dapat diubah menjadi fungsi dasar:

data RHS t nt = Q nt nt nt nt | L t

dan kemudian tipe M saya hanya titik tetap itu Functor.

M a ~ Mu (RHS a)

sementara G aakan terdiri dari string yang dipilih dan peta dari string ke (RHS String a).

Kita kemudian dapat memperluas Gke Mdengan mencari entri di peta string yang diperluas dengan malas.

Ini adalah jenis ganda dari apa yang dilakukan dalam data-reifypaket, yang dapat mengambil fungsi dasar seperti itu, dan sesuatu seperti Mdan memulihkan setara moral Anda Gdari itu. Mereka menggunakan tipe yang berbeda untuk nama-nama non-terminal, yang pada dasarnya hanyalah sebuah Int.

data Graph e = Graph [(Unique, e Unique)] Unique

dan berikan kombinator

reifyGraph :: MuRef s => s -> IO (Graph (DeRef s))

yang dapat digunakan dengan contoh yang sesuai pada tipe data di atas untuk mendapatkan grafik (MatrixGrammar) dari matriks arbitrer. Itu tidak akan melakukan deduplikasi kuadran identik tetapi disimpan secara terpisah, tetapi itu akan memulihkan semua berbagi yang ada di grafik asli.

Di Haskell, tipe String adalah alias untuk [Char], yang merupakan daftar Haskell reguler dari Char, bukan vektor atau larik. Char adalah tipe yang memiliki karakter Unicode tunggal. Literal string adalah, kecuali jika Anda menggunakan ekstensi bahasa, nilai-nilai tipe String.

Saya pikir Anda bisa menebak dari atas bahwa String bukan representasi yang sangat kompak atau efisien. Representasi alternatif umum untuk string meliputi tipe yang disediakan oleh Data.Text dan Data.ByteString.

Untuk kenyamanan ekstra, Anda bisa menggunakan -XOverloadedStrings sehingga Anda bisa menggunakan string literal sebagai representasi dari tipe string alternatif, seperti yang disediakan oleh Data.ByteString.Char8. Itu mungkin cara paling hemat-ruang untuk menggunakan string sebagai pengidentifikasi.

Sejauh Int berjalan, ini adalah tipe lebar tetap, tetapi tidak ada jaminan tentang seberapa lebar itu kecuali bahwa itu harus cukup lebar untuk menampung nilai [-2 ^ 29 .. 2 ^ 29-1]. Ini menunjukkan setidaknya 32 bit, tetapi tidak mengesampingkan menjadi 64 bit. Data.Int memiliki beberapa tipe yang lebih spesifik, Int8-Int64, yang dapat Anda gunakan jika Anda membutuhkan lebar tertentu.

Edit untuk menambahkan informasi

Saya tidak percaya semantik Haskell menentukan apa pun tentang berbagi data. Anda seharusnya tidak mengharapkan dua String literal, atau dua dari data yang dibangun, untuk merujuk ke objek 'kanonik' yang sama dalam memori. Jika Anda mengikat nilai yang dikonstruksikan ke nama baru (dengan membiarkan, kecocokan pola, dll.) Kedua nama kemungkinan besar akan merujuk pada data yang sama, tetapi apakah mereka melakukannya atau tidak tidak benar-benar terlihat karena sifat abadi dari Data Haskell.

Demi efisiensi penyimpanan, Anda dapat menginternir string, yang pada dasarnya menyimpan representasi kanonik masing-masing dalam tabel pencarian semacam, biasanya tabel hash. Ketika Anda menginternir suatu objek, Anda mendapatkan deskriptor untuk itu kembali, dan Anda dapat membandingkan deskriptor tersebut dengan yang lain untuk melihat apakah mereka sama jauh lebih murah daripada yang Anda bisa peroleh, dan mereka juga sering jauh lebih kecil.

Untuk perpustakaan yang tidak magang, Anda bisa menggunakan https://github.com/ekmett/intern/

Adapun untuk menentukan ukuran integer mana yang akan digunakan pada saat run-time, cukup mudah untuk menulis kode yang tergantung pada kelas tipe Integral atau Num daripada tipe numerik konkret. Ketik inferensi akan memberi Anda jenis paling umum yang dapat secara otomatis. Anda kemudian dapat memiliki beberapa fungsi berbeda dengan tipe yang secara eksplisit dipersempit menjadi tipe numerik tertentu yang dapat Anda pilih salah satu dari saat runtime untuk melakukan pengaturan awal, dan setelah itu semua fungsi polimorfik lainnya akan bekerja sama pada salah satu dari mereka. Misalnya:

polyConstructor :: Integral a => a -> MyType a
int16Constructor :: Int16 -> MyType Int16
int32Constructor :: Int32 -> MyType Int32

int16Constructor = polyConstructor
int32Constructor = polyConstructor

Sunting : Informasi lebih lanjut tentang magang

Jika Anda hanya ingin magang string, Anda bisa membuat tipe baru yang membungkus string (lebih disukai Teks atau ByteString) dan integer kecil bersama.

data InternedString = { id :: Int32, str :: Text }
instance Eq InternedString where
    {x, _ } == {y, _ }  =  x == y

intern :: MonadIO m => Text -> m InternedString

Apa yang dilakukan 'intern' adalah mencari string dalam HashMap referensi lemah di mana Teks adalah kunci dan InternedStrings adalah nilai. Jika kecocokan ditemukan, 'magang' mengembalikan nilai. Jika tidak, itu menciptakan nilai InternedString baru dengan Teks asli dan id integer unik (itulah sebabnya saya menyertakan kendala MonadIO; bisa menggunakan State monad atau operasi yang tidak aman sebagai gantinya untuk mendapatkan id unik; ada banyak kemungkinan) dan menyimpannya di peta sebelum mengembalikannya.

Sekarang Anda mendapatkan perbandingan cepat berdasarkan id integer dan hanya memiliki satu salinan dari setiap string unik.

Pustaka internal Edward Kmett menerapkan prinsip yang sama, kurang lebih, dengan cara yang jauh lebih umum sehingga seluruh istilah data terstruktur di-hash, disimpan secara unik, dan diberikan operasi perbandingan yang cepat. Ini agak menakutkan dan tidak terlalu terdokumentasi, tetapi dia mungkin bersedia membantu jika Anda bertanya; atau Anda bisa mencoba implementasi interning string Anda terlebih dahulu untuk melihat apakah itu cukup membantu.