Mengapa int di OCaml hanya 31 bit?

Belum pernah melihat "fitur" ini di tempat lain. Saya tahu bahwa bit ke-32 digunakan untuk pengumpulan sampah. Tetapi mengapa demikian hanya untuk int dan bukan untuk tipe dasar lainnya?

Ini disebut representasi penunjuk yang diberi tag , dan merupakan trik pengoptimalan yang cukup umum digunakan di banyak penafsir, VM, dan sistem runtime yang berbeda selama beberapa dekade. Hampir semua implementasi Lisp menggunakannya, banyak VM Smalltalk, banyak interpreter Ruby, dan seterusnya.

Biasanya, dalam bahasa tersebut, Anda selalu memberikan petunjuk ke objek. Objek itu sendiri terdiri dari header objek, yang berisi metadata objek (seperti jenis objek, kelasnya, mungkin pembatasan kontrol akses atau anotasi keamanan, dan sebagainya), dan kemudian data objek itu sendiri. Jadi, integer sederhana akan direpresentasikan sebagai pointer ditambah objek yang terdiri dari metadata dan integer sebenarnya. Bahkan dengan representasi yang sangat kompak, itu seperti 6 Byte untuk integer sederhana.

Selain itu, Anda tidak dapat meneruskan objek integer ke CPU untuk melakukan aritmatika integer dengan cepat. Jika Anda ingin menambahkan dua bilangan bulat, Anda benar-benar hanya memiliki dua pointer, yang menunjuk ke awal header objek dari dua bilangan bulat objek yang ingin Anda tambahkan. Jadi, pertama-tama Anda perlu melakukan aritmatika integer pada penunjuk pertama untuk menambahkan offset ke objek tempat data integer disimpan. Maka Anda harus membedakan alamat itu. Lakukan hal yang sama lagi dengan bilangan bulat kedua. Sekarang Anda memiliki dua bilangan bulat yang sebenarnya dapat Anda minta untuk ditambahkan oleh CPU. Tentu saja, sekarang Anda perlu membuat objek integer baru untuk menampung hasilnya.

Jadi, untuk melakukan satu penjumlahan bilangan bulat, Anda sebenarnya perlu melakukan tiga penjumlahan bilangan bulat ditambah dua pemutusan hubungan kerja penunjuk ditambah satu konstruksi objek. Dan Anda mengambil hampir 20 Byte.

Namun, triknya adalah dengan apa yang disebut tipe nilai yang tidak dapat diubah seperti bilangan bulat, Anda biasanya tidak memerlukan semua metadata di header objek: Anda bisa membiarkan semua itu, dan cukup mensintesisnya (yaitu VM-nerd- berbicara untuk "berpura-pura"), ketika ada yang peduli untuk melihatnya. Integer akan selalu memiliki kelas Integer, tidak perlu menyimpan informasi itu secara terpisah. Jika seseorang menggunakan refleksi untuk mengetahui kelas integer, Anda cukup membalas Integerdan tidak ada yang akan tahu bahwa Anda sebenarnya tidak menyimpan informasi itu di header objek dan pada kenyataannya, bahkan tidak ada header objek (atau obyek).

Jadi, trik ini adalah untuk menyimpan nilai dari objek dalam pointer ke objek, secara efektif runtuh dua menjadi satu.

Ada CPU yang sebenarnya memiliki ruang tambahan di dalam sebuah pointer (disebut bit tag ) yang memungkinkan Anda untuk menyimpan informasi tambahan tentang pointer di dalam pointer itu sendiri. Informasi tambahan seperti "ini sebenarnya bukan penunjuk, ini adalah bilangan bulat". Contohnya termasuk Burroughs B5000, berbagai Lisp Machines atau AS / 400. Sayangnya, sebagian besar CPU arus utama saat ini tidak memiliki fitur itu.

Namun, ada jalan keluarnya: kebanyakan CPU arus utama bekerja lebih lambat secara signifikan ketika alamat tidak selaras pada batas kata. Beberapa bahkan tidak mendukung akses tidak selaras sama sekali.

Artinya dalam praktiknya, semua pointer akan habis dibagi 4, yang berarti akan selalu diakhiri dengan dua 0bit. Hal ini memungkinkan kita untuk membedakan antara pointer nyata (yang diakhiri dengan 00) dan pointer yang sebenarnya adalah bilangan bulat yang disamarkan (yang diakhiri dengan 1). Dan itu masih menyisakan kita dengan semua petunjuk yang berakhir dengan 10bebas untuk melakukan hal-hal lain. Selain itu, sebagian besar sistem operasi modern menyimpan alamat yang sangat rendah untuk dirinya sendiri, yang memberi kita area lain untuk dipusingkan (petunjuk yang dimulai dengan, katakanlah, 24 0detik dan diakhiri dengan 00).

Jadi, Anda dapat mengenkode integer 31-bit menjadi pointer, hanya dengan menggesernya 1 bit ke kiri dan menambahkannya 1. Dan Anda dapat melakukan aritmatika integer yang sangat cepat dengan itu, hanya dengan menggesernya secara tepat (terkadang bahkan itu tidak perlu).

Apa yang kita lakukan dengan address space lainnya? Nah, contoh khas termasuk pengkodean floatdalam ruang alamat besar lainnya dan sejumlah objek khusus seperti true, false, nil, 127 karakter ASCII, beberapa yang umum digunakan string pendek, daftar kosong, obyek kosong, array kosong dan seterusnya dekat 0alamat.

