Jeg spør ikke om hvordan det matematiske begrepet modulus fungerer, eller hvordan 20 % 3 == 2 Jeg forstår denne fine. Jeg er mer nysgjerrig på hvordan kompilatoren / tolk bestemmer dette. Jeg kan tenke meg en veldig naiv måte å gjøre det på, slik:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (tydeligvis trenger dette noen flere tilfeller fordi a kan være mindre enn b, men du får ideen.) Men dette ville ha noen alvorlige ytelsesproblemer. Jeg kastet sammen noen C ++ for å teste effektiviteten til begge modulene operatør og min naive funksjon.
#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"; } og utgangen er:
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. moduloperatøren varierte fra 4.000-70.000 nanosekunder. Funksjonen min vant alltid på de små tallene, men tok rundt 2 sekunder på det store tallet. Siden moduloperatøren er så mye mer konsistent, antar jeg at den sammenligner tallet på et bitvis nivå.
Så hvordan fungerer moduloperatøren? Jeg kan tenke på noen tilfeller som det ville være veldig lett å fastslå. For eksempel, med mod 2 kan du bare se på det siste byte. Eller med mod 4 kan du se på den nest siste b yte. Men ikke alle tall har et så enkelt mønster.
Kommentarer
Svar
Nesten alle CPUer har en enkelt instruksjon som vil returnere modulens verdi. Tenk for eksempel på dette programmet:
int main() { int i = 10; return i % 3; } Hvis jeg kompilerer dette på min Intel OS X-maskin ved hjelp av g ++ -S, blir resultatet noe kjele og dette:
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 Den faktiske modulen skjer med denne instruksjonen: idivl %ecx. Når denne instruksjonen kjøres, plasseres kvotienten i %eax og resten plasseres i %edx.
Siden egentlig betyr dette at % operasjonen bare vil ta noen få tidssykluser, hvorav hoveddelen faktisk flytter dataene til riktig register. Vær også oppmerksom på at med Intel i det minste, finner den samme operasjonen både kvotienten og resten, så i referanse til kommentaren din, / og % ta nøyaktig samme tid. Det er den samme operasjonen. Det eneste som endres er hva register kompilatoren får resultatene fra.
Med hvilken som helst CPU laget de siste par tiårene, kan du anta at enhver grunnleggende matematisk operasjon (inkludert ting som ser ut som biblioteksfunksjoner som sqrt eller cos) er faktisk en enkelt maskininstruksjon og tar vanligvis bare noen få tidssykluser på det meste.
[UPDATE]
Som folk har bemerket i kommentarene, for å se noe som nærmer seg riktig timing, du trenger å fjerne utdataene fra den tidsbestemte delen slik:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Men selv det er sannsynligvis ikke nøyaktig, da den faktiske granulariteten til timingene kan overstige det du er prøver å tid. I stedet vil du kanskje gjøre dette:
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; Del deretter timingen din med 1.000.000. (Dette vil være litt høyt da det inkluderer tiden det tar for en oppgave, en sammenligning og en økning.) På maskinen min gir dette en tid på 5 nanosekunder.
Kommentarer
- Virkelig? Jeg ble fortalt at sqrt er en veldig treg instruksjon.
- Se stackoverflow.no / spørsmål / 7724061 / …
- @StevenBurnap det svaret er litt utdatert, basert på arkitekturen i år 2011. I følge Agner Fog ‘ s tabell, som oppdateres minst årlig , Haswell SSE2 instruksjoner SQRTSS / SQRTPS (32-bit float, med 23 bits av betydning) har en latens på 11 sykluser, SQRTSD / SQRTPD (64-bit float) har en latens på 16 sykluser. Disse instruksjonene er de nøyaktige, dvs. ikke av de raske tilnærmingsvariantene. Det er virkelig mye tregere i eldre arkitekturer. Husk også å ringe til
std::sqrt()pådra seg et biblioteksanrop i de fleste C ++ – kompilatorer. - Kompilatorer kan i tillegg bruke styrkereduksjonsoptimalisering for spesielle tilfeller. For eksempel kan x% 2 være optimalisert til en bitmaske hvis det ‘ er raskere på en bestemt arkitektur.
- @rwong Jeg hadde trodd at
std:sqrtvil vanligvis være inline (og bruke innebygd montering.) Men jeg ‘ har aldri sjekket.
DIVogIDIVinstruksjoner, som utfører heltallsdeling, lagrer også resten i et register). Spør du hvordan maskinvaren gjør det?cout <<de fleste operasjonene. Jeg tviler på at du faktisk kunne måle tiden det tar prosessoren å gjøre20 % 3selv om kompilatoren ikke ‘ ikke gjorde det på kompileringstid uansett .