search

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

Replacing MT with xoroshiro128+ #29

Closed kozross closed 6 years ago

kozross commented 7 years ago

As per request, I've made the commits against develop instead of master. Otherwise, this is identical to PR #28.

kozross commented 7 years ago

The comment on the commit probably refers to earlier changes - that was my bad. I fixed an overflow issue in the implementation, but when I committed, I only mentioned other unrelated changes.

The suggestion for extracting a random Boolean value is a bit puzzling - given the statistical strength of xoroshiro128+, using the method you described should work fine. I suspect this is Vigna being overly-cautious more than anything. As far as avoiding the 'everywhere-zero' problem, I deliberately xor the incoming seed with some random bytes. While it is theoretically possible to end up with an everywhere-zero result, it is extremely difficult, especially since I also initialize half of the RNG state with the bitwise complement of the input.

My main motivation for this change was that MT is a really slow PRNG, and xoroshiro128+ is just as good statistically, but runs faster and needs less state (as well as being considerably less complex). I'm a bit of an obsessive perfectionist in this regard, and it seemed like a very easy improvement. My own tests bear out a significant speedup (based on the tests provided).

silentbicycle commented 7 years ago

(I'm still expecting to merge this as part of the next release, barring running into major issues, but have been busy with work and haven't gotten back to it yet.)

silentbicycle commented 6 years ago

I'm expecting to merge this PR this soon; I've finally got time to work on this again.

From experiments so far, I see that simple numeric seeds (0, 1, ...) do take a couple steps to get mixed well, but I could use the hash of the provided seed.

kozross commented 6 years ago

@silentbicycle To avoid the problem of bad seeds, I use the advice given here and XOR the seed with 16 static random bytes in the code I've submitted.

silentbicycle commented 6 years ago

Looks good to me. The long-running work on the multicore branch shouldn't delay merging this any longer (and there should be minimal conflicts). Thanks!

silentbicycle commented 6 years ago

Xoroshiro128+ has been deprecated in favor of Xoshiro256**, so I'm probably going to switch it out for that in the 0.5.0 release, or possibly PCG instead. In any case, de-coupling the RNG and generalizing the comments was useful. Thanks.

(The 0.5.0 release has taken a while, because there's a ton of rework for multi-core support.)

silentbicycle commented 6 years ago

After some further testing (after merging the 0.4.4 release back into 0.5.0's develop) I think I'm going to revert this -- even with the current initialization, Xoroshiro128+ is causing a bunch of misc. test failures, particularly for tests that check that some large number of trials should always discover at least one failure. (Some of these are in the 11 you alluded to in #28.)

After changing the RNG again, there really isn't anything left of your changes in this PR. I'm still going to mention in the CHANGELOG that you helped with switching to a faster RNG, though.