En kysy, miten moduulin matemaattinen käsite toimii tai kuinka 20 % 3 == 2 ymmärrän tämän hienon. Olen utelias kuinka kääntäjä / tulkki määrittää tämän. Voin ajatella hyvin naiivista tapaa tehdä se, kuten:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (tietysti tämä vaatii vielä muutaman tapauksen, koska a voi olla pienempi kuin b, mutta saat idean.) Mutta tällä olisi vakavia suorituskykyongelmia. Heitin yhteen C ++: ta testatakseni molempien moduulien tehokkuuden operaattori ja naiivi toimintoni.
#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"; } ja lähtö on:
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. moduulioperaattori vaihteli välillä 4000-70 000 nanosekuntia. Toimintani voitti aina pienillä luvuilla, mutta kesti noin 2 sekuntia suurella luvulla. Koska moduulioperaattori on niin paljon johdonmukaisempi, oletan, että se vertaa lukua bitin tasolla.
Joten miten moduulioperaattori toimii? Voin ajatella joitain tapauksia, jotka olisi helppo määrittää. Esimerkiksi mod 2: lla voit vain tarkastella Tai tavulla 4 voit tarkastella toista viimeistä b yte. Kaikilla numeroilla ei kuitenkaan ole niin yksinkertaista mallia.
Kommentit
Vastaus
Lähes kaikilla suorittimilla on yksi käsky, joka palauttaa arvon moduulin. Harkitse esimerkiksi tätä ohjelmaa:
int main() { int i = 10; return i % 3; } Jos käännän tämän Intel OS X -tietokoneessani g ++ -S: n avulla, tuloksena on jokin kattolevy ja tämä:
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 Todellinen moduuli tapahtuu tämän käskyn kanssa: idivl %ecx. Kun tämä käsky suoritetaan, osamäärä sijoitetaan kohtaan %eax ja loput osaan %edx.
Koska todellakin, tämä tarkoittaa, että % -operaatio vie vain muutaman kellojakson, joista suurin osa siirtää tiedot oikeaan rekisteriin. Huomaa myös, että ainakin Intelin kanssa sama toiminto löytää sekä osamäärän että loppuosan, joten kommenttisi viitteeksi / ja % ota täsmälleen sama aika. Se on sama operaatio. Ainoa asia, joka muuttuu, on se, mistä rekisteristä kääntäjä saa tulokset.
Kaikilla parin viime vuosikymmenen aikana tehdyillä suorittimilla voit olettaa, että mikä tahansa matemaattinen perustoiminto (mukaan lukien kirjaston näyttävät toiminnot, kuten sqrt tai cos) on itse asiassa yksi koneohje ja kestää yleensä vain muutaman kellojakson.
[PÄIVITYS]
Kuten ihmiset ovat huomauttaneet kommenteissa, jos haluat nähdä jotain lähestyvän oikeaa ajoitusta, sinun on poistettava lähtö ajoitetusta osiosta tällä tavalla:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; Mutta se ei myöskään todennäköisesti ole tarkkaa, koska ajoituksen todellinen tarkkuus voi ylittää nykyisen yrittää ajoittaa. Sen sijaan haluat ehkä tehdä tämän:
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; Jaa sitten ajoitus 1 000 000: lla. (Tämä on hieman korkea, koska se sisältää tehtävään kuluvan ajan, vertailun ja lisäyksen.) Koneellani tämä antaa viiden nanosekunnin ajan.
Kommentit
- Todella? Minulle kerrottiin, että sqrt on erittäin hidas käsky.
- Katso pinoamisvirta.com / questions / 7724061 / …
- @StevenBurnap, että vastaus on hieman vanhentunut, perustuen vuoden 2011 arkkitehtuuriin. Agner Fog ’ -taulukko, joka päivitetään vähintään vuosittain , Haswell SSE2 -ohjeet SQRTSS / SQRTPS (32-bittinen float, 23 merkitsevää bittiä) latenssi on 11 sykliä, SQRTSD / SQRTPD (64-bittinen kelluva) on 16 sykliä. Nämä ohjeet ovat tarkkoja, ts. Eivät nopeita likiarvomuuttujia. Vanhemmissa arkkitehtuureissa se on todellakin paljon hitaampaa. Muista myös, että soittamalla
std::sqrt()kirjastokutsu tapahtuu useimmissa C ++ -kääntäjissä. - Kääntäjät voivat lisäksi soveltaa voiman vähentämisen optimointia erikoistapauksissa. Esimerkiksi x% 2 voidaan optimoida bittiseksi maskiksi, jos se ’ on nopeampi tietyllä arkkitehtuurilla.
- @rwong Olisin ajatellut, että
std:sqrtolisi yleensä viivoitettu (ja käytän sisäistä kokoonpanoa.) Mutta en ’ ole koskaan tarkistanut.
DIVjaIDIVohjeet, jotka suorittavat kokonaisluvun jakamisen, tallentavat myös loput rekisteriin). Kysytkö, miten laitteisto tekee sen?cout <<suurimpaan osaan toimintoja. Epäilen, voisitko todella mitata prosessorin suorittamiseen kuluvan ajan20 % 3, vaikka kääntäjä ei olisi tehnyt sitä ’ .