Here is the patch with hoisted the conditionals out of the loop.

New microbenchmarking results:

$ ./python -m timeit -s "s = set(range(10**4))" -- "frozenset(s)"
Unpatched:     1000 loops, best of 3: 407 usec per loop
With patch #4: 1000 loops, best of 3: 325 usec per loop  (speed up 25%)
With patch #5: 1000 loops, best of 3: 272 usec per loop  (speed up 50%)

$ ./python -m timeit -s "s = {i+(j<<64) for i in range(10**4//2) for j in range(2)}" -- "frozenset(s)"
Unpatched:     1000 loops, best of 3: 995 usec per loop
With patch #4: 1000 loops, best of 3: 447 usec per loop  (speed up 123%)
With patch #5: 1000 loops, best of 3: 417 usec per loop  (speed up 139%)

$ ./python -m timeit -s "s = set(range(10**4)); s.add(-1); s.discard(-1)" -- "frozenset(s)"
Unpatched:     1000 loops, best of 3: 411 usec per loop
With patch #4: 1000 loops, best of 3: 355 usec per loop  (speed up 16%)
With patch #5: 1000 loops, best of 3: 406 usec per loop  (equal)

$ ./python -m timeit -s "s = {i+(j<<64) for i in range(10**4//2) for j in range(2)}; s.add(-1); s.discard(-1)" -- "frozenset(s)"
Unpatched:     1000 loops, best of 3: 1.01 msec per loop
With patch #4: 1000 loops, best of 3: 572 usec per loop  (speed up 77%)
With patch #5: 1000 loops, best of 3: 609 usec per loop  (speed up 66%)