Pimp your random numbers with XorShift!

A 64bit XorShift is now used to generate random numbers in DWScript, and there is a now a separate random number generator per-execution, which is auto-randomized when an execution is created.

Previously, the RTL random generator was used, this was “okay” when you had only one script using random numbers at a time, but multiple scripts running at the same time would interfere (Randomize calls would affect each others f.i.), and Random isn’t really thread-safe.

Performance fo XorShift is roughly comparable to the Delphi RTL’s linear congruential generator, but with much better statistical random properties and a very long period, without the overhead of a Mersenne Twister. For those interested in the mathematical details, see “XorShift RNGs” paper by G. Marsagalia.

As an illustration of the improved random properties, consider filling a bitmap with “random” RGB colors for each pixel:

var x, y : Integer;
for x := 0 to bmp.Width-1 do
   for y := 0 to bmp.Height-1 do
      bmp.Pixel[x, y] := RandomInt($1000000);

Using the Delphi built-in Random, you’ll get something like the image below (generated at 512×512, then halved and downgraded to 4bpp for web consumption)

Delphi RTL Random

Oooh… the horizontal scratch lines! Not so random after all… I don’t know if the Delphi LCG is as biased as RANDU, but visibly, it is probably not something you want to rely upon too much.

And now, the same but with the XorShift implementation now used in DWS:

DWScript XorShift Random

The  XorShift implementation is very simple, fast, and doesn’t require much memory: a single 64bit value is enough to get good random, use two if you want longer periods that won’t have a chance to loop before the universe ends.

Last but not least, 64bit XorShift may be fast in 32bit binaries, but it practically walks on water in 64bit binaries 😉

DWS news roundup

Here is a quick summary of recent additions to DWScript:

  • exit, break and continue are now reserved keyword (and highlighted as such), previously they weren’t (as in Delphi), but having variables or functions named that way just “breaks” (pun intended) those language features (as it does in Delphi)
  • new TdwsRTTIEnvironment, fields and properties of a class exposed this way are directly accessible in scripts, more details on that one in a future post.
  • support passing constant arrays to dynamic array parameters (automatic conversion).
  • improved the language documentation.
  • added ability for custom extension of Abs() special function (now supported by TComplex).
  • added Clamp() floating-point function.
  • added Gcd(), Lcm(), IsPrime() and LeastFactor() integer functions.
  • fixed an issue that prevented conditional directives from being supported in all portions of the code, they can now properly be used anywhere.
  • JavaScript codegen optimization for variable symbol lookup.
  • minor tokenizer speedup, compile speed should now be close to 200k LOC/sec*.
  • more test cases, minor fixes.

*: FWIW since the old benchmark, compile and execution performance almost tripled and memory requirements were cut by approx 30%. At the same time the language became quite a bit richer.