Jag frågar inte hur det matematiska begreppet modul fungerar, eller hur 20 % 3 == 2 Jag förstår detta bra. Jag är mer nyfiken på hur kompilatorn / tolkar bestämmer detta. Jag kan tänka mig ett väldigt naivt sätt att göra det, som så:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (uppenbarligen behöver detta några fler fall eftersom a kan vara mindre än b, men du får idén.) Men detta skulle ha några allvarliga prestandafrågor. Jag kastade ihop lite C ++ för att testa effektiviteten hos både modulen operatör och min naiva funktion.
#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"; } och utgången är:
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 varierade från 4 000-70 000 nanosekunder. Min funktion vann alltid på de små siffrorna, men tog cirka 2 sekunder på det stora numret. Eftersom moduloperatören är så mycket mer konsekvent antar jag att den jämför antalet på en bitvis nivå.
Så hur fungerar moduloperatören? Jag kan tänka på några fall som skulle vara väldigt enkla att avgöra. Till exempel, med mod 2 kan du bara titta på sista byte. Eller med mod 4 kan du titta på den näst sista b yte. Men inte alla siffror har ett så enkelt mönster.
Kommentarer
Svar
Nästan alla processorer har en enda instruktion som returnerar modulens värde. Tänk till exempel på det här programmet:
int main() { int i = 10; return i % 3; } Om jag kompilerar detta på min Intel OS X-maskin med g ++ -S, blir resultatet en pannplatta och detta:
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 faktiska modulen händer med den här instruktionen: idivl %ecx. När den här instruktionen körs placeras kvoten i %eax och resten placeras i %edx.
Eftersom det egentligen betyder att % -operationen bara tar några klockcykler, varav huvuddelen faktiskt flyttar data till rätt register. Observera också att med Intel åtminstone samma operation hittar både kvoten och resten, så med hänvisning till din kommentar, / och % ta exakt samma tid. Det är samma operation. Det enda som ändras är vilket register kompilatorn får resultaten från.
Med vilken processor som helst som gjorts under de senaste decennierna kan du anta att alla grundläggande matematiska operationer (inklusive saker som ser ut som biblioteksfunktioner som sqrt eller cos) är faktiskt en enda maskininstruktion och tar vanligtvis bara några klockcykler högst.
[UPDATE]
Som folk har noterat i kommentarerna, för att se något som närmar sig en korrekt timing, du måste ta bort utdata från det tidsinställda avsnittet så här:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Men även det är troligtvis inte korrekt eftersom den faktiska granulariteten hos tidsinställningarna kan överstiga vad du är försöker tid. Istället kanske du vill göra detta:
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; Dela sedan din timing med 1 000 000. (Detta kommer att vara något högt eftersom det inkluderar den tid det tar för en uppgift, en jämförelse och ett steg.) På min maskin ger detta en tid på 5 nanosekunder.
Kommentarer
- Verkligen? Jag fick höra att sqrt är en mycket långsam instruktion.
- Se stackoverflow.com / frågor / 7724061 / …
- @StevenBurnap det svaret är lite föråldrat, baserat på arkitekturen år 2011. Enligt Agner Fog ’ s tabell, som uppdateras åtminstone årligen , Haswell SSE2 instruktioner SQRTSS / SQRTPS (32-bitars float, med 23 bitar av betydelse) har en latens på 11 cykler, SQRTSD / SQRTPD (64-bitars float) har en latens på 16 cykler. Dessa instruktioner är exakta, dvs inte av de snabba approximationsvarianterna. Det är verkligen mycket långsammare i äldre arkitekturer. Tänk också på att ringa till
std::sqrt()medför ett bibliotekssamtal i de flesta C ++ – kompilatorer. - Kompilatorer kan dessutom tillämpa styrka minskningsoptimering för speciella fall. Till exempel kan x% 2 optimeras till en bitmask om det ’ är snabbare på en specifik arkitektur.
- @rwong skulle jag ha trott att
std:sqrtbrukar vara inline (och använda inbyggd montering.) Men jag ’ har aldrig kontrollerat.
DIVochIDIVinstruktioner, som utför heltalsdelning, lagrar också resten i ett register). Frågar du hur hårdvaran gör det?cout <<de flesta operationerna. Jag tvivlar på att du faktiskt kunde mäta den tid det tar processorn att göra20 % 3även om kompilatorn inte ’ inte gjorde det vid sammanställningstid ändå .