[Patches] [ python-Patches-1335972 ] Fix for int(string, base) wrong answers (take 2)

Wed Dec 21 05:20:13 CET 2005

Patches item #1335972, was opened at 2005-10-24 00:33
Message generated for change (Comment added) made by alanmcintyre
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1335972&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Core (C code)
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Alan McIntyre (alanmcintyre)
Assigned to: Nobody/Anonymous (nobody)
Summary: Fix for int(string, base) wrong answers (take 2)

Initial Comment:
This incorporates patch #1334979, adds test cases for
all the   cases listed in bug #1334662, and adds test
cases for evaluation of 2**32+1.  There seem to be some
minor speed improvements (simplistic stats shown
below). Some simple performance test scripts have been
included in the attached file as well.

A lookup table was added for the maximum number of
digits that can never overflow on a 32-bit ulong for
each base.  Overflow is only checked when this limit is
exceeded by 1, and once the input string is determined
to be too long (2 over the limit), the evaluation is
halted and an overflow indication is returned.  This
appears to help reduce the evaluation time for very
long strings (no time is wasted trying to evaluate all
of it into a 32-bit ulong).

Evaluation of each character has also been replaced by
a lookup table.  I'm not certain of the amount of speed
benefit obtained from this; I added it early on and
haven't had time to go back and test.  It may be that
it's not worth the extra static table.

Baseline Python from CVS:
alan at tarantula:~/python/dist/src# ./python -m timeit
'int("9")'
100000 loops, best of 3: 4 usec per loop
alan at tarantula:~/python/dist/src# ./python -m timeit
'int("999999999")'
100000 loops, best of 3: 5.49 usec per loop
alan at tarantula:~/python/dist/src# ./python -m timeit
'int("999999999999")'
100000 loops, best of 3: 11.8 usec per loop
alan at tarantula:~/python/dist/src# ./python -m timeit
'int("999999999999999")'
100000 loops, best of 3: 13.4 usec per loop
alan at tarantula:~/python/dist/src# ./python -m timeit
'int("1"*600)'
1000 loops, best of 3: 997 usec per loop

Modified:
alan at tarantula:~/python_testint/dist/src# ./python -m
timeit 'int("9")'
100000 loops, best of 3: 3.63 usec per loop
alan at tarantula:~/python_testint/dist/src# ./python -m
timeit 'int("999999999")'
100000 loops, best of 3: 3.93 usec per loop
alan at tarantula:~/python_testint/dist/src# ./python -m
timeit 'int("999999999999")'  
100000 loops, best of 3: 9.79 usec per loop
alan at tarantula:~/python_testint/dist/src# ./python -m
timeit 'int("999999999999999")'
100000 loops, best of 3: 11 usec per loop
alan at tarantula:~/python_testint/dist/src# ./python -m
timeit 'int("1"*600)'
1000 loops, best of 3: 905 usec per loop

10.2% faster for 1-digit int
39.7% faster for 9-digit int
20.5% faster for 12-digit int
21.8% faster for 15-digit int
10.2% faster for 600-digit int

Test program that takes 750k ints from [0, 2**32)
through stdin:
    Baseline: 8.114 sec (best of 5 consecutive runs)
    Modified: 6.774 sec (best of 5 consecutive runs)

19.8% faster

NOTE: This patch causes new errors in test_array and
test_compile, but it seems that these *should* be
failing given the input string for long(), unless I'm
missing something:

======================================================================
ERROR: test_repr (__main__.FloatTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_array.py", line 187, in test_repr
    self.assertEqual(a, eval(repr(a), {"array":
array.array}))
ValueError: invalid literal for long(): 10000000000.0

======================================================================
ERROR: test_repr (__main__.DoubleTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "Lib/test/test_array.py", line 187, in test_repr
    self.assertEqual(a, eval(repr(a), {"array":
array.array}))
ValueError: invalid literal for long(): 10000000000.0

----------------------------------------------------------------------

test test_compile crashed -- exceptions.ValueError:
invalid literal for long():
90000000000000.

----------------------------------------------------------------------

>Comment By: Alan McIntyre (alanmcintyre)
Date: 2005-12-20 23:20

Message:
Logged In: YES 
user_id=1115903

I cleaned up the digitlimit vector and test cases now
include all bases on [2, 36].  Uploaded as
python-mystrtoul5.tgz.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2005-10-31 19:55

Message:
Logged In: YES 
user_id=31435

This looks pretty good to me -- talk about every trick in the 
book <wink>.

Note that the digitlimit vector is too cautious for bases that 
are powers of 2.  For example, it's obvious that any string of 
32 bits can't overflow an unsigned long, but the table cuts 
base 2 off at 31 instead.  The formula should use log(2**32, 
base) instead:

"N digits can't overflow" iff
base**N-1 < 2**32  iff
base**N < 2**32+1
base**N <= 2**32  iff
N <= log(2**32, base)

Assuming exact calculation of log(2**32, base) then 
(dubious, really), the floor of that is exactly the maximum 
safe N.

The power-of-2 bases, and base 10, should be added to the 
tests.  We really want to check that _all_ supported bases 
work, right?

----------------------------------------------------------------------

Comment By: Alan McIntyre (alanmcintyre)
Date: 2005-10-24 10:26

Message:
Logged In: YES 
user_id=1115903

Thanks, funny_falcon - that corrected the problem with the
literals. I also included the change to the digit lookup
table.  

The new patch is attached as python-mystrtoul4.tgz; it
passes all tests now on my machine.

----------------------------------------------------------------------

Comment By: funny_falcon (funny_falcon)
Date: 2005-10-24 02:07

Message:
Logged In: YES 
user_id=1290388

Instead of:
overflowed:

	/* spool through remaining characters */

	while ((c = Py_CHARMASK(*str)) != '\0')

		str ++;

Shoold be
	while ((c = Py_CHARMASK(*str)) != '\0') {

		c = digitlookup[c];

		if (c < 0 || c >= base) /* non-"digit" character */

			break;

		str++;
	}
And why not
static int digitlookup[] = {

	37, 37, 37 ......
};
and
		if (c >= base)  break;

----------------------------------------------------------------------

Comment By: Alan McIntyre (alanmcintyre)
Date: 2005-10-24 00:41

Message:
Logged In: YES 
user_id=1115903

I forgot to add that these results were obtained on a PIIIm
833MHz running Linux 2.4.2, GCC 3.2.2, with the Python 2.5a0
CVS source from about 8pm EST Oct 23, 2005.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1335972&group_id=5470