DEV Community: ArtyomKaltovich

The Numeric Tower: Adventures of Numbers in Python and mypy

ArtyomKaltovich — Sat, 13 Aug 2022 12:17:00 +0000

If you've ever felt like you've been bogged down in meetings and discussions that go on and on and there's still no solution, maybe you will fill better if you know that there is a 5 year old issue in mypy about an integer not being a number.

Type hints in python are an interesting topic. People from statically typed languages do not understand how it was possible to create a language without them, and then add them. Lovers of dynamics, do not understand why they should spend time adding types if the code already works, and type analyzers only give you false positive results. While python developers continue to read and debug the code, trying to understand what the author meant and adding type annotations, if they managed to understand it.

However, screwing up types and checking them somewhere on the side really has some problems, for example, we can look into such a seemingly simple topic as numbers.

Python has the following built-in types for numbers: integers, floating point and fixed point reals, rational fractions, and even complex numbers. These types implement certain interfaces (ABCs) organized into the numeric tower (Number, Complex, Real, Rational and Integral). And this is where the problems begin. Some solutions seem clear and valid, for example, you can always pass an int to a function that takes a float, and you can always pass both a float and an int to a function that takes a complex.

def sin(a: float):
    print(isinstance(a, float))


def cos(a:complex):
    print(isinstance(a, complex))


sin(1) # prints False
cos(4.5) # also prints False

Checking this code with mypy will output Success: no issues found in 1 source file. And from a mathematical point of view, this makes sense: any real number is complex, and any integer is real. But there are purists who will not accept such code, for example, in rust, you cannot pass integers to functions that expect a real number.

fn f(a: f32) {
}

fn main() {
    f(4)
}

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
 --> src/main.rs:6:7
  |
6 | f(4)
  | -^
  | | |
  | | expected `f32`, found integer
  | | help: use a float literal: `4.0`
  | arguments to this function are incorrect

As you can see, even in python, a beautiful mathematical abstraction begins to flow, type checks pass in mypy, but isinstance checks return False. So, the type in the signature and the type in isinstance are not the same thing, however, even this is understandable, given the __subclasshook__ and the dynamism of the language.

Also in python, decimal and float are not interchangeable and compatible, although from the mathematical point of view, both are real numbers, but the creators of the language decided that mixing two types in one operation is not worth it, as this can lead to the loss of precision.

>>> Decimal(1) + 2.5
TypeError: unsupported operand type(s) for +: 'decimal.Decimal' and 'float'

mypy knows about this and does not allow such operations:

ws.py:15: error: Unsupported operand types for + ("Decimal" and "float")

Also, a Decimal cannot be passed to a function that expects a complex variable, and an integer cannot be passed to a function that expects a Decimal. Although the mathematical abstraction, in theory, should not stop working from the fact that we changed real floating-point numbers to fixed-point numbers, they still remain real and mathematical operations that are valid on Decimal must also be performed on int. But mypy won't accept such code.

from decimal import Decimal
from numbers import Number


def sin(a: Decimal):
    ...


def cos(a:complex):
    ...


sin(1)
cos(Decimal(1))

ws.py:13: error: Argument 1 to "sin" has incompatible type "int"; expected "Decimal"
ws.py:14: error: Argument 1 to "cos" has incompatible type "Decimal"; expected "complex"

A separate funny moment is that in python bool is inherited from int.

