Il confronto 1 10 è meno costoso di 1 1000000?

64

Ho appena usato ~ 1 miliardo come conteggio per un z-index in CSS, e stavo pensando ai confronti che devono andare avanti. C'è una differenza nelle prestazioni a livello di ALU nei confronti tra numeri molto grandi rispetto a quelli molto piccoli?

Ad esempio, uno di questi due snippet sarebbe più costoso dell'altro?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}
    
posta Viziionary 02.02.2015 - 15:52
fonte

7 risposte

81

Ogni processore su cui ho lavorato fa il confronto sottraendo uno degli operandi dall'altro, scartando il risultato e lasciando i flag del processore (zero, negativo, ecc.) da solo. Poiché la sottrazione viene eseguita come una singola operazione, il contenuto degli operandi non ha importanza.

Il modo migliore per rispondere alla domanda è di compilare il codice in assembly e consultare la documentazione del processore di destinazione per le istruzioni generate. Per le attuali CPU Intel, questo sarebbe Manuale per gli sviluppatori del software Intel 64 e IA-32 Architectures .

La descrizione dell'istruzione CMP ("compare") è nel volume 2A, pagina 3-126 o pagina 618 del PDF e descrive la sua operazione come:

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

Questo significa che il secondo operando viene esteso al segno se necessario, sottratto dal primo operando e il risultato collocato in un'area temporanea nel processore. Quindi i flag di stato sono impostati nello stesso modo in cui sarebbero per l'istruzione SUB ("sottrazione") (pagina 1492 del PDF).

Non ci sono menzioni nella documentazione di CMP o SUB che i valori degli operandi hanno una qualche influenza sulla latenza, quindi qualsiasi valore che usi è sicuro.

    
risposta data 02.02.2015 - 17:20
fonte
24

Is there a difference in performance on the ALU level in comparisons between very large numbers vs very small ones?

È molto improbabile, a meno che passare da un numero piccolo a un numero elevato modifichi il tuo tipo numerico, ad esempio da int a long . Anche allora, la differenza potrebbe non essere significativa. È più probabile che tu veda una differenza se il tuo linguaggio di programmazione passa silenziosamente alla aritmetica di precisione arbitraria sotto le copertine.

Tuttavia, il tuo particolare compilatore potrebbe eseguire alcune intelligenti ottimizzazioni di cui non sei a conoscenza. Il modo in cui lo scopri è misurare Esegui un profiler sul tuo codice; vedere quali confronti impiegano più tempo. O semplicemente avviare e fermare un timer.

    
risposta data 02.02.2015 - 16:47
fonte
18

Molti processori hanno istruzioni "piccole" che possono eseguire operazioni aritmetiche, compresi i confronti, su alcuni operandi immediatamente specificati. Gli operandi diversi da quelli speciali devono utilizzare un formato di istruzioni più grande o, in alcuni casi, devono utilizzare un'istruzione "valore di caricamento dalla memoria". Nel set di istruzioni ARM Cortex-M3, ad esempio, ci sono almeno cinque modi in cui un valore può essere confrontato con una costante:

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

La prima forma è la più piccola; il secondo e il terzo modulo possono o non possono essere eseguiti più rapidamente, a seconda della velocità della memoria da cui viene prelevato il codice. La quarta forma di modulo sarà quasi certamente più lenta delle prime tre, e la quinta forma ancora più lenta, ma quest'ultima può essere utilizzata con qualsiasi valore a 32 bit.

Su processori x86 precedenti, le istruzioni di confronto in forma breve venivano eseguite più rapidamente di quelle a forma lunga, ma molti processori più recenti convertono entrambi i moduli lunghi e corti nella stessa rappresentazione quando vengono recuperati per la prima volta e memorizzano tale rappresentazione uniforme in il cache. Pertanto, mentre i controller incorporati (come quelli presenti su molte piattaforme mobili) avranno una differenza di velocità, molti computer basati su x86 non lo faranno.

Si noti inoltre che in molti casi in cui una costante viene utilizzata pesantemente all'interno di un ciclo, un compilatore dovrà solo caricare la costante in un registro una volta - prima che il ciclo inizi - rendendo evidenti le distinzioni temporali. D'altra parte, ci sono alcune situazioni, anche in piccoli cicli, dove ciò non accade sempre; se un ciclo è piccolo ma pesantemente eseguito, a volte può esserci una prestazione importante tra confronti che riguardano valori immediati brevi e quelli che coinvolgono valori più lunghi.

    
risposta data 02.02.2015 - 19:22
fonte
5

La risposta breve a questa domanda è, no , non c'è differenza di tempo per confrontare due numeri in base alla grandezza di quei numeri supponendo che siano memorizzati nello stesso tipo di dati (ad es. bit ints o entrambi a 64 bit.)

