🙇🏻 🧑🏿‍🤝‍🧑🏾 🆓 Implementasi Jenis Integer di CPython 🛑 🉐 🦏

Sudah ada artikel tentang Habré tentang rincian implementasi manajer memori CPython, Pandas , saya menulis sebuah artikel tentang penerapan kamus .

Tampaknya Anda dapat menulis tentang tipe integer biasa? Namun, tidak semuanya begitu sederhana dan tipe integer tidak begitu jelas.

Jika Anda bertanya-tanya mengapa x * 2 lebih cepat dari x << 1 .

Dan bagaimana cara menghidupkan trik berikut:

>>> 42 == 4 True >>> 42 4 >>> 1 + 41 4

Maka Anda harus membaca artikel ini.

Tidak ada tipe primitif dalam python - semua variabel adalah objek dan dialokasikan dalam memori dinamis. Pada saat yang sama, bilangan bulat diwakili oleh hanya satu jenis (kami tidak mempertimbangkan desimal ) - PyLongObject. Implementasi dan deklarasi yang terletak pada file longobject.h, longintrepr.h dan longobject.c.

 struct _longobject { PyObject_VAR_HEAD //       digit ob_digit[1]; //   };

Dalam objek apa pun di CPython ada dua bidang: ob_refcnt - counter referensi ke objek dan ob_type - pointer ke jenis objek, ke objek yang dapat mengubah panjangnya, bidang ob_size ditambahkan - ukuran yang dialokasikan saat ini (digunakan mungkin kurang).

Dengan demikian, tipe integer diwakili oleh array dengan panjang variabel dari digit yang terpisah, sehingga python di luar kotak mendukung aritmatika yang panjang, dalam versi bahasa kedua ada tipe terpisah dari bilangan bulat "biasa". Bilangan bulat panjang dibuat menggunakan huruf L atau, jika hasil operasi dengan disebabkan meluap oleh yang biasa, dalam versi ketiga diputuskan untuk menolaknya.

  # python2 num1 = 42 print num1, type(num1) # 42 <type 'int'> num2 = 42L print num2, type(num2) # 42 <type 'long'> num3 = 2 ** 100 print num3, type(num3) # 1267650600228229401496703205376 <type 'long'>

Nilai integer yang disimpan oleh struktur _longobject sama dengan:

s u m_{i = 0}^{a b s (o b_{s} i z e) - 1} o b_{d} i g i t_{i} * 2^{S H I F T * i}

$\ sum_ {i = 0} ^ {abs (ob \ _size) -1} {ob \ _digit_i * 2 ^ {SHIFT * i}}$

Sebagai bit, tipe unsigned 32-bit (uint32_t) pada sistem 64-bit dan tipe pendek 16-bit unsigned pada tipe 32-bit digunakan.

Algoritma yang digunakan dalam implementasi memberlakukan pembatasan ketat pada SHIFT dari formula sebelumnya, khususnya, harus dibagi 15, jadi sekarang cpython mendukung dua nilai: 30 dan 15, masing-masing, untuk sistem 64 dan 32-bit. Untuk nilai negatif, ob_size memiliki nilai negatif, nol diberikan oleh angka yang ob_size = 0.

Saat melakukan operasi aritmatika, penerjemah memeriksa panjang operan saat ini, jika keduanya terdiri dari satu bit, maka aritmatika standar dilakukan.

 static PyObject * long_add(PyLongObject *a, PyLongObject *b) { ... //   -     if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) { //      return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b)); } ... };

Multiplikasi memiliki struktur yang serupa, di samping itu, penerjemah mengimplementasikan algoritma Karatsuba dan quick squaring , namun, mereka tidak dilakukan untuk setiap "multiplikasi panjang", tetapi hanya untuk jumlah yang cukup besar, jumlah digit yang diberikan oleh dua konstanta:

 //     #define KARATSUBA_CUTOFF 70 //      #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)

 static PyObject * long_mul(PyLongObject *a, PyLongObject *b) { ... //   -     if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) { // stwodigits -  ,    // int64_t  64-   long  32-. stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b); return PyLong_FromLongLong((long long)v); } ... // ""    O(N^2),     . i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF; if (asize <= i) { if (asize == 0) return (PyLongObject *)PyLong_FromLong(0); else return x_mul(a, b); } ... };

Namun, perintah shift tidak memiliki pemeriksaan untuk kasus bilangan bulat "pendek", mereka selalu dieksekusi untuk kasus aritmatika panjang. Oleh karena itu, mengalikan dengan 2 lebih cepat daripada shift. Sangat menarik untuk dicatat bahwa divisi ini lebih lambat daripada shift kanan, yang juga tidak memeriksa kasus integer satu digit. Tetapi pembagiannya lebih rumit: ada satu metode yang pertama menghitung hasil bagi, kemudian sisanya, NULL diteruskan ke sana, jika Anda perlu menghitung satu hal, yaitu, metode harus memeriksa kasus ini juga, semua ini meningkatkan overhead.

Fungsi perbandingan juga tidak memiliki kasing khusus untuk bilangan bulat "pendek".

 static int long_compare(PyLongObject *a, PyLongObject *b) { Py_ssize_t sign; // ,        //        if (Py_SIZE(a) != Py_SIZE(b)) { sign = Py_SIZE(a) - Py_SIZE(b); } else { Py_ssize_t i = Py_ABS(Py_SIZE(a)); //  ""        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) ; if (i < 0) sign = 0; else { sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i]; if (Py_SIZE(a) < 0) sign = -sign; } } return sign < 0 ? -1 : sign > 0 ? 1 : 0; }

Array (daftar) angka

Saat membuat variabel tipe integer, juru bahasa harus mengalokasikan area yang cukup dalam memori dinamis, kemudian mengatur penghitung referensi (tipe ssize_t), pointer untuk mengetik PyLongObject, ukuran saat ini dari bit array (juga ssize_t) dan menginisialisasi array itu sendiri. Untuk sistem 64-bit, ukuran struktur minimum adalah: 2 * ssize_t + pointer + digit = 2 * 8 + 8 + 4 = 28 byte. Masalah tambahan muncul saat membuat daftar angka: karena angka bukan tipe primitif, dan daftar dalam python menyimpan referensi ke objek, objek tidak berurutan dalam memori dinamis.

Pengaturan ini memperlambat iterasi di atas array: pada kenyataannya, akses acak dilakukan, yang membuatnya tidak mungkin untuk memprediksi transisi.

Untuk menghindari alokasi memori dinamis yang berlebihan, yang memperlambat waktu pengoperasian dan berkontribusi pada fragmentasi memori, optimisasi diimplementasikan dalam cpython: pada fase start-up, array bilangan bulat kecil telah dialokasikan sebelumnya: dari -5 hingga 256.

 #ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257 //     python    . #endif #ifndef NSMALLNEGINTS #define NSMALLNEGINTS 5 #endif

Akibatnya, daftar angka dalam cpython diwakili dalam memori sebagai berikut:

Ada peluang untuk mencapai daftar bilangan bulat kecil yang sudah dipilih sebelumnya dari skrip, dipersenjatai dengan artikel ini dan modul ctypes standar:

Penafian: Kode berikut diberikan sebagaimana adanya, penulis tidak bertanggung jawab dan tidak dapat menjamin keadaan penerjemah, serta kesehatan mental Anda dan kolega Anda, setelah menjalankan kode ini.

 import ctypes #  PyLongObject class IntStruct(ctypes.Structure): #   _fields_ = [("ob_refcnt", ctypes.c_long), ("ob_type", ctypes.c_void_p), ("ob_size", ctypes.c_long), ("ob_digit", ctypes.c_int)] def __repr__(self): return ("IntStruct(ob_digit={self.ob_digit}, ob_size={self.ob_size}, " "refcount={self.ob_refcnt})").format(self=self) if __name__ == '__main__': #    42 int42 = IntStruct.from_address(id(42)) print(int42) int_minus_2 = IntStruct.from_address(id(-2)) print(int_minus_2) # ob_digit=2, ob_size=-1 #       int42.ob_digit = 4 print(4 == 42) # True print(1 + 41) # 4

PyLongObject jujur disimpan dalam daftar ini, yaitu, mereka memiliki counter referensi, misalnya, Anda dapat mengetahui berapa nol nol skrip Anda dan penggunaan interpreter.

Dari implementasi internal bilangan bulat, aritmatika dalam cpython tidak bisa cepat, di mana bahasa lain berurutan di atas array, membaca angka ke register dan secara langsung memanggil beberapa instruksi prosesor, cpython ditandai di seluruh memori, melakukan metode yang agak rumit. Dalam kasus bilangan bulat single-bit yang paling sederhana, di mana cukup untuk memanggil satu instruksi, penerjemah harus membandingkan ukuran, kemudian membuat objek dalam memori dinamis, mengisi bidang layanan, dan mengembalikan pointer ke dalamnya, apalagi tindakan ini memerlukan kunci GIL. Sekarang Anda mengerti mengapa perpustakaan numpy muncul dan mengapa sangat populer.

Saya ingin menyelesaikan artikel tentang seluruh tipe cpython, tiba-tiba, dengan informasi tentang tipe boolean.

Faktanya adalah bahwa untuk waktu yang lama dalam python tidak ada tipe terpisah untuk variabel Boolean, semua fungsi logis mengembalikan 0 dan 1. Namun, mereka memutuskan untuk memperkenalkan tipe baru. Apalagi itu diterapkan sebagai tipe anak untuk keseluruhan.

 PyTypeObject PyBool_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) //       // ,       //     ob_size "bool", //   sizeof(struct _longobject), //    ... &PyLong_Type, //   ... bool_new, //  };

Selain itu, masing-masing nilai dari tipe Boolean adalah singleton, variabel Boolean adalah pointer ke turunan True atau False (Tidak ada yang diimplementasikan dengan cara yang sama).

 struct _longobject _Py_FalseStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 0) { 0 } }; struct _longobject _Py_TrueStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 1) { 1 } }; static PyObject * bool_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *x = Py_False; long ok; if (!_PyArg_NoKeywords("bool", kwds)) return NULL; if (!PyArg_UnpackTuple(args, "bool", 0, 1, &x)) return NULL; ok = PyObject_IsTrue(x); if (ok < 0) return NULL; return PyBool_FromLong(ok); } PyObject *PyBool_FromLong(long ok) { PyObject *result; if (ok) result = Py_True; else result = Py_False; Py_INCREF(result); return result; }

