Use 30-bit digits instead of 15-bit digits for Python integers.

[mdickinson]

BPO	4258
Nosy	@tim-one, @loewis, @gpshead, @mdickinson, @pitrou, @vstinner, @tiran
Dependencies	bpo-5260: longobject.c: minor fixes, cleanups and optimizations
Files	pybench_results.txt: pybench results optimize.patch: Improve mark's patch long_stat.patch 30bit_longdigit13.patch 30bit_longdigit13+optimizations.patch pidigits.py 30bit_longdigit14.patch pidigits_noprint.py pidigits_bestof.py: pidigits benchmark w/warmup and 5 runs 30bit_longdigit13+optimizations1.patch: Improve mark's patch 30bit_longdigit17.patch 30bit_longdigit17+asm.patch 30bit_longdigit20.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/mdickinson'
closed_at = <Date 2009-03-20.16:08:05.934>
created_at = <Date 2008-11-04.10:45:10.677>
labels = ['interpreter-core', 'performance']
title = 'Use 30-bit digits instead of 15-bit digits for Python integers.'
updated_at = <Date 2009-03-20.16:08:05.899>
user = 'https://github.com/mdickinson'

bugs.python.org fields:

activity = <Date 2009-03-20.16:08:05.899>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2009-03-20.16:08:05.934>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2008-11-04.10:45:10.677>
creator = 'mark.dickinson'
dependencies = ['5260']
files = ['11950', '11951', '11952', '13108', '13118', '13119', '13122', '13127', '13132', '13137', '13142', '13149', '13164']
hgrepos = []
issue_num = 4258
keywords = ['patch']
message_count = 78.0
messages = ['75491', '75492', '75494', '75512', '75513', '75518', '75520', '75522', '75534', '75536', '75539', '75540', '75551', '75553', '75559', '75560', '75561', '75562', '75695', '75718', '75720', '75746', '77769', '77770', '82116', '82250', '82251', '82318', '82319', '82320', '82321', '82325', '82326', '82342', '82344', '82345', '82346', '82347', '82348', '82350', '82362', '82364', '82368', '82374', '82375', '82385', '82386', '82404', '82407', '82424', '82425', '82426', '82428', '82429', '82430', '82431', '82432', '82433', '82434', '82444', '82445', '82448', '82458', '82466', '82468', '82469', '82533', '82538', '82563', '82599', '82669', '82792', '83389', '83467', '83772', '83773', '83774', '83865']
nosy_count = 11.0
nosy_names = ['tim.peters', 'loewis', 'collinwinter', 'gregory.p.smith', 'mark.dickinson', 'pitrou', 'pernici', 'vstinner', 'christian.heimes', 'jyasskin', 'schuppenies']
pr_nums = []
priority = 'low'
resolution = 'accepted'
stage = 'patch review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue4258'
versions = ['Python 2.7']

[mdickinson]

Here's an experimental patch, against the py3k branch, that makes Python
represent its long integers internally in base 2**30 instead of base
2**15, on platforms that have 32-bit and 64-bit integers available.

On platforms for which autoconf is unable to find both 32-bit and 64-bit
integers, the representation falls back to the usual one.

See also bpo-1814 (GMP for longs), and the discussion at

http://mail.python.org/pipermail/python-dev/2008-November/083315.html

(note particularly Tim Peter's message at:

http://mail.python.org/pipermail/python-dev/2008-November/083355.html
)

[mdickinson]

Note that to avoid "bad marshal data" errors, you'll probably need to do a
'make distclean' before rebuilding with this patch.

[mdickinson]

Here's an updated patch, with the following changes from the original:

• make the size of a digit (both the conceptual size
  in bits and actual size in bytes) available to Python
  via a new structseq sys.int_info. This information
  is useful for the sys.getsizeof tests.

• fix a missing cast in long_hash

• better fast path for 1-by-1 multiplication that
  doesn't go via PyLong_FromLongLong.

[vstinner]

Note that to avoid "bad marshal data" errors,
you'll probably need to do a 'make distclean'
before rebuilding with this patch.

I saw that you choosed to use the base 2^30 for marshal. For a better
portability (be able to use .pyc generated without your patch), you
may keep the base 2^15. I implemented that in my GMP patch (manual
conversion from/to base 2^15).