>>> int.__subclasses__()
[bool, ...

from decimal import Decimal


def f(x: float):
    pass

f(Decimal(1)) # ws.py:7: error: Argument 1 to "sin" has incompatible type "Decimal"; expected "float"
f(1==0) # And these lines
f(True) # pass the check

That is, it is impossible to calculate the f function from one, but from the truth - it is possible.

Now back to the issue from the beginning of the article. int, Decimal and float are Number.

isinstance(1, Number) # True
isinstance(2.5, Number) # True
isinstance(Decimal(2.5), Number) # True

But mypy doesn't think so.

from decimal import Decimal
from numbers import Number


def sin(x: Number):
    pass

sin(Decimal(1))
sin(1)
sin(2.5)
sin(True)

ws.py:8: error: Argument 1 to "sin" has incompatible type "Decimal"; expected "number"
ws.py:9: error: Argument 1 to "sin" has incompatible type "int"; expected "number"
ws.py:10: error: Argument 1 to "sin" has incompatible type "float"; expected "number"
ws.py:11: error: Argument 1 to "sin" has incompatible type "bool"; expected "number"

sin(Number(1)) won't work either, since Number is an abstract class.

Python is quite a pleasant language to use, and it is not for nothing that it has become one of the most popular (and by some estimates, the most popular language). And many of the architectural decisions made during the implementation of the language and the interpreter are worthy of study. But, sometimes even such simple entities as numbers lead to the need to make complex and ambiguous decisions, allowing several bugs and non-obviousness in the process. So, if suddenly your boss is dissatisfied with your architecture, you can try to excuse yourself with the fact that not only you fail to create an ideal type hierarchy, even Guido does not always succeed.

Zython (minizinc python-wrapper) after year of development

ArtyomKaltovich — Mon, 24 Jan 2022 20:01:13 +0000

More then a year ago I've started to create python wrapper for minizinc. Which is, probably, the most popular constraint programming tool. You can find more info on what is constraint programming, minizinc, what is it used for in my previous article.

At the release in January 2021 zython supported variables and parameters declaration, arrays, all solving types (satisfy, maximize, minimize), many predefined operations and constraints (and CI of course). It could solve a number of models, some of which were specified in the documentation.

Adding float variable and parameters

But also it lacks some of minizinc features: float and enum types support and sets. I've started with float support. It seems natural and essential for "usual" programming paradigms, e.g. I can't name any popular language without float support (only brainfuck), but in constraint programming it is not so essential, many problems can be solved using integers only, many algorithm were developed only for discreet models. By the fact not every solver support floats (maybe not even the most of them). For example, default zython's solver gecode doesn't fully support them, so it was necessary to add a way the user could specify the solver (of course I've understood it only after I've implemented float variables).

Lets see, how you can use float variable, by solving an easy equation:

import zython as zn


class Model(zn.Model):
    def __init__(self, a, b, c, d, e, f):
        self.x = zn.var(float)
        self.constraints = [a ** 5 * self.x + b ** 4 * self.x +
                            c ** 3 * self.x + d ** 2 * self.x +
                            e * self.x + f == 0]


m = Model(2, 3, 4, 5, 6, 7)
result = m.solve_satisfy(solver="cbc")
print(result["x"])  # -0.03365384615384615

Enums and sets

Adding enums and sets was harder task. First of all, because I've started with adding enums, then I've understood, they are quite useless without sets, and start to add them. This task leads to massive refactoring (some of which still should be done), but it leads to a better code, and now everyone can use enums and sets in zython. Below I will provide an example from documentation:

Let’s imagine you’ve should to fight against Mike Tyson (don’t worry, you have a week to prepare). You should learn several boxing moves, each of them has strength, but you should invest some time to learn it and some money to hire a coach.

Move	Power	Time to learn	Money to learn
jab	1	1	3
cross	2	2	3
uppercut	1	1	3
overhand	2	2	2
hook	3	1	1

import enum
import zython as zn


class Moves(enum.Enum):
    jab = enum.auto()
    cross = enum.auto()
    hook = enum.auto()
    uppercut = enum.auto()
    slip = enum.auto()


class Model(zn.Model):
    def __init__(
            self,
            moves,
            time_available,
            money_available,
            power,
            time,
            money,
    ):
        self.time_available = time_available
        self.money_available = money_available
        self.power = zn.Array(power)
        self.time = zn.Array(time)
        self.money = zn.Array(money)
        self.to_learn = zn.Set(zn.var(moves))
        self.constraints = [
            zn.sum(self.to_learn, lambda move: self.time[move])
                < self.time_available,
            zn.sum(self.to_learn, lambda move: self.money[move])
                < self.money_available,
        ]


model = Model(
    Moves,
    5,
    10,
    [1, 2, 1, 2, 3],
    [1, 2, 1, 3, 1],
    [3, 4, 3, 2, 1],
)
result = model.solve_maximize(
    zn.sum(model.to_learn,
           lambda move: model.power[move])
)
print(f"Moves to learn: {result['to_learn']}, "
      f"power: {result['objective']}")

Other changes

The two changes described above, are not the only ones, which was add to zython. I've added support of increasing, decreasing and allequal constraints, except_0 parameter to alldifferent constraint. New python version was released, so now zython support cpython 3.7 - 3.10.
And a warning in case minizinc wasn't found in $PATH, I hope it will help in installation and integrating zython code.

Conclusion

This year wasn't easy (well not only for me, for everyone), but I've somehow managed to find time to improve zython, which becomes better and better in every version[citation needed]. It is an interesting experience and if you ever thought about starting your own project, you should try.

Constraint Programming in Python or How to Solve Traveling Salesman Problem just Describing it.

ArtyomKaltovich — Wed, 13 Jan 2021 18:56:17 +0000

I guess the most popular programming paradigm is the imperative programming, but it is not the only kind of programming, e.g. functional programming is famous too. Constraint programming is not so popular. But it is very powerful tool to solve combinatorial problems. Instead of implementing the algorithm which solves the problem and then spend a lot of time on debugging, refactoring and optimizing it, constraint programming allows you just describe the model in its own syntax and special program (solver) will find the solution for you (or says if there isn't any). Isn't it cool? When I first met it I was fascinated with such possibility.

Minizinc

Probably the most used constraint programming tool (at least for educational propose) is Minizinc. It provides IDE for model declaration and several built-in solver to look for solution of them. You can download it from the official site.

Simple Model in Minizinc

Let's see an example of model solving, we will start with cryptarithmetic problem. In such kind of problem all letters should be replaced with digits with two main restriction:

equation should be hold
the same digit can’t be assign to different letters and vise versa.

For example let's solve the following equation:

    S E N D
+   M O R E
= M O N E Y

Model structure

In minizinc every model is a collection of variables, parameters and constraints.
Variables are unknown values which should be found by solver, parameters are some constants which are known during model evaluation, you can change parameters from run to run, and this will, obviously, affect result. E.g. number of cities and distances between them are parameters for traveling salesman problem, the path will depends on them, but the programmer can create one model for the problem and then just execute it for different parameters without model source code changes.
Constraints are constraints :) which should be satisfied by variables values.

Model declaration

Lets start actual programming. Here we have 8 variables (S, E, N, D, M, O, R, Y), they are digits, so they can take values from 0 to 9 (S and M from 1 to 9, because the number can't start with 0).

In minizinc syntax this is declared by the following way:

var 1..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 1..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;

Next we should specify equation, in minizinc it is specified in the very common way:

constraint              1000*S + 100*E + 10*N + D
                      + 1000*M + 100*O + 10*R + E
           == 10000*M + 1000*O + 100*N + 10*E + Y;

We also should specify that every variable has its own values, and there shouldn't be any variables with the same value. Minizinc has specific constraint for it alldifferent, but it isn't specified in built-in functions, we should include it be special directive include "alldifferent.mzn";.

And the last thing we should do it to declare how to solve the model, there are 3 variant: satisfy, minimize and maximize, I guess their names are self-explaining :).

Resulting source code

include "alldifferent.mzn";

var 1..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 1..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;

constraint           1000 * S + 100 * E + 10 * N + D
                   + 1000 * M + 100 * O + 10 * R + E
       = 10000 * M + 1000 * O + 100 * N + 10 * E + Y;

constraint alldifferent([S,E,N,D,M,O,R,Y]);

solve satisfy;

output ["   ",show(S),show(E),show(N),show(D),"\n",
        "+  ",show(M),show(O),show(R),show(E),"\n",
        "= ",show(M),show(O),show(N),show(E),show(Y),"\n"];

Minizinc can execute the model and find the solution:

   9567
+  1085
= 10652

By default, minizinc stops execution of satisfy problem after the first solution, this behavior can be changed in the settings, you can reexecute this model and ask minizinc to find all solution, but it will say there is only one :).

