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

[Armin Rigo]

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.