More efficient representation of integers

[lpereira]

This is just to track my work on implementing #147. There's some discussion on this already on #231.

[jneb]

Maybe a silly question but are there any statistics on int size used in practice?
This could really help in making a wise decision on the boundary between "short" and "long".
I would guess that the size of the small ints could be anything down to about 16 bits, but actual statistics would really help.

[gvanrossum]

Maybe a silly question but are there any statistics on int size used in practice? This could really help in making a wise decision on the boundary between "short" and "long". I would guess that the size of the small ints could be anything down to about 16 bits, but actual statistics would really help.

I don't think we have any, but it would be simple to add code, normally #ifdef-ed out, to the int allocator that counts how many allocations there are of integers with k "digits" (a digit being a 15-bit or 30-bit chunk in the current representation), for k between 0 and some reasonable number (binning everything larger in a single overflow bin). Then we could run some test code and dump the stats. Or if you want more precise numbers, at considerable extra cost, we could calculate the number of bits needed to represent the value.

Of course, then we would have to look for "representative" test code for which to get the stats. Would the pyperformance benchmarks be representative? Some other set of benchmarks (maybe the Pyston ones)? Or maybe we could try running the standard library test suite? I imagine every application has its own distribution.

Nothing is ever easy... Until then, my intuition tells me that the vast, vast majority of integers in almost all Python applications are under 64 bits, and most are easily under 32 bits. We don't really need more precision than that since memory allocation doesn't have much finer granularity.

[jneb]

I did a test on this a very long time ago (~1990) when designing my own language and found that almost everything fits in two bytes, most in one byte (fewer negative that positive). Since I did cryptography, there were also big numbers, which were in my case about 512 bits (RSA size in these days). The numbers bigger than two bytes, but fewer than 64 were almost none.
Even though that data set had only a few programs in it, I believe you that 32 bits will be the big majority of numbers, and we must make these small and fast.

[markshannon]

Superseded by #548