First Part Conclusion

Minizinc provides powerful, general and easy to use way to deep into constraint programming. But it uses its own syntax, which slow down the learning and make integration with other programming languages harder.

Integration with Python

minizinc-python solves the second issue, by providing the way to call minizinc models from python, the library will run minizinc, serialize your input and parse output, but the programmer still should write quite a lot lines of code. We can look at the example of solving square equation solving:

import minizinc

# Create a MiniZinc model
model = minizinc.Model()
model.add_string("""
var -100..100: x;
int: a; int: b; int: c;
constraint a*(x*x) + b*x = c;
solve satisfy;
""")

# Transform Model into a instance
gecode = minizinc.Solver.lookup("gecode")
inst = minizinc.Instance(gecode, model)
inst["a"] = 1
inst["b"] = 4
inst["c"] = 0

# Solve the instance
result = inst.solve(all_solutions=True)
for i in range(len(result)):
    print("x = {}".format(result[i, "x"]))

Personally for me it is a problem to remember and recreate such example, and minizinc model (which is just 4 lines of code) is represented as a string, so IDE and python can't highlight the syntax and provide any help and checks for you.

There Must be a Better Way

Why don't we hide all solver lookup and parameter instantiation as well as provide the way to implement models on pure python?

This is what zython (miniZinc pYTHON) does. It is the most simply way to drive into constraint programming.
**from the ways I know
**at least if you are a python developer. :)

