[PATCH] libm,ieee754:New algorithm of fmod function for, dbl-64/wordsize-64

[Kirill Okhotnikov]

On 11/19/20 3:54 PM, Adhemerval Zanella wrote:
>
> On 19/11/2020 10:28, Kirill Okhotnikov wrote:
>> I proposed a new algorithm for fmod calculations for double type and
>> wordsize-64 architectures. Algorithm description is in the file.
>> I successfully ran internal tests on x86_64 processors.
>> Also I did some extensive tests and benchmark with my own test-suite on x86_64 and ARM64. See
>> https://github.com/orex/test_fmod
>> My tests on x86_64 (Intel, AMD) and ARM64 shows that the new algorithm up to 20 times faster for
>> "extreme" cases. And up to two times faster for regular cases of using the function.
>> Also, I did some unit testing which shows that old and a new algorithms gives binary
>> equivalent result for each of billions different pairs (x, y) with wide range of numbers
>> including normal, subnormal, and special one (NaN INF, 0).
>>
>> Reply to adhemerval.zanella@linaro.org from libc-help thread.
>>
>>> I won't comment to your implementation until it is submitted to
>>> libc-alpha with proper Copyright assignment, but some remarks:
>> FSF status: In progress.
> Thanks (I think other glibc developers will only check the patch itself
> once the paper are sorted out).
>
>>>    1. If you are benchmarking on i686, it won't use the generic
>>>       sysdeps/ieee754/dbl-64/e_fmod.c but rather a asm specific
>>>       implementation (sysdeps/i386/fpu/e_fmod.S).  It would be good
>>>       if you check if we can remove the i386 assembly implementation
>>>       in favor of the generic one.
>> You can remove it of course, but in favour to generic implementation, but I assume, you will get a strong performance degradation. It is worth to check it. I don't have a i686 machine. I don't know how relevant will be tests on my CPU.
> You can check the i686 performance on a x86_64 machine, the idea is to see
> if this resulting performance and depending of the result we might
> remove the assembly implementation.

I've checked i686 approach. It is simple FPU call, which is quite 
efficient. I did an extra checks on i5 machine with my function vs 
internal one (64 bit version) vs FPU one. The approximate rates are (FPU 
performance/my function performance) ( test details on github):

Main test: ~2.5x (FPU 2.5 times better).
Wrap 2pi: ~0.75x (proposed 25% better).
Wrap 1.0: 1.75x
Extreme cases: 0.55x

Although proposed function is better on (from my point of view) most 
frequent cases (wrap pi). It is still debateable which function should 
be used for x86_64: FPU or proposed one.

>
>>>    2. __builtin_clz might be a libcall on some targets, which might
>>>       be worse than using the loop.  It is usually not an issue on
>>>       some implementation (it is used on some float128 which is
>>>       usually soft implementation anyway), but it is something to
>>>       keep in mind.
>> I check the code of libm. The function is already used (except ldbl-128) in
>>
>> sysdeps/ieee754/flt-32/s_logbf.c:      rix -= __builtin_clz (ix) - 9;
>> sysdeps/ieee754/dbl-64/s_logb.c:      int m = __builtin_clzll (ix);
>>
>> The second thing is that loop is not efficient anyhow. There is more efficient approach with table (for CLZ and CTZ).
>>
>> https://www.geeksforgeeks.org/count-trailing-zero-bits-using-lookup-table/
>>
>> Probably it is already implemented in GCC?
> It really depends of the architecture, the stdlib/longlong.h has both
> count_trailing_zeros/count_trailing_zeros which should either call
> the __builtin_clzll/__builtin_ctzll or an optimized version without
> a libgcc libcall.
>
> The libgcc also has multiple optimized version depending of the
> architecture, and the generic one does use a lookup table afaik.
>
>>>    3. It would be good if could get rid of the wordsize-64
>>>       implementation and just have a generic one good enough regardless
>>>       of word size.
>> I can't imagine such algorithm. The size of double is 64 bit. Splitting it over two 32 bits variable, of course, will have a performance impact. Algorithm, proposed by me (see description), can work strictly with 64 bits variables.
> The question is whether using the 64-bit variable version yields
> enough good performance on 32-bit architecture so we can have only
> 1 implementation instead of multiple ones.  It would incur in less
> maintainability effort and a simple code base.

I compiled and ran 32 bit program on my computer. I used docker, it 
should not change performance significantly. So, I got a performance 
degradation compare to internal function by on average 1.5 times.

Best,
Kirill.