Inoltre, fino alla dimensione della parola della ALU , è incredibilmente improbabile che confrontando due numeri interi tra loro sarà mai prendere più di 1 ciclo di clock, poiché si tratta di una operazione banale equivalente a una sottrazione. Penso che ogni architettura con cui ho avuto a che fare abbia avuto un confronto tra interi a ciclo singolo.

Gli unici casi in cui riesco a pensare che ho riscontrato un confronto tra due numeri non era un'operazione a ciclo singolo:

  • Istruzioni in cui esiste effettivamente una latenza di memoria nel recupero degli operandi, ma ciò non ha nulla a che fare con il confronto stesso (e generalmente non è possibile sulle architetture RISC, sebbene sia solitamente possibile su disegni CISC, come x86 / x64 .)
  • I confronti in virgola mobile possono essere multi-ciclo, a seconda dell'architettura.
  • I numeri in questione non si adattano alla dimensione della parola della ALU e, quindi, il confronto deve essere suddiviso in più istruzioni.
risposta data 02.02.2015 - 19:01
fonte
4

@ La risposta di RobertHarvey è buona; considera questa risposta un supplemento al suo.

Dovresti considerare anche Predizione dei rami :

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86.

Fondamentalmente, nel tuo esempio, se l'istruzione if all'interno del ciclo restituisce sempre la stessa risposta, il sistema può ottimizzarlo indovinando in che modo si diramerà. Nel tuo esempio, poiché l'istruzione if nel primo caso restituisce sempre lo stesso risultato, verrà eseguita leggermente più veloce del secondo.

Domanda di overflow dello stack eccellente sull'argomento

    
risposta data 02.02.2015 - 17:00
fonte
3

Dipende dall'implementazione, ma sarebbe molto, molto improbabile .

Ammetto di non aver letto i dettagli di implementazione dei vari motori del browser e CSS non specifica alcun tipo particolare di memoria per i numeri. Ma credo che sia sicuro assumere che tutti i principali browser utilizzino numeri a virgola mobile a doppia precisione a 64 bit ("doubles", per prendere in prestito un termine da C / C ++) per gestire la maggior parte dei loro bisogni numerici nei CSS , perché questo è ciò che JavaScript usa per i numeri, e quindi l'uso dello stesso tipo semplifica l'integrazione.

Dal punto di vista del computer, tutti i doppi hanno la stessa quantità di dati: 64 bit, indipendentemente dal fatto che il valore sia 1 o -3.14 o 1000000 o 1e100 . La quantità di tempo necessaria per eseguire un'operazione su questi numeri non dipende dal valore effettivo di tali numeri, poiché funziona sempre sulla stessa quantità di dati. C'è un compromesso nel fare le cose in questo modo, in quanto i doppi non possono rappresentare con precisione tutti i numeri (o anche tutti i numeri all'interno del loro intervallo), ma possono avvicinarsi abbastanza per la maggior parte degli argomenti, e il tipo di cose che i CSS non sono numericamente -molto abbastanza da richiedere più precisione di quella. Combina questo con i vantaggi della compatibilità diretta con JavaScript, e hai un caso abbastanza strong per il doppio.

Non è impossibile che qualcuno possa implementare i CSS usando una codifica a lunghezza variabile per i numeri. Se qualcuno usasse una codifica a lunghezza variabile, quindi confrontando i numeri piccoli sarebbe meno costoso rispetto al confronto con numeri grandi, perché i numeri grandi hanno più dati da scricchiolare . Questi tipi di codifiche possono essere più precisi di quelli binari, ma sono anche molto più lenti, e per i CSS in particolare, i guadagni di precisione non sono probabilmente sufficienti per meritare il colpo di performance. Sarei molto sorpreso di sapere che qualsiasi browser ha fatto le cose in questo modo.

Ora, in teoria, c'è una possibile eccezione a tutto ciò che ho detto sopra: il confronto con lo zero è spesso più rapido rispetto al confronto con altri numeri . Questo non è perché zero è breve (se questo fosse il motivo, allora 1 dovrebbe essere altrettanto veloce, ma non lo è). È perché zero ti permette di imbrogliare. È l'unico numero in cui tutti i bit sono disattivati, quindi se sai che uno dei valori è zero, non devi nemmeno guardare l'altro valore come numero: se uno dei bit in poi non è uguale a zero, e quindi devi solo guardare un bit per vedere se è maggiore o minore di zero.

    
risposta data 04.02.2015 - 03:37
fonte
0

Se questo codice veniva interpretato ogni volta che veniva eseguito, ci sarebbe stata una differenza poiché ci vuole più tempo per tokenizzare e interpretare 10000000000000 rispetto a 1000 . Tuttavia, questa è la prima ovvia ottimizzazione degli interpreti in questo caso: un tokenise una volta e interpretare i token.

    
risposta data 04.02.2015 - 01:50
fonte

Leggi altre domande sui tag