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 B5D4F407A9 for ; Sun, 30 Jan 2022 18:23:46 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id B77AC68B1F6; Sun, 30 Jan 2022 20:23:43 +0200 (EET) Received: from relay11.mail.gandi.net (relay11.mail.gandi.net [217.70.178.231]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id B011668B112 for ; Sun, 30 Jan 2022 20:23:37 +0200 (EET) Received: from localhost (213-47-68-29.cable.dynamic.surfer.at [213.47.68.29]) (Authenticated sender: michael@niedermayer.cc) by mail.gandi.net (Postfix) with ESMTPSA id 7F2F7100004 for ; Sun, 30 Jan 2022 18:23:36 +0000 (UTC) Date: Sun, 30 Jan 2022 19:23:35 +0100 From: Michael Niedermayer To: FFmpeg development discussions and patches Message-ID: <20220130182335.GG2829255@pb2> References: <20220125102109.522-1-michael@niedermayer.cc> <164337232528.23111.7444999659506493047@lain.red.khirnov.net> MIME-Version: 1.0 In-Reply-To: <164337232528.23111.7444999659506493047@lain.red.khirnov.net> Subject: Re: [FFmpeg-devel] [PATCH 1/2] avutil/random_seed: Speed up fate test 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="===============6647517873412025473==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: --===============6647517873412025473== Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="OXQl9MXAJIeKbuNn" Content-Disposition: inline --OXQl9MXAJIeKbuNn Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Jan 28, 2022 at 01:18:45PM +0100, Anton Khirnov wrote: > Quoting Michael Niedermayer (2022-01-25 11:21:08) > > This decreases the quality of the seeds during the test, it does not af= fect > > the seeds outside the test. > > There is a small chance that this causes test failures, if that happens > > the threshold needs adjusting > >=20 > > Testing on an idle x86_64 system shows that this passes even with the t= est strength > > increased to 32768 from 256 with 0 retries > > So test failures are not anticipated > > Lowering the threshold from 3 to 2 causes failure at test strength of 3= 2768 > >=20 > > Signed-off-by: Michael Niedermayer > > --- > > libavutil/random_seed.c | 2 +- > > 1 file changed, 1 insertion(+), 1 deletion(-) > >=20 > > diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c > > index 70dc509d2f..509b74936c 100644 > > --- a/libavutil/random_seed.c > > +++ b/libavutil/random_seed.c > > @@ -95,7 +95,7 @@ static uint32_t get_generic_seed(void) > > last_td =3D t - last_t; > > buffer[++i & 511] +=3D last_td % 3294638521U; > > if ((t - init_t) >=3D CLOCKS_PER_SEC>>5) > > - if (last_i && i - last_i > 4 || i - last_i > 64 || TES= T && i - last_i > 8) > > + if (last_i && i - last_i > 4 || i - last_i > 64 || TES= T && i - last_i > 3) >=20 > On my Ryzen 5950x, this brings the test runtime from > 60s to ~30s, > which is a good improvement, but still quite a lot (the entire FATE run > with -j32 and without the random-seed test is ~40s). >=20 > How about something like this instead (takes about 8s on my machines, obs= erved > no test failures): this works, though it may be better to estimate the collected entropy=20 and stop once enough is collected i played around with the code a bit and got the test to pass with 32768 in = 5min down from i think 17min and the unmodified 256 test from 8 sec to 3 sec=20 the 8 is with my 2 and your patch applied but the resulting threshold in the code doesnt feel correct also a completely different approuch would be to predict/compress the timestamp deltas to estimate the entropy i need to do something else now or i loose my sanity, maybe ill look at it again in a few days, but feel free to continue working on the WIP below if you like (if something makes no sense in it it likely doesnt) thx diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c index b1bbbd1b69..0255de7302 100644 --- a/libavutil/random_seed.c +++ b/libavutil/random_seed.c @@ -62,18 +62,21 @@ static int read_random(uint32_t *dst, const char *file) #endif } =20 +#define N_COUNTS 5 + static uint32_t get_generic_seed(void) { uint64_t tmp[120/8]; struct AVSHA *sha =3D (void*)tmp; clock_t last_t =3D 0; clock_t last_td =3D 0; - clock_t init_t =3D 0; + clock_t last_td2 =3D 0; static uint64_t i =3D 0; static uint32_t buffer[512] =3D { 0 }; unsigned char digest[20]; uint64_t last_i =3D i; - uint64_t cnt =3D 0; + uint32_t last_td_count[N_COUNTS] =3D {0}; + int entropy =3D 0; =20 av_assert0(sizeof(tmp) >=3D av_sha_size); =20 @@ -89,21 +92,33 @@ static uint32_t get_generic_seed(void) =20 for (;;) { clock_t t =3D clock(); - if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >=3D t && - !(TEST && cnt > (1 << 15))) { - last_td =3D t - last_t; - buffer[i & 511] =3D 1664525*buffer[i & 511] + 1013904223 + (la= st_td % 3294638521U); - cnt++; + clock_t tmp =3D t - last_t; + if (last_td =3D=3D tmp || last_td2 =3D=3D tmp) { + buffer[i & 511] =3D 1664525*buffer[i & 511] + 1013904223 + (tm= p % 3294638521U); + if (last_td =3D=3D tmp) { + last_td_count[0] ++; + } else { + int add_entropy =3D INT_MAX; + for (int j =3D N_COUNTS-1; j; j--) { + add_entropy =3D FFMIN(add_entropy, abs(last_td_count[j= ] - last_td_count[0])); + last_td_count[j] =3D last_td_count[j-1]; + } + last_td_count[0] =3D 0; + if (last_td2 !=3D last_td) + entropy +=3D av_log2(add_entropy); + last_td2 =3D last_td; + } } else { - last_td =3D t - last_t; - buffer[++i & 511] +=3D last_td % 3294638521U; - if ((t - init_t) >=3D CLOCKS_PER_SEC>>5) - if (last_i && i - last_i > 4 || i - last_i > 64 || TEST &&= i - last_i > 3) - break; + if (last_td2 !=3D last_td) + entropy +=3D av_log2(FFMIN(abs(last_td - tmp), abs(last_td= 2 - tmp)) + 1) + av_log2(last_td_count[0]); + buffer[++i & 511] +=3D tmp % 3294638521U; + last_td2 =3D last_td; + last_td_count[0] =3D 0; } + if (last_i && entropy > 32 || entropy > 128 || TEST && entropy > 8) + break; + last_td =3D tmp; last_t =3D t; - if (!init_t) - init_t =3D t; } =20 if(TEST) { [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB No snowflake in an avalanche ever feels responsible. -- Voltaire --OXQl9MXAJIeKbuNn Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEIAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCYfbXowAKCRBhHseHBAsP q71jAJ4y9vwY351bvZJcBLAuZfJCS2c2fwCfRhfUfVXJTB0Bk4Wx6Casqp+poGE= =zYGJ -----END PGP SIGNATURE----- --OXQl9MXAJIeKbuNn-- --===============6647517873412025473== 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". --===============6647517873412025473==--