c-比%运算符更快的可分割性测试

Question

我注意到我的电脑上有一个奇怪的东西^*手写可分割性测试明显快于%算子。考虑一个最小的例子：

_{*AMD Ryzen Threadipper 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;
}

用gcc -std=c99 -march=native -O3 -DNDEBUG在AMD Ryzen Threadipper 2990WX上编译，带有

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

您所做的叫做强度降低：用一系列廉价的操作取代昂贵的操作。

许多CPU上的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;
}

其使用混洗功能进行混洗。

没有混洗，结果仍然是

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

然而，一旦我打乱这些数组，结果就会不同

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