Nu mă întreb cum funcționează conceptul matematic de modul sau cum 20 % 3 == 2 înțeleg bine. Sunt „mai curios cum determină compilatorul / interpretul acest lucru. Mă pot gândi la un mod foarte naiv de a o face, așa:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (evident că mai are nevoie de câteva cazuri, deoarece a poate fi mai mic decât b, dar îți vine ideea.) Dar acest lucru ar avea unele probleme de performanță serioase. Am aruncat câteva C ++ pentru a testa eficiența ambelor module operator și funcția mea naivă.
#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"; } iar ieșirea este:
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. operatorul modulului a variat de la 4.000-70.000 nanosecunde. Funcția mea a câștigat întotdeauna pe numerele mici, dar a durat în jur de 2 secunde pe numărul mare. Deoarece operatorul modulului este mult mai consistent, presupun că compară numărul la nivel de bit.
Deci, cum funcționează operatorul de modul? Mă pot gândi la câteva cazuri care ar fi foarte ușor de determinat. De exemplu, cu mod 2, puteți doar să priviți foarte ultimul octet. Sau cu mod 4 puteți privi al doilea până la ultimul b yte. Dar nu toate numerele au un model atât de simplu.
Comentarii
Răspuns
Aproape toate procesoarele au o singură instrucțiune care va returna modulul unei valori. De exemplu, luați în considerare acest program:
int main() { int i = 10; return i % 3; } Dacă compilez acest lucru pe mașina mea Intel OS X folosind g ++ -S, rezultatul va fi o boilerplate și aceasta:
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 Modulul real se întâmplă cu această instrucțiune: idivl %ecx. Când se execută această instrucțiune, coeficientul va fi plasat în %eax, iar restul va fi plasat în %edx.
Într-adevăr, aceasta înseamnă că operațiunea % va dura doar câteva cicluri de ceas, cea mai mare parte dintre acestea mutând datele în registrul corect. De asemenea, rețineți că, cu cel puțin Intel, aceeași operație găsește atât coeficientul, cât și restul, deci, referitor la comentariul dvs., / și % ia exact în același timp. Este aceeași operație. Singurul lucru care se schimbă este din ce registru obține rezultatele compilatorului.
Cu orice procesor realizat în ultimele câteva decenii, puteți presupune că orice operație matematică de bază (inclusiv lucruri care arată ca funcții de bibliotecă precum sqrt sau cos) este de fapt o singură instrucțiune mașină și, în general, durează cel puțin câteva cicluri de ceas.
[UPDATE]
După cum au remarcat oamenii în comentarii, pentru a vedea ceva care se apropie de un moment corect, tu trebuie să eliminați ieșirea din secțiunea temporizată astfel:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Dar chiar și asta nu este probabil precis, deoarece granularitatea reală a temporizărilor poate depăși ceea ce sunteți încercând să cronometreze. În schimb, s-ar putea să doriți să faceți acest lucru:
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; Apoi împărțiți calendarul la 1.000.000. (Acest lucru va fi ușor ridicat, deoarece include timpul necesar unei sarcini, o comparație și o creștere.) Pe mașina mea, acest lucru oferă un timp de 5 nanosecunde.
Comentarii
- Chiar? Mi s-a spus că sqrt este o instrucțiune foarte lentă.
- Consultați stackoverflow.com / questions / 7724061 / …
- @StevenBurnap acel răspuns este puțin depășit, pe baza arhitecturii din anul 2011. Conform Agner Fog ‘, care este actualizată cel puțin anual , instrucțiuni Haswell SSE2 SQRTSS / SQRTPS (32-bit float, cu 23 de biți de semnificație) are o latență de 11 cicluri, SQRTSD / SQRTPD (64-bit float) are o latență de 16 cicluri. Aceste instrucțiuni sunt cele precise, adică nu din variantele de aproximare rapidă. Este într-adevăr mult mai lent în arhitecturile mai vechi. De asemenea, rețineți că apelarea
std::sqrt()implică un apel de bibliotecă în majoritatea compilatoarelor C ++. - Compilatoarele pot aplica suplimentar optimizarea reducerii puterii pentru cazuri speciale. De exemplu, x% 2 ar putea fi optimizat pentru o mască de biți dacă ‘ este mai rapid pe o anumită arhitectură.
- @rwong aș fi crezut că
std:sqrtar fi, de obicei, înclinat (și ar folosi ansamblul inline.) Dar eu ‘ nu am verificat niciodată.
IDIV, care efectuează diviziuni întregi, stochează și restul într-un registru). Întrebați cum funcționează hardware ?cout <<majoritatea operațiunilor. Mă îndoiesc că de fapt ați putea măsura timpul necesar procesorului pentru a face20 % 3chiar dacă compilatorul nu a făcut-o oricând la timpul de compilare .