Re: [PATCH v2 3/5] math: Improve fmod

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 15/03/23 21:58, H.J. Lu wrote:
> On Wed, Mar 15, 2023 at 1:59 PM Adhemerval Zanella
> <adhemerval.zanella@linaro.org> wrote:
>>
>> This uses a new algorithm similar to already proposed earlier [1].
>> With x = mx * 2^ex and y = my * 2^ey (mx, my, ex, ey being integers),
>> the simplest implementation is:
>>
>>    mx * 2^ex == 2 * mx * 2^(ex - 1)
>>
>>    while (ex > ey)
>>      {
>>        mx *= 2;
>>        --ex;
>>        mx %= my;
>>      }
>>
>> With mx/my being mantissa of double floating pointer, on each step the
>> argument reduction can be improved 11 (which is sizeo of uint64_t minus
>> MANTISSA_WIDTH plus the signal bit):
>>
>>    while (ex > ey)
>>      {
>>        mx << 11;
>>        ex -= 11;
>>        mx %= my;
>>      }  */
>>
>> The implementation uses builtin clz and ctz, along with shifts to
>> convert hx/hy back to doubles.  Different than the original patch,
>> this path assume modulo/divide operation is slow, so use multiplication
>> with invert values.
>>
>> I see the following performance improvements using fmod benchtests
>> (result only show the 'mean' result):
>>
>>   Architecture     | Input           | master   | patch
>>   -----------------|-----------------|----------|--------
>>   x86_64 (Ryzen 9) | subnormals      | 19.1584  | 12.5049
>>   x86_64 (Ryzen 9) | normal          | 1016.51  | 296.939
>>   x86_64 (Ryzen 9) | close-exponents | 18.4428  | 16.0244
> 
> I tried it with the test in
> 
> https://sourceware.org/bugzilla/show_bug.cgi?id=30179
> 
> On Intel i7-10710U, I got
> 
> time ./sse
> 3.13user 0.00system 0:03.13elapsed 99%CPU (0avgtext+0avgdata 512maxresident)k
> 0inputs+0outputs (0major+37minor)pagefaults 0swaps
> time ./x87
> 0.24user 0.00system 0:00.24elapsed 100%CPU (0avgtext+0avgdata 512maxresident)k
> 0inputs+0outputs (0major+37minor)pagefaults 0swaps
> time ./generic
> 0.55user 0.00system 0:00.55elapsed 99%CPU (0avgtext+0avgdata 512maxresident)k
> 0inputs+0outputs (0major+37minor)pagefaults 0swaps
> 
> The new generic is still slower than x87.

I think it really depends of the underlying hardware and on the input range.
Using the benchmark from the patch set and patch 66182 [1], I see:

CPU              | Input           | patch    | 66182
-----------------|-----------------|----------|--------
Ryzen 9          | subnormals      | 12.5049  | 31.2822
Ryzen 9          | normal          | 296.939  | 592.489
Ryzen 9          | close-exponents | 16.0244  | 33.5172
E5-2640          | subnormals      | 34.5454  | 652.59
E5-2640          | normal          | 473.602  | 438.836
E5-2640          | close-exponents | 39.298   | 22.2742
i7-4510U         | subnormals      | 25.2624  | 666.964
i7-4510U         | normal          | 386.489  | 454.222
i7-4510U         | close-exponents | 29.463   | 22.8572

So it seems that fprem performance is not really consistent over x86 CPUs, and 
even for recent AMD is far from great.  So I still think the generic is better
for x86, and I think fprem should be used along with ifunc to select on CPUs
that really yields better numbers (and take in consideration that subnormals
numbers seems to be pretty bad).

You might get better x86 performance by remove the SVID wrapper as I did
on the last patch; but it will increase 66182 complexity (you will need to
check for NaN/INF/0.0 and set errno).  And I hardly think it will close the
gap on the AMD chip I use.

I am also checking a algorithm change to use simple loop for the normal inputs,
where integer modulo operation is used instead of inverse multiplication. 
But as far I am testing performance is really bad on all x86 Intel chips I 
tests (it is not as bad on AMD).

[1] https://patchwork.sourceware.org/project/glibc/patch/20230309183312.205763-1-hjl.tools@gmail.com/