C语言 对于整数模计算,fmod是否比%快

ttcibm8c  于 2023-03-07  发布在  其他
关注(0)|答案(4)|浏览(174)

刚刚在一些旧的源代码中发现了下面的行:

int e = (int)fmod(matrix[i], n);

其中matrixint的数组,nsize_t
我想知道为什么使用fmod而不是%,这里我们有整数参数,也就是说,为什么不:

int e = (matrix[i]) % n;

选择fmod而不是%可能有性能方面的原因,还是仅仅是一段奇怪的代码?

x4shl7ld

x4shl7ld1#

选择fmod而不是%可能有性能方面的原因,还是仅仅是一段奇怪的代码?
fmod在具有高延迟IDIV指令的架构上可能会快一点,这需要(比如)大约50个周期或更多,因此fmod的函数调用和int <---> double转换成本可以分摊。
根据Agner's Fog instruction tablesIDIV在AMD K10架构上需要24-55个时钟周期,与现代Intel Haswell相比,其延迟范围被列为22-29个时钟周期,但如果没有依赖链,相反的吞吐量在Intel上要好得多,为8-11个时钟周期。

628mspwn

628mspwn2#

fmod可能比所选体系结构上的整数除法快一点点。
然而注意,如果n在编译时具有已知的非零值,则matrix[i] % n将被编译为具有小调整的乘法,这应当比整数模数和浮点模数快得多。
另一个有趣的区别是n == 0INT_MIN % -1上的行为。整数模运算调用未定义的溢出行为,这在许多当前架构上导致异常程序终止。相反,浮点模没有这些极端情况,结果是+Infinity-InfinityNan取决于matrix[i]-INT_MIN的值,所有这些值都超过int的范围,并且转换回int是实现定义的,但通常不会导致异常程序终止。这可能是最初的程序员选择这个令人惊讶的解决方案的原因。

xlpyo6sf

xlpyo6sf3#

从实验上看(与直觉相反),fmod%快--至少在 * AMD Phenom(tm)II X4 955上是这样,它具有6400 bogomips *。下面是两个使用其中一种技术的程序,都使用相同的编译器(GCC)和相同的选项(cc -O3 foo.c -lm)编译,并且运行在相同的硬件上:

#include <math.h>
#include <stdio.h>

int main()
{
    int volatile a=10,b=12;
    int i, sum = 0;
    for (i = 0; i < 1000000000; i++)
        sum += a % b;
    printf("%d\n", sum);
    return 0;
}

运行时间:九点零七秒。

#include <math.h>
#include <stdio.h>

int main()
{
    int volatile a=10,b=12;
    int i, sum = 0;
    for (i = 0; i < 1000000000; i++)
        sum += (int)fmod(a, b);
    printf("%d\n", sum);
    return 0;
}

运行时间:8.04秒

q5lcpyga

q5lcpyga4#

fmod()肯定总是比整数除法慢,因为减法和移位操作不在硬件中。下面的代码显示了我的fmod()实现:

#include <stdint.h>
#include <string.h>
#include <fenv.h>
#if defined(_MSC_VER)
    #include <intrin.h>
#endif

#if defined(__clang__)
    #pragma clang diagnostic ignored "-Wdangling-else"
    #pragma clang diagnostic ignored "-Wbitwise-op-parentheses"
    #pragma clang diagnostic ignored "-Wlogical-op-parentheses"
#endif

#if defined(__GNUC__) || defined(__llvm__)
    #define likely(x) __builtin_expect((x), 1)
    #define unlikely(x) __builtin_expect((x), 0)
#else
    #define likely(x) (x)
    #define unlikely(x) (x)
#endif

#define MAX_EXP (0x7FF)
#define SIGN_BIT ((uint64_t)1 << 63)
#define EXP_MASK ((uint64_t)MAX_EXP << 52)
#define IMPLCIT_BIT ((uint64_t)1 << 52)
#define MANT_MASK (IMPLCIT_BIT - 1)
#define QNAN_BIT (IMPLCIT_BIT >> 1)

#define IS_ZERO(b) (!(b & ~SIGN_BIT))
#define HAS_MAX_EXP(b) ((b & EXP_MASK) == EXP_MASK)
#define HAS_INF_MANT(b) (!(b & MANT_MASK))
#define IS_NON_NAN(b) (!HAS_MAX_EXP(b) || HAS_MAX_EXP(b) && HAS_INF_MANT(b))

