[FFmpeg-devel] [PATCH] lavu/lfg: add 64 bit random number generator
Michael Niedermayer
michael at niedermayer.cc
Tue Mar 15 21:35:49 CET 2016
On Tue, Mar 15, 2016 at 05:10:57PM -0300, Daniel Serpell wrote:
> Hi,
>
> El Mon, Mar 14, 2016 at 08:42:32PM -0400, Ganesh Ajjanagadde escribio:
> > On Sun, Mar 13, 2016 at 11:08 PM, Michael Niedermayer
> > <michael at niedermayer.cc> wrote:
> > > 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
> >
> > I just wanted to lay out the implementation, it was easier for me to
> > test and compare that way. Also, don't really know if it should be
> > public or private. I really felt that all random number stuff should
> > go into e.g lavu/rand.h, right now it is quite scattered across
> > random_seed.c, lfg.h (which is not great from a discoverability
> > standpoint).
> >
> > Anyway, if you are flexible about where it could go, I will resubmit
> > as lavu/rand.h, lavu/rand.c containing this 64 bit gen. Is this fine
> > with you?
> >
> > Some day or the other this can be cleaned up into e.g a single header,
> > but that maybe best handled later.
> >
> > >
> > > also the LFG could be trivially extended/changed to 64bit if one wants
> > > only needs uint64_t being used
> >
> > I can believe the extendability, but note that I do not know about the
> > quality of such generators. The linked TestU01 paper did not seem too
> > happy with the additive lagged Fibonacci generators, and instead
> > favored multiplicative ones like av_mlfg_get.
> >
> > >
> > > also theres av_mlfg_get() which passes all tests, though slower of
> > > course
> >
> > Are you sure it passes all of BigCrush? What test suite are you referring to?
> >
> > >
> > > and does xorshift128+ really pass all tests ?
> >
> > This was a claim on wikipedia that is I believe incorrect, Vigna
> > himself makes no such absolute claims. All he claims is (from
> > http://xorshift.di.unimi.it/xorshift128plus.c):
> > "
> >
> > /* This is the fastest generator passing BigCrush without
> > systematic failures, but due to the relatively short period it is
> > acceptable only for applications with a mild amount of parallelism;
> > otherwise, use a xorshift1024* generator. */
> > "
> > As such, he does not rule out all possible failures.
> > In fact, his page http://xorshift.di.unimi.it/#quality suggest certain failures.
> >
> > I therefore did not mention explicit absolute claims in the message either.
> >
> > > what if the bits are reversed so that the least significant and most
> > > significant are exchanged ?
> > > the text seems unclear about that
> >
> > Not sure exactly which text you are referring to, I did not look at
> > this in too much depth because it is claimed on the page that Chrome,
> > Firefox, and others use it - I doubt they would have hunted down and
> > used this if this was bad.
> >
> > >
> > > 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
> >
> > Thanks, unfortunately I am not a PRNG expert and have not dug too
> > deeply into this.
> >
>
> I normally use the PRNG from Bob Jenkins,
> http://www.burtleburtle.net/bob/rand/smallprng.html
"there is no guaranteed minimum cycle length"
that would imply that the generator could be arbitrarily bad for some
seeds
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
For every action, there is an equal and opposite reaction. -- Newton
For every man jailed for a minor crime, theres one person more that
will hate the government, some of them will become terrorists.
-------------- 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/20160315/6949abac/attachment.sig>
More information about the ffmpeg-devel
mailing list