python 3 code slower with pypy3

Issue #2770 new
lesshaste
created an issue

The following code was written by someone called Dennis.

from functools import lru_cache

@lru_cache(maxsize = None)
def haf(matrix):
        n = len(matrix)
        if n == 2: return matrix[0][1]
        h = 0
        for j in range(1, n):
                if matrix[0][j] == 0: continue
                copy = list(matrix)
                del copy[:j+1:j]
                copy = list(zip(*copy))
                del copy[:j+1:j]
                h += matrix[0][j] * haf(tuple(copy))
        return h

print(haf(tuple(map(tuple, eval(open(0).read())))))

If you feed into it the following input (for example):

[[0, -1, 0, 0, -1, 1, 1, -1, 1, -1, -1, 1, 1, 0, 1, 1, 1, 0, 1, -1, -1, 0, 0, -1, -1, 0], [-1, 1, 1, 1, -1, 1, -1, 0, 1, -1, 0, 0, -1, 0, 1, 1, 1, 0, 0, -1, 0, 0, -1, -1, -1, 0], [0, 1, 1, -1, 0, 0, 1, 0, 0, -1, 1, 0, -1, 1, -1, 0, 0, 0, -1, 0, 1, 0, 1, 1, 1, -1], [0, 1, -1, 0, -1, 0, 0, 1, 0, 0, -1, 1, 1, -1, -1, -1, 0, 1, -1, 1, -1, 0, 1, 0, 0, -1], [-1, -1, 0, -1, 1, 0, 1, 0, -1, 1, 1, -1, 0, -1, 0, 1, 1, -1, 0, -1, 1, 0, -1, 1, 1, -1], [1, 1, 0, 0, 0, 0, 0, -1, 1, 0, 0, 1, 0, -1, -1, -1, -1, 0, 0, -1, -1, 1, 1, 0, 1, 0], [1, -1, 1, 0, 1, 0, 0, 1, -1, -1, -1, 1, -1, -1, 0, -1, 1, 0, -1, 0, -1, -1, 0, -1, 0, -1], [-1, 0, 0, 1, 0, -1, 1, 0, 1, 0, 0, -1, -1, -1, 1, 0, 0, 1, -1, 1, 1, 0, -1, 0, -1, 1], [1, 1, 0, 0, -1, 1, -1, 1, 0, 0, -1, -1, -1, -1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1], [-1, -1, -1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 1, 0, 0, 0, -1, -1, 0, -1, 1, 0, -1, -1, -1, 0], [-1, 0, 1, -1, 1, 0, -1, 0, -1, -1, 0, 1, 1, 0, 1, 0, 0, -1, -1, 1, 0, -1, 1, 1, 0, 0], [1, 0, 0, 1, -1, 1, 1, -1, -1, 0, 1, -1, 1, 0, -1, -1, 1, 1, 1, 0, 1, -1, -1, 0, -1, 1], [1, -1, -1, 1, 0, 0, -1, -1, -1, 1, 1, 1, 1, -1, -1, 1, 1, -1, 0, 0, -1, 0, 0, -1, 1, -1], [0, 0, 1, -1, -1, -1, -1, -1, -1, 0, 0, 0, -1, 1, -1, 0, 1, -1, 0, 0, 1, -1, -1, 1, 1, 1], [1, 1, -1, -1, 0, -1, 0, 1, 1, 0, 1, -1, -1, -1, -1, 1, 1, -1, 0, 1, 1, 0, 0, -1, 0, 1], [1, 1, 0, -1, 1, -1, -1, 0, 1, 0, 0, -1, 1, 0, 1, 1, 0, 1, -1, 1, 1, 1, -1, 1, 1, -1], [1, 1, 0, 0, 1, -1, 1, 0, 1, -1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, -1, 0, 1, 0, 1, 0], [0, 0, 0, 1, -1, 0, 0, 1, 1, -1, -1, 1, -1, -1, -1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 1, 0], [1, 0, -1, -1, 0, 0, -1, -1, -1, 0, -1, 1, 0, 0, 0, -1, 1, -1, -1, 1, 0, 1, -1, 0, -1, -1], [-1, -1, 0, 1, -1, -1, 0, 1, 1, -1, 1, 0, 0, 0, 1, 1, 0, -1, 1, 1, -1, -1, -1, -1, 0, 1], [-1, 0, 1, -1, 1, -1, -1, 1, -1, 1, 0, 1, -1, 1, 1, 1, -1, 0, 0, -1, 1, 1, 1, 1, 0, 0], [0, 0, 0, 0, 0, 1, -1, 0, 1, 0, -1, -1, 0, -1, 0, 1, 0, 0, 1, -1, 1, -1, -1, 1, 1, 1], [0, -1, 1, 1, -1, 1, 0, -1, -1, -1, 1, -1, 0, -1, 0, -1, 1, 1, -1, -1, 1, -1, 0, -1, 0, 0], [-1, -1, 1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 1, -1, 1, 0, 1, 0, -1, 1, 1, -1, 0, 0, -1], [-1, -1, 1, 0, 1, 1, 0, -1, 1, -1, 0, -1, 1, 1, 0, 1, 1, 1, -1, 0, 0, 1, 0, 0, 1, -1], [0, 0, -1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 1, 1, -1, 0, 0, -1, 1, 0, 1, 0, -1, -1, 1]]

it takes about 10 seconds on python3 and about 14 seconds using pypy3.5-5.10.1-linux_x86_64-portable

Comments (2)

  1. Carl Friedrich Bolz-Tereick

    Ah, I see. This is a very unfortunate case where PyPy is not actually helped by its integer list strategy. The constant conversion back and forth between lists (which store integers unboxed) and tuples (which don't) means that PyPy spends a lot of time allocating ints. Indeed, if I change the algorithm to use a subclass of int to defeat this optimization, PyPy becomes faster (roughly the speed of CPython, I don't think we can go much faster anyway since we spend most of the time doing dict lookups and list copies anyway).

    Possible approach to fix this: have specialized int tuples for the case where people use long tuples as hashable lists.

  2. Log in to comment