C语言 是否最好尽可能避免使用mod运算符?

0md85ypi  于 2023-10-16  发布在  其他
关注(0)|答案(9)|浏览(176)

我假设计算一个数字的模是一个有点昂贵的操作,至少与简单的算术测试(例如查看一个数字是否超过数组的长度)相比。如果确实是这样,那么替换例如以下代码是否更有效:

res = array[(i + 1) % len];

与以下?:

res = array[(i + 1 == len) ? 0 : i + 1];

第一个更容易看,但我想知道第二个是否更有效。如果是这样的话,我是否可以期望一个优化编译器在使用编译语言时用第二个代码片段替换第一个代码片段?
当然,这种“优化”(如果它确实是一种优化)并不是在所有情况下都有效(在这种情况下,它只在i+1永远不会大于len时有效)。

nafvub8i

nafvub8i1#

我的一般建议如下。使用您认为更美观的版本,然后分析整个系统。只优化分析器标记为瓶颈的代码部分。我敢打赌,模运算符不会在其中。
就具体的例子而言,只有基准测试才能告诉你,在你的特定架构上,使用你的特定编译器,哪一个更快。你可能会用branching代替modulo,但很明显哪一个更快。

fzsnzjdm

fzsnzjdm2#

一些简单的测量:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int test = atoi(argv[1]);
    int divisor = atoi(argv[2]);
    int iterations = atoi(argv[3]);

    int a = 0;

    if (test == 0) {
        for (int i = 0; i < iterations; i++)
            a = (a + 1) % divisor;
    } else if (test == 1) {
        for (int i = 0; i < iterations; i++)
            a = a + 1 == divisor ? 0 : a + 1;
    }

    printf("%d\n", a);
}

使用gcc或clang和-O3编译,并运行time ./a.out 0 42 1000000000(模版本)或time ./a.out 1 42 1000000000(比较版本),结果如下:

*6.25秒用户运行时间为模数版本,
*对比版本为1.03秒

(使用gcc 5.2.1或clang 3.6.2;英特尔酷睿i5- 4690K@3.50GHz; 64位Linux)
这意味着使用比较版本可能是一个好主意。

ewm0tg9j

ewm0tg9j3#

那么,看看2种方法来获得“模3”循环计数器的下一个值。

int next1(int n) {
    return (n + 1) % 3;
}

int next2(int n) {
    return n == 2 ? 0 : n + 1;
}

我使用gcc -O3选项(用于通用的x64架构)和-s来编译它,以获取汇编代码。
第一个函数的代码做了一些无法解释的魔术(*)来避免除法,无论如何都使用乘法:

addl    $1, %edi
movl    $1431655766, %edx
movl    %edi, %eax
imull   %edx
movl    %edi, %eax
sarl    $31, %eax
subl    %eax, %edx
leal    (%rdx,%rdx,2), %eax
subl    %eax, %edi
movl    %edi, %eax
ret

并且比第二个函数长得多(我敢打赌慢得多):

leal    1(%rdi), %eax
cmpl    $2, %edi
movl    $0, %edx
cmove   %edx, %eax
ret

因此,“(现代)编译器无论如何都比你做得更好”并不总是正确的。
有趣的是,用4代替3的相同实验导致第一个函数的与掩码

addl    $1, %edi
movl    %edi, %edx
sarl    $31, %edx
shrl    $30, %edx
leal    (%rdi,%rdx), %eax
andl    $3, %eax
subl    %edx, %eax
ret

但总的来说,它仍然不如第二个版本。
更明确地说明正确的做事方法

int next3(int n) {
    return (n + 1) & 3;;
}

产生更好的结果:

leal    1(%rdi), %eax
andl    $3, %eax
ret

)好吧,没那么复杂。乘以倒数。计算整数常数K =(2^N)/3,对于N的某个足够大的值。现在,当你想要X/3的值时,而不是除以3,计算XK,并将其向右移动N个位置。

xdyibdwo

xdyibdwo4#

如果代码中的“len”足够大,那么条件语句会更快,因为分支预测器几乎总是能正确猜测。
如果不是,那么我相信这与循环队列密切相关,在循环队列中,长度通常是2的幂。这将使编译器能够用一个简单的AND代替模。
代码如下:

#include <stdio.h>
#include <stdlib.h>

#define modulo

int main()
{
    int iterations = 1000000000;
    int size = 16;
    int a[size];
    unsigned long long res = 0;
    int i, j;

    for (i=0;i<size;i++)
        a[i] = i;

    for (i=0,j=0;i<iterations;i++)
    {
        j++;
        #ifdef modulo
            j %= size;
        #else
            if (j >= size)
                j = 0;
        #endif
        res += a[j];
    }

    printf("%llu\n", res);
}

size=15:

  • 模数:4,868秒
  • 第二:1,291秒

size=16:

  • 模数:1,067秒
  • 第二:1,599秒

在gcc 7.3.0中编译,使用-O3优化。这台机器是i7 920。

f8rj6qna

f8rj6qna5#

这里有一些额外的基准。请注意,我还添加了一个无分支版本:

