Come posso ridurre la divisione per 2^n + 1?

Ho bisogno di eseguire alcune divisioni di interi nel percorso caldo del mio codice. Ho già determinato tramite il profiling e il conteggio dei cicli che le divisioni intere mi stanno costando. Spero che ci sia qualcosa che posso fare per forza ridurre le divisioni in qualcosa di più economico.Come posso ridurre la divisione per 2^n + 1?

In questo percorso, sto dividendo per 2^n + 1, dove n è variabile. In sostanza voglio ottimizzare questa funzione per rimuovere l'operatore di divisione:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    return a/((1 << n) + 1); 
}

Se fossi dividendo per 2^n, vorrei solo sostituire il div con uno spostamento a destra per n. Se dividessi per una costante, lascerei che la forza del compilatore riducesse quella divisione specifica, probabilmente trasformandola in una moltiplicazione e in alcuni cambiamenti.

Esiste un'ottimizzazione simile a 2^n + 1?

Modifica: un qui può essere un numero arbitrario a 64 bit. n richiede solo alcuni valori tra 10 e, ad esempio, 25. Posso certamente precomputare alcuni valori per ogni n, ma non per a.

fonte

2010-10-25 J.S.

Vi sono vincoli sui valori di una e n? –

Qual è il contesto in cui stai chiamando la funzione? – GManNickG

'return a/lookup [n];' –

Dal momento che è possibile spostare solo un int tanti luoghi, si può mettere tutti quei casi in una scelta di una delle diverse divisioni per una costante:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader): 
    switch (n) { 
     case 0: return a/((1 << 0) + 1); 
     case 1: return a/((1 << 1) + 1); 
     case 2: return a/((1 << 2) + 1); 

      // cases 3 through 30... 

     case 31: return a/((1 << 31) + 1); 
    } 
}

Così ora ogni divisione è per una costante, che i compilatori di solito si riducono a una serie di istruzioni di moltiplicazione/spostamento/aggiunta (come la domanda menzionata). Vedi Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts? per i dettagli.

fonte

2010-10-25 17:39:10

Idea interessante. Forse posso scrivere questo codice, quindi estrarre i parametri di riduzione della forza in una tabella. –

Vale la pena provare, ma stai facendo un salto imprevedibile contro la differenza tra le istruzioni shift + division e la divisione equivalente alla forza ridotta. Qualche idea quando questo è un buon compromesso? –

+ 1, ha senso; anche se probabilmente vorrai fare un benchmark per confermare che le ramificazioni indirette e/o condizionali richieste per implementare il 'switch()' sono in realtà più veloci della divisione intera ... –

È possibile sostituire la divisione integer di una costante, per moltiplicazione (modulo wordsize) con un numero magico e uno spostamento.

I numeri magici possono essere precalcolati per le costanti conosciute.

Poiché n non può assumere molti valori, ad es. 0..31 è "facile" precalcolare questi numeri magici per tutto il n e memorizzarlo in una tabella con 32 elementi.

Javascript Page for calculating the magic numbers

Un buon compilatore può calcolare i numeri magici e sostituire divisione intera per moltiplicazione e spostare se il divisore è costante in fase di compilazione. A seconda di come il resto del codice è strutturato attorno al codice critico delle prestazioni, potresti utilizzare macro o trucchi in linea per srotolare tutti i possibili valori di n e lasciare che il compilatore faccia il lavoro di trovare i numeri magici (simili alla risposta con passare, ma vorrei mettere più codice nella regione costante altrimenti potrebbe essere un tradeof non ne vale la pena - ramificazione può costare prestazioni anche)

Descrizione dettagliata insieme con il codice per il calcolo dei numeri magici possono essere fondi nel Prenota "Hackers Delight" di Henry S. Warren, Jr. (altamente raccomandato deve avere un libro!) pp. 180ff.

il link di Google Libri per il capitolo:

Chapter 10-9 Unsigned Division by Divisors >= 1

fonte

2010-10-25 18:16:31

Come posso ridurre la divisione per 2^n + 1?

risposta

Problemi correlati