From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id C9585485F7 for ; Wed, 10 Jan 2024 22:48:45 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 8BA5668CFCB; Thu, 11 Jan 2024 00:48:42 +0200 (EET) Received: from mail-wm1-f44.google.com (mail-wm1-f44.google.com [209.85.128.44]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 8701868CF3E for ; Thu, 11 Jan 2024 00:48:36 +0200 (EET) Received: by mail-wm1-f44.google.com with SMTP id 5b1f17b1804b1-40e55c885d7so14450295e9.0 for ; Wed, 10 Jan 2024 14:48:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1704926915; x=1705531715; darn=ffmpeg.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :mail-followup-to:message-id:subject:to:from:date:from:to:cc:subject :date:message-id:reply-to; bh=NZ059fx4qVGs14xahfD2zlyg8PQsp7LHnk81Quh7P1A=; b=SrcZ5JhBfkTTC0X34AGs8m6Hahl0XzAaFoCXFMNmXdXWFp8r/CI0hjl/FOG+PlQWbN 3DLb72xnY/fgho6SqEJN3F4huQeZyxF0v07Sg7ZzTp7i7d3CPNPQJUh2t1mRHPR9+9hZ oiFUN2ygYkwB6fBRVAJ6hjBrxsRqzyk6u0QS2J4cAscAtoJrQb1ff3NlZFFb7MmtPM9P nd7FETfeOxcMdp8A/Ik29bUSMEjk/kQhZD5yuJvkVttTeMjLT5sNNfViEN1Z2n8pAmuY lSHTLQ9FUaVf9ay4I6AZ/sUX3k5Cm9+axdj96yglRAJuwso5XZkYgCX0Bs6tE7thEmWB G8GQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704926915; x=1705531715; h=user-agent:in-reply-to:content-disposition:mime-version:references :mail-followup-to:message-id:subject:to:from:date:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=NZ059fx4qVGs14xahfD2zlyg8PQsp7LHnk81Quh7P1A=; b=Kv3RuZrCdPqJs5K4E00eDOUtCoQYtMewqJn+a7hgKVBcfCxZ1xvBR2pepI85u/g1yD IaUll9z74SqPoN2+cyNZ0p/KUVW5JQ7W64eVlCneSeUIPnCuflF7WiY9DiuZnkjWAK4t 6TIcyZnNCqXV0XxdO1J8HsQ1IPMFhphO+4aedA4FLeQU2mGIcDgqPcMVmG4kZ0q3L+ek 8ic3WT8VbR4IzDt3OjngA61kWbP24m0J+bgUUmqfgW4w4uZjcG40RF5fYjtyfhRHGbzH 42K0pvvmuAuL46t3a2nYo7Z00DyCS655fdSuaJaG6+AEqXwCZxiqFEEsEGGAmx8QlDoQ tdBg== X-Gm-Message-State: AOJu0YxsPE+lBuYb0CUEsO1O6145IYEVF8huRSX17kR7cuuvaD8bUF2N E2fNpKVgtBDG876YPek7J8sxrLkO+HY= X-Google-Smtp-Source: AGHT+IG31bUCH43zyvCCrmqU9ICbVN/mzGJ5tpfmnRL9s0UWdpIpfj5byvkVJl9cdYrT++E2bMTyzA== X-Received: by 2002:a7b:c8cd:0:b0:40e:540a:dc22 with SMTP id f13-20020a7bc8cd000000b0040e540adc22mr71571wml.182.1704926914686; Wed, 10 Jan 2024 14:48:34 -0800 (PST) Received: from mariano (dynamic-adsl-84-220-189-10.clienti.tiscali.it. [84.220.189.10]) by smtp.gmail.com with ESMTPSA id n10-20020a170906118a00b00a2a37f63216sm2544127eja.171.2024.01.10.14.48.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 10 Jan 2024 14:48:34 -0800 (PST) Received: by mariano (Postfix, from userid 1000) id 2AE1BBFCDC; Wed, 10 Jan 2024 23:48:33 +0100 (CET) Date: Wed, 10 Jan 2024 23:48:33 +0100 From: Stefano Sabatini To: FFmpeg development discussions and patches Message-ID: Mail-Followup-To: FFmpeg development discussions and patches References: <20240109015521.26231-1-michael@niedermayer.cc> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20240109015521.26231-1-michael@niedermayer.cc> User-Agent: Mutt/2.1.4 (2021-12-11) Subject: Re: [FFmpeg-devel] [PATCH] avutil/eval: Use even better PRNG X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: 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 > --- > 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 > + * > + * 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 > + > +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".