[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
Hi Armin,
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.
Cheers,
Carl Friedrich
Armin Rigo <arigo at tunes.org> wrote:
>Hi Nathan,
>
>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
>splitting
>> algorithm:
>
>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.
>
>
>A bientôt,
>
>Armin.
>_______________________________________________
>pypy-dev mailing list
>pypy-dev at python.org
>http://mail.python.org/mailman/listinfo/pypy-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/pypy-dev/attachments/20130531/b9360e48/attachment.html>
More information about the pypy-dev
mailing list