www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 6594] New: Xorshift as default generator

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594

           Summary: Xorshift as default generator
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



In the std.random module I suggest to use Xorshift as default generator (the
one used when a generator is not specified, like in uniform(0,5)).

Two or three times I have had to hunt for performance problems in D code, and
in the end the cause was the high-quality but slow Mersenne Twister used on
default. Replacing it with the Xorshift has solved my problems, because it is
significantly faster. And the quality of numbers generated by Xorshift was
enough for all my purposes, it's better than the linear congruences generator.

The disadvantage of using Xorshift on default is that where you need really
high quality random numbers, the default is not enough any more. But I think
such situations are not common. If in your code you need very high quality
random numbers, then I think you know it, and you know to use the Mersenne
Twister (or even better).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Sep 02 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594


Joseph Rushton Wakeling <joseph.wakeling webdrake.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |joseph.wakeling webdrake.ne
                   |                            |t



2013-07-05 06:58:35 PDT ---
Have to register a disagreement here.  The default behaviour should be
statistically reliable -- choosing a faster but lower-quality RNG should be
done advisedly.  We shouldn't reproduce the awful situation of C/C++ where the
default RNG is awful and users have to be educated to avoid it.

However, we could think about easy ways to specify the default RNG type Random
at compile-time.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 05 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra gmail.com



MersenneTwister is supposed to be fast though...

I think the problem could have something to do with the whole "PRNG value
semantic" fiasco:

pragma(msg, Mt19937.sizeof);  //2504u
pragma(msg, Xorshift.sizeof); //16u

The mersenne twister range has a size of 2.5 KB (!)

The performance penalty most probably comes from passing it (by value) to
algorithms or whatnot.

I know for a fact this *will* cause significant slowdown. I observed this while
implementing a Lagged Fibonacci PRNG, whose size varies a lot. The bigger
flavors of the PRNG would make the runtime grind to a halt, while the biggest
versions simply stack overflowed.

----
All this to say, I think it is not the algorithm of mersenne itself that is
slow, but rather the range implementation. Until this is fixed, we *may* want
to change the default.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 05 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594




2013-07-05 08:37:38 PDT ---


 The performance penalty most probably comes from passing it (by value) to
 algorithms or whatnot.


If you're passing it by value, you have bigger problems than slowdown ... :-)


 I know for a fact this *will* cause significant slowdown. I observed this while
 implementing a Lagged Fibonacci PRNG, whose size varies a lot. The bigger
 flavors of the PRNG would make the runtime grind to a halt, while the biggest
 versions simply stack overflowed.
 
 ----
 All this to say, I think it is not the algorithm of mersenne itself that is
 slow, but rather the range implementation. Until this is fixed, we *may* want
 to change the default.


Fully agree that the real solution here is to change the RNGs to reference
types.  I don't think switching default to Xorshift is a good idea, though,

should give us pause on that idea.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 05 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX





 Have to register a disagreement here.  The default behaviour should be
 statistically reliable -- choosing a faster but lower-quality RNG should be
 done advisedly.
 I don't think switching default to Xorshift is a good idea, though,
 even as a short term method.  Apart from any other consideration, Issue



I have to agree.
Closed.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 08 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594




2013-07-08 06:09:36 PDT ---


 I have to agree.
 Closed.


Just to note, for future reference -- the Xorshift generators have been
criticized by other authors on a number of grounds -- see e.g.:
http://dx.doi.org/10.1145/1113316.1113319
[PDF preprint copy:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.7497&rep=rep1&type=pdf
]

However, there are some successors which look promising:
http://arxiv.org/abs/1004.3115
[This work was originally published in an Australian journal but the preprint
copy seems to be the only one readily available.]

So, I think there is future scope for replacing MT with a faster, simpler and
high-quality algorithm.

I also recently came across some further work extending MT to work with SIMD
and GPU implementations, which might be worth looking into:
http://www.math.sci.hiroshima-u.ac.jp/~saito/articles/sfmt.pdf
http://arxiv.org/abs/1005.4973v3

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 08 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=6594







 I also recently came across some further work extending MT to work with SIMD
 and GPU implementations, which might be worth looking into:
 http://www.math.sci.hiroshima-u.ac.jp/~saito/articles/sfmt.pdf


The SIMD MT seems very fit for Phobos (including its block-generation and the
variant that generates directly two doubles at a time).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 08 2013