Why is this improved sieve slower with pypy?

Question

def sieve(n):
    nums = [0] * n
    for i in range(2, int(n**0.5)+1):
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

    return [i for i in range(2, n) if nums[i] == 0]

def sieve_var(n):
    nums = [0] * n
    for i in range(3, int(n**0.5)+1, 2):
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

    return [2] + [i for i in range(3, n, 2) if nums[i] == 0]

On my machine, sieve(10**8) takes 2.28 s while sieve_var(10**8) takes 2.67 s. I don't think pypy's warmup time is the culprit here, so why isn't sieve_var, which iterates over less, faster? In standard python 3.3 sieve_var is faster as expected. Using pypy 4.0.1 32bit on Windows 8.1.

Edit: As a test, I added count = 0 at the start of the function and count += 1 inside the inner loop (where nums[j] = 1 is). sieve(10**8) counts 242570202 while sieve_var(10**8) counts 192570204. So although the count isn't halved for sieve_var, it is doing less "work".

For fun, here is a version with slice indexing:

def sieve_slice(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

With python 3.6, sieve_slice runs about 4x faster than sieve, but with pypy3 7.3.0, sieve runs about 2x faster than sieve_slice.

Answer 1

I'm not sure why it's slightly slower on Windows. On Linux the speed is the same. However, I can answer why we get mostly the same speed. The answer would be the same if the program was written in C, and the answer is purely at the level of the processor. This program is bound on memory I/O accessing the list, which is 400 or 800MB in size. In the second version, you're basically avoiding one extra if nums[i] == 0 check. This extra check costs nothing, though, because the CPU just fetched nums[i - 1] in its caches during the previous iteration and will need nums[i + 1] during the next iteration. The CPU is waiting for the memory anyway.

To verify what I'm saying, try to make the nums array more compact. I tried to access it with nums[i // 2], assuming that i is always odd, and the result was twice faster. You can probably win even more by not using a Python list (stored as an array of 32-bit integers on a 32-bit PyPy), but instead an array of bits (but it's much more code because there is no standard built-in array of bits).