[PATCH v3 2/4] hash: add dynamic polynomial calculation

[Medvedkin, Vladimir]

Hi Stephen,

On 17/10/2024 04:23, Stephen Hemminger wrote:
> On Wed, 16 Oct 2024 17:28:17 +0100
> "Medvedkin, Vladimir"<vladimir.medvedkin at intel.com>  wrote:
>
>> Hi Stephen,
>>
>> On 15/10/2024 23:29, Stephen Hemminger wrote:
>>> On Fri, 11 Oct 2024 18:17:00 +0000
>>> Vladimir Medvedkin<vladimir.medvedkin at intel.com>   wrote:
>>>   
>>>> +
>>>> +uint32_t
>>>> +rte_thash_get_rand_poly(uint32_t poly_degree)
>>>> +{
>>>> +	uint32_t ret_poly;
>>>> +
>>>> +	if (poly_degree > 32)
> Error log here?
>
>>>> +		return 0;
>>>> +
>>>> +	do
>>>> +		ret_poly = __thash_get_rand_poly(poly_degree);
>>>> +	while (thash_test_poly_order(ret_poly, poly_degree));
>>> Unbounded loop adds some risk, should there be an upper limit on retries.
>> Thisis the probabilisticpartof the algorithm.
>>
>> __thash_get_rand_poly() returns a random polynomial that either
>> satisfies the order criteria (element <x> of the field must generate
>> multiplicative subgroup of order not less than some number), or not. The
>> probability that it does not meet this criteria is strictly less than 1.
>> Thus, with each attempt, the probability of not finding suitable
>> polynomial exponentially tends to zero.
> Never trust probabilities to converge. Just add an upper bound of something big
> like 32 tries and log error and give up.

I disagree. I don't want this to give up. Take a look at this algorithm 
from the perspective of an equivalent bounded random function:

https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171 
<https://lxr.missinglinkelectronics.com/dpdk/lib/eal/common/rte_random.c#L171>

or

https://elixir.bootlin.com/linux/v6.11.3/source/include/linux/random.h#L60

The job must be done. Imagine if these random functions may return 
something like "EAGAIN". The caller needs random value at this pointto 
continue, so there are only 2 options left - either panic or call the 
function again.

We definitely don't want to panic here. But calling this algorithm again 
will have the same effect as not having runtime bound inside the 
algorithm at all. In other words, here I prefer to have "Las Vegas" 
rather than "Monte Carlo" algorithm. And it make sense since in these 
particular cases (i.e. my algorithm and bounded random implementations) 
we have:

1. A simple deterministic algorithm for checking the complianceof 
somerandomvariablewith a condition

2. Every random variable is independent from each other. So probability 
of getting unsatisfying random variable after n steps drops 
exponentially (negative outcome probabilities multiplies). That's why 
those algorithms runtime expected value is bounded.


>
>>>   
>>>> +
>>>> +	return ret_poly;
>>>> +}
>>>> diff --git a/lib/hash/version.map b/lib/hash/version.map
>>>> index 4f13f1d5aa..7ce6ab1121 100644
>>>> --- a/lib/hash/version.map
>>>> +++ b/lib/hash/version.map
>>>> @@ -61,4 +61,5 @@ INTERNAL {
>>>>    
>>>>    	rte_thash_gfni_stub;
>>>>    	rte_thash_gfni_bulk_stub;
>>>> +	rte_thash_get_rand_poly;
>>> Why does this function need to be moved to its own file?
>>> Only used in one place in rte_thash.c.
>> It was done just for convenience. If you insist, I'll move it to rte_thash.c
>
> It is actually good to put in seperate file, but you can keep the old name.
> Best to reserve names with rte_ prefix for user visible prefixes.
>
>
-- 
Regards,
Vladimir
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mails.dpdk.org/archives/dev/attachments/20241018/2c165161/attachment.htm>