Pertanyaan bagaimana daftar yang dibuat oleh erlang vm?


Ketika saya membuat daftar di erlang, seperti di shell erlang:

1> [1, 2].

Dari apa yang saya pahami, di vm daftar ini akan direpresentasikan sebagai daftar tertaut tunggal.

Bagaimana struktur ini dibuat oleh runtime erlang? Misalnya, apakah itu dibangun seperti ini:

  1. buat struktur dalam memori untuk menyimpan daftar yang mengakhiri daftar
  2. buat struktur di memori untuk menahan item '2', dan referensi ke daftar kosong.
  3. buat struktur di memori untuk menahan item '1', dan referensi ke item '2'.

Apakah saya benar dalam berpikir kode c dan erlang berikut adalah di mana sebagian besar pekerjaan dilakukan?

erl_term.h mengandung makro make_list tapi aku belum bisa menemukan implementasinya ...


5
2017-08-04 18:46


asal


Jawaban:


The BEAM implementasi VM BEAM menggunakan teknik yang tanggal kembali ke implementasi Lisp pertama kembali ke tahun 60an atau awal 70-an. Kadang-kadang disebut sebagai pointer yang ditandai atau diketik. (Tag) Teknik ini tidak menyimpan jenis target dalam objek target (mencantumkan CONS dalam kasus ini) tetapi di penunjuk itu sendiri atau menyimpan nilai skalar di tempat yang biasanya berupa penunjuk. Hal ini memungkinkan menyimpan jumlah memori yang cukup baik terutama dalam bahasa yang diketik secara dinamis sebagai LISP atau Erlang. (Itu menarik di masa lalu ketika memori sangat mahal dan menjadi penting lagi saat ini ketika CPU menjadi jauh lebih cepat daripada memori dan cache miss / hit menentukan kecepatan algoritma.) Sebagai kerugian, itu juga mengarah ke kode sedikit membingungkan. Seluruh bagian yang berhubungan dengan konstruksi daftar dimulai pada baris 216 dari erl_term.h. Anda dapat mencatat ada makro

#define _unchecked_make_list(x) ((Uint) COMPRESS_POINTER(x) + TAG_PRIMARY_LIST)

yang merupakan makro yang Anda cari. Ini milikmu make_list. Garis

_ET_DECLARE_CHECKED(Eterm,make_list,const Eterm*)

Akan membuat versi yang dicentang ketika dikompilasi ET_DEBUG. (Lihat keterangan lebih lanjut.) Makro make_list

#define make_list(x)        _ET_APPLY(make_list,(x))

hanya akan memanggil diperiksa atau tidak dicentang versi dari make_list. Makro yang benar-benar menyusun daftar adalah

#define CONS(hp, car, cdr) \
        (CAR(hp)=(car), CDR(hp)=(cdr), make_list(hp))

#define CAR(x)  ((x)[0])
#define CDR(x)  ((x)[1])

Struktur sel daftar hanya dua kali berturut-turut Uint nilai pada heap (hp) alamat mana dikompresi dan diberi tag (Lihat _unchecked_make_list). Semoga uraian ini membantu Anda.


4
2017-08-05 17:51