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

This patchset makes it possible for Python to use base 2**30 instead
of base 2**15 for its internal representation of arbitrary-precision integers.

The aim is both to improve performance of integer arithmetic, and to
make possible some additional optimizations (not currently included in
this patchset).

The patchset includes:

- a new configure option --enable-big-digits
- a new structseq sys.int_info giving information about the
   internal representation

See http://bugs.python.org/issue4258 for the related tracker discussion.

[Martin v. Löwis, 2009-02-17 22:39:17]

http://codereview.appspot.com/14105/diff/1/11
File Doc/library/sys.rst (right):

http://codereview.appspot.com/14105/diff/1/11#newcode418
Line 418: A struct sequence that holds information about Python's
I don't think the sequence interface is really important here. There should be a
way to easily define regular struct-like classes (with no sequence interface).
Perhaps structseq could be modified to drop sequence interface, and new
structseqs should turn it off usually.

http://codereview.appspot.com/14105/diff/1/6
File Include/longintrepr.h (right):

http://codereview.appspot.com/14105/diff/1/6#newcode24
Line 24: Furthermore, NSMALLNEGINTS and NSMALLPOSINTS should fit in a digit. */
Merge the comments into a single on. There is no need to preserve the evolution
of the code in the comment structure.

http://codereview.appspot.com/14105/diff/1/9
File Objects/longobject.c (right):

http://codereview.appspot.com/14105/diff/1/9#newcode2872
Line 2872: /* XXX benchmark this! Is is worth keeping? */
Why not PyLong_FromLongLong if available (no special case if not)?

http://codereview.appspot.com/14105/diff/1/10
File PC/pyconfig.h (right):

http://codereview.appspot.com/14105/diff/1/10#newcode318
Line 318: #define PY_UINT64_T unsigned __int64
I think this should use PY_LONG_LONG, to support MingW32; likewise, __int32
shouldn't be used, as it is MSC specific

http://codereview.appspot.com/14105/diff/1/2
File Python/marshal.c (right):

http://codereview.appspot.com/14105/diff/1/2#newcode160
Line 160: w_long((long)(Py_SIZE(ob) > 0 ? l : -l), p);
This needs to deal with overflow (sizeof(size_t) > sizeof(long))

http://codereview.appspot.com/14105/diff/1/2#newcode540
Line 540: if (n < -INT_MAX || n > INT_MAX)
I think this is obsolete now; longs can have up to ssize_t_max digits.

http://codereview.appspot.com/14105/diff/1/8
File configure.in (right):

http://codereview.appspot.com/14105/diff/1/8#newcode3132
Line 3132: # determine what size digit to use for Python's longs
I'm skeptical (-0) that we really need to have such a configure option.

http://codereview.appspot.com/14105/diff/1/14
File pyconfig.h.in (left):

http://codereview.appspot.com/14105/diff/1/14#oldcode9
Line 9: #undef AC_APPLE_UNIVERSAL_BUILD
We should find out why this is gone.

http://codereview.appspot.com/14105/diff/1/14#oldcode958
Line 958: /* Enable extensions on AIX 3, Interix.  */
Likewise, this needs to be preserved.

http://codereview.appspot.com/14105/diff/1/14#oldcode1017
Line 1017: /* Define WORDS_BIGENDIAN to 1 if your processor stores words with
the most
This also needs to be preserved.

[dickinsm, 2009-02-18 17:06:33]

http://codereview.appspot.com/14105/diff/1/11
File Doc/library/sys.rst (right):

http://codereview.appspot.com/14105/diff/1/11#newcode418
Line 418: A struct sequence that holds information about Python's
Agreed.  All that's important here is the attribute access.

http://codereview.appspot.com/14105/diff/1/6
File Include/longintrepr.h (right):

http://codereview.appspot.com/14105/diff/1/6#newcode24
Line 24: Furthermore, NSMALLNEGINTS and NSMALLPOSINTS should fit in a digit. */
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> Merge the comments into a single on. There is no need to preserve the
evolution
> of the code in the comment structure.