Misalnya, dalam interpreter MRI, YARV dan Rubinius Ruby, bilangan bulat dikodekan seperti yang saya jelaskan di atas, falsedikodekan sebagai alamat 0(yang kebetulan juga merupakan representasi falsedalam C), truesebagai alamat 2(yang kebetulan saja representasi C truebergeser satu bit) dan nilsebagai 4.

Lihat bagian "representasi bilangan bulat, bit tag, nilai yang dialokasikan heap" di https://ocaml.org/learn/tutorials/performance_and_profiling.html untuk penjelasan yang baik.

Jawaban singkatnya adalah untuk kinerja. Saat meneruskan argumen ke suatu fungsi, argumen itu diteruskan sebagai integer atau pointer. Pada level bahasa level mesin tidak ada cara untuk mengetahui apakah register berisi integer atau pointer, itu hanya nilai 32 atau 64 bit. Jadi run time OCaml memeriksa bit tag untuk menentukan apakah yang diterima adalah integer atau pointer. Jika bit tag disetel, maka nilainya adalah bilangan bulat dan diteruskan ke kelebihan beban yang benar. Jika tidak, itu adalah penunjuk dan tipe dicari.

Mengapa hanya bilangan bulat yang memiliki tag ini? Karena segala sesuatu yang lain diteruskan sebagai penunjuk. Apa yang dilewatkan bisa berupa integer atau penunjuk ke beberapa tipe data lainnya. Dengan hanya satu bit tag, hanya ada dua kasus.

Itu tidak persis "digunakan untuk pengumpulan sampah." Ini digunakan untuk membedakan secara internal antara pointer dan integer tanpa kotak.

Saya harus menambahkan tautan ini untuk membantu OP memahami lebih lanjut Jenis floating-point 63-bit untuk 64-bit OCaml

Walaupun judul artikelnya terkesan tentang float, sebenarnya artikel itu berbicara tentangextra 1 bit

Runtime OCaml memungkinkan polimorfisme melalui representasi tipe yang seragam. Setiap nilai OCaml direpresentasikan sebagai satu kata, sehingga dimungkinkan untuk memiliki implementasi tunggal, katakanlah, “daftar hal-hal”, dengan fungsi untuk mengakses (misalnya List.length) dan membangun (misalnya List.map) daftar ini yang berfungsi sama baik itu daftar int, float, atau daftar set integer.

Apa pun yang tidak cocok dengan sebuah kata akan dialokasikan dalam blok di heap. Kata yang mewakili data ini kemudian menjadi penunjuk ke blok. Karena heap hanya berisi sekumpulan kata, semua petunjuk ini disejajarkan: beberapa bit yang paling tidak signifikan selalu tidak disetel.

Konstruktor tanpa argumen (seperti ini: type fruit = Apple | Orange | Banana) dan bilangan bulat tidak mewakili begitu banyak informasi sehingga perlu dialokasikan di heap. Representasinya tidak dikotakkan. Data tersebut langsung berada di dalam kata yang seharusnya menjadi penunjuk. Jadi sementara daftar daftar sebenarnya adalah daftar petunjuk, daftar int berisi int dengan satu tipuan yang lebih sedikit. Fungsi-fungsi yang mengakses dan membangun daftar tidak memperhatikan karena int dan pointer memiliki ukuran yang sama.

Namun, Pengumpul Sampah harus bisa mengenali petunjuk dari bilangan bulat. Pointer menunjuk ke blok yang terbentuk dengan baik di heap yang menurut definisi hidup (karena dikunjungi oleh GC) dan harus ditandai demikian. Sebuah integer dapat memiliki nilai apapun dan dapat, jika tindakan pencegahan tidak dilakukan, secara tidak sengaja terlihat seperti sebuah pointer. Hal ini dapat menyebabkan blok mati terlihat hidup, tetapi yang jauh lebih buruk, ini juga akan menyebabkan GC mengubah bit dalam apa yang dianggap sebagai header dari blok langsung, ketika sebenarnya mengikuti bilangan bulat yang terlihat seperti penunjuk dan mengacaukan pengguna data.

Inilah sebabnya mengapa bilangan bulat yang tidak dikotak menyediakan 31 bit (untuk 32-bit OCaml) atau 63 bit (untuk 64-bit OCaml) ke programmer OCaml. Dalam representasi, di belakang layar, bit yang paling tidak signifikan dari sebuah kata yang mengandung integer selalu diatur, untuk membedakannya dari pointer. Integer 31- atau 63-bit agak tidak biasa, jadi siapa pun yang menggunakan OCaml sama sekali mengetahui hal ini. Apa yang biasanya tidak diketahui oleh pengguna OCaml adalah mengapa tidak ada tipe float 63-bit unboxed untuk 64-bit OCaml.

Mengapa int di OCaml hanya 31 bit?

Pada dasarnya, untuk mendapatkan performa terbaik pada prover teorema Coq dimana operasi yang dominan adalah pencocokan pola dan tipe data yang dominan adalah tipe varian. Representasi data terbaik ditemukan menjadi representasi seragam menggunakan tag untuk membedakan pointer dari data yang tidak dikotakkan.

Tetapi mengapa demikian hanya untuk int dan bukan untuk tipe dasar lainnya?

Tidak hanya itu int. Tipe lain seperti chardan enum menggunakan representasi tag yang sama.