Newsgroup: it.comp.lang.c++
Titolo: Calcolare velocemente numero di bit necessari a rappresentare un valore intero

Ciao a tutti!
    secondo voi qual'è il modo più veloce per calcolare il numero di bit 
minimo necessario a rappresentare un valore intero?
Per esempio, prendiamo il valore 126. Mi servono almeno 7 bit.
Per fare questo calcolo è più velore utilizzare una lookup table o 
calcolarselo ogni volta, considerando che mi serve saperlo solo per valori 
tra 0 e 512?
Grazie 

 while (TestValue != 0)
Questa soluzione è credo la più valida alternativa alla lookup table. 
Considera che questa operazione deve essere inserita in una routine che 
lavora sui pixel di un'immagine, per cui verrà eseguita centinaia di 
migliaia di volte. Tuttavia, il valore di TestValue non è ugualmente 
distribuito nel range 0 : 512, ma i valori più vicini allo 0 sono anche di 
gran lunga i più frequenti. Per cui, credo che questa soluzione sia 
vantaggiosa rispetto alla lookup table, che richiederebbe un tempo di 
accesso costante x ogni valore (correggetemi se sbaglio, nn sono un 
programmatore professionista), mentre qui per valori piccoli il calcolo 
richiederebbe pochissimi cicli.
Cosa ne dici?
Grazie 

suo scope riservato e pulito ... magari con la convenzione __fastcall)
Vorrei evitare la chiamata a funzione, per i motivi espressi nel mio post 
precedente ho bisogno di una espressione davvero velocissima. Non sò, magari 
come inline, cosa ne dite di:
inline unsigned BitSize(unsigned Value) {
NumBits = 0;
do
     {
     TestValue >> 1;
     NumBits ++;
     }
while (TestValue != 0)
return NumBits;
}

 Per fare questo calcolo  pi velore utilizzare una lookup table o 


 log in base 2 di X=log in b e di X / log in e di 2 
ok .. mi sa che è lenta come la morte :) 

     TestValue /= 2;
