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 613A3485FF for ; Thu, 11 Jan 2024 02:39:38 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 16A1868CF16; Thu, 11 Jan 2024 04:39:36 +0200 (EET) Received: from relay6-d.mail.gandi.net (relay6-d.mail.gandi.net [217.70.183.198]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id AFF5468CDDB for ; Thu, 11 Jan 2024 04:39:29 +0200 (EET) Received: by mail.gandi.net (Postfix) with ESMTPSA id CA498C0002 for ; Thu, 11 Jan 2024 02:39:28 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=niedermayer.cc; s=gm1; t=1704940769; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=LwrJP1qwpDrJEGx87tMVvk5UvnAtKk6FTi7263Yqe7k=; b=g9DPXLzDZkXcL4Fq2qgg64SJYBdsUBqJhNRZj65zrQXxthQ6xUsgF5FQ4dohTxR4PSnaX5 TWtQmTAx0P2Qh6a6tbXdeYPEE4j7xR6blOJcF+BXIiY0q8GaK3JgrBxx2bQngcMLp4oWs6 NG1ut8SJHd/M/kvuZituqr2VFRXBvFcZUrMQy7pMWzKpLsFm4lU+B493cs/wq5R4NDCXCI CCsFxPpPfAkyQCO/1o1nqPLRtAWxcJDQQr5Pv2er7RjJKW0BeQvdDMhsodGhdpqdhzCRxZ tKpmuDXKmChZpgUtOUEBUn6z9wK6oAlD9D4FG3IGPNcRzcZ24TMB+lA8oUk7vA== Date: Thu, 11 Jan 2024 03:39:27 +0100 From: Michael Niedermayer To: FFmpeg development discussions and patches Message-ID: <20240111023927.GV6420@pb2> References: <20240109015521.26231-1-michael@niedermayer.cc> MIME-Version: 1.0 In-Reply-To: X-GND-Sasl: michael@niedermayer.cc 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: multipart/mixed; boundary="===============4959796120628116250==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: --===============4959796120628116250== Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="by4yvP7wYiOyYgE8" Content-Disposition: inline --by4yvP7wYiOyYgE8 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Jan 10, 2024 at 11:48:33PM +0100, Stefano Sabatini wrote: > On date Tuesday 2024-01-09 02:55:21 +0100, Michael Niedermayer wrote: [...] > > =20 > > static const AVClass eval_class =3D { > > @@ -174,7 +175,7 @@ struct AVExpr { > > } a; > > struct AVExpr *param[3]; > > double *var; > > - uint64_t *var_uint64; > > + SFC64 *prng_state; > > }; > > =20 > > static double etime(double v) > > @@ -233,10 +234,15 @@ static double eval_expr(Parser *p, AVExpr *e) > > =20 > > #define COMPUTE_NEXT_RANDOM() \ > > int idx =3D av_clip(eval_expr(p, e->param[0]), 0, VARS-1);= \ > > - uint64_t r =3D p->var_uint64[idx] ? p->var_uint64[idx] : (= isnan(p->var[idx]) ? 0 : p->var[idx]);\ > > - r =3D r * 1664525 + 1013904223; = \ > > + SFC64 *s =3D p->prng_state + idx; = \ > > + uint64_t r; \ > > + \ > > + if (!s->counter) { \ > > + r =3D isnan(p->var[idx]) ? 0 : p->var[idx]; = \ >=20 > > + sfc64_init(s, r, r, r, 12); \ >=20 > for the record, why 12? The reference has 3 init functions * one that uses one seed for the 3 parameters, it uses 12 rounds * one that uses 3 seperate seeds that uses 18 rounds * one that has "fast" in its name and does 8 rounds with one seed in 3 para= meters I will document this better [...] > > return e->value * (p->var[index]=3D 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); > > } > > =20 > > @@ -744,8 +750,8 @@ int av_expr_parse(AVExpr **expr, const char *s, > > goto end; > > } > > e->var=3D av_mallocz(sizeof(double) *VARS); > > - e->var_uint64=3D av_mallocz(sizeof(uint64_t) *VARS); > > - if (!e->var || !e->var_uint64) { > > + e->prng_state =3D av_mallocz(sizeof(*e->prng_state) *VARS); > > + if (!e->var || !e->prng_state) { > > ret =3D AVERROR(ENOMEM); > > goto end; > > } > > @@ -787,7 +793,7 @@ double av_expr_eval(AVExpr *e, const double *const_= values, void *opaque) > > { > > Parser p =3D { 0 }; > > p.var=3D e->var; > > - p.var_uint64=3D e->var_uint64; > > + p.prng_state=3D e->prng_state; > > =20 > > p.const_values =3D const_values; > > p.opaque =3D 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 > > + * >=20 > > + * This is a implementation of SFC64 a 64-bit PRNG by Chris Doty-Humph= rey. >=20 > nit: This is a implementation of SFC64, a 64-bit PRNG by Chris Doty-Humph= rey. >=20 > > + * > > + * This Generator is much faster (0m1.872s) than 64bit KISS (0m3.823s)= and PCG-XSH-RR-64/32 (0m2.700s) >=20 > what are these benchmarks against? a loop that computes alot of random numbers and at the end prints their sum. The behavior was btw quite different if the numbers are not summed and prin= ted as the compiler can then optimize some things out but noone would run a PRNG and not use the values. [...] > > +static inline uint64_t sfc64_get(SFC64 *s) { > > + uint64_t tmp =3D s->a + s->b + s->counter++; > > + s->a =3D s->b ^ (s->b >> 11); > > + s->b =3D s->c + (s->c << 3); // This is a multiply by 9 > > + s->c =3D ((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 =3D seeda; > > + s->b =3D seedb; > > + s->c =3D seedc; > > + s->counter =3D 1; > > + while (rounds--) > > + sfc64_get(s); > > +} > > + > > +#endif // AVUTIL_SFC64_H >=20 > 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). ok [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Take away the freedom of one citizen and you will be jailed, take away the freedom of all citizens and you will be congratulated by your peers in Parliament. --by4yvP7wYiOyYgE8 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEIAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCZZ9U2AAKCRBhHseHBAsP q2JnAJ937M6Ne3JOfdlz+MALJPYk4q8CpQCeJF9cklzBwcFRHlz1tJyyK3o0MFg= =isdP -----END PGP SIGNATURE----- --by4yvP7wYiOyYgE8-- --===============4959796120628116250== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ 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". --===============4959796120628116250==--