| Message ID | 20240102022845.9916-1-michael@niedermayer.cc |
|---|---|
| State | New |
| Headers | show |
| Series | [FFmpeg-devel] avutil/eval: Use integer for random() state | expand |
| Context | Check | Description |
|---|---|---|
| yinshiyou/make_loongarch64 | success | Make finished |
| yinshiyou/make_fate_loongarch64 | success | Make fate finished |
| andriy/make_x86 | success | Make finished |
| andriy/make_fate_x86 | success | Make fate finished |
On date Tuesday 2024-01-02 03:28:45 +0100, Michael Niedermayer wrote: > rounding the 64bit integer state to double between each iteration > causes a reduction in quality of the random number generator. > For example its period drops from 2^64 to around 200 million > > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc> > --- > libavutil/eval.c | 16 +++++++++++++--- > 1 file changed, 13 insertions(+), 3 deletions(-) > > diff --git a/libavutil/eval.c b/libavutil/eval.c > index bad9e4ecb8d..89c61ba4bf5 100644 > --- a/libavutil/eval.c > +++ b/libavutil/eval.c > @@ -55,6 +55,7 @@ typedef struct Parser { > void *log_ctx; > #define VARS 10 > double *var; > + uint64_t *var_uint64; > } Parser; > > static const AVClass eval_class = { > @@ -173,6 +174,7 @@ struct AVExpr { > } a; > struct AVExpr *param[3]; > double *var; > + uint64_t *var_uint64; > }; > > static double etime(double v) > @@ -230,9 +232,10 @@ static double eval_expr(Parser *p, AVExpr *e) > } > case e_random:{ > int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1); > - uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx]; > + uint64_t r= p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]); > r= r*1664525+1013904223; > p->var[idx]= r; > + p->var_uint64[idx]= r; > return e->value * (r * (1.0/UINT64_MAX)); > } > case e_while: { > @@ -319,7 +322,11 @@ static double eval_expr(Parser *p, AVExpr *e) > case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY); > case e_add: return e->value * (d + d2); > case e_last:return e->value * d2; > - case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2); > + case e_st : { > + int index = av_clip(d, 0, VARS-1); > + p->var_uint64[index] = 0; can't you set this to d2 and then in case e_random: uint64_t r = isnan(p->var[idx]) ? 0 : p->var_uint64[idx]; ?
On Tue, Jan 02, 2024 at 12:06:29PM +0100, Stefano Sabatini wrote: > On date Tuesday 2024-01-02 03:28:45 +0100, Michael Niedermayer wrote: > > rounding the 64bit integer state to double between each iteration > > causes a reduction in quality of the random number generator. > > For example its period drops from 2^64 to around 200 million > > > > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc> > > --- > > libavutil/eval.c | 16 +++++++++++++--- > > 1 file changed, 13 insertions(+), 3 deletions(-) > > > > diff --git a/libavutil/eval.c b/libavutil/eval.c > > index bad9e4ecb8d..89c61ba4bf5 100644 > > --- a/libavutil/eval.c > > +++ b/libavutil/eval.c > > @@ -55,6 +55,7 @@ typedef struct Parser { > > void *log_ctx; > > #define VARS 10 > > double *var; > > + uint64_t *var_uint64; > > } Parser; > > > > static const AVClass eval_class = { > > @@ -173,6 +174,7 @@ struct AVExpr { > > } a; > > struct AVExpr *param[3]; > > double *var; > > + uint64_t *var_uint64; > > }; > > > > static double etime(double v) > > @@ -230,9 +232,10 @@ static double eval_expr(Parser *p, AVExpr *e) > > } > > case e_random:{ > > int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1); > > - uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx]; > > + uint64_t r= p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]); > > r= r*1664525+1013904223; > > p->var[idx]= r; > > + p->var_uint64[idx]= r; > > return e->value * (r * (1.0/UINT64_MAX)); > > } > > case e_while: { > > @@ -319,7 +322,11 @@ static double eval_expr(Parser *p, AVExpr *e) > > case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY); > > case e_add: return e->value * (d + d2); > > case e_last:return e->value * d2; > > - case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2); > > + case e_st : { > > + int index = av_clip(d, 0, VARS-1); > > > + p->var_uint64[index] = 0; > > can't you set this to d2 and then in case e_random: > > uint64_t r = isnan(p->var[idx]) ? 0 : p->var_uint64[idx]; > > ? setting var_uint64[] to d2 would require us to check for non representable cases like outside 0..UINT64_MAX and NAN. We would have to do this for every st() even though very few actually get used as seeds. So it would slow it down. if we set it to 0, then we only need to do these checks in the first call to random (or just require the user not to use random with such values) subsequent calls use integers and need not check the double value thx [...]
diff --git a/libavutil/eval.c b/libavutil/eval.c index bad9e4ecb8d..89c61ba4bf5 100644 --- a/libavutil/eval.c +++ b/libavutil/eval.c @@ -55,6 +55,7 @@ typedef struct Parser { void *log_ctx; #define VARS 10 double *var; + uint64_t *var_uint64; } Parser; static const AVClass eval_class = { @@ -173,6 +174,7 @@ struct AVExpr { } a; struct AVExpr *param[3]; double *var; + uint64_t *var_uint64; }; static double etime(double v) @@ -230,9 +232,10 @@ static double eval_expr(Parser *p, AVExpr *e) } case e_random:{ int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1); - uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx]; + uint64_t r= p->var_uint64[idx] ? p->var_uint64[idx] : (isnan(p->var[idx]) ? 0 : p->var[idx]); r= r*1664525+1013904223; p->var[idx]= r; + p->var_uint64[idx]= r; return e->value * (r * (1.0/UINT64_MAX)); } case e_while: { @@ -319,7 +322,11 @@ static double eval_expr(Parser *p, AVExpr *e) case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY); case e_add: return e->value * (d + d2); case e_last:return e->value * d2; - case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2); + case e_st : { + int index = av_clip(d, 0, VARS-1); + p->var_uint64[index] = 0; + return e->value * (p->var[index]= d2); + } case e_hypot:return e->value * hypot(d, d2); case e_atan2:return e->value * atan2(d, d2); case e_bitand: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d & (long int)d2); @@ -339,6 +346,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); } @@ -724,7 +732,8 @@ int av_expr_parse(AVExpr **expr, const char *s, goto end; } e->var= av_mallocz(sizeof(double) *VARS); - if (!e->var) { + e->var_uint64= av_mallocz(sizeof(uint64_t) *VARS); + if (!e->var || !e->var_uint64) { ret = AVERROR(ENOMEM); goto end; } @@ -766,6 +775,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.const_values = const_values; p.opaque = opaque;
rounding the 64bit integer state to double between each iteration causes a reduction in quality of the random number generator. For example its period drops from 2^64 to around 200 million Signed-off-by: Michael Niedermayer <michael@niedermayer.cc> --- libavutil/eval.c | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-)