Re: [FFmpeg-devel] [PATCH] avutil/eval: Use even better PRNG

[Stefano Sabatini <stefasab@gmail.com>]

On date Tuesday 2024-01-09 02:55:21 +0100, Michael Niedermayer wrote:
> This is the 64bit version of Chris Doty-Humphreys SFC64
> 
> Compared to the LCGs these produce much better quality numbers.
> Compared to LFGs this needs less state. (our LFG has 224 byte
> state for its 32bit version) this has 32byte state
> Also the initialization for our LFG is slower.
> This is also much faster than KISS or PCG.
> 
> This could be merged with the change to integer LCG
> Also a few fate tests need an update. I will update fate if SFC64
> is the chosen PRNG
> 
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---
>  libavutil/eval.c    | 26 ++++++++++++--------
>  libavutil/sfc64.h   | 59 +++++++++++++++++++++++++++++++++++++++++++++
>  tests/ref/fate/eval |  2 +-
>  3 files changed, 76 insertions(+), 11 deletions(-)

cool :-)

>  create mode 100644 libavutil/sfc64.h
> 
> diff --git a/libavutil/eval.c b/libavutil/eval.c
> index 9d41140056c..d15becf9cda 100644
> --- a/libavutil/eval.c
> +++ b/libavutil/eval.c
> @@ -33,6 +33,7 @@
>  #include "eval.h"
>  #include "ffmath.h"
>  #include "internal.h"
> +#include "sfc64.h"

nit: sort order

>  #include "log.h"
>  #include "mathematics.h"
>  #include "time.h"
> @@ -55,7 +56,7 @@ typedef struct Parser {
>      void *log_ctx;
>  #define VARS 10
>      double *var;
> -    uint64_t *var_uint64;
> +    SFC64 *prng_state;
>  } Parser;

this is on top of another patch I guess

>  
>  static const AVClass eval_class = {
> @@ -174,7 +175,7 @@ struct AVExpr {
>      } a;
>      struct AVExpr *param[3];
>      double *var;
> -    uint64_t *var_uint64;
> +    SFC64 *prng_state;
>  };
>  
>  static double etime(double v)
> @@ -233,10 +234,15 @@ static double eval_expr(Parser *p, AVExpr *e)
>  
>  #define COMPUTE_NEXT_RANDOM()                                        \
>              int idx = av_clip(eval_expr(p, e->param[0]), 0, VARS-1); \
> -            uint64_t r = p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]);\
> -            r = r * 1664525 + 1013904223;                            \
> +            SFC64 *s = p->prng_state + idx;                          \
> +            uint64_t r;                                              \
> +                                                                     \
> +            if (!s->counter) {                                       \
> +                r = isnan(p->var[idx]) ? 0 : p->var[idx];            \

> +                sfc64_init(s, r, r, r, 12);                          \

for the record, why 12?

> +            }                                                        \
> +            r = sfc64_get(s);                                        \
>              p->var[idx] = r;                                         \
> -            p->var_uint64[idx]= r;

>  
>          case e_random: {
>              COMPUTE_NEXT_RANDOM();
> @@ -334,7 +340,7 @@ static double eval_expr(Parser *p, AVExpr *e)
>                  case e_last:return e->value * d2;
>                  case e_st :  {
>                      int index = av_clip(d, 0, VARS-1);

> -                    p->var_uint64[index] = 0;
> +                    p->prng_state[index].counter = 0;

I wonder if we should have a dedicated strandom() (or randomst)
function to store the value (and deprecate st for setting the random
seed, now that we are using a separated variable to store the state) -
not blocking though

>                      return e->value * (p->var[index]= d2);
>                  }
>                  case e_hypot:return e->value * hypot(d, d2);
> @@ -356,7 +362,7 @@ void av_expr_free(AVExpr *e)
>      av_expr_free(e->param[1]);
>      av_expr_free(e->param[2]);
>      av_freep(&e->var);
> -    av_freep(&e->var_uint64);
> +    av_freep(&e->prng_state);
>      av_freep(&e);
>  }
>  
> @@ -744,8 +750,8 @@ int av_expr_parse(AVExpr **expr, const char *s,
>          goto end;
>      }
>      e->var= av_mallocz(sizeof(double) *VARS);
> -    e->var_uint64= av_mallocz(sizeof(uint64_t) *VARS);
> -    if (!e->var || !e->var_uint64) {
> +    e->prng_state = av_mallocz(sizeof(*e->prng_state) *VARS);
> +    if (!e->var || !e->prng_state) {
>          ret = AVERROR(ENOMEM);
>          goto end;
>      }
> @@ -787,7 +793,7 @@ double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
>  {
>      Parser p = { 0 };
>      p.var= e->var;
> -    p.var_uint64= e->var_uint64;
> +    p.prng_state= e->prng_state;
>  
>      p.const_values = const_values;
>      p.opaque     = opaque;
> diff --git a/libavutil/sfc64.h b/libavutil/sfc64.h
> new file mode 100644
> index 00000000000..25bc43abef1
> --- /dev/null
> +++ b/libavutil/sfc64.h
> @@ -0,0 +1,59 @@
> +/*
> + * Copyright (c) 2024 Michael Niedermayer <michael-ffmpeg@niedermayer.cc>
> + *
> + * This file is part of FFmpeg.
> + *
> + * FFmpeg is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * FFmpeg is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with FFmpeg; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + *

> + * This is a implementation of SFC64 a 64-bit PRNG by Chris Doty-Humphrey.

nit: This is a implementation of SFC64, a 64-bit PRNG by Chris Doty-Humphrey.

> + *
> + * This Generator is much faster (0m1.872s) than 64bit KISS (0m3.823s) and PCG-XSH-RR-64/32 (0m2.700s)

what are these benchmarks against?

> + * And passes testu01 and practrand test suits.
> + *
> + */
> +
> +/**
> + * @file
> + * simple Pseudo Random Number Generator
> + *
> + */
> +
> +#ifndef AVUTIL_SFC64_H
> +#define AVUTIL_SFC64_H
> +
> +#include <inttypes.h>
> +
> +typedef struct SFC64 {
> +    uint64_t a,b,c,counter;
> +} SFC64;
> +

> +static inline uint64_t sfc64_get(SFC64 *s) {
> +    uint64_t tmp = s->a + s->b + s->counter++;
> +    s->a = s->b ^ (s->b >> 11);
> +    s->b = s->c + (s->c << 3); // This is a multiply by 9
> +    s->c = ((s->c << 24) | (s->c >> 40)) + tmp;
> +    return tmp;
> +}
> +
> +static inline void sfc64_init(SFC64 *s, uint64_t seeda, uint64_t seedb, uint64_t seedc, int rounds) {
> +    s->a       = seeda;
> +    s->b       = seedb;
> +    s->c       = seedc;
> +    s->counter = 1;
> +    while (rounds--)
> +        sfc64_get(s);
> +}
> +
> +#endif // AVUTIL_SFC64_H

nit: probably it still makes sense to use ff/FF prefixes even if the
header is not public (and if this is useful, probably it could be made
public as a faster/smaller alternative to lfg).
_______________________________________________
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
https://ffmpeg.org/mailman/listinfo/ffmpeg-devel

To unsubscribe, visit link above, or email
ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".