Use canonical representation for small integers

[lpereira]

Currently, CPython has only one representation for integers, which can hold arbitrarily long numbers. This simplifies things -- previous Python had two different integer objects, and implementing specialized opcodes would be quite a bit more laborious. Given that numbers that wouldn't fit in a machine register are far rarer than those that don't, it should be beneficial to using a more efficient representation for these "small" numbers.

[lpereira]

Questions to answer after some investigations:

• Is the cost of keeping the reciprocal of that number stored somewhere worth it? This can improve division performance slightly
• Are the compilers generating the most efficient instructions for the use case we're interested in? Would using inline assembly in these cases help us a bit?
• Maybe look into doing some strength reduction specialization for some cases (e.g. multiplication, division, or mod by a power of two constant)

[gvanrossum]

Questions to answer after some investigations:

* [ ]  Is the cost of keeping the reciprocal of that number stored somewhere worth it?  This can improve division performance slightly

Probably not. Division is exceedingly rare.

* [ ]  Are the compilers generating the most efficient instructions for the use case we're interested in? Would using inline assembly in these cases help us a bit?

I'll defer to @mdickinson or @tim-one to help answer this.

* [ ]  Maybe look into doing some strength reduction specialization for some cases (e.g. multiplication, division, or mod by a power of two constant)

Also for Mark and/or Time.

I would assume the more important use case we're trying to optimize is cases where the value fits (comfortably) in 64 bits so we can put it in the ob_size field (with a flag bit to distinguish such "immediate" values from those where abs(ob_size) is the number of "digits" as it currently is. (Might have to become abs(ob_size/2) or something like that.)

(But I may be misunderstanding what you mean by "canonical". What I'm thinking of is Discussion #147.)

[tim-one]

In general, CPython's bigints are represented in a way that lets us work in portable, standard C. For example, even on 64-bit boxes, we use internal "digits" of 30 bits. That lets us get the full double-width product just by casting to uint64_t before multiplying. Not using all 32 bits per digit also, e.g., lets us explicitly deal with "carry bits" in portable C without any help from HW gimmicks to deal with carries.

So, in effect, we designed it so that the ability to tweak generated code would be useless 😉. We do pay prices for that, though! With full access to modern HW facilities, we could use 64-bit digits, with all the speed advantages that would bring.

But we'd have to essentially rewrite all of longobject.c. What people are keener on isn't to speed bigints, but to speed arithmetic on native platform-sized ints.

Agreed that we wouldn't have much use for storing a reciprocal.

Possible strength reductions is a large topic, but isn't so acute in Python as in other languages, at least not yet. Experienced Python programmers have it beaten into their bones that if they want strength reductions, they need to code them up front. For example, rather than type i % 8, they do i & 7 instead. Part of that is because Python has no idea what type i is at compile-time, so traditionally couldn't make this transformation itself. There's no reason in general to imagine that i.__mod__() and i.__and__() have any relation.

This is sometimes carried to extremes. For example, at the start of a large function I may write i1 = i + 1, if i + 1 is used in the body of a loop (and use i1 in the loop body instead). Else Python would add 1 to i all over again on every iteration.

[ericsnowcurrently]

Also see #147.

[lpereira]

This is actually a duplicate of #147. Closing to avoid dicussing this in two places.