比 % 运算符更快的可除性测试？

Question

我在电脑上注意到一件奇怪的事情。^* 手写整除测试比 % 运算符快得多。考虑最小的例子：

^{*_{AMD 锐龙 Threadripper 2990WX，GCC 9.2.0}}

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

示例受限于奇数a和m > 0。但是，它可以很容易地推广到所有 a 和 m。该代码只是将除法转换为一系列加法。

现在考虑用-std=c99 -march=native -O3编译的测试程序：

    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m = 1; m < 100000; m += 1) {
#if 1
            volatile int r = divisible_ui_p(m, a);
#else
            volatile int r = (m % a == 0);
#endif
        }
    }

...我电脑上的结果：

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.52user |
| builtin % operator |   17.61user |

因此快了 2 倍多。

问题：你能告诉我代码在你的机器上的表现如何吗？它是否错过了 GCC 中的优化机会？你能更快地完成这个测试吗？

更新： 根据要求，这是一个最小的可重现示例：

#include <assert.h>

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

int main()
{
    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m = 1; m < 100000; m += 1) {
            assert(divisible_ui_p(m, a) == (m % a == 0));
#if 1
            volatile int r = divisible_ui_p(m, a);
#else
            volatile int r = (m % a == 0);
#endif
        }
    }

    return 0;
}

在 AMD Ryzen Threadripper 2990WX 上用 gcc -std=c99 -march=native -O3 -DNDEBUG 编译

gcc --version
gcc (Gentoo 9.2.0-r2 p3) 9.2.0

UPDATE2: 根据要求，可以处理任何 a 和 m 的版本（如果你也想避免整数溢出，测试有以两倍于输入整数的整数类型实现）：

int divisible_ui_p(unsigned int m, unsigned int a)
{
#if 1
    /* handles even a */
    int alpha = __builtin_ctz(a);

    if (alpha) {
        if (__builtin_ctz(m) < alpha) {
            return 0;
        }

        a >>= alpha;
    }
#endif

    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

#if 1
    /* ensures that 0 is divisible by anything */
    if (m == 0) {
        return 1;
    }
#endif

    return 0;
}

Answer 1

你在做的事情叫做强度缩减：用一系列便宜的操作代替昂贵的操作。

许多 CPUs 上的 mod 指令很慢，因为它在历史上没有在几个常见的基准测试中进行测试，因此设计者优化了其他指令。如果必须进行多次迭代，该算法的性能会更差，而 % 在只需要两个时钟周期的 CPU 上性能会更好。

最后，请注意，有许多快捷方式可以通过特定常数取余数。（虽然编译器通常会为您处理这个问题。）

Answer 2

我会自己回答我的问题。看来我成了分支预测的牺牲品了。操作数的相互大小似乎并不重要，重要的是它们的顺序。

考虑以下实现

int divisible_ui_p(unsigned int m, unsigned int a)
{
    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

    return 0;
}

和数组

unsigned int A[100000/2];
unsigned int M[100000-1];

for (unsigned int a = 1; a < 100000; a += 2) {
    A[a/2] = a;
}
for (unsigned int m = 1; m < 100000; m += 1) {
    M[m-1] = m;
}

哪些是 / 未使用 shuffle 函数打乱顺序。

没有洗牌，结果还是

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.56user |
| builtin % operator |   17.59user |

但是，一旦我对这些数组进行洗牌，结果就不同了[=15=]

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |   31.34user |
| builtin % operator |   17.53user |

比 % 运算符更快的可除性测试？

Faster divisibility test than % operator?

c

math

x86

modulo

compiler-optimization