[FFmpeg-devel] [PATCH] lavu/lfg: add 64 bit random number generator

[Michael Niedermayer]

On Sun, Mar 13, 2016 at 07:12:50PM -0400, Ganesh Ajjanagadde wrote:
> This is based on the relatively well known xorshift128+ of Sebastiano
> Vigna (https://en.wikipedia.org/wiki/Xorshift) that performs very well on the
> BigCrush suite, is very efficient, and is thus used by a number of
> clients: http://xorshift.di.unimi.it/ (see Introduction).
> 
> Moreover, the implementation is in the public domain:
> http://xorshift.di.unimi.it/xorshift128plus.c.
> 
> Concretely, it is nearly as fast as av_lfg_get (which only returns 32 bits),
> and has a much smaller cache (128 bits). Thus, the timings should also
> be more stable.
> 
> This is needed because av_lfg_get<<32 | av_lfg_get is far slower, and
> likely less random as measured by BigCrush - most LFG's perform
> quite poorly on the BigCrush suite:
> http://www6.tw.freebsd.org/distfiles/testu01.pdf.
> In particular, FFmpeg's seems to be Ran055 in the paper, see pg31.
> 
> Sample benchmark (Haswell, GCC + -march=native):
>   23200 decicycles in 624 calls of av_lfg_get,       1 runs,      0 skips
>   23040 decicycles in 624 calls of av_lfg_get,       2 runs,      0 skips
>   22810 decicycles in 624 calls of av_lfg_get,       4 runs,      0 skips
> [...]
>   19884 decicycles in 624 calls of av_lfg_get,   65532 runs,      4 skips
>   19880 decicycles in 624 calls of av_lfg_get,  131067 runs,      5 skips
>   19884 decicycles in 624 calls of av_lfg_get,  262136 runs,      8 skips
>   19877 decicycles in 624 calls of av_lfg_get,  524276 runs,     12 skips
> 
>   25380 decicycles in 624 calls of av_rand64_get,       1 runs,      0 skips
>   28560 decicycles in 624 calls of av_rand64_get,       2 runs,      0 skips
>   30112 decicycles in 624 calls of av_rand64_get,       4 runs,      0 skips
> [...]
>   22627 decicycles in 624 calls of av_rand64_get,   65536 runs,      0 skips
>   22625 decicycles in 624 calls of av_rand64_get,  131072 runs,      0 skips
>   22625 decicycles in 624 calls of av_rand64_get,  262143 runs,      1 skips
>   22624 decicycles in 624 calls of av_rand64_get,  524286 runs,      2 skips
> 
> Signed-off-by: Ganesh Ajjanagadde <gajjanag at gmail.com>
> ---
>  libavutil/lfg.c | 33 ++++++++++++++++++++++++++++++++-
>  libavutil/lfg.h | 26 ++++++++++++++++++++++++++
>  2 files changed, 58 insertions(+), 1 deletion(-)

why do you add this code to lfg.* (Lagged Fibonacci Generator)?
its not a lfg

also the LFG could be trivially extended/changed to 64bit if one wants
only needs uint64_t being used

also theres av_mlfg_get() which passes all tests, though slower of
course

and does xorshift128+ really pass all tests ?
what if the bits are reversed so that the least significant and most
significant are exchanged ?
the text seems unclear about that

anyway, iam fine with the addition of xorshift128plus but please
put it in a different file
above questions are more due to curiousity and not a objection

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

I am the wisest man alive, for I know one thing, and that is that I know
nothing. -- Socrates
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20160314/89ca5650/attachment.sig>