What makes pypy64 slow here?

Revision en1, by conqueror_of_tourist, 2021-12-30 20:52:55

In the recent Goodbye 2021 Round on Problem E my code seems to run a lot slower when running on pypy64 as opposed to regular pypy.

The following submissions are identical, with the exception being the language used.

141113239 (pypy3.7 — AC 732ms)

141185703 (pypy3.8 64bit — TLE)

Running on Custom Invocation on one testcase of size $$$10^5$$$ shows that pypy3.7 will take about 250ms whereas pypy3.8-64 will take 5600ms.

Profiling my code it seems like the culprit is my find function

#Finds smallest index of segtree such that seg[ind] <= x
#Only works if func = min
def find(self, x):
    curr = 1
    if self.data[curr] > x:
        return -1
    while curr < self._size:
        assert self.data[curr] <= x
        if self.data[2 * curr] <= x:
            curr = 2 * curr
            curr = 2 * curr + 1
        assert self.data[curr] <= x
    return curr - self._size

Replacing this function with a trivial (but incorrect) function makes the submission run in ~230 ms in both languages. However it seems like this function should run in $$$O(log n)$$$ and not be 20x slower than the rest of my code (and if itis slow, why is it not an issue in 32bit pypy?). If anyone can figure out the issue here (and what I need to avoid to be able to run code in pypy64 quickly) it would be greatly appreciated.


  Rev. Lang. By When Δ Comment
en1 English conqueror_of_tourist 2021-12-30 20:52:55 1429 Initial revision (published)