[Python-Dev] int(string)

[Michael Hudson]

Tim Peters <tim.peters at gmail.com> writes:

> Turns out it's _not_ input speed that's the problem here, and not even
> mainly the speed of integer mod:  the bulk of the time is spent in
> int(string) (and, yes, that's also far more important to the problem
> Neal was looking at than list.append time). If you can even track all
> the levels of C function calls that ends up invoking <wink>, you find
> yourself in PyOS_strtoul(), which is a nifty all-purpose routine that
> accepts inputs in bases 2 thru 36, can auto-detect base, and does
> platform-independent overflow checking at the cost of a division per
> digit.  All those are features, but it makes for sloooow conversion.

> I assume it's the overflow-checking that's the major time sink, and
> it's not correct anyway:  it does the check slightly differently for
> base 10 than for any other base, explained only in the checkin comment
> for rev 2.13, 8 years ago:
>
>     For base 10, cast unsigned long to long before testing overflow.
>     This prevents 4294967296 from being an acceptable way to spell zero!
>
> So what are the odds that base 10 was the _only_ base that had a "bad
> input" case for the overflow-check method used?  If you thought
> "slim", you were right ;-)  Here are other bad cases, under all Python
> versions to date (on a 32-bit box; if sizeof(long) == 8, there are
> different bad cases):
>
> int('102002022201221111211', 3) = 0
[...]

Eek!

> Now fixing that is easy:  the problem comes from being too clever,

Surprise!

> doing both a multiply and an addition before checking for overflow. 
> Check each operation on its own and it would be bulletproof, without
> special-casing.  But that might be even slower (it would remove the
> branch special-casing 10, but add a cheap integer addition overflow
> check with its own branch).
>
> The challenge (should you decide to accept it <wink>) is to replace
> the overflow-checking with something both correct _and_ much faster
> than doing n integer divisions for an n-character input.  For example,
> 36**6 < 2**32-1, so whenever the input has no more than 6 digits
> overflow is impossible regardless of base and regardless of platform. 
> That's simple and exploitable.  For extra credit, make int(string) go
> faster than preparing your taxes ;-)

So, you're suggesting dividing the input up into known non-overflowing
chunks and using the normal Python operations to combine those chunks,
relying on them overflowing to longs as needed?  All of the examples
you posted should have returned longs anyway, right?

I guess the change to automatically overflowing to longs has led to
some code that shows its history more than one would like.

Cheers,
mwh

-- 
  I think if we have the choice, I'd rather we didn't explicitly put
  flaws in the reST syntax for the sole purpose of not insulting the
  almighty.                                    -- /will on the doc-sig