[pypy-dev] PyPy doesn't make code written in C faster
Carl Friedrich Bolz
cfbolz at gmx.de
Fri May 31 12:01:27 CEST 2013
I have only glanced at the code, but isn't the right argument of the divmod always a power of two? So it can be replaced by a shift and a mask, giving the right complexity.
Armin Rigo <arigo at tunes.org> wrote:
>On Thu, May 30, 2013 at 6:41 PM, Nathan Hurst <njh at njhurst.com> wrote:
>> It doesn't have to be quadratic, it's easy to come up with a
>I believe that you're right on one point and wrong on another. You're
>right in that this gives a faster algo for str(). You're wrong in
>that it's still quadratic. If 'a' has 2N digits and 'b' has N digits,
>then divmod(a,b) is quadratic --- takes time proportional to N*N. It
>can be shown by measuring the time spent by your algo to do the repr
>of larger and larger numbers.
>> beating the builtin C implementation by a factor of 7.5 seems a
>> reasonable outcome for pypy.
>No, precisely my point: this argument is bogus. The proof that it's
>wrong is that CPython gets very similar timing results! Your pure
>Python version outperforms the C str(long) in a very similar way on
>PyPy and on CPython! The "bug" is originally in CPython, for having a
>str() that is too slow, and I just copied it into PyPy. The pure
>Python version you posted is faster. Its speed is roughly the same on
>CPython and on PyPy because most of the time is spent doing divmod on
>large "long" objects (which is this post's original point).
>> I think I could come up with a linear time two pass algorithm working
>> on intdigits if this were important to pypy.
>That would be interesting for both PyPy and CPython.
>pypy-dev mailing list
>pypy-dev at python.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the pypy-dev