@cfbolz This is just a small detail, but reading the code you just added to PyPy, you are using
diff = b - a
mid = a + diff // 2 # rounding down
But the original python code I wrote uses
mid = (a + b + 1) >> 1 # rounding up
While the direction of rounding wont affect correctness, it matters a tiny bit for performance (maybe 5%). The rounding also affects the size of mem
. For example with s='123' * 1234562
, rounding up makes len(mem)
be 16, and down makes len(mem)
be 21.
I'd say that that would be a significant improvement, yes.
I'm suprised that a code without any if statements could have problems like this.
Another thing that surprised me is that the following codes run fast:
def f():
zero = 0
for i in range(2000):
for j in range(1041):
i == zero
j % 6 == 0
f()
for i in range(2000):
for j in range(1041):
i == 0
j % 6 == 0
A couple of additional comments about this issue.
j % 6 == 0
can be subsituted with many other things. The reason I use j % 6 == 0
is that it is the simplest thing I could come up with that triggers the bug.
The bug is surprisingly easy to trigger in practice. If you are working with a 2000x2000 matrix or a 2000x2000 grid, and use if i == 0:
to deal with the first row, then it is easy to trigger the bug. So there are tons of real world examples that trigger this extreme slowdown issue.
Previously today, I found a code snippet that ran really really slow in PyPy for no apparent reason. The following is the minimal working example that I was able to come up with
def f():
for i in range(2000):
for j in range(1041):
i == 0
j % 6 == 0
f()
This code should run basically instant, but it takes a significant amount of time to run (like half a second). Almost any change to the code will make it run around 40 times faster. For example changing range(2000)
to range(1, 2000)
.
This is a really weird bug, probably the weirdest bug in PyPy that I have ever seen. I suspect the culprit is the i == 0
calculation, but I really have no clue.
I just noticed that PyPy and CPython dictionaries work in slightly different ways.
In CPython the formula being used is
i = x & mask
perturb = x
while ...:
perturb >>= 5
i = ((i << 2) + i + perturb + 1) & mask
and in PyPy it is
i = x & mask
perturb = x
while ...:
i = ((i << 2) + i + perturb + 1) & mask
perturb >>= 5
I'm not sure if this difference is intentional or not, but it does make a small difference for constructing anti-hash hacks.
I recently noticed that list.count
runs extremely slow in both PyPy2 and PyPy3. See for example this simple benchmark:
n = q = 10000
A = [0] * n
def my_counter(A, a):
count = 0
for b in A:
count += a == b
return count
import time
l = time.clock()
for i in range(q):
my_counter(A, 1)
r = time.clock()
print("Time taken:", r - l)
l = time.clock()
for i in range(q):
A.count(1)
r = time.clock()
print("Time taken:", r - l)
Locally using PyPy3 (v3.7.10) I get
Time taken: 0.09564578769311112
Time taken: 3.9947766063414565
so my_counter
takes 0.1 s and list.count
takes 4 s. It is not reasonable that list.count takes 4 s to do 10^8 counts.
Do you know the reason as to why randomization isn't applied to integer hashes too?
From what I understand, randomized string hashing was added to avoid being able to make ddos attacks. I'm currently getting ddosed from integer sequences. So I belive it would make a ton of sense to also randomized integer hashes.
A couple of days ago, there was a blog post about how to make Python dictionaries and sets run in O(n^2). Turns out it is super easy to construct it, and all versions of Python that I know of are affected (in particular PyPy2 and PyPy3).
The following is my implementation of the hack:
def anti_hash_hack(n):
"""
Input: integer n > 0
Output: List A of length n
such that 0 <= A[i] <= 2**(n.bit_length() + 2)
"""
pow2 = 2**(n.bit_length() + 2)
A = [pow2]
i = 1
while len(A) < n//2:
A.append(i)
i = (5 * i + 1) % pow2
while len(A) < n:
A.append(0)
return A
n = 123456
A = anti_hash_hack(n)
print("Creating set:")
set(A)
print("Done")
print("Creating dict:")
my_dict = {}
for i in range(n):
my_dict[A[i]] = i
print("Done")
Locally in PyPy3 creating the set (of size n = 123456
) takes 7.5 s, and creating the dictionary (of size n = 123456
) also takes 7.5 s. In CPython3 creating the set is almost instant, but creating the dictionary takes 11 s. From what I understand, sets in CPython can still be anti-hash hacked, but you need a slightly different hack for that.
For my usage of Python, hash tables being easily hackable is a deal breaker. I get that this is more of an issue with Python itself than with PyPy, but I still would like to hear your opinion of this. My questions are:
Should this / will this ever be fixed? For example adding some kind of random element to the integer hashing would fix this. Or will Python always have broken hash tables?
What is the best work around? The best work around I could come up with is:
import random
RANDOM = random.randrange(2**62)
...
n = 123456
A = anti_hash_hack(n)
set([a ^ RANDOM for a in A])
While this is the best work around that I could think of, it also makes the code a mess. So I really don't want to have to do this.
This very simple piece of code
for i in range(10**7):
if set([]):
break
takes 9 s with pypy3.8-v7.3.7-win64
, but only takes 0.1 s in pypy3.7-v7.3.7-win64
and pypy2.7-v7.3.6-win64
. From my testing it seems this issue exists in all PyPy3.8 versions (on both windows and linux).
Worth noting is that adding in an empty for loop fixes it (it makes it run in 0.1 s independently of PyPy version).
for i in range(10**7):
for _ in range(1): pass
if set([]):
break
Also worth noting is that switching set([])
to other similar expressions will also run crazy slow in PyPy3.8. Other examples you could try is min(0,1)
, list()
, []
, sum([])
, any([])
, all([0])
, set(set(set()))
, ... and the list goes on. Almost anything that I've tried makes it run super slow.
I'm active in a competitive programming website called codeforces.com. Somewhat recently the website switched from pypy3.6-v7.3.0-win32
to pypy3.8-v7.3.7-win64
. I must unfortunately say that we've seen a ton of performance regression. In general what I've noticed is that if I just add for _ in range(1):pass
everywhere, then the problems go away. Here is a link to some people talking about it.
Historically, I do have some examples of needing to use for _ in range(1):pass
for huge speed ups, but they were few and far between. Probably the best real world example of this is the datastructure RMQ. Here is an example of a RMQ implementation needing for _ in range(1):pass
to not run super slow.
I'm very well aware of this. The reason why I'm interested in the speed of .insert is that I've been trying to do a very fast implementation of insert sort. My idea is that if the number of elements I'm trying to sort are few (say <= 256), then I should be able to use array.array('B') to speed up the insert step by a factor of 8 compared to doing it with a list.
The reason why a fast running insert sort is super useful in Python is because there is a fascinating data structure called SortedList. This data structure uses insert sort on chunks (of size ~1000) as a subrutine, and it runs faster than any treap/AVL-tree/rbtree implementation that I've ever tried.
I have for a long time been playing around with implementing my own version of the sorted list data structure, and my hope was that I could use array.array('H') to make my version run up to 4 times faster. But when I benchmarked using array, I noticed that it ran really fast in CPython, and really sluggish in PyPy.
array.array insert(0,x) runs really sluggish in PyPy. PyPy can be slower by a factor of 13 compared to CPython. For example, on my windows computer running this program
import array
if 2/3: # Python3 vs Python2 check
from time import perf_counter as timer
else:
from time import clock as timer
for A in [], array.array('H'), array.array('B'):
l = timer()
for x in range(10**5):
A.insert(0, x % 100)
r = timer()
print('Took %f seconds' % (r - l))
I get the following output:
CPython 3.9.5 (64 bit)
Took 1.095486 seconds
Took 0.158121 seconds
Took 0.081960 seconds
CPython 2.7.18 (64 bit)
Took 1.103622 seconds
Took 0.261555 seconds
Took 0.139270 seconds
PyPy3 7.3.4 (64 bit)
Took 0.626467 seconds
Took 1.049843 seconds
Took 1.051765 seconds
PyPy2 7.3.4 (64 bit)
Took 0.628617 seconds
Took 2.114030 seconds
Took 1.054899 seconds
Thanks!
This basic Python program will segfault when run in either PyPy2 or PyPy3.
def gcd(x, y):
while y:
x, y = y, x % y
return x
def main():
n = 50
a = list(range(1, n + 1))[::-1]
f = [0] * n
f[0] = 1
g = a[0]
for i in range(n):
mx = 0
pos = -1
for i in range(n):
if f[i] == 0:
if gcd(g, a[i]) > mx:
mx = gcd(g, a[i])
pos = i
g = gcd(g, a[pos])
main()
I've tested this locally on my Windows computers (running PyPy2 and PyPy3 7.3.1) and I've also had multiple friends try running it on their systems. It segfaults for everyone.
Worth noting is that adding the line pypyjit.set_param(threshold = 2)
at the top will make it segfault for n = 3. So the segfault seems to be connected to the JIT.
So is this a bug in PyPy? I thought that setrecursionlimit(N) in PyPy was supposed to Setting the value to N reserves N/1000 times 768KB of stack space.
making it so you can do deeper recursion.
Ah yes, 32 bit CPython actually does segfault too. Don't know how I didn't notice that. Sorry
CPython never segfaults, it seems to be Windows PyPy specific.
This simple program segfaults at the f(5000)
call (when using Windows)
import sys
sys.setrecursionlimit(10**5)
def f(x):
if x:
f(x - 1)
f(5000)
print('Done')
It never prints Done
.
I've tested this on the latest versions of PyPy2 and PyPy3 running the program locally on both of my Windows computers and everything segfaults. I've also tried running it on codeforces.com (which runs Windows) and it segfaults there too.
The smallest x
for which f(x)
segfaults seems to vary depending on the system, but f(5000)
has segfaulted on every computer I've tested it on so far.