Done, along with a general rewrite of this set of comments.

http://codereview.appspot.com/14105/diff/1/9
File Objects/longobject.c (right):

http://codereview.appspot.com/14105/diff/1/9#newcode2872
Line 2872: /* XXX benchmark this! Is is worth keeping? */
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> Why not PyLong_FromLongLong if available (no special case if not)?

Yes, PyLong_FromLongLong would make sense.  If this is not available,
we still need to make sure that CHECK_SMALL_INT gets called.

http://codereview.appspot.com/14105/diff/1/10
File PC/pyconfig.h (right):

http://codereview.appspot.com/14105/diff/1/10#newcode318
Line 318: #define PY_UINT64_T unsigned __int64
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> I think this should use PY_LONG_LONG, to support MingW32; likewise, __int32
> shouldn't be used, as it is MSC specific

Ok.  I'll use PY_LONG_LONG for 64-bit, and try int and long for 32-bit.

http://codereview.appspot.com/14105/diff/1/2
File Python/marshal.c (right):

http://codereview.appspot.com/14105/diff/1/2#newcode160
Line 160: w_long((long)(Py_SIZE(ob) > 0 ? l : -l), p);
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> This needs to deal with overflow (sizeof(size_t) > sizeof(long))

Hmm.  It looks as though there are many places in this file,
particularly in w_object, that do "w_long((long)n, p), where
n has type Py_ssize_t.  Presumably all of these should
be fixed.

http://codereview.appspot.com/14105/diff/1/2#newcode540
Line 540: if (n < -INT_MAX || n > INT_MAX)
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> I think this is obsolete now; longs can have up to ssize_t_max digits.

Agreed. Again, this needs to be fixed throughout marshal.c (many
occurrences in r_object).

http://codereview.appspot.com/14105/diff/1/8
File configure.in (right):

http://codereview.appspot.com/14105/diff/1/8#newcode3132
Line 3132: # determine what size digit to use for Python's longs
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> I'm skeptical (-0) that we really need to have such a configure option.

I think it's potentially useful to be able to do --disable-big-digits
on platforms where the compiler isn't smart enough to translate
a 32-bit by 32-bit multiply into the appropriate CPU instruction,
so that using 30-bit digits might hurt performance.

I've also found it handy during debugging and testing.  But I guess
I'm only +0.5 on the configure option;  if others think that it's just
unnecessary clutter then I'll remove it.

http://codereview.appspot.com/14105/diff/1/14
File pyconfig.h.in (left):

http://codereview.appspot.com/14105/diff/1/14#oldcode9
Line 9: #undef AC_APPLE_UNIVERSAL_BUILD
On 2009/02/17 22:39:18, Martin v. Löwis wrote:
> We should find out why this is gone.

Looks like an autoconf 2.63/autoconf 2.61 difference.
Whoever previously ran autoconf and autoheader used 2.63;
I used 2.61. (Which explains the huge configure diff as well.)

[Martin v. Löwis, 2009-02-18 21:27:04]

On all other follow-ups I agree, so no further comments there.

http://codereview.appspot.com/14105/diff/1/2
File Python/marshal.c (right):

http://codereview.appspot.com/14105/diff/1/2#newcode160
Line 160: w_long((long)(Py_SIZE(ob) > 0 ? l : -l), p);
> Presumably all of these should be fixed.

Ok, so I'd waive this for this patch; please do create a separate report.

[dickinsm, 2009-02-19 09:42:14]

http://codereview.appspot.com/14105/diff/1/2
File Python/marshal.c (right):

http://codereview.appspot.com/14105/diff/1/2#newcode160
Line 160: w_long((long)(Py_SIZE(ob) > 0 ? l : -l), p);
On 2009/02/18 21:27:04, Martin v. Löwis wrote:
> Ok, so I'd waive this for this patch; please do create a separate report.

Done.

http://bugs.python.org/issue5308