[pypy-issue] [issue1011] pypy slower than CPython for recursion

[Jagadish]

New submission from Jagadish <krshnam at gmail.com>:

The following simple example program is slower with pypy than with CPython.
In my machine(Dell Inspiron 6400, Arch Linux, Python 2.7.1, pypy 1.7.0 ), I get, 
for example, these numbers:
$ time python2 five_three_rec.py 12017
real	2m55.367s
user	2m53.129s
sys	0m1.290s

$ time pypy five_three_rec.py 12017
real	7m58.881s
user	7m56.239s
sys	0m0.830s

#five_three_rec.py
def findSequence(goal):
    def find(start, history):
        if start == goal :
            return history
        elif start > goal :
            return None
        else :
            return ( find(start + 5, "(%s + 5)" % history) or
                    find(start * 3, "(%s * 3)" % history))
    return find(1, '1')

if __name__ == '__main__' :
    import sys
    sys.setrecursionlimit(5000)
    input_num = int(sys.argv[1])
    print (findSequence(input_num) or
            'No sequence in terms of 5 and 3 for %d.' % input_num)

The non-recursive version below, however, is faster with pypy:
$ time python2 five_three_iter.py 12017
real	1m36.279s
user	1m36.187s
sys	0m0.013s

$ time pypy five_three_iter.py 12017
real	0m10.770s
user	0m10.703s
sys	0m0.040s


#five_three_iter.py
def findSequence(goal):
    node_list = [{'num':1, '5':False, '3':False}]
    op_seq_list = ['1']

    def printOpSeq():
        seq_str ='1'
        for op_str in op_seq_list[1:]:
            seq_str = '(' + seq_str + op_str + ')'
        print seq_str
        print eval(seq_str)

    while True:
        node = node_list[-1]
        if not node['5'] :
            node['5'] = True
            new_num = node['num'] + 5
            if new_num <= goal:
                op_seq_list.append(' + 5')
                if new_num == goal:
                    printOpSeq()
                    break
                else :
                    node_list.append({'num': new_num,
                        '5': False, '3': False})
                    continue
        if not node['3'] :
            node['3'] = True
            new_num = node['num'] * 3
            if new_num <= goal :
                op_seq_list.append(' * 3')
                if new_num == goal:
                    printOpSeq()
                    break
                else :
                    node_list.append({'num': new_num,
                        '5': False, '3': False})
                    continue
        else:
            if len(node_list) == 1:
                print "No solution"
                break
            else:
                node_list.pop()
                op_seq_list.pop()
                continue


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(5000)
    input_num = int(sys.argv[1])
    findSequence(input_num)

I am not an expert at Python and if there is something very bad with the code 
above, please do excuse me. I hope this is the place to report this thing.

----------
messages: 3744
nosy: jarav, pypy-issue
priority: performance bug
status: unread
title: pypy slower than CPython for recursion

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