تنفيذ عدد صحيح في CPython

كانت هناك بالفعل مقالات عن Habré حول تفاصيل تنفيذ مدير ذاكرة CPython ، Pandas ، كتبت مقالًا حول تنفيذ القاموس .

يبدو أنه يمكنك الكتابة عن نوع عدد صحيح منتظم؟ ومع ذلك ، ليس كل شيء بسيطًا جدًا ونوع الأعداد الصحيحة غير واضح.

إذا كنت تتساءل لماذا x * 2 أسرع من x << 1 .

وكيف تحريك الخدعة التالية:

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

ثم يجب عليك قراءة هذا المقال.

لا توجد أنواع بدائية في الثعبان - كل المتغيرات هي كائنات ويتم تخصيصها في الذاكرة الديناميكية. في الوقت نفسه ، يتم تمثيل الأعداد الصحيحة بنوع واحد فقط (لا نعتبر العلامة العشرية ) - PyLongObject. تطبيق والإعلانات التي تكمن في ملفات longobject.h و longintrepr.h و longobject.c.

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

يوجد في أي كائن في CPython حقلان: ob_refcnt - عداد الإشارات إلى الكائن و ob_type - مؤشر لنوع الكائن ؛ إلى الكائنات التي يمكن تغيير طولها ، يضاف حقل ob_size - الحجم المخصص الحالي (قد يكون المستخدم أقل).

وبالتالي ، يتم تمثيل نوع الأعداد الصحيحة بمجموعة من الطول المتغير من أرقام منفصلة ، لذلك فإن الثعبان خارج الصندوق يدعم الحساب الطويل ، في الإصدار الثاني من اللغة كان هناك نوع منفصل من الأعداد الصحيحة "العادية". تم إنشاء أعداد صحيحة "طويلة" باستخدام الحرف L أو إذا كانت نتيجة العمليات مع تسبب في تجاوز من قبل تلك العادية ؛ في الإصدار الثالث تقرر رفض ذلك.

  # 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'> 

قيمة عدد صحيح المخزنة بواسطة بنية _longobject تساوي:

$$

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

يتم استخدام نوع 32 بت غير موقعة (uint32_t) على أنظمة 64 بت ونوع قصير غير موقّع 16 بت على 32 بت.

تفرض الخوارزميات المستخدمة في التنفيذ قيودًا صارمة على SHIFT من الصيغة السابقة ، على وجه الخصوص ، يجب تقسيمها على 15 ، لذلك يدعم cpython الآن قيمتين: 30 و 15 ، على التوالي ، للأنظمة 64 و 32 بت. بالنسبة للقيم السالبة ، يكون ob_size له قيمة سالبة ، ويتم إعطاء الصفر من خلال رقم الذي ob_size = 0.

عند إجراء العمليات الحسابية ، يقوم المترجم بالتحقق من الطول الحالي للمعاملات ، إذا كان كلاهما يتكون من بت واحد ، ثم يتم تنفيذ الحساب القياسي.

 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)); } ... }; 

الضرب له بنية مماثلة ، بالإضافة إلى ذلك ، يقوم المترجم بتنفيذ خوارزمية Karatsuba والتربيع السريع ، ومع ذلك ، لا يتم تنفيذها لكل "ضرب طويل" ، ولكن فقط لأعداد كبيرة بما فيه الكفاية ، وعدد الأرقام التي يتم تقديمها بواسطة ثوابتين:

 //     #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); } ... }; 

ومع ذلك ، لا تملك أوامر shift فحصًا لحالة الأعداد الصحيحة "القصيرة" ؛ يتم تنفيذها دائمًا في حالة الحساب الطويل. لذلك ، ضرب 2 أسرع من التحول. من المثير للاهتمام أن نلاحظ أن التقسيم أبطأ من التحول الصحيح ، والذي لا يتحقق أيضًا من حالة الأعداد الصحيحة المكونة من رقم واحد. لكن القسمة أكثر تعقيدًا: هناك طريقة واحدة تحسب أولاً الحاصل ، ثم الباقي ، يتم تمرير NULL إليها ، إذا كنت بحاجة إلى حساب شيء واحد ، وهو أن الطريقة يجب أن تتحقق من هذه الحالة أيضًا ، كل هذا يزيد من الحمل.

لا تشتمل وظيفة المقارنة أيضًا على حالة خاصة للأعداد الصحيحة "القصيرة".

 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; } 

صفائف (قوائم) الأرقام

عند إنشاء متغير نوع صحيح ، يجب على المترجم تخصيص مساحة كافية في الذاكرة الديناميكية ، ثم تعيين عداد المرجع (type ssize_t) ، وهو مؤشر لكتابة PyLongObject ، والحجم الحالي لصفيف البت (ssize_t) الحالي وتهيئة الصفيف نفسه. بالنسبة لأنظمة 64 بت ، يكون الحد الأدنى لحجم الهيكل: 2 * ssize_t + pointer + digit = 2 * 8 + 8 + 4 = 28 بايت. تظهر مشاكل إضافية عند إنشاء قوائم الأرقام: بما أن الأرقام ليست نوعًا بدائيًا ، والقوائم الموجودة في مخزن python تشير إلى الكائنات ، فإن الكائنات ليست متتابعة في الذاكرة الديناميكية.