Getting Started

To start with zython you should have python 3.6+ and minizinc installed into the default location or available in $PATH.

pip install zython
python
>>> import zython as zn

If everything was installed correctly, there shouldn't be any errors and you can start to play with zython.

Send More Money

At first lets look at the model, we already know - Send More Money problem.

import zython as zn


class MoneyModel(zn.Model):
    def __init__(self):
        self.S = zn.var(range(1, 10))
        self.E = zn.var(range(0, 10))
        self.N = zn.var(range(0, 10))
        self.D = zn.var(range(0, 10))
        self.M = zn.var(range(1, 10))
        self.O = zn.var(range(0, 10))
        self.R = zn.var(range(0, 10))
        self.Y = zn.var(range(0, 10))

        self.constraints = [(self.S * 1000 + self.E * 100 + self.N * 10 + self.D +
                             self.M * 1000 + self.O * 100 + self.R * 10 + self.E ==
                             self.M * 10000 + self.O * 1000 + self.N * 100 + self.E * 10 + self.Y),
                             zn.alldifferent((self.S, self.E, self.N, self.D, self.M, self.O, self.R, self.Y))]

model = MoneyModel()
result = model.solve_satisfy()
print(" ", result["S"], result["E"], result["N"], result["D"])
print(" ", result["M"], result["O"], result["R"], result["E"])
print(result["M"], result["O"], result["N"], result["E"], result["Y"])

It should return the same result as before. It has still pretty a lot of code, isn't it? But if we look more precise we will see, it is mostly variable declaration and arithmetic equation, zython makes all dirty work as finding solver, instantiation parameters, parsing result and running model. All you do is the programming itself. As well zython provides python syntax for model definition, which makes it possible for IDE to highlight your code and check it for errors before running. Zython provides additional checks and error messages during execution.

Sudoku generation

Lets generate sudoku field. We should use zn.Array for it. Array can be both variable and parameter, in this model it is variable, as we don't now the values and want to find them.

import zython as zn


class MyModel(zn.Model):
    def __init__(self):
        self.a = zn.Array(zn.var(range(1, 10)), shape=(9, 9))

        self.constraints = \
            [zn.forall(range(9),
                       lambda i: zn.alldifferent(self.a[i])),
             zn.forall(range(9),
                       lambda i: zn.alldifferent(self.a[:, i])),
             zn.forall(range(3),
                       lambda i: zn.forall(range(3),
                                           lambda j: zn.alldifferent(self.a[i * 3: i * 3 + 3, j * 3: j * 3 + 3]))),
            ]


model = MyModel()
result = model.solve_satisfy()
print(result["a"])

The model should produce something like it:

Traveling Salesman (or Salesperson?) Problem

As I promise we will look at TSP model, it can be declared with the following way:

import zython as zn


class TSP(zn.Model):
    def __init__(self, distances):
        self.distances = zn.Array(distances)
        self.path = zn.Array(zn.var(range(len(distances))),
                             shape=len(distances))
        self.cost = (self._cost(distances))
        self.constraints = [zn.circuit(self.path)]

    def _cost(self, distances):
        return (zn.sum(range(1, len(distances)),
                       lambda i: self.distances[self.path[i - 1],
                                                self.path[i]]) +
                self.distances[self.path[len(distances) - 1],
                               self.path[0]])


distances = [[0, 6, 4, 5, 8],
             [6, 0, 4, 7, 6],
             [4, 4, 0, 3, 4],
             [5, 7, 3, 0, 5],
             [8, 6, 4, 5, 0]]
model = TSP(distances)
result = model.solve_minimize(model.cost)
print(result)

We again used array in the model, but now it is a parameter, which means its values defined before model execution.

Second Part Conclusion

