Nem azt kérdezem, hogy hogyan működik a modulus matematikai fogalma, vagy hogy 20 % 3 == 2 hogyan értem ezt a bírságot. Kíváncsi vagyok arra, hogy a fordító / tolmács hogyan határozza meg ezt. Gondolhatok egy nagyon naiv módot erre:
int modulus(int a, int b) { while (a > b) { a -= b; } return a; } (nyilvánvalóan ehhez még néhány esetre van szükség, mert az a lehet kisebb, mint b, de megkapja az ötletet.) De ennek komoly teljesítményproblémái lennének. Dobtam néhány C ++ -ot, hogy teszteljem mindkét modulus hatékonyságát operátor és a naiv funkcióm.
#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"; } és a kimenet:
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. a modulus operátor 4000-70 000 nanoszekundum között változott. A funkcióm mindig kis számokon nyert, nagy számnál azonban körülbelül 2 másodpercet vett igénybe. Mivel a modulus operátor sokkal következetesebb, feltételezem, hogy a számot bitenkénti szinten hasonlítja össze.
Tehát hogyan működik a a modulus operátor? Gondolhatok néhány olyan esetre, amelyeket nagyon könnyű meghatározni. Például a 2-es modral egyszerűen megnézheti a Vagy a 4-es moddal megnézheted a második utolsót b yte. De nem minden számnak van ilyen egyszerű mintázata.
Megjegyzések
Válasz
Szinte az összes CPU-nak egyetlen utasítása van, amely visszaadja az érték modulusát. Vegyük például fontolóra ezt a programot:
int main() { int i = 10; return i % 3; } Ha ezt az Intel OS X gépemen fordítom le a g ++ -S használatával, az eredmény valamilyen kazántábla lesz, és ez:
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 A tényleges modulus ezzel az utasítással történik: idivl %ecx. Amikor ez az utasítás végrehajtásra kerül, a hányados a %eax mappába, a fennmaradó pedig a %edx helyre kerül.
Mivel valójában ez azt jelenti, hogy a % művelet csak néhány óraciklust fog igénybe venni, amelyek zöme az adatokat valóban a megfelelő regiszterbe mozgatja. Vegye figyelembe azt is, hogy legalább az Intel esetében ugyanaz a művelet megtalálja a hányadost és a maradékot is, ezért a megjegyzésére hivatkozva / és % pontosan ugyanabban az időben. Ugyanaz a művelet. Az egyetlen dolog változik, hogy a fordító milyen regisztrációból kapja az eredményeket.
Bármely CPU-val, amely az elmúlt néhány évtizedben készült, feltételezhetjük, hogy bármilyen alapvető matematikai művelet (ideértve a könyvtárhoz hasonló dolgokat is, például sqrt vagy cos) valójában egyetlen gépi utasítás, és általában csak néhány óraciklust vesz igénybe.
[UPDATE]
Amint az emberek megjegyezték a megjegyzésekben, hogy valami helyes időzítéshez közeledjen, így kell eltávolítania a kimenetet az időzített szakaszból:
int i; auto start = Clock::now(); i = 20 % 3; auto end = Clock::now(); cout << i << endl; De ez még valószínűleg nem is pontos, mivel az időzítések tényleges részletessége meghaladhatja megpróbálja időzíteni. Ehelyett érdemes ezt megtennie:
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; Ezután ossza el az időzítést 1 000 000-vel. (Ez kissé magas lesz, mivel magában foglalja a feladat elvégzéséhez szükséges időt, az összehasonlítást és a növekményt.) A gépemen ez 5 nanoszekundumot ad.
Megjegyzések
- Tényleg? Azt mondták, hogy az sqrt nagyon lassú utasítás.
- Lásd: stackoverflow.com / questions / 7724061 / …
- @StevenBurnap ez a válasz kissé elavult, a 2011-es architektúra alapján. Agner Fog ‘ táblázat, amelyet legalább évente frissítenek , Haswell SSE2 utasítások SQRTSS / SQRTPS (32 bites lebegő, 23 bit jelentőségű) késleltetési ideje 11 ciklus, az SQRTSD / SQRTPD (64 bites lebegő) 16 ciklusú. Ezek az utasítások a pontosak, vagyis nem a gyors közelítési változatok. A régebbi architektúráknál valóban sokkal lassabb. Ne feledje, hogy a
std::sqrt()hívás könyvtárhívást von maga után a legtöbb C ++ fordítóban. - A fordítók emellett speciális eseteknél alkalmazhatnak erősségcsökkentési optimalizálást is. Például x% 2 optimalizálható egy bitmaszkra, ha ez ‘ s gyorsabb egy adott architektúrán.
- @rwong azt hittem volna, hogy
std:sqrtáltalában be van vonva (és használjuk az inline összeállítást.) De ‘ soha nem ellenőriztem.
IDIVutasítások a maradékot is regiszterben tárolják). Azt kérdezi, hogy a hardver hogyan csinálja?cout <<időigényét mérik. Kétlem, hogy valóban meg tudnád mérni azt az időt, amelyre a processzornak szüksége van20 % 3elvégzéséhez, még akkor is, ha a fordító nem ‘ nem tette ezt fordításkor .