If we change the marshal format of long, the magic number should be
different (we might use a tag like the "full unicode" tag used in
Python3 magic number) and/or the bytecode (actual bytecode is 'l').
The base should be independent of the implementation, like Python does
with text: UTF-8 for files and UCS-4 in memory. We may use the base
2^8 (256) or another power or 2^8 (2^16, 2^32, 2^64?). The base 256
sounds interresting because any CPU is able to process 8 bits digits.

Cons: Use a different bases makes Python slower for loading/writing
from/to .pyc.

[gpshead]

oh yay, thanks. it looks like you did approximately what i had started
working on testing a while back but have gone much further and added
autoconf magic to try and determine when which size should be used. good.

(i haven't reviewed your autoconf stuff yet)

As for marhsalled data and pyc compatibility, yes that is important to
consider.

We should probably base the decision on which digit size to use
internally on benchmarks, not just if the platform can support 64bit
ints. Many archs support 64bit numbers as a native C type but require
multiple instructions or are very slow when doing it.

(embedded arm, mips or ppc come to mind as obvious things to test that on)

[vstinner]

As for marhsalled data and pyc compatibility, yes that is important to
consider.

The problem is also that with the 30-bit digit patch, some Python will use 15
bits whereas some other will use 30 bits. The base in marshal should be the
same in both cases.

And why 30 bits and not 31 bits, or 63 bits, or 120 bits? We may use other
bases in the future. That's why I prefer to use a common base like base 256.
And GMP has functions (mpz_import) to load data in base 256, but it's more
complicate to load data in base 2^15.

[mdickinson]

[Victor Stinner]

I saw that you choosed to use the base 2^30 for marshal. For a better
portability (be able to use .pyc generated without your patch), you
may keep the base 2^15. I implemented that in my GMP patch (manual
conversion from/to base 2^15).

Agreed. I'll fix this so that the .pyc format is unchanged. Thanks!

And why 30 bits and not 31 bits, or 63 bits, or 120 bits?

Mostly laziness: the change from 15 to 30 bits turned out to be extraordinarily easy. Note that the longobject.c part of
the patch does almost nothing except adding a bunch of casts here and there.

31 bits would involve rewriting the powering algorithm, which assumes that PyLong_SHIFT is divisible by 5. It would gain
very little over 30 bits, and if Pernici Mario's optimizations are considered (bpo-3944) multiplication would likely be
slower with 31-bit digits than with 30-bit digits.

63 (or 62, or 60) bits is simply too large right now: you'd need access to a hardware 64 x 64 -> 128 bit multiply to make
this worth it, and I'd guess there are many fewer platforms that make this easy, though I don't really know. I know it's
possible on gcc/x86_64 by making use of the (undocumented) __uint128_t type. But even where this type is available, base
2**63 might still be slower than base 2**30. I've done some experiments with multiprecision *decimal* arithmetic in C that
showed that even on a 64-bit machine, using base 10**9 (i.e. approx 30 bits) was significantly faster than using base
10**18.

120 bits? Does GMP even go this far? I guess part of the attraction is that it's a multiple of 8...

The other obvious choices to consider would be 32 bits (or 16 bits, or 64 bits). This is possible, and may even be worth
it, but it would be a *much* bigger effort; most of the algorithms would need to be rewritten. One problem is again the
mismatch between C and assembler: detecting overflow when adding two 32-bit unsigned integers is trivial in x86 assembler,
but it's not so obvious how to write portable C code that has a decent chance of being compiled optimally on a wide variety
of compilers.

I guess my feeling is simply that the 15-bit to 30-bit change seems incredibly easy and cheap: very little code change, and
hence low risk of accidental breakage. So if there are indeed significant efficiency benefits (still to be determined) then
it looks like a clear win to me.

[Gregory Smith]

(i haven't reviewed your autoconf stuff yet)

The changes to configure and pyconfig.h are just from rerunning autoconf and autoheader; it's only configure.in that should
need looking at.

[vstinner]

> And why 30 bits and not 31 bits, or 63 bits, or 120 bits?

Mostly laziness (...)

It was an argument for changing the base used by the mashal :-)

31 bits would involve rewriting the powering algorithm, which assumes that
PyLong_SHIFT is divisible by 5

Powering is an simple algorithm. If it was the division, it would be much
harder :-) Python stores the sign of the number in the first digit. Because
of that, we are limited to 15/30 bits. Storing the sign in the size (which
size? no idea yet) would allows to use a bigger base (31 bits? 63 bits?).

