[FFmpeg-devel,1/2] avutil/random_seed: Speed up fate test

This decreases the quality of the seeds during the test, it does not affect
the seeds outside the test.
There is a small chance that this causes test failures, if that happens
the threshold needs adjusting

Testing on an idle x86_64 system shows that this passes even with the test 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 32768

Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
---
 libavutil/random_seed.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Quoting Michael Niedermayer (2022-01-25 11:21:08)
> This decreases the quality of the seeds during the test, it does not affect
> the seeds outside the test.
> There is a small chance that this causes test failures, if that happens
> the threshold needs adjusting
> 
> Testing on an idle x86_64 system shows that this passes even with the test 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 32768
> 
> Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> ---
>  libavutil/random_seed.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> 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 = t - last_t;
>              buffer[++i & 511] += last_td % 3294638521U;
>              if ((t - init_t) >= CLOCKS_PER_SEC>>5)
> -                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
> +                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 3)

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).

How about something like this instead (takes about 8s on my machines, observed
no test failures):
diff --git a/libavutil/random_seed.c b/libavutil/random_seed.c
index 70dc509d2f..b006a75c39 100644
--- a/libavutil/random_seed.c
+++ b/libavutil/random_seed.c
@@ -73,6 +73,7 @@ static uint32_t get_generic_seed(void)
     static uint32_t buffer[512] = { 0 };
     unsigned char digest[20];
     uint64_t last_i = i;
+    uint64_t cnt = 0;
 
     av_assert0(sizeof(tmp) >= av_sha_size);
 
@@ -88,9 +89,11 @@ static uint32_t get_generic_seed(void)
 
     for (;;) {
         clock_t t = clock();
-        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t) {
+        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t &&
+            !(TEST && cnt > (1 << 15))) {
             last_td = t - last_t;
             buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
+            cnt++;
         } else {
             last_td = t - last_t;
             buffer[++i & 511] += last_td % 3294638521U;

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 affect
> > the seeds outside the test.
> > There is a small chance that this causes test failures, if that happens
> > the threshold needs adjusting
> > 
> > Testing on an idle x86_64 system shows that this passes even with the test 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 32768
> > 
> > Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
> > ---
> >  libavutil/random_seed.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > 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 = t - last_t;
> >              buffer[++i & 511] += last_td % 3294638521U;
> >              if ((t - init_t) >= CLOCKS_PER_SEC>>5)
> > -                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 8)
> > +                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 3)
> 
> 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).
> 
> How about something like this instead (takes about 8s on my machines, observed
> no test failures):

this works, though it may be better to estimate the collected entropy 
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 
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
 }
 
+#define N_COUNTS 5
+
 static uint32_t get_generic_seed(void)
 {
     uint64_t tmp[120/8];
     struct AVSHA *sha = (void*)tmp;
     clock_t last_t  = 0;
     clock_t last_td = 0;
-    clock_t init_t = 0;
+    clock_t last_td2 = 0;
     static uint64_t i = 0;
     static uint32_t buffer[512] = { 0 };
     unsigned char digest[20];
     uint64_t last_i = i;
-    uint64_t cnt = 0;
+    uint32_t last_td_count[N_COUNTS] = {0};
+    int entropy = 0;
 
     av_assert0(sizeof(tmp) >= av_sha_size);
 
@@ -89,21 +92,33 @@ static uint32_t get_generic_seed(void)
 
     for (;;) {
         clock_t t = clock();
-        if (last_t + 2*last_td + (CLOCKS_PER_SEC > 1000) >= t &&
-            !(TEST && cnt > (1 << 15))) {
-            last_td = t - last_t;
-            buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (last_td % 3294638521U);
-            cnt++;
+        clock_t tmp = t - last_t;
+        if (last_td == tmp || last_td2 == tmp) {
+            buffer[i & 511] = 1664525*buffer[i & 511] + 1013904223 + (tmp % 3294638521U);
+            if (last_td == tmp) {
+                last_td_count[0] ++;
+            } else {
+                int add_entropy = INT_MAX;
+                for (int j = N_COUNTS-1; j; j--) {
+                    add_entropy = FFMIN(add_entropy, abs(last_td_count[j] - last_td_count[0]));
+                    last_td_count[j] = last_td_count[j-1];
+                }
+                last_td_count[0] = 0;
+                if (last_td2 != last_td)
+                    entropy += av_log2(add_entropy);
+                last_td2 = last_td;
+            }
         } else {
-            last_td = t - last_t;
-            buffer[++i & 511] += last_td % 3294638521U;
-            if ((t - init_t) >= CLOCKS_PER_SEC>>5)
-                if (last_i && i - last_i > 4 || i - last_i > 64 || TEST && i - last_i > 3)
-                    break;
+            if (last_td2 != last_td)
+                entropy += av_log2(FFMIN(abs(last_td - tmp), abs(last_td2 - tmp)) + 1) + av_log2(last_td_count[0]);
+            buffer[++i & 511] += tmp % 3294638521U;
+            last_td2 = last_td;
+            last_td_count[0] = 0;
         }
+        if (last_i && entropy > 32 || entropy > 128 || TEST && entropy > 8)
+            break;
+        last_td = tmp;
         last_t = t;
-        if (!init_t)
-            init_t = t;
     }
 
     if(TEST) {



[...]