#include <iostream>
#include <array>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std::chrono;

constexpr size_t iter = 1e8;

int main() {
  std::minstd_rand rnd_engine{1234};
  std::uniform_int_distribution<int> dist {-1000, 1000};
  auto gen = [&]() { return dist(rnd_engine); };

  std::array<int, 10> a;
  std::generate( a.begin(), a.end(), gen);

  for (size_t size = 2; size < 10; size++) {
    std::cout << "Modulus size = " << size << '\n';
  
    {
      std::cout << "operator%  ";
      long sum = 0;
      size_t x = 0;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x];
        x = (x + 1) % size;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }
  
    {
      std::cout << "ternary    ";
      long sum = 0;
      size_t x = 0;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x];
        x = ((x + 1) == size) ? 0 : x + 1;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }
    
    {
      std::cout << "branchless ";
      long sum = 0;
      size_t x = 1;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x-1];
        x = ( x != size ) * x + 1;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }

  }
  return 0;
}

这是我的i7- 4870 HQ的输出

$ g++ -Ofast test.cpp && ./a.out
Modulus size = 2
operator%  904.249ms    (sum = -4200000000)
ternary    137.04ms     (sum = -4200000000)
branchless 169.182ms    (sum = -4200000000)
Modulus size = 3
operator%  914.911ms    (sum = -31533333963)
ternary    113.384ms    (sum = -31533333963)
branchless 167.614ms    (sum = -31533333963)
Modulus size = 4
operator%  877.3ms      (sum = -36250000000)
ternary    97.265ms     (sum = -36250000000)
branchless 167.215ms    (sum = -36250000000)
Modulus size = 5
operator%  891.295ms    (sum = -30700000000)
ternary    88.562ms     (sum = -30700000000)
branchless 167.087ms    (sum = -30700000000)
Modulus size = 6
operator%  903.644ms    (sum = -39683333196)
ternary    83.433ms     (sum = -39683333196)
branchless 167.778ms    (sum = -39683333196)
Modulus size = 7
operator%  908.096ms    (sum = -34585713678)
ternary    79.703ms     (sum = -34585713678)
branchless 166.849ms    (sum = -34585713678)
Modulus size = 8
operator%  869ms        (sum = -39212500000)
ternary    76.972ms     (sum = -39212500000)
branchless 167.29ms     (sum = -39212500000)
Modulus size = 9
operator%  875.003ms    (sum = -36500000580)
ternary    75.011ms     (sum = -36500000580)
branchless 172.356ms    (sum = -36500000580)

在这种特殊情况下,三元运算符看起来要上级得多,当分支预测器上升时,它变得更加优越。但请注意,这是一个非常特殊的情况:如果我们不通过非常量值递增索引,使用更通用的operator%将是简单的,而其他两种方法可能会变得非常复杂。
我想强调一下这个被低估的评论:

  • 如果len是一个编译时常量,最近的GCC编译器(使用-02)通常会做一些聪明的事情,通常会避免目标处理器的模数机**指令。

例如,通过删除size变量上的循环并将其声明为const size_t size = 4;,我得到:

g++ -Ofast test.cpp && ./a.out
Modulus size = 4
operator%  62.103ms     (sum = -36250000000)
ternary    93.674ms     (sum = -36250000000)
branchless 166.774ms    (sum = -36250000000)

结论

无分支版本的执行时间在各种场景中都非常稳定。在所考虑的情况下,三进制始终优于无分支,特别是当分支预测器启动时。最后,operator%虽然更通用,速度也更慢,但有机会得到优化,成为最快的,就像右侧的特定常量值一样。
当然,这是完全依赖于平台的,谁知道这将如何在Arduino上:)

unftdfkk

unftdfkk6#

我读了一篇关于快速哈希Map的文章。瓶颈可以是求模运算符以找到哈希桶。他们建议把你的桶数设为2的幂。显然,用2的幂求模就像看最后n位。

dddzy1tm

dddzy1tm7#

模运算代价很高,但除法运算代价也很高。因此,将代码从使用模运算符转换为除法并不会优化代码。

(i + 1) % len

优化上述代码

if ((i+1)==len){
   return 0
} else {
   return i+1
}
rta7y2nd

rta7y2nd8#

是的,如果你在循环中调用取模运算符%,它会慢得多。如果你只是叫它几倍最大值,我不会担心它。
即使在Visual Studio 2022的发布模式下,我的分析器也会将if (value % alignment != 0)语句标记为约10%的CPU使用率,这是相当大的。我能够通过使用简单的按位&来显着优化它,因为我的对齐总是2的幂:

if ((value & (alignment - 1)) != 0)

优化编译器不能确定我的对齐总是2的幂,所以编译器不允许隐式地进行优化。这是编译器不能自动帮助你的例子之一。
现在,我的分析器只显示if语句的CPU使用率为0.3%,这比直接使用%时更有效。

mefy6pfw

mefy6pfw9#

在大多数架构上,模运算可以用一条处理器指令来完成(例如,x86上的DIV)。然而,这可能是一个不成熟的优化,你需要什么。

相关问题