يؤدي هذا الترتيب إلى إبطاء التكرار على المصفوفة: في الواقع ، يتم الوصول العشوائي ، مما يجعل من المستحيل التنبؤ بالانتقالات.

لتجنب التخصيص المفرط للذاكرة الديناميكية ، مما يبطئ وقت التشغيل ويساهم في تجزئة الذاكرة ، يتم تنفيذ التحسين في cpython: في مرحلة البدء ، يتم تخصيص مجموعة من الأعداد الصحيحة الصغيرة: من -5 إلى 256.

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

نتيجة لذلك ، يتم تمثيل قائمة الأرقام في cpython في الذاكرة كما يلي:



هناك فرصة للوصول إلى قائمة محددة مسبقًا من أعداد صحيحة صغيرة من البرنامج النصي ، مسلحة بهذه المقالة ووحدة نمطية ctypes القياسية:

إخلاء المسؤولية: يتم توفير الكود التالي كما هو ، لا يتحمل المؤلف أية مسؤولية ولا يمكنه ضمان حالة المترجم الشفهي ، وكذلك الصحة العقلية لك ولزملائك ، بعد تشغيل هذا الرمز.

 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 

يتم تخزين Honest PyLongObject في هذه القائمة ، أي أنها تحتوي على عداد مرجعي ، على سبيل المثال ، يمكنك معرفة عدد الأصفار التي يستخدمها النص البرمجي واستخدام المترجم.

من التطبيق الداخلي للأعداد الصحيحة ، يترتب على ذلك أن الحساب في cpython لا يمكن أن يكون سريعًا ، حيث تتكرر اللغات الأخرى بشكل متتابع على المصفوفة ، وقراءة الأرقام في السجلات والاتصال مباشرة بالعديد من إرشادات المعالج ، يتم تمييز cpython في جميع أنحاء الذاكرة ، مع تنفيذ طرق معقدة إلى حد ما. في أبسط الحالات للأعداد الصحيحة ذات البت الواحد ، والتي ستكون كافية لاستدعاء تعليمة واحدة ، يجب أن يقوم المترجم بمقارنة الأحجام ، ثم إنشاء كائن في الذاكرة الديناميكية ، وملء حقول الخدمة ، وإرجاع مؤشر إليها ؛ علاوة على ذلك ، تتطلب هذه الإجراءات قفل GIL. أنت الآن تفهم سبب ظهور المكتبة الغريبة ولماذا تحظى بشعبية كبيرة.

أرغب في إنهاء المقالة المتعلقة بالنوع الكامل في cpython ، فجأة ، بمعلومات حول النوع Boolean.

الحقيقة هي أنه لفترة طويلة في الثعبان لم يكن هناك نوع منفصل للمتغيرات المنطقية ، فكل الوظائف المنطقية ترجع 0 و 1. ومع ذلك ، فقد قرروا إدخال نوع جديد. في الوقت نفسه ، تم تنفيذه كنوع تابع إلى الكل.

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

علاوة على ذلك ، كل من قيم نوع Boolean هي حرف مفرد ، متغير Boolean هو مؤشر لمثيل True أو False (لا يتم تطبيق None بطريقة مماثلة).

 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) عبارة عن آلية صعبة لحساب قيمة منطقية ، يمكنك أن ترى ذلك هنا في القسم الخاص بوظيفة bool أو في الوثائق .

يؤدي هذا الإرث إلى بعض التأثيرات المضحكة ، مثل المساواة الحقيقية بين True و 1 ، وعدم القدرة على وجود True و 1 كمفاتيح في القاموس والمجموعة ، ومقبولية العمليات الحسابية على نوع Boolean:

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

لغة الثعبان رائعة بسبب مرونتها وقابليتها للقراءة ، ومع ذلك ، يجب أن يؤخذ في الاعتبار أن كل هذا يأتي بثمن ، على سبيل المثال ، في شكل تجريدات زائدة عن الحاجة ونفقات عامة ، والتي غالباً ما لا نفكر فيها أو نخمنها. آمل أن يكون هذا المقال قد سمح لك بتبديد "ضباب الحرب" بقليل على الكود المصدري للمترجم الشفوي ، وربما حتى يحثك على دراسته. من السهل جدًا قراءة رمز المترجم الشفهي ، تمامًا مثل الكود الموجود على بيثون نفسه ، وستتيح لك دراسته معرفة ليس فقط كيفية تنفيذ المترجم الشفهي ، ولكن أيضًا حلول الخوارزمية المثيرة للاهتمام وحلول النظام ، فضلاً عن إمكانية كتابة كود أكثر كفاءة أو أن تصبح مطور cpython نفسه.