Is there any release plan for 0.93 version?
statistical tests & psuedo- random number generators (RNGs, PRNGs)
Status: Beta
Brought to you by:
orz
Menu
▾
▴
Hello,
any plan to release 0.93 version? I think that alone patches for multithreaded option are worth to make 0.93 release. Once 0.93 is released I will create RPM package for Fedora.
Thanks a lot!
Jirka
I had a second HDD crash and lost everything I'd done for 0.93. I'm going back over everything I did for (the multithreading fixes were easy enough), but it has been a lower priority than other things.
Oh dear!
Hopefully new year will bring you new (good) luck.
Suggestion for next version: leave out the *.lib binary files. To actually make use of a static linking library, you need a compiler, hence you can build it yourself from source.
Seems like a pretty reasonable idea to me.
Last edit: 2015-01-11
+1
Hi,
it has been a while since we have been in contact. How are you doing? I hope everything is fine on your side.
I have broken my right wrist in summer and I'm still recovering. Plaster is off now but apparently median nerve has been damaged and it will take quite some time till it's healed....
I hope you were able to recover your work from a second HDD crash. Are there any news on 0.93 release?
Jirka
Hi,
have you seen my question above?
Jirka
Hey, sorry, got distracted and forgot about that.
I haven't changed much with the PractRand library code in a while (on the library side; many of my projects make use its RNGs). IIRC it's mostly in an okay state (though probably I should review the multithreading code... IIRC there were some issues there were fixes might have gotten eaten in my HDD crashes?). Seeing the strong showing of gjrands test suite (shocking from such an obscure project, after seeing so many more popular test suites vastly underperform) was tempting me to try to understand its tests better to see if I could add some variations on their concepts to PractRand, but I haven't looked at it in a long while now... I don't think I even have records of which gjrand tests were producing the good results.
Hey,
I'm glad to hear back from you! How are you doing?
It's an excellent news that project is still used and supported. I have reviewed the discussions and found following issues being discussed for 93 version:
1) Improved input/ouptut performance by using 16kB buffer size for fwrite/fread calls. It was partailly fixed but not for fwrite.
2) Issues with multithreading. I will send you the patched files.
3) Suggestion for next version: leave out the .lib binary files. To actually make use of a static linking library, you need a compiler, hence you can build it yourself from source.
4) I vagualy remember that there was something with BRank test but I cannot find it anymore. Not sure if it was fixed or not.
5) I think you were working on some new tests but I have no details.
I will attach here patched tools directory. When comapring it against official 92 release I can see following changes:
1)Fix for multithreading. Minor change in the code but very important.
2)Added signal handling.
3)I believe fwrite in RNG_output.cpp is not fully fixed. I can see buffer size 16kB, but fwrite is still using only 512 bytes (hardcoded 64 value in for loop. consider using #define SIZEOF(a) ( sizeof (a) / sizeof (a[0]) ) macro instead to get buffer size.)
4)RNG_from_name.h -> BUF_SIZE 8kB instead of 16kB. Better reporting about the amount of read data implemented.
I believe that based on the attached files you can prepare 93 version preatty easily (at least bug fixes and read/write improvements)
Thanks a lot!
Jirka
I'm kind of in the middle of moving atm, so there won't be anything for a while.
Good luck with the moving!
I would like to check with you if it would be OK to fork the project on Github and publish my changes there. It would be limited for now to 4 items listed above. We can then merge the code when you have again time to look into it. Please let me know what you think about it. My changes are minor but some other people could stil benefit from them. Thanks for considering this.
Working on a next version atm.
Problems likely to get fixed this time around:
1. the multithreading fixes that got eaten need to be put back in, maybe checked over. I think Jirka's done most of the work there.
2. BRank on my version is crashing occasionally on longer test runs. Not sure how that slipped by. Looks like it's probably a very simple issue.
3. BCFN_FF in the expanded test set is producing some bad pvalues on its "freq" subresults. Not sure yet how I want to address that... can simply bias more away from failure reports, or switch it to a different algorithm (BRank uses one that might work for that circumstance).
4. The constants used in sfc32 seem significantly suboptimal, will adjust them.
Practrand has been noticed and cited this year, by Sebastiano Vigna, and just recently by Guy Steele. As a result it suddenly has a bigger presence on google search results. If you've got something new, this might be a good time for releasing a new version. Most of the interest seems to be in the tests.
Huh. There seem to be three PRNGs between those two citations: xoroshiro128plus, SplitMix, and TwoLCG.
xoroshiro128plus seems like an interesting variation on LFSRs, it maintains the excessive linearity problem, but the variation in structure (compared to classic LFSRs) costs little and may significantly improve quality, not sure yet. In PractRand it quickly fails binary rank tests, and also eventually fails a short-medium range linear tests in the expanded test suite (DC6-5x4Byte-1). The author suggests avoiding reliance on the lowest bit to work around the binary rank problem, but the 2nd lowest bit also fails binary rank tests (though it takes substantially larger matrices to detect that). A non-linear output function could fix that stuff, but I'd also prefer a larger statespace. It's not clear how well this PRNG supports random access - a function to skip forward exactly 2^64 is provided, but there's no obvious way to skip forward/backward other amounts - I'd guess it's possible, but requires significant precomputation on a per-power-of-2 basis and might be slow at runtime for distances that are not neat powers of two. I think xoroshiro has a single cycle of length 2^128-1.
SplitMix has a VERY simple state transition function with a reasonable output hashing function. As the author notes, there are several types of bad parameterizations and no good way to avoid them. I'd call the quality about 3-star if you avoid the bad parameterizations, but I haven't had time to run any tests on it. SplitMix has 2^63 cycles of length 2^64, though an unknown number of those cycles are bad.
TwoLCG looks pretty high in quailty, though I prefer to avoid variable shifts, and I'm a touch nervous about how similar the two LCGs used internally are. And is it just me or does that multiplier on the 2nd LCG look a bit odd, with 14 consecutive zero bits occuring twice in the same 64 bit number? Overall I'd rate it about 4-star quality by PractRand standards, TwoLCG has 2^126 - 2^63 good cycles of length 2^64 according to the author.
Considering that all three are single-cycle, based upon 64 bit math with 64 bit output, and look capable of supporting random access, I'd guess the closest comparison in PractRand is xsm64, which is 4-star quality and probably slower than xoroshiro128plus and vaguely comparable in speed to SplitMix or TwoLCG (I haven't benchmarked those, just eyeballing it). xsm64 has 2^63 cycles of length 2^128.
Er... anyway... back on topic. PractRand 0.94 is basically ready, I just need to fix up the documentation. I'm considering adding a new PRNG targetted soley at speed, it's about 50% faster than sfc of jsf on my computer, and passes all output tests (for the 32 and 64 bit version), though its avalanche properties are mediocre and it does not offer any minimum cycle length guarantees (average cycle length 2^191 for the 64 bit version).
Hey, post early, post often. Put one up ASAP if you've got some good new stuff ready. Do another one when you fix everything. After such a long wait, if you keep going until it's perfect, you'll never post anything.
50% faster than sfc or jsf, in my opinion is faster than it needs to be. But it will be fun to see how it's done, especially if it's fairly good :-)
Yes, three fairly interesting PRNGs. Not necessarily better than sfc64v4 or gjrand.
xoroshiro128+ has a reasonably quick random seek, (certainly under a millisecond) but like most linear generators, not supplied by the authors, and a real dog to try to program from first principles even though the theory is fairly simple.
Best of luck, and looking forward to the new version.
I just found by serendipity this conversation. Can you detail your test of xoroshiro128+? I have tested up to 8TB and I didn't found the DC6-5x4Byte-1 failure you mention. I use
./RNG_test stdin64 -tf 2 -te 1 -tlmaxonly
I tested the generator reversed, to avoid billions of reports of BRank, so that might be the cause, but before rerunning the tests I'd like be sure we're testing in the same setting.
./RNG_test xoroshiro128plus -tf 0 -te 1 -tlmaxonly -e 1
DC6-5x4Bytes-1 p-value at 8 terabytes: 1.1e-3
at 16 terabytes: 9.7e-7
I haven't let it run long enough to reach 32 terabytes yet, but I suspect it will come with a "FAIL" evaluation.
My xoroshiro128plus implementation looks like:
Uint64 result = state0 + state1; Uint64 tmp = state0 ^ state1; state0 = ((state0 << 55) | (state0 >> (64 - 55))) ^ tmp ^ (tmp << 14); state1 = ((tmp << 36) | (tmp >> (64 - 36))); return result;IIRC I also tried a variant that discarded the lowest bit and the upper 31 bits, plus a variant that instead of returning sequential values returned values from 2^64 apart in the stream. I think they both failed BRank eventually, but nothing I noticed asside from BRank.
OK, the code is perfect. Then probably the difference is due to testing the generator reversed. I'll retry the test without reversing (it'll take a while...).
I ran it on a modified executable with most of the tests in the expanded test set disabled in test_batteries.cpp. That kept my run time to relatively reasonable levels - about 12 hours for 16 terabytes. It also prevented BRank from filling the output with spam. I'm not sure exactly what "reversed" means in this context, but I would not expect it to matter. Neither bit-reversal of each output, nor order reversal of the output stream, should have any effect upon the outcome. Probably.
xoroshiro128plus on DC6-5x4Bytes-1, updated with the 32 TB result:
8 TB: 1.1e-3
16 TB: 9.7e-7
32 TB: 5.3e-13
In fact, the most interesting new option in PractRand would be able to exclude (or include only) some tests.
My post just got eaten, don't want to fully rewrite it, but: It would be nice to support fully specifying a test list from the command line, but long story short:
A. it would be a pain to implement
B. a powerful implementation would expose people to tests and parameterizations that aren't ready for remotely normal users ; a weak implementation doesn't seem very sexy to me
C. the core test battery with standard foldings often produces failures on tests other than those one would expect at first blush, disabling those is a bad idea in a surprisingly wide variety of circumstances ; and they are fast enough that there's usually not that much benefit to being able to disable some of them either. I'm not sure who would benefit from being able to enable individual tests from the expanded test set.
The use case in question here, of reproducing a failure on a known test at an unknown test length, is too much of a special case to justify the efforts and tradeoffs needed. There are a few other cases it would help too, but there are cases it would hurt as well, and overall I'm not seeing it being a good idea at this time.
I was able to replicate your results. I can confirm that reversing the bits (bit 0 becomes bit 63, bit 1 becomes bit 62, etc.) has a significant impact on the test.
Huh. IIRC that test is supposed to opperate only on hamming weights of 32 bit numbers, so if your PRNG outputs 32 bits at a time in theory bit reversal should have zero impact.
And... xoroshiro128plus doesn't output 32 bits a time, does it? Doh. So... 5 32 bit values covers two full 64 bit outputs and half of a third, so bit-reversal will change which half of the third it sees. Actually, the stride is 32 bits, so it will alternate between two full outputs and the lower half of the following output, and two full outputs plus the upper half of the preceding output. Assuming the hardware is little-endian. Bit reversal will swap which direction it sees which half in. Somewhat subtle, but I guess it must make a difference. I think bit-reversal in this case will give you identical results to running normally on hardware of the opposite endianness.