Constraint programming is worth to know paradigm of programming, which can save a lot of time on solving a lot of problem: create schedule, determine which units should be hire to own the strongest army for such amount of resources in your favorite strategy, or what is the strongest build in your favorite RPG, what colors you should use to brush the geographical regions on the map in a way, that all adjacent regions will have different color, and even what is the base timeslot for public transport and which cakes you should bake to maximize your bakery profit.
Zython provide the way to express constraint programming model in pure python and easily solve it. You can see more examples in documentation.
I would like to hear your opinion about this library, don't hesitate to report bug and feature request as will as collaborate and create PR.

Good luck in constraint programming learning.

How The Integer Type is Implemented in CPython

ArtyomKaltovich — Sun, 29 Nov 2020 19:39:25 +0000

It would seem that you can't write an article about an ordinary integer type? However, everything is not so simple here, and the integer type is not so obvious.

If you're wondering why x * 2 is faster than x << 1.

And how to do the following trick:

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

Then you should read this article.

Integer Implementation

There are no primitive types in python - all variables are objects and are allocated in heap. At the same time, integers are represented by only one type (we do not consider decimal) - PyLongObject. It is implemented in the files longobject.h, longintrepr.h and longobject.c, you can see it on CPython project github page.

struct _longobject {
    PyObject_VAR_HEAD // standard header for variable length objects
    digit ob_digit [1]; // array of numbers
};

Any object in CPython includes two fields: ob_refcnt - a counter of references to an object and ob_type - a pointer to the type of an object; to objects that can change their length, the ob_size field is added - the current allocated size (actually used space can be less).

Thus, the integer type is represented by an array of variable length from individual digits, so python supports long arithmetic out of the box, in the second version of the language there was a separate type of "ordinary" integers. "Long" integers were created using the letter L or, if the result of operations between "ordinary" integers caused an overflow, in the third version it was decided to make every integer long by default.

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

The integer value stored by the _longobject can be represented by the next equation:

The digit is either 32-bit unsigned type (uint32_t) on 64-bit systems or a 16-bit unsigned short type on 32-bit systems.

The algorithms used in the implementation impose strict restrictions on SHIFT parameter from the previous formula, in particular, it must be divisible by 15, so for now CPython supports two values: 30 and 15, respectively for 64 and 32-bit systems. For negative values ob_size has a negative value too, zero is set by a number with ob_size = 0.

Arithmetic Operations

When performing arithmetic operations, the interpreter checks the current length of the operands, if they both consist of one digit, then standard arithmetic is performed.

static PyObject *
long_add (PyLongObject * a, PyLongObject * b)
{
    ...
    // both operands fit into one bit
    if (Py_ABS (Py_SIZE (a)) <= 1 && Py_ABS (Py_SIZE (b)) <= 1) {
    // sum them up and return the result
        return PyLong_FromLong (MEDIUM_VALUE (a) + MEDIUM_VALUE (b));
    }
    ...
};

Multiplication has a similar structure, in addition, the interpreter implements the Karatsuba algorithm and fast squaring, but they are not performed with every "long multiplication", but only for sufficiently large numbers, the number of digits in which are set by two constants:

// in case of unequal operands
#define KARATSUBA_CUTOFF 70
// in case of squaring
#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)

static PyObject *
long_mul (PyLongObject * a, PyLongObject * b)
{
    ...
    // both operands fit into one bit
    if (Py_ABS (Py_SIZE (a)) <= 1 && Py_ABS (Py_SIZE (b)) <= 1) {
    // stwodigits is a signed type that can hold two digits
    // int64_t on 64-bit systems and long on 32-bit systems.
        stwodigits v = (stwodigits) (MEDIUM_VALUE (a)) * MEDIUM_VALUE (b);
        return PyLong_FromLongLong ((long long) v);
    }
    ...

    // "School" long multiplication O(N ^ 2) if both operands are small enough.
    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);
    }
    ...
};

Logical Operations and Comparisons

However, shift instructions do not have a check for short integers, they are always executed as long arithmetic. Therefore, multiplying by 2 turns out to be faster than shifting. It is interesting to note that division is still slower than right shift. Right shift also doesn't check for single-digit integers. But division is more complicated: there is only one function for both the quotient and remainder calculation. NULL is passed to the function, if you need to calculate only one, so, the function must check this case too, all this increases the overhead.

The comparison function also has no special case for "short" integers.

