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 the much faster and much less heavy xoroshiro128+ #28

Closed kozross closed 7 years ago

kozross commented 7 years ago

If you'd like empirical evidence for the improvements gained from using xoroshiro128+ over MT, you can find it here. This change also simplifies your licensing - the implementation given at the resource linked is public domain, so I simply put the one used here under ISC. I've modified the documentation in the source files and README.md appropriately. I have attempted to stick to the code style used throughout the rest of the project as much as possible - let me know if I missed anything, and I will happily fix it.

Based on my own testing, this change does indeed provide a noticeable boost in performance - the tests finish in about 37 seconds on my machine on my branch, versus 53 or so on the mainline. Additionally, I managed to raise CPU efficiency: according to perf stat, mainline has an IPC (instructions per cycle) of 2.5, while my branch has 3.0.

Unfortunately, I get 11 failing tests, but it's a little difficult for me to distinguish which ones have failed and why. My preliminary read of the codebase suggests that these tests may be based on 'hardcoded' RNG states, which obviously won't work any more. If you could direct me to what I'd need to fix to have them pass (or even where to start looking!), I would be very grateful, and happy to amend.

silentbicycle commented 7 years ago

I'm traveling right now (coming back from Strange Loop...) and may not get to this for a couple days. I was going to evaluate SipHash as an alternative for both MT64 and FNV-1a once I was done with refactoring for adding multi-core support; this sounds promising too.

(Also, unrelated to this, but examples of how you're using theft, thoughts about API usability stuff, and so on would be appreciated.)

silentbicycle commented 7 years ago

Oh: and please target the PR against develop, rather thanmaster, so it can be included in the release process. There are a few interface changes there, but probably nothing that will cause merge conflicts besides nearby changes to docs.