계수의 수학적 개념이 어떻게 작동하는지 또는 20 % 3 == 2이 문제를 잘 이해하는지 묻지 않습니다. 컴파일러 / 인터프리터가 이것을 어떻게 결정하는지 더 궁금합니다. 다음과 같이 매우 순진한 방법을 생각할 수 있습니다.
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (분명히 이것은 a가 b보다 작을 수 있기 때문에 몇 가지 케이스가 더 필요하지만 아이디어를 얻을 수 있습니다.) 그러나 이것은 심각한 성능 문제가있을 것입니다. 두 모듈러스의 효율성을 테스트하기 위해 C ++를 함께 사용했습니다. 연산자와 내 순진한 함수입니다.
#include <iostream> #include <chrono> #include <limits> #include "chrono_io" using namespace std; typedef chrono::high_resolution_clock Clock; int mod(int a, int b) { while (a > b) { a -= b; } return a; } int main() { auto start = Clock::now(); cout << 20 % 3 << endl; auto end = Clock::now(); cout << "Modulus on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << numeric_limits<int>::max() % 3 << endl; end = Clock::now(); cout << "Modulus on a large number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(20, 3) << endl; end = Clock::now(); cout << "My modulus function on a small number took " << end - start << " seconds to calculate.\n"; start = Clock::now(); cout << mod(numeric_limits<int>::max(), 3) << endl; end = Clock::now(); cout << "My modulus function on a large number took " << end - start << " seconds to calculate.\n"; } 출력은 다음과 같습니다.
2 Modulus on a small number took 43629 nanoseconds seconds to calculate. 1 Modulus on a large number took 5644 nanoseconds seconds to calculate. 2 My modulus function on a small number took 3682 nanoseconds seconds to calculate. 1 My modulus function on a large number took 2153824554 nanoseconds seconds to calculate. 모듈러스 연산자는 4,000-70,000 나노초로 다양했습니다. 내 함수는 항상 작은 숫자에서 이겼지 만 큰 숫자에서는 약 2 초가 걸렸습니다. 모듈러스 연산자가 훨씬 더 일관 적이기 때문에 비트 수준에서 숫자를 비교한다고 가정합니다.
그러면 모듈러스 연산자가 어떻게 동작 합니까? 결정하기 쉬운 몇 가지 경우를 생각할 수 있습니다. 예를 들어, 모드 2를 사용하면 마지막 바이트. 또는 모드 4를 사용하면 두 번째에서 마지막 b까지 볼 수 있습니다. yte. 그러나 모든 숫자가 그렇게 단순한 패턴을 가지고있는 것은 아닙니다.
댓글
답변
거의 모든 CPU에는 값의 계수를 반환하는 단일 명령이 있습니다. 예를 들어 다음 프로그램을 고려해보십시오.
int main() { int i = 10; return i % 3; } g ++ -S를 사용하여 Intel OS X 컴퓨터에서 컴파일하면 결과는 몇 가지 상용구와 다음과 같습니다.
movl $3, %eax movl $0, -4(%rbp) movl $10, -8(%rbp) movl -8(%rbp), %ecx movl %eax, -12(%rbp) ## 4-byte Spill movl %ecx, %eax cltd movl -12(%rbp), %ecx ## 4-byte Reload idivl %ecx movl %edx, %eax 실제 계수는 idivl %ecx 명령으로 발생합니다. 이 명령어가 실행되면 몫은 %eax에 배치되고 나머지는 %edx에 배치됩니다.
실제로 이것은 % 작업이 몇 개의 클록 사이클 만 소요된다는 것을 의미하며, 대부분은 실제로 데이터를 올바른 레지스터로 이동합니다. 또한 Intel에서는 동일한 작업이 몫과 나머지를 모두 찾습니다. 따라서 귀하의 의견과 관련하여 / 및 % 정확히 같은 시간이 걸립니다. 동일한 작업입니다. 변경되는 유일한 것은 컴파일러가 결과를 가져 오는 레지스터입니다.
지난 20 년 동안 만들어진 CPU를 사용하면 모든 기본적인 수학 연산 (sqrt 또는 cos)는 실제로 단일 기계 명령어이며 일반적으로 최대 몇 클록 사이클 만 소요됩니다.
[UPDATE]
사람들이 댓글에서 언급했듯이 올바른 타이밍에 접근하는 것을보기 위해 다음과 같이 시간이 지정된 섹션에서 출력을 제거해야합니다.
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; 그러나 타이밍의 실제 세분화가 현재 수준을 초과 할 수 있으므로 정확하지 않을 수 있습니다. 시간을하려고합니다. 대신 다음과 같이 할 수 있습니다.
int i=0; int x; auto start = Clock::now(); for(i=0;i<1000000;i++) x = i % 3; auto end = Clock::now(); cout << i << endl; 그런 다음 타이밍을 1,000,000으로 나눕니다. (이것은 할당, 비교 및 증분에 걸리는 시간을 포함하므로 약간 높을 것입니다.) 내 컴퓨터에서 이것은 5 나노초의 시간을 제공합니다.
댓글
- 정말? sqrt는 매우 느린 명령어라고 들었습니다.
- stackoverflow를 참조하세요.com / questions / 7724061 / …
- @StevenBurnap 그 대답은 2011 년의 아키텍처를 기반으로 한 것입니다. Agner Fog ' s 테이블 (적어도 매년 업데이트 됨 ), Haswell SSE2 지침 SQRTSS / SQRTPS (32 비트 부동 소수점, 23 비트의 중요도)는 지연 시간이 11 사이클이고 SQRTSD / SQRTPD (64 비트 부동)는 지연 시간이 16 사이클입니다. 이러한 지침은 정확한 것입니다. 즉, 빠른 근사 변형이 아닙니다. 실제로 오래된 아키텍처에서는 훨씬 느립니다. 또한
std::sqrt()를 호출하면 대부분의 C ++ 컴파일러에서 라이브러리 호출이 발생합니다. - 컴파일러는 특수한 경우에 강도 감소 최적화를 추가로 적용 할 수 있습니다. 예를 들어 x % 2는 특정 아키텍처에서 ' 더 빠른 경우 비트 마스크에 최적화 될 수 있습니다.
- @rwong
std:sqrt는 일반적으로 인라인되고 인라인 어셈블리를 사용합니다.하지만 ' 확인한 적이 없습니다.
IDIV명령어는 나머지도 레지스터에 저장합니다. 하드웨어 가 어떻게 작동하는지 궁금하십니까?cout <<걸리는 시간을 실제로 측정하는 타이밍입니다. 컴파일러가 ' 어쨌든 컴파일 타임에 수행하지 않았더라도 프로세서가20 % 3를 수행하는 데 걸리는 시간을 실제로 측정 할 수 있을지 의심됩니다. .