Implementación de tipo entero en CPython

Ya había artículos sobre Habré sobre los detalles de implementación del administrador de memoria de CPython, Pandas . Escribí un artículo sobre la implementación del diccionario .

Parece que puedes escribir sobre un tipo entero regular? Sin embargo, no todo es tan simple y el tipo entero no es tan obvio.

Si se pregunta por qué x * 2 es más rápido que x << 1 .

Y cómo hacer el siguiente truco:

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

Entonces deberías leer este artículo.

No hay tipos primitivos en python: todas las variables son objetos y se asignan en la memoria dinámica. Al mismo tiempo, los enteros están representados por un solo tipo (no consideramos decimales ): PyLongObject. La implementación y las declaraciones de los cuales se encuentran en los archivos longobject.h, longintrepr.h y longobject.c.

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

En cualquier objeto en CPython hay dos campos: ob_refcnt - contador de referencias al objeto y ob_type - puntero al tipo del objeto; a los objetos que pueden cambiar su longitud, se agrega el campo ob_size - el tamaño asignado actual (usado puede ser menor).

Por lo tanto, el tipo entero está representado por una matriz de longitud variable de dígitos separados, por lo que Python fuera de la caja admite aritmética larga, en la segunda versión del lenguaje había un tipo separado de enteros "ordinarios". Los enteros "largos" se crearon usando la letra L o, si el resultado de operaciones con causó desbordamiento por los comunes; en la tercera versión se decidió rechazarlo.

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

El valor entero almacenado por la estructura _longobject es igual a:

$$

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

Como bit, se utilizan el tipo sin signo de 32 bits (uint32_t) en los sistemas de 64 bits y el tipo corto sin signo de 16 bits en los de 32 bits.

Los algoritmos utilizados en la implementación imponen restricciones estrictas al SHIFT de la fórmula anterior, en particular, debe dividirse por 15, por lo que ahora cpython admite dos valores: 30 y 15, respectivamente, para sistemas de 64 y 32 bits. Para valores negativos, ob_size tiene un valor negativo, cero está dado por un número para el cual ob_size = 0.

Al realizar operaciones aritméticas, el intérprete verifica la longitud actual de los operandos, si ambos consisten en un bit, se realiza la aritmética estándar.

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

La multiplicación tiene una estructura similar, además, el intérprete implementa el algoritmo Karatsuba y la cuadratura rápida , sin embargo, no se realizan para cada "multiplicación larga", sino solo para números suficientemente grandes, el número de dígitos en el que se dan dos constantes:

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

Sin embargo, los comandos shift no tienen una verificación para el caso de enteros "cortos", siempre se ejecutan para el caso de aritmética larga. Por lo tanto, multiplicar por 2 es más rápido que el cambio. Es interesante notar que la división es más lenta que el desplazamiento a la derecha, que tampoco verifica el caso de los enteros de un solo dígito. Pero la división es más complicada: hay un método que primero calcula el cociente, luego el resto, se le pasa NULL, si necesita calcular una cosa, es decir, el método también debe verificar este caso, todo esto aumenta la sobrecarga.

La función de comparación tampoco tiene un caso especial para enteros "cortos".

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

Matrices (listas) de números

Al crear una variable de tipo entero, el intérprete debe asignar suficiente espacio en la memoria dinámica, luego establecer el contador de referencia (escriba ssize_t), un puntero para escribir PyLongObject, el tamaño actual de la matriz de bits (también ssize_t) e inicializar la matriz en sí. Para sistemas de 64 bits, el tamaño mínimo de la estructura es: 2 * ssize_t + puntero + dígito = 2 * 8 + 8 + 4 = 28 bytes. Aparecen problemas adicionales al crear listas de números: dado que los números no son un tipo primitivo, y las listas en Python almacenan referencias a objetos, los objetos no están secuencialmente en la memoria dinámica.

Esta disposición ralentiza la iteración sobre la matriz: de hecho, se realiza un acceso aleatorio, lo que hace que sea imposible predecir las transiciones.

Para evitar la asignación excesiva de memoria dinámica, que ralentiza el tiempo de funcionamiento y contribuye a la fragmentación de la memoria, la optimización se implementa en cpython: en la fase de inicio, se asigna previamente una matriz de enteros pequeños: de -5 a 256.

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

Como resultado, la lista de números en cpython se representa en la memoria de la siguiente manera:



Existe la oportunidad de llegar a la lista preseleccionada de enteros pequeños del script, armado con este artículo y el módulo de tipos estándar:

Descargo de responsabilidad: el siguiente código se proporciona tal cual, el autor no asume ninguna responsabilidad y no puede garantizar el estado del intérprete, así como la salud mental de usted y sus colegas, después de ejecutar este código.

 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 honesto se almacena en esta lista, es decir, tienen un contador de referencia, por ejemplo, puede averiguar cuántos ceros usa su script y el intérprete.

De la implementación interna de enteros se deduce que la aritmética en cpython no puede ser rápida, donde otros lenguajes iteran secuencialmente sobre la matriz, leen números en registros y llaman directamente a varias instrucciones de procesador, cpython se etiqueta en toda la memoria, realizando métodos bastante complicados. En el caso más simple de enteros de un solo bit, en el que sería suficiente llamar a una instrucción, el intérprete debe comparar los tamaños, luego crear un objeto en la memoria dinámica, completar los campos de servicio y devolverle un puntero; además, estas acciones requieren un bloqueo GIL. Ahora entiendes por qué surgió la biblioteca numpy y por qué es tan popular.

Me gustaría terminar el artículo sobre todo el tipo en cpython, de repente, con información sobre el tipo booleano.

El hecho es que durante mucho tiempo en Python no hubo un tipo separado para las variables booleanas, todas las funciones lógicas devolvieron 0 y 1. Sin embargo, decidieron introducir un nuevo tipo. Al mismo tiempo, se implementó como un tipo secundario para el conjunto.

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

Además, cada uno de los valores del tipo booleano es un singleton, una variable booleana es un puntero a una instancia de Verdadero o Falso (Ninguno se implementa de manera similar).

 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) es un mecanismo complicado para calcular un valor booleano, puede verlo aquí en la sección sobre la función bool o en la documentación .

Tal legado conduce a algunos efectos divertidos, como la igualdad exacta de True y 1, la incapacidad de tener True y 1 como claves en el diccionario y el conjunto, y la admisibilidad de operaciones aritméticas en el tipo booleano:

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

El lenguaje python es magnífico por su flexibilidad y legibilidad, sin embargo, debe tenerse en cuenta que todo esto tiene un precio, por ejemplo, en forma de abstracciones superfluas y gastos generales, que a menudo no pensamos ni adivinamos. Espero que este artículo te haya permitido disipar un poco la "niebla de guerra" sobre el código fuente del intérprete, tal vez incluso te induzca a estudiarlo. El código del intérprete es muy fácil de leer, casi como el código en Python, y su estudio le permitirá no solo aprender cómo se implementa el intérprete, sino también interesantes soluciones algorítmicas y del sistema, así como posiblemente escribir código más eficiente o convertirse en un desarrollador de cpython.