Random numbers [LWN.net]

Random numbers

Posted May 14, 2020 22:57 UTC (Thu) by corbet (editor, #1)
In reply to: The weighted TEO cpuidle governor by Paf
Parent article: The weighted TEO cpuidle governor

Bear in mind that the number of sleep states is typically rather larger than the three I showed in the simplified example. If you are going to pick between four choices, each of which has a probability between, say, 18-22%, does it really make sense to always pick the highest? In a sense, this is the mechanism for tie breaking.

to post comments

Random numbers

Posted May 16, 2020 4:15 UTC (Sat) by martinfick (subscriber, #4455) [Link] (4 responses)

Wouldn't it be just as good to simply pick one randomly then without any weighting?

Random numbers

Posted May 16, 2020 13:24 UTC (Sat) by mathstuf (subscriber, #69389) [Link] (3 responses)

If you have 4 each around 20%-30%, sure. But if you have a fifth at 1%, probably not. Wouldn't it be more expensive to detect the first case and handle it specially than to just handle the general case?

Random numbers

Posted May 16, 2020 19:33 UTC (Sat) by Wol (subscriber, #4433) [Link] (2 responses)

Or just randomly select any one over average. So if you've got 8, randomly select any of those over 13%

Cheers,
Wol

Random numbers

Posted May 16, 2020 20:18 UTC (Sat) by mathstuf (subscriber, #69389) [Link] (1 responses)

That still seems to pessimize a bit too much to me. If you have all of them right around 12.5%, why use a selection algorithm that makes half (on average) effectively 0%? Instead of introducing a divide for your average, just track the sum, make a random number within [0, sum) (any other scheme is likely to have something here anyways to get a number within your domain), then subtract off each bucket's size until you get a value < 0 and you've found your selection. Tracking is then just counting into each bucket and the sum and you reweight to avoid overflows every so often. Reweighting after each measurement seems excessively expensive.

Random numbers

Posted May 16, 2020 22:30 UTC (Sat) by Wol (subscriber, #4433) [Link]

If your scheme is quicker than mine at doing the calculation, then fine. I was just thinking that less than half the choices would be above average (and the more widely spread the scores are, the smaller the above-average proportion). So if you want one of the high-rankers, at random, just grabbing anything above average isn't a bad way of doing it.

Cheers,
Wol