가능하면 mod 연산자를 사용하지 않는 것이 좋습니까?
적어도 단순한 산술 테스트(예를 들어 숫자가 배열의 길이를 초과하는지 확인하는 것)와 비교하면, 숫자의 계수를 계산하는 것은 다소 비용이 드는 작업이라고 생각합니다.이 경우, 예를 들어 다음 코드를 교체하는 것이 더 효율적인가?
res = array[(i + 1) % len];
다음과 같이요?:
res = array[(i + 1 == len) ? 0 : i + 1];
첫 번째 것이 눈에 더 좋지만, 두 번째 것이 더 효율적일까 하는 생각이 듭니다.그렇다면 컴파일된 언어를 사용할 때 최적화 컴파일러가 첫 번째 스니펫을 두 번째 스니펫으로 대체할 것으로 예상할 수 있습니까?
이 「모든 하는 것은 아닙니다(이 「라고 하는 것은, 「최적화」라고 하는 것은 ).i+1len를 참조해 주세요.
저의 일반적인 조언은 다음과 같습니다.보기 좋은 버전을 사용하여 시스템 전체를 프로파일합니다.프로파일러가 병목현상으로 플래그를 표시하는 코드 부분만 최적화하십시오.모듈로 오퍼레이터는 그들 사이에 없을 거라고 장담합니다.
구체적인 예에 대해서는 벤치마크만으로 특정 컴파일러를 사용하여 특정 아키텍처에서 어떤 것이 더 빠른지 알 수 있습니다.modulo를 브랜칭으로 대체할 가능성이 있으며, 어느 쪽이 더 빠를지는 분명하지 않습니다.
간단한 측정:
#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);
}
또는 중 하나를 하여 컴파일합니다.-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 사용, 인텔 Core i5-4690K @ 3.50GHz, 64비트 Linux)
이는 비교 버전을 사용하는 것이 좋을 수 있음을 의미합니다.
"modulo 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
그래서 "어쨌든 (현대) 컴파일러가 당신보다 일을 더 잘 한다"는 것은 항상 사실이 아니다.
Interestingly, the same experiment with 4 instead of 3 leads to a and-masking for the first function
addl $1, %edi
movl %edi, %edx
sarl $31, %edx
shrl $30, %edx
leal (%rdi,%rdx), %eax
andl $3, %eax
subl %edx, %eax
ret
but it is still, and by large, inferior to the second version.
Being more explicit about proper ways to do the things
int next3(int n) {
return (n + 1) & 3;;
}
yields much better results :
leal 1(%rdi), %eax
andl $3, %eax
ret
(*) well, not that complicated. Multiplication by reciprocical. Compute the integer constant K = (2^N)/3, for some large enough value of N. Now, when you want the value of X/3, instead of a division by 3, compute X*K, and shift it N positions to the right.
Here is some additional benchmark. Note that I also added a branchless version:
#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;
}
And here is the output on my i7-4870HQ
$ 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%다른 두 가지 방법은 매우 복잡할 수 있지만 간단할 것입니다.
I would like to stress this very much underrated comment:
if len is a compile-time constant a recent GCC compiler (with -02) is usually doing clever things, often avoiding the modulus machine instruction of the target processor. – Basile Starynkevitch
예를 들어 루프를 제거함으로써sizevariable로 선언합니다.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)
Conclusions
브런치리스 버전의 실행 시간은 다양한 시나리오에서 매우 안정적입니다.삼항은 특히 분기 예측 변수가 작용한 경우 고려된 경우에서 분기 없는 경우보다 일관되게 좋습니다.마지막으로,operator%는 보다 일반적이고 현저하게 느리지만 우측의 특정 const 값의 경우와 같이 최단속도가 되도록 최적화될 가능성이 있습니다.
Of course this is completely platform dependent, who knows how this will be on an Arduino :)
If 'len' in your code is big enough, then the conditional will be faster, as the branch predictors will nearly always guess correctly.
If not, then I believe this is closely connected to circular queues, where it is often the case that the length is a power of 2. This will enable the compiler to substitute modulo with a simple 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);
}
크기=15:
- 모듈로: 4,868s
- 상태: 1,291초
크기=16:
- 모듈로: 1,067초
- 상태: 1,599s
gcc 7.3.0으로 컴파일되어 있으며 -O3 최적화로 되어 있습니다.이 기계는 i7 920입니다.
나는 빠른 해시맵을 만드는 기사를 읽었다.병넥은 해시 버킷을 찾는 계수 연산자가 될 수 있습니다.이들은 버킷 수를 2의 거듭제곱으로 만들 것을 제안했습니다.마지막 n비트를 보는 것처럼 두 가지 수단의 거듭제곱으로 계수를 계산하는 것 같습니다.
모듈로 연산자는 비싸지만 분할도 비싸다.따라서 modulo 연산자를 사용하여 코드를 나눗셈으로 변환하는 것은 코드를 최적화할 수 없습니다.
(i + 1) % len
위의 코드를 최적화하려면
if ((i+1)==len){
return 0
} else {
return i+1
}
모듈로는 대부분의 아키텍처에서 단일 프로세서 명령으로 실행할 수 있습니다(예:DIV(x86).그러나 필요한 것을 최적화하기에는 너무 이르다고 할 수 있습니다.
언급URL : https://stackoverflow.com/questions/15596318/is-it-better-to-avoid-using-the-mod-operator-when-possible
'programing' 카테고리의 다른 글
| C와 C++는 왜 (int) + 4*5 식을 사용할 수 있습니까? (0) | 2022.08.09 |
|---|---|
| vuex-pathify make.display를 사용한 스토어 액션을 사용한 서브커밋 쓰기 커밋 (0) | 2022.08.09 |
| 로컬 검색 v-data-table Vuetify (0) | 2022.08.09 |
| 포장된 구조물은 휴대 가능합니까? (0) | 2022.08.09 |
| Vue + VUEX + 타입 스크립트 + Vue 라우터컴포넌트가 파괴되지 않음 (0) | 2022.08.09 |