Godefroid developed a state space exploration technique that does not store states in memory. This stateless search technique is effective for testing concurrent programs. It performs deterministic executions of a concurrent program by automatically controlling the execution of synchronization operations. This technique also uses partial order reduction methods to reduce the chance of executing two or more different totally-ordered paths with the same partial order. In this paper, we propose extensions to Godefroid's technique and compare it with other stateless search techniques for testing concurrent programs. Our empirical results indicate that a combination of stateless search and a simple cycle prediction method is very cost-effective for detecting deadlocks and violations of assertions.