Re: [RFC PATCH v1 09/50] <linux/random.h> prandom_u32_max() for power-of-2 ranges

[Stephen Hemminger <stephen@networkplumber.org>]

On Sat, 16 Mar 2019 02:32:04 -0400
George Spelvin <lkml@sdf.org> wrote:

> +static inline u32 prandom_u32_max(u32 range)
>  {
> -	return (u32)(((u64) prandom_u32() * ep_ro) >> 32);
> +	/*
> +	 * If the range is a compile-time constant power of 2, then use
> +	 * a simple shift.  This is mathematically equivalent to the
> +	 * multiplication, but GCC 8.3 doesn't optimize that perfectly.
> +	 *
> +	 * We could do an AND with a mask, but
> +	 * 1) The shift is the same speed on a decent CPU,
> +	 * 2) It's generally smaller code (smaller immediate), and
> +	 * 3) Many PRNGs have trouble with their low-order bits;
> +	 *    using the msbits is generaly preferred.
> +	 */
> +	if (__builtin_constant_p(range) && (range & (range - 1)) == 0)
> +		return prandom_u32() / (u32)(0x100000000 / range);
> +	else
> +		return reciprocal_scale(prandom_u32(), range);


The optimization is good, but I don't thin that the compiler
is able to propogate the constant property into the function.
Did you actually check the generated code.