One problem is again the mismatch between C and assembler: detecting
overflow when adding two 32-bit unsigned integers is trivial in x86
assembler, but it's not so obvious how to write portable C code that has a
decent chance of being compiled optimally on a wide variety of compilers.

I wrote an example to detect overflows in C on the mailing list. Copy of my
email:
------------------------------- 8< ----------------------
About 31, 32, 63 or 64 bits: I guess that you want to avoid integer overflow.
Intel has an "overflow" flag, changed for all instructions. For other CPUs,
you can use emulate this flag. Example with the type int that I used in my
GMP patch:

Add:
  int a, b, sum;
  sum = a + b;
  exact = ((a < 0) ^ (b < 0)) || ((a < 0) == (sum < 0));

Substract:
  int a, b, diff;
  diff = a + b;
  exact = ((a < 0) == (b < 0)) || ((a < 0) == (diff < 0));

Multiply:
  int a, b, product;
  if (a == 0 || b == 0) {
     product = 0;  /* exact */
  } else if (a != INT_MIN || (b == 1)) {
     product = a * b;
     exact = (product / b) == a);
  } else {
     /* INT_MIN * -1 = -INT_MIN: overflow */
  }

Divide:
  int a, b, q;
  if (a != INT_MIN || b != -1) {
     q = a / b;   /* exact */
  } else {
     /* INT_MIN / -1 = -INT_MIN: overflow */
  }

Checking overflow may costs more than using a smaller base. Only a benchmark
can answer ;-)
------------------------------- 8< ----------------------

I guess my feeling is simply that the 15-bit to 30-bit change seems
incredibly easy and cheap: very little code change, and hence low risk of
accidental breakage.

Python has an amazing regression test suite! I used it to fix my GMP patch. We
can experiment new bases using this suite.

Anyway, i love the idea of using 30 bits instead of 15! Most computer are now
32 or 64 bits! But it's safe to keep the 15 bits version to support older
computers or buggy compilers.

I started to work with GIT. You may be interrested to work together on GIT.
It's much easier to exchanges changeset and play with branches. I will try to
publish my GIT tree somewhere.

[mdickinson]

Following Victor's suggestion, here's an updated patch; same as before,
except that marshal now uses base 2**15 for reading and writing,
independently of whether PyLong_SHIFT is 15 or 30.

[vstinner]

Mark: would it be possible to keep the "2 digits" hack in
PyLong_FromLong, especially with base 2^15? Eg. "#if PyLong_SHIFT ==
15". The base 2^15 slow, so don't make it slower :-)

• /* 2 digits */
• if (!(ival >> 2*PyLong_SHIFT)) {

•   v = \_PyLong_New(2);
  

•   if (v) {
  

•   	Py_SIZE(v) = 2\*sign;
  

•   	v-\>ob_digit[0] = (digit)ival & PyLong_MASK;
  

•   	v-\>ob_digit[1] = ival \>\> PyLong_SHIFT;
  

•   }
  

•   return (PyObject*)v;
  

• }

[vstinner]

marshal now uses base 2**15 for reading and writing

Yes, it uses base 2**15 but it's not the correct conversion to base
2**15. You convert each PyLong digit to base 2**15 but not the whole
number. As a result, the format is different than the current mashal
version.

[vstinner]

PyLong_FromLong() doesn't go into the 1 digit special case for 
negative number. You should use:
	/* Fast path for single-digits ints */
	if (!(abs_ival>>PyLong_SHIFT)) {
		v = _PyLong_New(1);
		if (v) {
			Py_SIZE(v) = sign;
			v->ob_digit[0] = abs_ival;
		}
		return (PyObject*)v;
	}

[mdickinson]

Yes, it uses base 2**15 but it's not the correct conversion to base
2**15. You convert each PyLong digit to base 2**15 but not the whole
number.

I don't understand: yes, each base 2**30 digit is converted to a pair
of base 2**15 digits, and if necessary (i.e., if the top 15 bits of the
most significant base 2**30 digit are zero) the size is adjusted. How
is this not converting the whole number?

As a result, the format is different than the current mashal version.

Can you give an example of an integer n such that marshal.dumps(n) gives
you different results with and without the patch? As far as I can tell,
I'm getting the same marshal results both with the unpatched version and
with the patch applied.