Why is set.remove so slow here?

Question

(Extracted from another question.) Removing this set's 200,000 elements one by one like this takes 30 seconds (Attempt This Online!):

s = set(range(200000))
while s:
    for x in s:
        s.remove(x)
        break

Why is that so slow? Removing a set element is supposed to be fast.

Answer 1

I think this is happening because you are removing the first element in the set every time. This creates a set which is increasingly empty one each iteration, so each time you create a new iterator and call __next__, it has to search further and further away.

So, here is the source code for the iterator __next__

It has to find the next entry like this:

while (i <= mask && (entry[i].key == NULL || entry[i].key == dummy))
    i++;

The the iterator __next__ works by finding the first non-empty, non-dummy value:

So, say we have something like:

entries = [null, 1, null, 2, null, 3, null, 4,  null, 5]

Then on each iteration of the while loop, you get:

entries = [null, 1, null, 2, null, 3, null, 4,  null, 5]
entries = [null, DUMMY, null, 2, null, 3, null, 4,  null, 5]
entries = [null, DUMMY, null, DUMMY, null, 3, null, 4,  null, 5]
entries = [null, DUMMY, null, DUMMY, null, DUMMY, null, 4,  null, 5]

So each time, the iterator has to search further and further away from the beginning of the entires, since each iteration of the while loop removes the first one. Hence, the quadratic time behavior.