static int
long_compare(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t sign;

    // the case, of different size integers
    // just define the longest one with regards to the signs
    if (Py_SIZE(a) != Py_SIZE(b)) {
        sign = Py_SIZE(a) - Py_SIZE(b);
    }
    else {
        Py_ssize_t i = Py_ABS(Py_SIZE(a));
        // run cycle for integers of equal length
        // for "short" integers the number of iterations will be
        // less, no other optimizations are applied
        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;
}

Arrays (lists) of numbers

When creating a variable of an integer type, the interpreter must allocate a sufficient area in dynamic memory, then set the reference counter (type ssize_t), a pointer to the PyLongObject type, the current size of the bit array (also ssize_t) and initialize the array itself. For 64-bit systems, the minimum structure size is: 2 * ssize_t + pointer + digit = 2 * 8 + 8 + 4 = 28 bytes. Additional problems appear when creating lists of numbers: since numbers are not a primitive type, and lists in python store references to objects, they are not sequentially stored in heap.

This placement slows down iterating over the array: in fact, random access is performed, which makes it impossible to predict transitions.

In order to avoid unnecessary allocations of dynamic memory, which slows down the execution time and contributes to memory fragmentation, an optimization is implemented in CPython: at the startup stage, an array of small integers is preallocated: from -5 to 256.

#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257 // As expected in python, the right border is not included.
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS 5
#endif

As a result, a list of numbers in cpython is represented in memory like this:

It is possible to reach the preselected list of small integers from the script, armed with this article and the standard ctypes module:

Disclaimer: The following code is supplied as is, the author assumes no responsibility and cannot guarantee the state of the interpreter, as well as the mental health of you and your colleagues, after running this code.

import ctypes

# PyLongObject structure
class IntStruct (ctypes.Structure):
    # declaration of fields
    _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 (f"IntStruct (ob_digit = {self.ob_digit}, "
                f"ob_size = {self.ob_size}, "
                f"refcount = {self.ob_refcnt})")


if __name__ == '__main__':
    # get the address of number 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

    # change the value in the list of preallocated numbers
    int42.ob_digit = 4
    print (4 == 42) # True
    print (1 + 41) # 4

This list contains honest PyLongObjects, so, they have a reference counter, for example, you can find out how many zeros your script and the interpreter itself are using.

It follows from the internal implementation of integers that arithmetic in cpython cannot be fast, while other languages iterate sequentially over an array, read numbers into registers and directly call several processor instructions, cpython rushes around all memory, executing rather complex methods. In the simplest case of one-bit integers, in which it would be enough to call one instruction, the interpreter must compare the sizes, then create an object in dynamic memory, fill in all the service fields, and return a pointer to it, moreover, these actions require GIL locking. Now you understand why the numpy library was created and why it is so popular.

Boolean Type

I would like to finish the article about an integer type in cpython, suddenly, with information about a boolean type.

The fact is that for a long time in python there was no separate type for boolean variables, all logical functions returned 0 and 1. However, they decided to introduce a new type. At the same time, it was implemented as a child type to an integer.

PyTypeObject PyBool_Type = {
    PyVarObject_HEAD_INIT (& PyType_Type, 0) // the length of the boolean type cannot be changed
                                            // however, since it inherits from integer
                                            // there is already an ob_size field
    "bool", // type name
    sizeof (struct _longobject), // size in memory
    ...
    & PyLong_Type, // base type
    ...
    bool_new, // constructor
};

Moreover, each of the values of the boolean type is a singleton, the boolean variable is a pointer to an instance of True or False (None is implemented in a similar way).

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) is a tricky mechanism for calculating a boolean value, you can see it in the documentation.

This inheritance leads to some funny effects, like the exact equality of True and 1, the impossibility of having both True and 1 as keys in the dictionary and the set, and the admissibility of arithmetic operations on a Boolean type:

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

The python language is great for its flexibility and readability, however, it must be borne in mind that all this has a price, for example, in the form of unnecessary abstractions and overhead, which we often do not think or guess about. I hope this article allowed you to dispel a little the "fog of war" over the source code of the interpreter, perhaps even encourage you to study it. The interpreter code is very easy to read, almost like the code in python itself, and studying it will allow you not only to learn how the interpreter is implemented, but also interesting algorithmic and system solutions, as well as, possibly, write more efficient code or become a developer of cpython itself.