Hello,
On Tue, 10 May 2022, Menglong Dong wrote:
> On Tue, May 10, 2022 at 2:17 AM Julian Anastasov <ja@xxxxxx> wrote:
> >
> > or just use
> >
> > start = prandom_u32_max(svc->num_dests);
> >
> > Also, this line can be before the spin_lock_bh.
> >
> > > + cur = &svc->destinations;
> >
> > cur = svc->sched_data;
> >
> > ... and to start from current svc->sched_data because
> > we are called for every added dest. Better to jump 0..127 steps
> > ahead, to avoid delay with long lists?
> >
>
> I'm a little afraid that the 'steps' may make the starting dest not
> absolutely random, in terms of probability. For example, we have
> 256 services, and will the services in the middle have more chances
> to be chosen as the start? It's just a feeling, I'm not good at
> Probability :/
Me too, so I created a test for the eyes :) I hope
it correctly implements the algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DESTS 1024
#define NTESTS (500000)
#define MAX_STEP 32
/* MAX_STEP:
* 4: last has 3 times more chance than first
* 5: last has 2 times more chance than first
* 6: last has 60% more chance than first
* 7: last has 50% more chance than first
* 10: last has 20% more chance than first
* 16: last has 10% more chance than first
* 32: last has 3% more chance than first
*/
int
main (int argc, char *argv[])
{
int arr[DESTS]; /* Hits per dest */
int i, n;
int64_t perc = 0, perc2;
memset(arr, 0, sizeof(arr));
srand(257);
/* Do more test for better stats */
for (i = 0; i < NTESTS; i++)
{
int pos = 0; /* sched_data */
/* Show progress */
perc2 = ((int64_t) i * 100) / NTESTS;
if (perc != perc2)
{
fprintf(stderr, "\r%d%%", (int) perc2);
fflush(stderr);
perc = perc2;
}
/* Add all dests */
for (n = 2; n < DESTS; n++)
{
int m, step;
/* New dest -> new step */
m = n;
if (m > MAX_STEP)
m = MAX_STEP;
step = rand() % m;
pos = (pos + step) % n;
}
/* Start pos determined */
arr[pos] ++;
}
fprintf(stderr, "\n");
for (n = 0; n < DESTS; n++)
{
printf("%d\t%d\n", n, arr[n]);
}
return 0;
}
$ gcc -Wall -O -o test test.c
Output can be saved to file and shown with gnuplot:
$ ./test > file.out
$ gnuplot
gnuplot> plot 'file.out'
What I see is that the value 128 is good but using
32 (MAX_STEP in the test) gives good enough results (3% diff).
The test shows that:
- last dests have more chance to be selected as starting point
- low value for MAX_STEP causes higher difference in probability
between first and last dests
Our goal is to select lower value for MAX_STEP that
provides probability difference that is low enough.
Regards
--
Julian Anastasov <ja@xxxxxx>
