Ik vraag niet hoe het wiskundige concept van modulus werkt, of hoe 20 % 3 == 2 ik dit goed begrijp. Ik ben meer benieuwd hoe de compiler / interpreter dit bepaalt. Ik kan een zeer naïeve manier bedenken om het te doen, zoals:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (dit heeft uiteraard nog een paar gevallen nodig omdat a kleiner kan zijn dan b, maar je snapt het wel.) Maar dit zou serieuze prestatieproblemen hebben. Ik gooide wat C ++ samen om de efficiëntie van beide modulus te testen operator en mijn naïeve functie.
#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"; } en de uitvoer is:
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. De modulus-operator varieerde van 4.000-70.000 nanoseconden. Mijn functie won altijd bij de kleine getallen, maar duurde ongeveer 2 seconden bij het grote getal. Omdat de modulus-operator zo veel consistenter is, neem ik aan dat hij het getal bitgewijs vergelijkt.
Dus hoe werkt de modulus-operator werkt? Ik kan enkele gevallen bedenken die heel gemakkelijk te bepalen zijn. Met mod 2 kun je bijvoorbeeld gewoon naar de laatste byte Of met mod 4 kun je kijken naar de voorlaatste b yte. Maar niet alle nummers hebben zon eenvoudig patroon.
Opmerkingen
Answer
Bijna alle CPUs hebben een enkele instructie die de modulus van een waarde retourneert. Beschouw bijvoorbeeld dit programma:
int main() { int i = 10; return i % 3; } Als ik dit compileer op mijn Intel OS X-machine met g ++ -S, zal het resultaat een standaardplaat zijn en dit:
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 De feitelijke modulus gebeurt met deze instructie: idivl %ecx. Wanneer deze instructie wordt uitgevoerd, wordt het quotiënt in %eax geplaatst en de rest wordt in %edx geplaatst.
Aangezien dit in feite betekent dat de % -bewerking maar een paar klokcycli zal duren, waarvan het grootste deel feitelijk de gegevens naar het juiste register verplaatst. Merk ook op dat met tenminste Intel dezelfde bewerking zowel het quotiënt als de rest vindt, dus met verwijzing naar uw opmerking, / en % neem precies dezelfde tijd. Het is dezelfde operatie. Het enige dat verandert, is waaruit het register de compiler haalt.
Met elke CPU die in de afgelopen decennia is gemaakt, kun je aannemen dat elke wiskundige basisbewerking (inclusief dingen die eruit zien als bibliotheekfuncties zoals sqrt of cos) is eigenlijk een enkele machine-instructie en duurt doorgaans slechts een paar klokcycli.
[UPDATE]
Zoals mensen hebben opgemerkt in de commentaren: om iets te zien dat een juiste timing nadert, moet de uitvoer als volgt uit de getimede sectie verwijderen:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Maar zelfs dat is waarschijnlijk niet nauwkeurig, aangezien de werkelijke granulariteit van de timings groter kan zijn dan u bent proberen te timen. In plaats daarvan zou je dit misschien willen doen:
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; Deel vervolgens je timing door 1.000.000. (Dit zal een beetje hoog zijn aangezien het de tijd omvat die nodig is voor een opdracht, een vergelijking en een verhoging.) Op mijn computer geeft dit een tijd van 5 nanoseconden.
Opmerkingen
- Echt? Mij is verteld dat sqrt een erg trage instructie is.
- Zie stackoverflow.com / questions / 7724061 / …
- @StevenBurnap is dat antwoord een beetje verouderd, gebaseerd op de architectuur in het jaar 2011. Volgens Agner Fog ‘ s tabel, die minstens jaarlijks wordt bijgewerkt , Haswell SSE2-instructies SQRTSS / SQRTPS (32-bit float, met 23 bits significantie) heeft een latentie van 11 cycli, SQRTSD / SQRTPD (64-bit float) heeft een latentie van 16 cycli. Deze instructies zijn de precieze, d.w.z. niet van de snelle benaderingsvarianten. Het is inderdaad een stuk langzamer in oudere architecturen. Houd er ook rekening mee dat het aanroepen van
std::sqrt()in de meeste C ++ -compilers een bibliotheekoproep veroorzaakt. - Compilers kunnen bovendien optimalisatie van de sterkte-reductie toepassen voor speciale gevallen. X% 2 kan bijvoorbeeld worden geoptimaliseerd tot een bitmasker als dat ‘ sneller is op een specifieke architectuur.
- @rwong Ik had gedacht dat
std:sqrtzou meestal inline zijn (en inline assembly gebruiken). Maar ik ‘ heb het nooit gecontroleerd.
DIVenIDIVinstructies, die het delen van gehele getallen uitvoeren, slaan ook de rest op in een register). Vraagt u zich af hoe de hardware het doet?cout <<de meeste bewerkingen te doen. Ik betwijfel of je de tijd zou kunnen meten die de processor nodig heeft om20 % 3te doen, zelfs als de compiler het niet ‘ deed tijdens het compileren .