In case there is some confusion: "constant-time" for purposes of timing side channels is not the same thing as completing in some bounded time. It's a rather terrible naming. Generate-and-test is just fine because you discard the iterations that you leaked something about.