Actually set_find_free_slot() is not needed because there is set_insert_clean(). Results with using set_insert_clean():

$ ./python -m timeit -s "s = set(range(10**4))" -- "frozenset(s)"
Unpatched: 1000 loops, best of 3: 700 usec per loop
Patched:   1000 loops, best of 3: 570 usec per loop
Speed up: 23%

$ ./python -m timeit -s "s = {i+(j<<64) for i in range(10**4//2) for j in range(2)}" -- "frozenset(s)"
Unpatched: 100 loops, best of 3: 2.2 msec per loop
Patched:   1000 loops, best of 3: 765 usec per loop
Speed up: 188%

$ ./python -m timeit -s "s = set(range(10**4)); s.add(-1); s.discard(-1)" -- "frozenset(s)"
Unpatched: 1000 loops, best of 3: 700 usec per loop
Patched:   1000 loops, best of 3: 605 usec per loop
Speed up: 16%

$ ./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: 100 loops, best of 3: 2.2 msec per loop
Patched:   1000 loops, best of 3: 1.06 msec per loop
Speed up: 108%

Note that unpatched version is 6% slower now than before, perhaps due to issue23119.