[Issue 3738] MinstdRand0 and MinstdRand very poor performance

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=3738


Witold Baryluk <baryluk at smp.if.uj.edu.pl> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW


--- Comment #3 from Witold Baryluk <baryluk at smp.if.uj.edu.pl> 2010-01-24 08:35:08 PST ---
One can observe that ?: line (branch2)
        _x = (y < v || y >= 2147483647) ? ((y+1) & 0x7fff_ffffu) : y;
can be changed , first to not contain not needed y<v, to  (branch1)
        _x = (y >= 2147483647) ? ((y+1) & 0x7fff_ffffu) : y;
or even remove branch completly (branchlessA)
        _x = (y & 0x7fff_ffff) + (y >> 31);
and possibly rearange terms (branchlessB)
        _x = (y + (y >> 31)) & 0x7fff_ffff;


MinstdRnd0
  standard: 44.65 s
  inline: 41.11 s
  standard with tricks (2 branches): 17.08 s
  inline with tricks (2 branches): 17.04 s
  standard with tricks (1 branch): 15.24 s
  inline with tricks (1 branch): 13.59 s
  standard with tricks (branchlesA): 16.50 s
  inline with tricks (branchelesA): 15.82 s
  standard with tricks (branchlesB):  17.74 s
  inline with tricks (branchelesB): 15.30 s

MinstdRnd
  standard: 44.95 s
  inline: 41.17 s
  standard with tricks (2 branch): 17.04 s
  inline with tricks (2 branche): 17.03 s
  standard with tricks (1 branch): 15.29 s
  inline with tricks (1 branche): 13.54 s
  standard with tricks (branchlesA): 16.46 s
  inline with tricks (branchelessA): 15.88 s
  standard with tricks (branchlesB): 18.10 s
  inline with tricks (branchelessB): 15.31 s

So fastest is currently branch1 version. 

Updated patch:

     void popFront()
     {
         static if (m)
-            _x = cast(UIntType) ((cast(ulong) a * _x + c) % m);
+            static if (is(UIntType == uint) && m == 4294967295uL) {
+                 const ulong x = (cast(ulong) a * _x + c);
+                 const ulong v = x >> 32;
+                 const ulong w = (x & 0xffff_ffffuL);
+                 const uint y = cast(uint)(v+w);
+                 _x = (y < v || y >= 4294967295u) ? (y+1) : y;
+            } else static if (is(UIntType == uint) && m == 2147483647u) {
+                 const ulong x = (cast(ulong) a * _x + c);
+                 const ulong v = x >> 31;
+                 const ulong w = (x & 0x7fff_ffffuL);
+                 const uint y = cast(uint)(v+w);
+                 _x = (y >= 2147483647u) ? ((y+1) & 0x7fff_ffffu) : y;
+            } else {
+                _x = cast(UIntType) ((cast(ulong) a * _x + c) % m);
+            }
         else
             _x = a * _x + c;
     }

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