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

@tim-one

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

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
)

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

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.

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.

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)

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.

[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.

> 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.

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.

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;
```
}

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.

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;
	}

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.

Here's an updated patch that includes the x_divrem fixes and
optimizations. I've also updated the Rietveld issue with these
fixes.

I think this is (modulo any requested changes) the version
that I'd like to get into py3k. After that we can look
at the possibility of optimizing the multiplication algorithm;
the discussion for this should probably go back to bpo-3944.

Here's a detailed list of the changes to x_divrem.

Most importantly, in the inner loop, we make sure that the
multiplication is digit x digit -> twodigits; previously it was
digit x twodigits -> twodigits, which is likely to expand to
several instructions on a 32-bit machine. I suspect that
this is the main cause of the slowdown that Victor was
seeing.
Make all variables unsigned. This eliminates the need for
Py_ARITHMETIC_RIGHT_SHIFT, and also removes the only essential use
of stwodigits in the entire long object implementation.
Save an iteration of the outer loop when possible by comparing top
digits.
Remove double tests in the main inner loop and correction loop.
Quotient digit correction step follows Knuth more closely, and uses
fewer operations. The extra exit condition (r >= PyLong_BASE) will
be true more than 50% of the time, and should be cheaper than the
main test.
In quotient digit estimation step, remove unnecessary special case
when vj == w->ob_digits[w_size-1]. Knuth only needs this special
case
because his base is the same as the wordsize.
There's no need to fill the eliminated digits of v with zero;
instead, set Py_SIZE(v) at the end of the outer loop.
More comments; some extra asserts.

There are many other optimizations possible; I've tried only to include
those that don't significantly complicate the code. An obvious
remaining inefficiency is that on every iteration of the outer loop we
divide by the top word of w; on many machines I suspect that it would
be more efficient to precompute an inverse and multiply by that instead.

Updated benchmarks results with 30bit_longdigit17.patch:

Victor's bench_int.py:

32-bit with patch: 1178.3 ms (24% speedup)
64-bit with patch: 990.8 ms (27% speedup)

Calculating 2000 digits of pi:

32-bit with patch: 2.16 s. (25% speedup)
64-bit with patch: 1.5 s. (55% speedup)

This is very good work.

Adding Tim Peters to the nosy list, mainly to give him an opportunity to
throw up his hands in horror at my rewrite of his (I'm guessing)
implementation of division.

It finally occurred to me that what might be killing 32-bit performance
is the divisions, rather than the multiplications.

To test this, here's a version of 30bit_longdigit17.patch that replaces
just *two* of the divisions in Objects/longsobject.c by the appropriate
x86 divl assembler instruction. The result for pydigits is an
astonishing 10% speedup!

Results of running python pydigits_bestof.py 2000 on 32-bit OS X
10.5.6/Core 2 Duo:

upatched py3k
-------------
Best Time; 2212.6 ms

30bit_longdigit17.patch
-----------------------
Best Time; 2283.9 ms (-3.1% relative to py3k)

30bit_longdigit17+asm.patch
---------------------------
Best Time; 2085.7 ms (+6.1% relative to py3k)

The problem is that (e.g., in the main loop of x_divrem) we're doing a
64-bit by 32-bit division, expecting a 32-bit quotient and a 32-bit
remainder. From the analysis of the algorithm, *we* know that the
quotient will always fit into 32 bits, so that e.g., on x86, a divl
instruction is appropriate. But unless the compiler is extraordinarily
clever it doesn't know this, so it produces an expensive library call to
a function that probably involves multiple divisions and/or some
branches, that produces the full 64-bit quotient.

On 32-bit PowerPC things are even worse, since there there isn't even a
64-by-32 bit divide instruction; only a 32-bit by 32-bit division.

So I could still be persuaded that 30-bit digits should only be enabled
by default on 64-bit machines...

Okay, let's abandon 30-bit digits on 32-bit machines: it's still
unclear whether there's any real performance gain, and it's trivial to
re-enable 30-bit digits by default later. I'm also going to abandon the
optimizations for now; it'll be much easier to work on them once the base patch is in.

Here's a 'release-candidate' version of the patch: it's exactly the
same as before, except:

I removed all x_divrem changes (though I've left the extra division
tests in, since they're just as relevant to the old x_divrem).
I'll open a separate issue for these optimizations.
enable 30-bit digits by default only on 64-bit platforms, where
for the purposes of this patch a 64-bit platform is one with all
the necessary integer types available (signed and unsigned 32-
and 64-bit integer types) and SIZEOF_VOID_P >= 8.

I've also updated the version uploaded to Rietveld: the patchset there
should exactly match 30bit_longdigit20.patch. See:

http://codereview.appspot.com/14105

Martin, thank you for all your help with reviewing the previous patch.
Is it okay with you to check this version in? It's the same as the
version that you reviewed, except with some extra tests for correct
division, and with 30-bit digits disabled by default on 32-bit
platforms.

Gregory, if you have time, please could you double check that the
configure stuff is working okay for you with this patch? "configure --
enable-big-digits" should produce 30-bit digits; "configure --disable-
big-digits" should produce 15-bit digits, and a plain "configure" should
give 15-bit or 30-bit depending on your platform.

Anyone else have any objections to this going in exactly as it is? I'd
quite like to resolve this issue one way or the other and move on.

1 comment and 1 question about 30bit_longdigit20.patch:

I love fixed size type: you use them when PYLONG_BITS_IN_DIGIT ==
30 (eg. digit=PY_UINT32_T) but not when PYLONG_BITS_IN_DIGIT == 15
(eg. digit=unsigned short). Even if short is always 16 bits, I would
prefer fixed size types in any case.
In pyport.h, you redefine PYLONG_BITS_IN_DIGIT if it's not set. Is
it for the Windows world (which doesn't use configure script)?

I prefer the patch version 20 because it's much simplier than the
other with the algorithm optimisations. The patch is already huge, so
it's better to split it into smaller parts ;-)

[Victor]

In pyport.h, you redefine PYLONG_BITS_IN_DIGIT if it's not set. Is
it for the Windows world (which doesn't use configure script)?

Yes, but it's also for Unix: PYLONG_BITS_IN_DIGIT is only set when the --
enable-big-digits option is supplied to configure. So the code in
pyport.h always gets used for a plain ./configure && make.

I love fixed size type: you use them when PYLONG_BITS_IN_DIGIT ==
30 (eg. digit=PY_UINT32_T) but not when PYLONG_BITS_IN_DIGIT == 15
(eg. digit=unsigned short). Even if short is always 16 bits, I would
prefer fixed size types in any case.

I agree with you to some extent, but I'd still prefer to leave the 15-bit
definitions as they are, partly out of a desire not to make unnecessary
changes. The 'unsigned short' type used for 15-bit digits is both
theoretically sufficient and not wasteful in practice.

Barring further objections, I'm planning to get the
30bit_longdigit20.patch in later this week.

I tried the patch on a 64-bit Linux system and it's ok.

Committed 30bit_longdigit20.patch to py3k in r70460, with some minor
variations (incorporate Nick Coghlan's improved error messages
for marshal, fix some comment typos, add whatsnew and Misc/NEWS entries).

Thanks all for your feedback.

I might get around to backporting this to 2.7 one day...

That should be r70459, of course.

Great!

Committed 30bit_longdigit20.patch to py3k in r70460, with some minor
variations (incorporate Nick Coghlan's improved error messages
for marshal, fix some comment typos, add whatsnew and Misc/NEWS entries).

Backported to trunk in r70479.

Mario, thanks for the long multiplication tweaks you submitted: could you
possibly regenerate your Feb 19th patch against the trunk (or py3k,
whichever you prefer) and attach it to bpo-3944?

Navigation Menu

Repository navigation

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

53 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

mdickinson commented on Nov 4, 2008

mdickinson commented on Nov 4, 2008

mdickinson commented on Nov 4, 2008

vstinner commented on Nov 5, 2008

gpshead commented on Nov 5, 2008

vstinner commented on Nov 5, 2008

mdickinson commented on Nov 5, 2008

vstinner commented on Nov 5, 2008

mdickinson commented on Nov 5, 2008

vstinner commented on Nov 5, 2008

vstinner commented on Nov 6, 2008

vstinner commented on Nov 6, 2008

mdickinson commented on Nov 6, 2008

53 remaining items

mdickinson commented on Feb 20, 2009

pitrou commented on Feb 20, 2009

mdickinson commented on Feb 21, 2009

mdickinson commented on Feb 22, 2009

mdickinson commented on Feb 24, 2009

vstinner commented on Feb 26, 2009

mdickinson commented on Mar 9, 2009

pitrou commented on Mar 11, 2009

mdickinson commented on Mar 18, 2009

mdickinson commented on Mar 18, 2009

pitrou commented on Mar 18, 2009

mdickinson commented on Mar 20, 2009

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions