Skip to content

Fast random number generators: Vectorized (SIMD) version of xorshift128+

License

Notifications You must be signed in to change notification settings

lemire/SIMDxorshift

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

35 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

SIMDxorshift

Xorshift are a family of pseudo-random number generators (RNG) invented by Marsaglia.

https://en.wikipedia.org/wiki/Xorshift

We present a vectorized version of xorshift128+, a popular random-number generator part of this family. It is written in C. The implementation uses Intel's SIMD instructions and is based on Vigna's original (pure C) implementation.

As a random number generator, xorshift128+ is not very strong. It fails statistical tests such as BigCrush. It should never be used alone in applications where the quality of the random numbers matters a great deal. However, when you just want fast and "good enough" random numbers, it should do well.

Since speed is the primary benefit of xorshift128+, then it is tempting to accelerate it further using vector instructions.

This library is used by the Yandex ClickHouse high-performance data engine.

Prerequisite

You should have a recent Intel processor (Haswell or better). If you bought your PC before everyone on Earth had a smartphone, it is probably too old a PC. Please upgrade.

Your compiler supports C99, right? C99 stands for 1999. That was almost 20 years ago.

Code sample

#include "simdxorshift128plus.h"

// create a new key
avx_xorshift128plus_key_t mykey;
avx_xorshift128plus_init(324,4444,&mykey); // values 324, 4444 are arbitrary, must be non-zero

// generate 32 random bytes, do this as many times as you want
__m256i randomstuff =  avx_xorshift128plus(&mykey);

Usage

$ make
$ ./fillarray
Generating 5000 32-bit random numbers
Time reported in number of cycles per array element.
We store values to an array of size = 19 kB.

We just generate the random numbers:
populateRandom_xorshift128plus(prec, size):  3.63 cycles per operation
populateRandom_avx_xorshift128plus(prec, size):  2.21 cycles per operation
populateRandom_avx_xorshift128plus_two(prec, size):  1.88 cycles per operation
populateRandom_avx512_xorshift128plus_two(prec, size):  1.47 cycles per operation

(Tests on a Skylake-X processor.)

Shallow analysis

SIMD random-number generation is something like twice as fast as plain C random number generation. However on algorithms such as random shuffling, the benefits of faster random number generation are lesser because other bottlenecks arise.

For the most part however, the application of SIMD instructions for random number generation is "free" if the CPU supports it.

Related work

Reference

Vigna's xorshift128+ implementation http://xorshift.di.unimi.it/xorshift128plus.c

About

Fast random number generators: Vectorized (SIMD) version of xorshift128+

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published