Jeg spørger ikke, hvordan det matematiske begreb modulus fungerer, eller hvordan 20 % 3 == 2 Jeg forstår denne bøde. Jeg er mere nysgerrig over, hvordan kompilatoren / tolk bestemmer dette. Jeg kan tænke på en meget naiv måde at gøre det på, som sådan:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (naturligvis har dette brug for et par flere tilfælde, fordi a kan være mindre end b, men du får ideen.) Men dette ville have nogle alvorlige ydeevneproblemer. Jeg kastede nogle C ++ sammen for at teste effektiviteten af begge moduler operatør og min naive 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"; } og output 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. modulus operator varierede fra 4.000-70.000 nanosekunder. Min funktion vandt altid på de små tal, men tog omkring 2 sekunder på det store antal. Da moduloperatoren er så meget mere konsistent, antager jeg, at den sammenligner antallet på et bitvis niveau.
Så hvordan fungerer moduloperatøren? Jeg kan tænke på nogle tilfælde, der ville være meget lette at bestemme. For eksempel med mod 2 kan du bare se på det meget sidste byte. Eller med mod 4 kan du se på den næstsidste b yte. Men ikke alle tal har et så simpelt mønster.
Kommentarer
Svar
Næsten alle CPUer har en enkelt instruktion, der returnerer modulets værdi. Overvej for eksempel dette program:
int main() { int i = 10; return i % 3; } Hvis jeg kompilerer dette på min Intel OS X-maskine ved hjælp af g ++ -S, bliver resultatet noget kedelplade 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 aktuelle modulus sker med denne instruktion: idivl %ecx. Når denne instruktion udføres, placeres kvotienten i %eax, og resten placeres i %edx.
Siden virkelig betyder det, at % -operationen kun tager et par urcyklusser, hvoraf hovedparten faktisk flytter dataene til det rigtige register. Bemærk også, at i det mindste med Intel finder den samme operation både kvotienten og resten, så med henvisning til din kommentar / og % tage nøjagtigt samme tid. Det er den samme operation. Det eneste, der ændres, er, hvilket register kompilatoren får resultaterne fra.
Med en hvilken som helst CPU lavet i de sidste par årtier kan du antage, at enhver grundlæggende matematisk operation (inklusive ting, der ligner biblioteksfunktioner som sqrt eller cos) er faktisk en enkelt maskininstruktion og tager normalt kun få urcyklusser højst.
[UPDATE]
Som folk har bemærket i kommentarerne, for at se noget der nærmer sig en korrekt timing, skal du har brug for at fjerne output fra det tidsindstillede afsnit sådan:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Men selv det er sandsynligvis ikke nøjagtigt, da den faktiske granularitet af timingen kan overstige det, du er forsøger at tid. I stedet vil du muligvis gø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; Dele derefter din timing med 1.000.000. (Dette vil være lidt højt, da det inkluderer den tid det tager for en opgave, en sammenligning og en stigning.) På min maskine giver dette en tid på 5 nanosekunder.
Kommentarer
- Virkelig? Jeg fik at vide, at sqrt er en meget langsom instruktion.
- Se stackoverflow.com / spørgsmål / 7724061 / …
- @StevenBurnap det svar er lidt forældet, baseret på arkitekturen i år 2011. Ifølge Agner Fog ‘ s tabel, der opdateres mindst årligt , Haswell SSE2 instruktioner SQRTSS / SQRTPS (32-bit float, med 23 bits af betydning) har en latenstid på 11 cyklusser, SQRTSD / SQRTPD (64-bit float) har en latens på 16 cyklusser. Disse instruktioner er de nøjagtige, dvs. ikke af de hurtige tilnærmelsesvarianter. Det er faktisk meget langsommere i ældre arkitekturer. Husk også at ringe til
std::sqrt()pådrager et biblioteksopkald i de fleste C ++ – kompilatorer. - Kompilatorer kan desuden anvende styrkereduktionsoptimering til specielle tilfælde. Eksempelvis kan x% 2 optimeres til en bitmaske, hvis det ‘ er hurtigere på en bestemt arkitektur.
- @rwong Jeg ville have troet, at
std:sqrtville normalt være inline (og bruge inline-samling.) Men jeg ‘ har aldrig kontrolleret.
DIVogIDIVinstruktioner, som udfører heltalsdeling, gemmer også resten i et register). Spørger du hvordan hardware gør det?cout <<de fleste af operationerne. Jeg tvivler på, at du rent faktisk kunne måle den tid, det tager processoren at gøre20 % 3, selvom compileren ikke ‘ ikke gjorde det på kompileringstidspunktet alligevel .