Python Internals Serie: Int (Long) Object

This reminds me of my favourite gotcha in python - that parsing integers is O(n^2).

This is because (conceptually at least - there might be some optimizations that change the details slightly) an integer is parsed by parsing each digit in a loop, and keeping a running total `value = 10 * value + digit`. This seems O(n), until you realise that the "10 * value + digit" operation takes O(log(value)) because of the internal digit-based representation. log(value) is proportional to the number of parsed digits so far, so we can say that the `value = 10 * value + digit` step is O(n), making the whole loop O(n^2).

Some basic timing tests bear this out - on my machine, a 1000-digit number takes ~10us to parse but a 1000000-digit number (which is a 1MB payload - within the possibility of maliciously provided input) takes 5sec (that is, 5000000x longer for a 1000x longer input).

As a fun aside, I was able to write a replacement int() function optimised for numbers this large that is O(n log n). It does this by splitting the input string in two, parsing both sides recursively (switching to native int() below a size threshold) then joining them together with `left * 10*len(right_str) + right`.

Though given that we're parsing base10 digits and the internal representation uses a power of 10 as digits (which I only learned today - I'd assumed the internal digits would be powers of 2), it would be possible to special-case parsing of base10 integers so that it's O(n), by just grouping digits directly into internal digits instead of doing true multiply operations. Given base10 parsing is by far the most common case, that's an optimization that may be worth doing.

One of my favourite things about Python is that its integers are true integers: they do not overflow or wrap. In my opinion, this is the correct default for most programming languages (in fact, I would have gone a step further and made integer division return fractions rather than floats by default, as well). It removes so many problems (especially for beginners) since it is the way that integers work in the real world: for example x + 1 > x always, with no exceptions.

Of course for efficiency concerns, programmers should have access to fixed-width integers as well, but I think that true integers should be the default. It was also contemplated for Go [1], and was pointed out that true integers benefit from being a core language feature, since the compiler can perform a lot of SMI (SMall Integer) optimisations, which essentially use machine integers for small enough integers, before switching to a more complicated implementation. They also recognise that the biggest benefit to a bigint type is making it the default integer type.

[1]: https://github.com/golang/go/issues/19623

One important detail: "digit" when talking about sdigit & ob_digit are not base-10 digits, but base 10000 for 32-bit CPython and base 1000000000 for 64-bit CPython!

That means PY_SIZE(-15) is -1, not -2! And the maximum representable integer in Python should be closer to 10000 * (sys.maxsize / 2) for 32-bit and 1000000000 * (sys.maxsize / 4) for 64-bit.

For reference, here is the live copy of longobject.c: https://github.com/python/cpython/blob/master/Objects/longob...

Python 2 had distinct `int` and `long` types, but Python 3 merged them together into just `int`.

I wasn't sure if the internal C implementation code still used `long`/`Long` for naming, but this blog post and official source code shows that the naming still exists.

BTW, the use of a size 1 array in the struct is a common 'hack', which has some form of dynamic arrays in structs. When the object is allocated through malloc, the size of the struct is actually smaller than the size you want for the array, so you allocate the size you want for the struct and add it to the size you want for the array. You can then access this memory after the structure, since it's technically allocated a part of it. As to why it is size 1, and not size 0, some compilers don't accept a size 0 array, so it's probably size 1 to ensure compatibility with those compilers. This is commonly referred to as the 'C Struct Hack'.

What does "serie" mean? It's not an English word.

`10**sys.maxsize` o_o