inline uint64_t bin( double d )
{
    uint64_t u;
    memcpy( &u, &d, sizeof d );
    return u;
}

inline double dbl( uint64_t u )
{
    double d;
    memcpy( &d, &u, sizeof u );
    return d;
}

inline double NaN( int raise )
{
    if( raise )
        feraiseexcept( FE_INVALID );
    return dbl( SIGN_BIT | EXP_MASK | QNAN_BIT );
}

inline void normalize( uint64_t *mant, int *exp )
{
#if defined(__GNUC__) || defined(__llvm__)
    unsigned bits = __builtin_clzll( *mant ) - 11;
    *mant <<= bits;
#elif defined(_MSC_VER)
    unsigned long bits;
    #if defined(_M_X64)
    _BitScanReverse64( &bits, *mant );
    #elif defined(_M_IX86)
    if( likely(*mant >> 32) ) 
        _BitScanReverse( &bits, (uint32_t)(*mant >> 32) ),
        bits += 32;
    else
        _BitScanReverse( &bits, (uint32_t)*mant );
    #endif
    bits = (bits ^ 63) - 11;
    *mant <<= bits;
#else
    unsigned bits = 0;
    for( ; !(*mant & IMPLCIT_BIT); *mant <<= 1, ++bits );
#endif
    *exp -= bits;
}

#if defined(__cplusplus)
extern "C"
#endif
double myFmodC( double counter, double denominator )
{
    uint64_t const
        bCounter = bin( counter ),
        bDenom = bin( denominator );
    if( unlikely(IS_ZERO(bCounter)) )
        // +/-0.0 % ...
        if( likely(!IS_ZERO(bDenom)) )
            // +/-0.0 % non-zero = +/-0.0
            return counter;
        else
            // +/-0.0 % +/-0.0 = raised-NaN
            return NaN( 1 );
    if( unlikely(HAS_MAX_EXP(bCounter)) )
        // [Inf|QNaN|SNaN] % ...
        if( likely(HAS_INF_MANT(bCounter)) )
            // Inf % ...
            if( likely(IS_NON_NAN(bDenom)) )
                // Inf % non-NaN = raised-NaN
                return NaN( 0 );
            else
                // Inf % NaN = NaN
                return NaN( 0 );
        else
            // NaN % ... = NaN = NaN
            return NaN( 0 );
    if( unlikely(IS_ZERO(bDenom)) )
        // ... % +/-0.0
        if( likely(IS_NON_NAN(bCounter)) )
            // non-NaN % +/-0.0 = raised-NaN
            return NaN( 1 );
        else
            // NaN % +/-0.0 = NaN
            return NaN( 0 );
    if( unlikely(HAS_MAX_EXP(bDenom)) )
        // ... % [Inf|NaN|SNan]
        if( likely(HAS_INF_MANT(bDenom)) )
            // ... % Inf
            if( likely(!HAS_MAX_EXP(bCounter)) )
                // real % Inf = real
                return counter;
            else
                // [Inf|NaN|SNan] % Inf = NaN
                return NaN( 0 );
        else
            // ... % NaN = NaN
            return NaN( 0 );
    int
        counterExp = bCounter >> 52 & MAX_EXP,
        denomExp = bDenom >> 52 & MAX_EXP;
    uint64_t
        counterMant = (uint64_t)(counterExp != 0) << 52 | bCounter & MANT_MASK,
        denomMant = (uint64_t)(denomExp != 0) << 52 | bDenom & MANT_MASK;
    if( unlikely(!counterExp) )
        // normalize counter
        normalize( &counterMant, &counterExp ),
        ++counterExp;
    if( unlikely(!denomExp) )
        // normalize denominator
        normalize( &denomMant, &denomExp ),
        ++denomExp;
    int remExp = counterExp;
    uint64_t remMant = counterMant;
    for( ; ; )
    {
        int below = remMant < denomMant;
        if( unlikely(remExp - below < denomExp) )
            break;
        remExp -= below;
        remMant <<= below;
        if( unlikely(!(remMant -= denomMant)) )
        {
            remExp = 0;
            break;
        }
        normalize( &remMant, &remExp );
    };
    if( unlikely(remExp <= 0) )
        // denormal result
        remMant >>= -remExp + 1,
        remExp = 0;
    return dbl( bCounter & SIGN_BIT | (uint64_t)remExp << 52 | remMant & MANT_MASK );
}

你真的认为这个比我电脑上的glibc快100%到150%的代码可以和硬连线的div-instruction竞争吗?

相关问题