Come funziona il modulo?

Question

Come funziona il modulo?

#1 da (9 voti)

5

Non sto chiedendo come funziona il concetto matematico del modulo, o come 20 % 3 == 2 capisco bene. Sono più curioso di come il compilatore / interprete lo determini. Posso pensare ad un modo ingenuo molto per farlo, in questo modo:

int modulus(int a, int b)
{
    while (a > b)
    {
        a -= b;
    }
return a;
}

(ovviamente questo ha bisogno di un paio di casi in più perché a può essere più piccolo di b, ma si ottiene l'idea.) Ma questo avrebbe alcuni problemi di prestazioni gravi. Ho buttato insieme qualche C ++ per testare l'efficienza sia dell'operatore modulo che della mia funzione ingenua.

#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";
}

e l'output è:

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.

L'operatore del modulo variava da 4.000 a 70.000 nanosecondi. La mia funzione ha sempre vinto sui numeri piccoli, ma ha impiegato circa 2 secondi per il numero elevato. Dato che l'operatore modulo è molto più coerente, presumo che confronta il numero a livello di bit.

Quindi come fa l'operatore del modulo funziona? Posso pensare ad alcuni casi che sarebbero molto facili da determinare. Ad esempio, con mod 2, puoi solo guardare all'ultimo byte. Oppure con mod 4 puoi guardare il penultimo byte. Ma non tutti i numeri hanno un modello così semplice.

c++ performance efficiency

posta DJMcMayhem 06.05.2015 - 02:08

fonte

1 risposta

Leggi altre domande sui tag c++ performance efficiency

Come gestisco il seguente problema tecnico? [chiuso] Perché non posso fare riferimento a un'interfaccia all'interno di parentesi generiche in una dichiarazione di variabile?

score 9 · Accepted Answer

Quasi tutte le CPU hanno una singola istruzione che restituirà il modulo di un valore. Ad esempio, considera questo programma:

int main()
{
    int i = 10;
    return i % 3;
}

Se lo compilo sulla mia macchina Intel OS X usando g ++ -S, il risultato sarà qualche testo standard e questo:

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

Il modulo reale si verifica con questa istruzione: idivl %ecx . Quando questa istruzione viene eseguita, il quoziente verrà inserito in %eax e il resto verrà inserito in %edx .

Poiché in realtà, ciò significa che l'operazione % richiederà solo alcuni cicli di clock, la maggior parte dei quali sta effettivamente spostando i dati nel registro corretto. Nota anche che con Intel, almeno, la stessa operazione trova sia il quoziente che il resto, quindi in riferimento al tuo commento, / e % prendono esattamente la stessa ora. È la stessa operazione. L'unica cosa che cambia è ciò che registra il compilatore ottiene i risultati da.

Con qualsiasi CPU creata negli ultimi due decenni, si può presumere che qualsiasi operazione matematica di base (comprese cose che assomigliano a funzioni di libreria come sqrt o cos ) sia in realtà una singola istruzione macchina e in genere ne bastano pochi al massimo cicli di clock.

[UPDATE]

Come le persone hanno notato nei commenti, per vedere qualcosa che si avvicina ad un timing corretto, è necessario rimuovere l'output dalla sezione temporizzata come questa:

int i;
auto start = Clock::now();
i = 20 % 3;
auto end = Clock::now();
cout << i << endl;

Ma anche questo probabilmente non è accurato in quanto l'effettiva granularità dei tempi può superare quello che stai provando a tempo. Invece, potresti voler fare questo:

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;

Quindi dividi i tuoi tempi per 1.000.000. (Questo sarà leggermente alto in quanto include il tempo impiegato per un incarico, un confronto e un incremento.) Sulla mia macchina, questo dà un tempo di 5 nanosecondi.