Implementação de tipo inteiro no CPython

Já havia artigos em Habré sobre os detalhes de implementação do gerenciador de memória do CPython, Pandas , escrevi um artigo sobre a implementação do dicionário .

Parece que você pode escrever sobre um tipo inteiro regular? No entanto, nem tudo é tão simples e o tipo inteiro não é tão óbvio.

Se você está se perguntando por que x * 2 é mais rápido que x << 1 .

E como iniciar o seguinte truque:

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

Então você deve ler este artigo.

Não há tipos primitivos em python - todas as variáveis ​​são objetos e são alocadas na memória dinâmica. Ao mesmo tempo, números inteiros são representados por apenas um tipo (não consideramos decimal ) - PyLongObject. A implementação e as declarações estão nos arquivos longobject.h, longintrepr.he longobject.c.

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

Em qualquer objeto no CPython, existem dois campos: ob_refcnt - contador de referências ao objeto e ob_type - ponteiro para o tipo do objeto; para objetos que podem alterar seu comprimento, o campo ob_size é adicionado - o tamanho alocado atual (usado pode ser menor).

Assim, o tipo inteiro é representado por uma matriz de comprimento variável a partir de dígitos separados, de modo que o python pronto para uso suporta aritmética longa, na segunda versão do idioma havia um tipo separado de números inteiros “comuns”. causou um transbordamento por outros comuns; na terceira versão, foi decidido recusar.

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

O valor inteiro armazenado pela estrutura _longobject é igual a:

$$

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

Um tipo não assinado de 32 bits (uint32_t) em sistemas de 64 bits e um tipo curto não assinado de 16 bits em 32 bits são usados ​​como um bit.

Os algoritmos usados ​​na implementação impõem restrições estritas ao SHIFT da fórmula anterior, em particular, devem ser divididos por 15; agora, o cpython suporta dois valores: 30 e 15, respectivamente, para sistemas de 64 e 32 bits. Para valores negativos, ob_size tem um valor negativo, zero é dado por um número para o qual ob_size = 0.

Ao executar operações aritméticas, o intérprete verifica o comprimento atual dos operandos; se os dois consistem em um bit, a aritmética padrão é executada.

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

A multiplicação possui uma estrutura semelhante; além disso, o intérprete implementa o algoritmo Karatsuba e o quadrado rápido , no entanto, eles não são executados para cada "multiplicação longa", mas apenas para números suficientemente grandes, o número de dígitos que são dados por duas 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); } ... }; 

No entanto, os comandos shift não têm uma verificação para o caso de números inteiros "curtos"; eles sempre são executados para o caso da aritmética longa. Portanto, multiplicar por 2 é mais rápido que o turno. É interessante notar que a divisão é mais lenta que o turno certo, o que também não verifica o caso de números inteiros de um dígito. Mas a divisão é mais complicada: há um método que primeiro calcula o quociente e, em seguida, o restante NULL é passado a ela, se você precisar calcular uma coisa, ou seja, o método deve verificar esse caso também, tudo isso aumenta a sobrecarga.

A função de comparação também não possui um caso especial para números inteiros "curtos".

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

Matrizes (listas) de números

Ao criar uma variável de tipo inteiro, o intérprete deve alocar espaço suficiente na memória dinâmica e definir o contador de referência (tipo ssize_t), um ponteiro para digitar PyLongObject, o tamanho atual da matriz de bits (também ssize_t) e inicializar a própria matriz. Para sistemas de 64 bits, o tamanho mínimo da estrutura é: 2 * ssize_t + ponteiro + dígito = 2 * 8 + 8 + 4 = 28 bytes. Problemas adicionais aparecem ao criar listas de números: como os números não são do tipo primitivo e as listas no python armazenam referências a objetos, os objetos não estão seqüencialmente na memória dinâmica.

Esse arranjo diminui a iteração sobre a matriz: na verdade, o acesso aleatório é realizado, o que torna impossível prever transições.

Para evitar alocação excessiva de memória dinâmica, que diminui o tempo de operação e contribui para a fragmentação da memória, a otimização é implementada em cpython: na fase de inicialização, uma matriz de números inteiros pequenos é pré-alocada: de -5 a 256.

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

Como resultado, a lista de números em cpython é representada na memória da seguinte maneira:



Há uma oportunidade de acessar a lista pré-selecionada de números inteiros pequenos do script, armada com este artigo e o módulo ctypes padrão:

Isenção de responsabilidade: O código a seguir é fornecido como está, o autor não assume nenhuma responsabilidade e não pode garantir o estado do intérprete, bem como a saúde mental de você e seus colegas, depois de executar 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 

O PyLongObject honesto está armazenado nesta lista, ou seja, eles têm um contador de referência, por exemplo, você pode descobrir quantos zeros seu script e o intérprete usam.

Da implementação interna de números inteiros, segue-se que a aritmética em cpython não pode ser rápida, onde outras linguagens iteram sequencialmente sobre o array, lendo números em registradores e chamando diretamente várias instruções do processador, cpython é marcado em toda a memória, executando métodos bastante complicados. No caso mais simples de números inteiros de um bit, no qual seria suficiente chamar uma instrução, o intérprete deve comparar os tamanhos, criar um objeto na memória dinâmica, preencher os campos de serviço e retornar um ponteiro para ele; além disso, essas ações requerem um bloqueio GIL. Agora você entende por que a biblioteca numpy surgiu e por que é tão popular.

Gostaria de terminar o artigo sobre todo o tipo em cpython, de repente, com informações sobre o tipo booleano.

O fato é que, durante muito tempo em python, não havia um tipo separado para variáveis ​​booleanas, todas as funções lógicas retornavam 0 e 1. No entanto, eles decidiram introduzir um novo tipo. Ao mesmo tempo, foi implementado como um tipo filho para o todo.

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

Além disso, cada um dos valores do tipo booleano é um singleton, uma variável booleana é um ponteiro para uma instância de True ou False (nenhum é implementado de maneira semelhante).

 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) é um mecanismo complicado para calcular um valor booleano, você pode vê-lo aqui na seção sobre a função bool ou na documentação .

Esse legado leva a alguns efeitos engraçados, como a exata igualdade de True e 1, a incapacidade de ter True e 1 como chaves no dicionário e no conjunto e a admissibilidade de operações aritméticas no tipo booleano:

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

A linguagem python é magnífica por sua flexibilidade e legibilidade, no entanto, deve-se ter em mente que tudo isso tem um preço, por exemplo, na forma de abstrações supérfluas e sobrecarga, sobre as quais muitas vezes não pensamos ou pensamos. Espero que este artigo tenha permitido que você dissipe um pouco o “nevoeiro da guerra” sobre o código-fonte do intérprete, talvez até induza você a estudá-lo. O código do intérprete é muito fácil de ler, quase como o código do próprio python, e seu estudo permitirá que você não apenas aprenda como o interpretador é implementado, mas também soluções algorítmicas e de sistema interessantes, além de possivelmente escrever um código mais eficiente ou se tornar um desenvolvedor do próprio cpython.