kentonv/capnproto — pull request #104 by dwrensha (2014-06-25 21:45:58+00:00)
Title: switch from linear congruential to Xorshift generator

This algorithm is a bit slower, but it would allow us not to worry about cycles. #103 would no longer be needed.

I also looked at a 32-bit Xorshift algorithm, but it was not significantly faster than this 128-bit one, and its numerical properties are certainly worse.

Below are some measurements from running the benchmark suite (run_all.bash on my benchmark branch), comparing the current linear congruential algorithm to the 128-bit Xorshift algorithm in this patch.

Interestingly, the eval case gets faster! I suspect this is because it, like catrank, hits some kind of cycle when it uses LCE.

carsales:

LCE | Xorshift
---------|--------
0m0.230s | 0m0.268s|
0m0.266s | 0m0.303s|
0m0.233s | 0m0.277s|
0m0.361s | 0m0.398s|
0m0.447s | 0m0.492s|
0m0.625s | 0m0.664s|
0m0.341s | 0m0.379s|
0m0.471s | 0m0.520s|
0m0.528s | 0m0.573s|
0m0.700s | 0m0.743s|

catrank:

LCE | Xorshift
---------|---------
0m0.610s | 0m0.620s|
0m0.644s | 0m0.658s|
0m0.623s | 0m0.631s|
0m0.785s | 0m0.800s|
0m0.833s | 0m0.837s|
0m1.020s | 0m1.029s|
0m0.781s | 0m0.794s|
0m0.950s | 0m0.961s|
0m0.861s | 0m0.868s|
0m1.038s | 0m1.051s|

eval:

LCE | Xorshift
---------|---------
0m0.472s | 0m0.439s|
0m0.530s | 0m0.496s|
0m0.522s | 0m0.490s|
0m0.588s | 0m0.574s|
0m1.060s | 0m1.013s|
0m1.167s | 0m1.114s|
0m2.200s | 0m2.204s|
0m2.366s | 0m2.324s|
0m2.533s | 0m2.478s|
0m2.724s | 0m2.650s|