PyObject_IsTrue (x) adalah mekanisme rumit untuk menghitung nilai Boolean, Anda dapat melihatnya di sini di bagian fungsi bool atau dalam dokumentasi .

Warisan semacam itu mengarah ke beberapa efek lucu, seperti kesetaraan yang tepat dari True dan 1, ketidakmampuan untuk memiliki True dan 1 sebagai kunci dalam kamus dan set, dan penerimaan operasi aritmatika pada tipe Boolean:

 >>> True == 1 True >>> {True: "true", 1: "one"} {True: 'one'} >>> True * 2 + False / (5 * True) - (True << 3) -6.0 >>> False < -1 False

Bahasa python luar biasa untuk fleksibilitas dan keterbacaannya, namun, harus diingat bahwa semua ini ada harganya, misalnya, dalam bentuk abstraksi dan overhead yang berlebihan, yang sering kita tidak pikirkan atau tebak. Saya harap artikel ini memungkinkan Anda untuk menghilangkan "kabut perang" sedikit lebih dari kode sumber penerjemah, bahkan mungkin mendorong Anda untuk mempelajarinya. Kode interpreter sangat mudah dibaca, hampir seperti kode pada python itu sendiri, dan mempelajarinya akan memungkinkan Anda untuk tidak hanya mempelajari bagaimana penerjemah diimplementasikan, tetapi juga solusi algoritmik dan sistem yang menarik, serta mungkin menulis kode yang lebih efisien atau menjadi pengembang cpython sendiri.

Implementasi Jenis Integer di CPython

Array (daftar) angka

More articles: