[FFmpeg-devel] [PATCH] avutil/eval: Use even better PRNG
Stefano Sabatini
stefasab at gmail.com
Thu Jan 11 00:48:33 EET 2024
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 at 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 at 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).
More information about the ffmpeg-devel
mailing list