[pypy-issue] [issue1330] fib(47) vs fib(48)

[Armin Rigo]

Armin Rigo <armin.rigo at gmail.com> added the comment:

It's not related to getting ints vs longs.  I see for example that fib(27) is
slower than fib(28) as well.  The cause is, roughly speaking, nondeterminism in
the order in which loops and bridges are compiled.  Looking at the code
generated for fib(47) vs fib(48), then fib(47) has the expected kind of code,
but the faster fib(48) optimizes it better --- it ends up with code that looks
like this:

def f(n):
    guard n >= 2
    guard n <= 2
    return 1   # == f(1) + f(0)

with of course additional bridges if the guards fail.  The point is that this is
particularly efficient for f(2), containing the inlined copy of f(1) and f(0)
and constant-folding the addition.  This makes a difference because whenever we
reach f(2), we can just return 1 (and we reach f(2) a huge number of times,
certainly more than sys.maxint).

The fib(47) version contains the more expected special cases for f(n<2) only.

Unsure if or how to fix that.

----------
nosy: +arigo

________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue1330>
________________________________________