[pypy-issue] [issue930] Recursion with cache slower on pypy than CPython 2.6

[qbproger]

New submission from qbproger <qbproger at gmail.com>:

This runs slower on Pypy 1.6 (and trunk) than CPython 2.6.5.  CPython 2.7 runs
this even faster

OR_VAL = [0] * 10
FINAL_CHECK = 0
for i in xrange(0, 10):
    OR_VAL[i] = 1 << i
    FINAL_CHECK |= OR_VAL[i]

def place_numbers(last_num, check, left, cache):
    if left == 0:
        if check == FINAL_CHECK:
            return 1
        return 0
    
    if (check, left, last_num) in cache:
        return cache[(check, left, last_num)]
    
    output = 0
    for n in (last_num - 1, last_num + 1):
        if n < 10 and n > -1:
            flip = False
            if (check & OR_VAL[n]) == 0:
                flip = True
                check = check | OR_VAL[n]
            output += place_numbers(n, check, left-1, cache)
            if flip:
                check = check & (~OR_VAL[n])
    
    cache[(check, left, last_num)] = output
    
    return output

def main():
    cache = {}
    check = 0
    ans = 0
    for size in xrange(10, 41):
        for first_number in xrange(1, 10):
            check |= OR_VAL[first_number]
            ans += place_numbers(first_number, check, size-1, cache)
            check &= ~OR_VAL[first_number]
    print ans
main()

----------
messages: 3443
nosy: pypy-issue, qbproger
priority: performance bug
status: unread
title: Recursion with cache slower on pypy than CPython 2.6

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