IMHO e` altrettanto sicura la prima, questa forse e` un tantino piu` 
leggibile, ogni compilatore moderno con le ottimizzazioni attive 
dovrebbe farla collassare nella prima formulazione.
Bye,
  Gabry

 dovrebbe farla collassare nella prima formulazione.
Non è detto perchè sui numeri negativi
	x/2 != (x>>1)
E.

 O forse lavori alla compressione delle immagini ?
Esatto, lavoro ad un algoritmo di compressione per le immagini. I tuoi
suggerimenti sono tutti validi, ma per le ottimizzazioni spinte è
ancora troppo presto, per ora punto ad un codice sì efficiente, ma non
estremo.
Grazie x l'aiuto!


Per fortuna nn è il mio caso, come da primo post i valori sono
compresi tra 0 e 512 :-P


Ok, ma ricordati di informare il compilatore, utilizzando un tipo unsigned!
E.

 e quindi farle girare più veloci
Se la cosa deve essere veramente veloce, *e* il numero è intero e
positivo e compreso fra 0 e 512, sappiamo anche che l'1 più grosso può
stare in determinate posizioni. Si può fare un loop unrolling 'manuale'.
BTW lo standard dice che se il numero è positivo o unsigned (e i numeri
in gioco ci stanno nei tipi) a sinistra vengono introdotti degli 0. 
-- 
cc = callcc {|cc| cc.call cc}; cc.call cc

 stare in determinate posizioni. Si puň fare un loop unrolling 'manuale'.
O una ricerca binaria:
int myLog2(int x) {
	assert(x>=0 && x <= 0x1FF);
	if (x&0x100) return 8;
	if (x&0xF0) {
	  if (x&0xC0) {
	    if (x&0x80) return 7;
	    else return 6
           } else {
	    if (x&0x20) return 5;
	    else return 4;
	  }
	} else {
	  if (x&0x0C) {
	    if (x&0x08) return 3;
	    else return 2;
	  } else {
	    if (x&0x02) return 1;
	    else return 0;
	  }
	}
}
...comunque mi pare strano che una funzione del genere non esista nella 
libreria standard. Immagino (ma forse sbaglio?) che le CPU moderne 
dovrebbero avere una istruzione del genere...
E.

 O una ricerca binaria:
Non credo che sia necessario. Mi spiego meglio, l'uno più significativo
è per sua definizione unico. Per cui una volta trovatolo, sai quale è la
dimensione. 
Non hai bisogno di nestare così tanti if, che è un inferno per il branch
predictor. 
Quello che intendo è che ci vogliono 8 test binari. Partendo dal più
grosso, mano mano che falliscono hai informazioni.
Pure questo non è un gran chè per il predictor. Ma non riesco a pensare
a nulla di meglio. Mah, forse usando i vari shift. Boh.


 bit minimo necessario a rappresentare un valore intero?
unsigned int log2i(unsigned int v)
{
  unsigned int s ;
  unsigned int r = 0 ;
 
  s = ((v & 0xFFFF0000) != 0) << 4 ; v = v >> s ; r = r | s ;
  s = ((v & 0x0000FF00) != 0) << 3 ; v = v >> s ; r = r | s ;
  s = ((v & 0x000000F0) != 0) << 2 ; v = v >> s ; r = r | s ;
  s = ((v & 0x0000000C) != 0) << 1 ; v = v >> s ; r = r | s ;
  s = ((v & 0x00000002) != 0) << 0 ; v = v >> s ; r = r | s ;
 
  return r ;
}
ammetto che il codice non č completamente mio. trovai in giro un po di 
codice e "mettendolo assieme" ne usci questo. per v<512 potresti anche 
eliminare la prima riga per rismarmiare qualcosina volendo. abbastanza 
veloce da poter essere usato pesantemente realtime, confermo.

 }
Uh! Spettacolo!
E.

?manu* ha scritto:

Mica tanto!
La seguente mi risulta oltre 10 volte piu' veloce (difficile essere 
precisi con operazioni cosi' veloci).
Ovviamente il compilatore ha espanso inline la funzione in entrambi i casi.
unsigned int log2i(unsigned int v)
{
   static unsigned char lut[] = {
     0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
     9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
   };
   return lut[v];
}
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 BTW lo standard dice che se il numero č positivo o unsigned (e i numeri


 La seguente mi risulta oltre 10 volte piu' veloce
Beh si, in effetti una lookup table per n piccoli è cosa migliore, 
sopratutto se calcoli dozilioni di log2i() in batch e la lookup table 
rimane in cache, altrimenti cominci ad avere un po di cache miss. E poi 
ti ci voglio vedere con numeri a 32bit con 4gb di lookup table (il caso 
mio ai tempi) :)

 dimensione. 
ahh, forse ho capito cosa intendevi, non come ho scritto 
nell'altro post
if ((TestValue & 512) != 0) return 10:
if ((TestValue & 256) != 0) return 9:
.....................................
if ((TestValue & 4) != 0) return 3:
if ((TestValue & 2) != 0) return 2:
if ((TestValue & 1) != 0) return 1:
return 1:
L'unico problema è che, se come ha scritto l'op. sono di gran 
lunga diffusi i valori molto bassi, questa sequenza lavora 
sempre fin verso la fine e esegue molti confronti.
D'altra parte il testo al contrario non ha nessun senso.
Dilemma ...
altre idee ?
ciao
Soviet_Mario


 altre idee ?
Basta testare gli 0 anzichè l'1 usando l'or:
if ((TestValue | 1) == 1) return 1;
if ((TestValue | 3) == 3) return 2;
if ((TestValue | 7) == 7) return 3;
.....................................
if ((TestValue | 255) == 255) return 8;
if ((TestValue | 511) == 511) return 9;
return 10;
GM

 Beh si, in effetti una lookup table per n piccoli è cosa migliore,
Mi rendo conto che su operazioni così rapide non è facile farsi
un'idea delle differenze di velocità. D'altra parte entrano in gioco
molti fattori (cache, dimensione dei valori in input e via dicendo).
Dunque alla fine ritorna in auge la mitica lookup table!
Se non ricordo male, ho letto che l'accesso agli array con numero di
elementi pari a una potenza di 2 venga gestito dai compilatori in modo
da ottimizzare l'accesso, magari potrebbe essere per questo che và
così veloce visto che abbiamo appunto 512 valori
Ad ogni modo, grazie a tutti x l'aiuto! Ma quante ne sapete! :-P

 intendi un loop-senza-loop ?
Si, qualcosa del genere. Confesso che preferisco la versione di GM. O
forse io avrei fatto direttamente delle maschere in and, senza gli
shift. Chiaramente tutto da dimostrare quale sia più efficiente.
Purtroppo in queste cose di basso livello l'intuizione guida male
(specialmente perchè è molto difficile capire cosa fa il branch
predictor). 
Aggiungo, probabilmente per una singola routine io passerei all'asm. Mi
da molto più controllo su quello che sto facendo ed è comunque qualcosa
che rimane isolato. Perchè è bene fidarsi dell'ottimizzatore (e uno
passa *anche* per quello), ma anche dare un occhio al codice generato
aiuta a capire, nel caso.


 framite shift: è un'affermazione abbastanza precisa, IMHO.
Ora credo di aver capito, scusa. Hai usato quei numeri che
'rappresentano' l'operazione specifica fatta con gli interi. Giusto?


 ......................................


 
Rileggendomi, ammetto che avevi avuto ragione tu a fare la 
critica sui numeri. Solo che li avevo buttati lì in maniera 
tanto approssimativa che non mi ero proprio posto il problema 
che potessero essere interpretati in senso quantitativamente 
significativo, per cui mi ero anche completamente scordato di 
avere scritto quella frase, azz !
Dato che poi non l'hai quotata tu stesso, nel contestarmela, non 
mi ha nemmeno più sfiorato il dubbio di rileggere le mie stesse 
parole.
In effetti avevo guardato su un vecchio manuale del 386-387, di 
secoli fa, dove ciascuno shift usava 3/7 cicli di clock 
rispettivamente con operando di registro precaricato o in ram 
(il test contro zero è poi pure esso veloce, perchè il registro 
flag di zero è aggiornato da sé, e a seconda che si verificasse 
la condizione di salto, return, o meno, il clock era 8 / 3 cicli 
rispettivamente), ma non c'era riportato nessun dato di clock 
relativamente alle istruzioni floating point (mai capito 
perchè), quindi proprio ho fatto una "stima" alla cazzo.
Certo però che eventuali numeri scritto dopo il prefisso 
"spannometrically" non sembrano ottimi candidati di affidabilità.
Vabbè, mea culpa cmq
ciao
Soviet_smemorato

 pi— valoce possibile in termini di clock.
confermo. ho fatto un po di profiling e in effetti il metodo di GM è 20% 
piu veloce del mio con n < 2^9. con n < 2^32 è invece il 100% piu lento 
del mio, visto che il suo metodo è O(n) mentre il mio O(log n). la 
lookuptable comunque stravince su entrambi, ma ha il difetto che al 
chescere di n la tabella raggiunge dimensioni impraticabili. il metodo di 
GM potrebbe però essere ottimizato anche per n > 2^9 nello specifico del 
problema dell'OP se si avesse una distribuzione dei valori, cosi da 
mettere in tesca alla catena di if i valori piu probabili.
e a titolo di cronaca, log(n)/log(2) è il 500% piu lento del mio e il 
480% del codice di GM, in qualsiasi caso (è praticamente costante)

 480% del codice di GM, in qualsiasi caso (è praticamente costante)
ciao
Soviet


I valori sono distribuiti secondo una geometrica, la cui pendenza dipende 
dalla struttura dell'immagine oggetto dell'elaborazione.
Danilo

 perchč), quindi proprio ho fatto una "stima" alla cazzo.
Ah, lol. Ricordo anche io. Istruzione e di fianco numero di cicli di
clock (ma non era piů veloce lo shift?) Perň ora quasi tutte le
istruzioni sono considerevolemnte piů veloci, i processori tendono ad
essere superscalari e in piů ci si ficcano dentro un mucchio di
considerazioni collaterali (tipo la mia fissazione sul branch
predictor). 


 in gioco ci stanno nei tipi) a sinistra vengono introdotti degli 0. 
Per un shift "logico". Esiste anche quello aritmetico, che prevede
l'estensione del segno.

 l'estensione del segno.
Io ti parlo dello standard. A quanto leggo il punto è che se il numero
da shiftare è con segno e negativo, il risultato è implementation
defined.
Il che vuole dire è che è ragionevole che un'implementazione faccia lo
shift aritmetico, ma non è detto. Tipicamente viene fatto, per quello
che ne so. Ma appunto, dipende dal compilatore. 
Gli altri casi invece ci si mette la mano sul fuoco.


 Gli altri casi invece ci si mette la mano sul fuoco.
meglio allora affidarsi (come sarebbe buona cosa) alle ottimizzazioni
del compilatore.

 predictor). 
Il che porta ad una considerazione. Perché tutti i programmatori (o
almeno la maggior parte di quelli che conosco io) si considerano così
intelligenti e scrupolosi da preferire fare le ottimizzazioni via
assembly piuttosto che lasciarle fare ad un compilatore? Io che
lavoricchio anche in vhdl (che è più a basso livello dell'asm) non mi
azzarderei mai a fare una cosa del genere. Sarà un mio limite...?

 azzarderei mai a fare una cosa del genere. Sarà un mio limite...?
Beh, un programmatore particolarmente bravo può ancora ottimizzare molto
(anche se bisogna vedere quali di queste ottimizzazioni non possano
essere fatte dal compilatore).
Ad ogni modo ottimizzare a livello di ASM deve essere una delle ultime
cose da fare: quando ci si è resi conto che il codice così come è è
troppo lento, che non lo si può migliorare a livello algoritmico, etc
etc etc


 del compilatore.
Quoto. Possibilmente avendo idea di come funzionano, scrivendo codice
che senza stravolgere la logica umana rende più facile al compilatore
ottimizzare. *E* avere presente come funziona la macchina.
Mi viene in mente un esempio che ho letto su 'Computer Organization and
Design' di Patterson e Hennessy. In pratica mostrava come in un codice
pesantemente iterativo, cambiando l'ordine di iterazione il tempo di
esecuzione migliorava drasticamente per un migliore utilizzo della
cache. Incidentalmente alcuni compilatori sono in grado di fare questo
tipo di ottimizzazioni, ma non sono particolarmente banali, ecco. Specie
non in C (in Pascal sarebbe più facile)[0].
-------
[0] ovviamente nel caso generale per sapere che due cicli sono
invertibili, dobbiamo *anche* dimostrare che nessuno dei due non termina
(altrimenti ovviamente non possiamo farlo), nè che sia possibile uscire
indeterminatamente dal loop. Il for del pascal in buona sostanza
gestisce tutto questo (non so come si mette con il goto, ma supponiamo
che non sia usato), sempre a patto che gli altri statement nei corpi dei
loop siano a loro volta 'buoni' secondo il criterio soprastante.
Nel caso di C il compilatore deve essere più astuto e dimostrare che i
valori delle variabili di iterazione siano monotoni e limitati (tenendo
conto che 0-1 in unsigned int da MAX_UNSIGNED_INT).


 cache. 
Ad esempio se devi iterare su un array 2-dimensionale conviene sempre 
mettere all'interno il ciclo che scorre i dati contigui in memoria. In 
questo modo i dati saranno probabilmente già nella cache.
E.

 questo modo i dati saranno probabilmente già nella cache.
Esatto.


 gran lunga i più frequenti. 
Mi viene da pensare che se gli elementi fossero ordinati quella funzione 
sarebbe ottimizzabile...PErò ordinarli ti costa NLogN che è quanto ti 
costa applicare quella funzione a tutti i tui valori (che in realtà se 
in media sono piccoli diventa molto minore di NLogN.
ciao


Mah. Solo in casi specifici: cioè, le ottimizzazioni possono non andare
più bene da un modello di cpu all'altro, figurarsi con i multicore.
Riporto il link della pagina del blog (scusate la pubblicità occulta)
dove giusto oggi riportavo tre citazioni sull'ottimizzazione.
Modestamente l'ho sempre pensata cosi' :-)
http://engineering.splinder.com/post/15713894/Ottimizzazione

 più bene da un modello di cpu all'altro, figurarsi con i multicore.
E io ribadisco: ci sono ottimizzazioni piuttosto cross-cpu (per lo meno
all'interno della stessa famiglia). D'altra parte quando compili
normalmente generi per una cpu generica, non per la tua specifica. 
Ribadisco, poi: se sono d'accordo sul fatto che ottimizzare a mano deve
essere una delle ultime cose da fare e se e solo se chi la sta facendo
sa quello che fa, le evidenze sperimentali dicono che ci sono tutt'ora
casi in cui un uomo è necessario. Prova a disabilitare le ottimizzazioni
asm da gmp e guarda di quanto peggiora, per dire.
D'altra parte a loro la cosa interessa. Hanno individuato alcune
primitive (4-5) che si succhiano buona parte del tempo di macchina e in
una libreria di calcolo avere ottime prestazioni è fondamentale. Per cui
si sono messi li e le hanno strizzate. 
Non a caso tempo fa il processore su cui erano più ottimizzate erano gli
allora 'ultimi' AMD. Li era proprio ottimizzazione estrema, fatta da
programmatori competenti che avevano *studiato* il problema.


 programmatori competenti che avevano *studiato* il problema.
Non dubito, ma sono casi estremi. Che espongono il fianco a problemi
innumerevoli -- ad esempio, cambio di hardware -- e non raggiungibili al
comune mortale e alle comuni esigenze.


Ma la comodità è più quella di rimanere in ambito C che la portabilità,
visto che queste mappano sostanzialmente 1-1 alcune istruzioni hardware.
Ribadisco: non sto dicendo che la gente si deve mettere ad ottimizzare
in asm. Tuttavia non è così infrequente che un programmatore abbia una
percezione del problema migliore del compilatore. Se a questo aggiunge
specifiche conoscenze sul funzionamento delle CPU target, è possibile
che possa fare un buon lavoro. 
Nota che pipelining e compagnia non sono roba non predicibile (specie su
architetture ben fatte). Solo sono roba da conoscere.


 percezione del problema migliore del compilatore. 
Ad esempio il programmatore può fare delle assunzioni che per il 
compilatore sarebbe impossibile fare. Ad esempio può sapere a priori che 
un certo dato passato ad una funzione può assumere solo certi valori ben 
determinati.
Oppure un altro caso potrebbe essere:
switch(x) {
	case 0:
		// bla bla bla...
	break;
	case 1:
		// blu blu blu...
	break;
	case 2:
		// bli bli bli...
	break;
	....
}
il compilatore non può sapere con quale frequenza la x può assumere i 
vari valori. Ma il programmatore potrebbe sapere, ad esempio, che il 
valore 42 capita in media nel 50% dei casi. Allora sarebbe (forse!) più 
opportuno fare:
if (x==42) {
	...
} else {
	switch(x) {
	};
}
E.