[pypy-dev] PyPy doesn't make code written in C faster

[Carl Friedrich Bolz]

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>