silentbicycle / theft

property-based testing for C: generate input to find obscure bugs, then reduce to minimal failing input
ISC License
611 stars 31 forks source link

Multi-core searching and shrinking #16

Open silentbicycle opened 7 years ago

silentbicycle commented 7 years ago

Now that optional forking per-call is implemented, theft could support using multiple worker processes to concurrently search. For nontrivial property tests, searching for failures and shrinking them should parallelize well -- the main serializing point would be handling cases where multiple workers have concurrently found different failures, or when multiple tactics successfully shrink. For the former, the hashes for the other failures could be pushed back and shrunk immediately after shrinking the first completes (with a check for duplication). For the latter, it should favor the lower tactic ID.

This will need (at least) the following changes:

On the upside, there would not be any shared mutable state -- just shared state with copy-on-write -- so all decisions could be kept in the main process. It wouldn't need to coordinate concurrent updates to the bloom filter or queues.

silentbicycle commented 7 years ago

The property functions will run on worker processes, but type_info callbacks will need to run on the main process due to COW. This could be a bottleneck, particularly in cases where the property function itself is relatively quick.

Aside from user callbacks, the theft runner spends virtually all of its time in the random number generator. If that ends up being a significant bottleneck when running with several workers, it may be worth experimenting with moving the RNG out of the main process.