[C] Valore assoluto di un numero + velocemente possibile

[MFSPO=DBGPOF]

Ho chiesto, e pare che così è meglio:

int abs(int x)

{
	return ((x^(x>>31))-(x>>31));
}

[Ufo13]

Originariamente inviato da MFSPO=DBGPOF

Ho chiesto, e pare che così è meglio:

int abs(int x)

{
	return ((x^(x>>31))-(x>>31));
}

cross platform soprattutto

[MFSPO=DBGPOF]

Originariamente inviato da Ufo13

cross platform soprattutto

vabbe, metto a posto

int abs(int x)

{
	return ((x^(x>>((sizeof(int)<<3)-1)))-(x>>((sizeof(int)<<3)-1)));
}

Contento?

[gugoXX]

Guardate che io avevo barato.
L'implementazione piu' veloce e' esattamente quella che abbiamo imparato, ovvero usare la
funzione gia' disponibile nella stdlib.h (e nella math.h)

Ovvero
int abs(int x)
gia' dichiarata e pronta per tutti.

Il mio codice infatti non era altro che il Disassembly del codice generato da tale funzione.

Fra l'altro il codice generato dalla soluzione di MFSPO=DBGPOF e' easttamente equivalente, a parte il
CDQ generato dalla ABS di libreria
e il (SAR registro,31) generato dalla soluzione.
entrambi vogliono riempire un registro con quello che e' il bit piu' significativo, ovvero il segno, della nostra variabile in questione.

Usare la ABS di libreria secondo me e' quindi piu' veloce, piu' leggibile e piu' cross-platform di qualunque altro metodo.

[MFSPO=DBGPOF]

Originariamente inviato da gugoXX

Guardate che io avevo barato.
L'implementazione piu' veloce e' esattamente quella che abbiamo imparato, ovvero usare la
funzione gia' disponibile nella stdlib.h (e nella math.h)

Ovvero
int abs(int x)
gia' dichiarata e pronta per tutti.

Il mio codice infatti non era altro che il Disassembly del codice generato da tale funzione.

Fra l'altro il codice generato dalla soluzione di MFSPO=DBGPOF e' easttamente equivalente, a parte il
CDQ generato dalla ABS di libreria
e il (SAR registro,31) generato dalla soluzione.
entrambi vogliono riempire un registro con quello che e' il bit piu' significativo, ovvero il segno, della nostra variabile in questione.

Usare la ABS di libreria secondo me e' quindi piu' veloce, piu' leggibile e piu' cross-platform di qualunque altro metodo.

Quoto gugoXX. Ho disassemblato la abs(x) della stdlib.h, e il codice x86 generato è pari pari quello proposto da gugoXX. La abs() di stdlib.h è la più veloce possibile.

[Mr. X]

Ragazzi vedo che vi siete impegnati per darmi la soluzione...
Ovviamente ho fatto un attento profiling ed il collo di bottiglia è proprio il calcolo del valore assoluto che è da calcolarsi il più velocemente possibile... Ho provato anche ad utilizzare la funzione abs di libreria come dite voi ma la LUT continua ad essere la soluzione più veloce...

[cionci]

Mi spieghi come hai fatto la lookup table per l'abs ?

[Mr. X]

Originariamente inviato da cionci

Mi spieghi come hai fatto la lookup table per l'abs ?

siccome il mio numero da "assolutizzare" va da -23000 a +23000 per ognuno di quesi numeri mi sono fatto una tabella lunga 46001 elementi mettendoci il risultato. Questa tabella l'ho generata con Matlab su un file di testo che poi ho dato in pasto al C.

[cionci]

Sicuramente è molto veloce, ma fare il quadrato e poi la divisione era molto più lento ?

[Mr. X]

Originariamente inviato da cionci

Sicuramente è molto veloce, ma fare il quadrato e poi la divisione era molto più lento ?

Guarda ti faccio un piccolo schema:

Funzione abs di libreria => 16ms
Mia funzione citata nel primo post => 14ms
Quadrato e poi divisione => 13ms
LUT => 9ms

Se consideri che tale algoritmo lo voglio fare in real-time anche se formalmente più brutto preferisco la LUT.

[cionci]

In real time intendi in so real time ? In tal caso ti capisco

[^TiGeRShArK^]

Originariamente inviato da Mr. X

Guarda ti faccio un piccolo schema:

Funzione abs di libreria => 16ms
Mia funzione citata nel primo post => 14ms
Quadrato e poi divisione => 13ms
LUT => 9ms

Se consideri che tale algoritmo lo voglio fare in real-time anche se formalmente più brutto preferisco la LUT.

ma non è tantissimo 9ms?
...spero che non sia per un'esecuzione sola...

[gugoXX]

Originariamente inviato da Mr. X

siccome il mio numero da "assolutizzare" va da -23000 a +23000 per ognuno di quesi numeri mi sono fatto una tabella lunga 46001 elementi mettendoci il risultato. Questa tabella l'ho generata con Matlab su un file di testo che poi ho dato in pasto al C.

La prossima volta spiega bene il problema allora.
46KB*4 di memoria non sono nulla
4GB*4 potrebbero esserlo.

Nelle valutazioni quantitative devi anche considerare che quella lookup table sono sempre 200KB di cache che usi solo per il calcolo del valore assoluto, e che potrebbero essere usati per altro.

[^TiGeRShArK^]

Originariamente inviato da ^TiGeRShArK^

ma non è tantissimo 9ms?
...spero che non sia per un'esecuzione sola...

ho fatto una semplicissima prova in ruby sul mio A64 3000+@4000+ (2520mhz e RAM 186 mhz se non sbaglio):

startTime = Time.new
for i in 0..1000000
  a = -2.abs
end
puts Time.new - startTime

risultato... 350 msec per un milione di iterazioni....
e ruby è notoriamente molto lento come implementazione (ho usato la versione 1.8.6 non la ben + veloce 1.9.0 )

[Mr. X]

Originariamente inviato da cionci

In real time intendi in so real time ? In tal caso ti capisco

Esatto

[Mr. X]

Originariamente inviato da ^TiGeRShArK^

ma non è tantissimo 9ms?
...spero che non sia per un'esecuzione sola...

9ms impiega tutto l'algoritmo al cui interno ci sono diverse migliaia di valori assoluti

[Mr. X]

Originariamente inviato da gugoXX

La prossima volta spiega bene il problema allora.
46KB*4 di memoria non sono nulla
4GB*4 potrebbero esserlo.

Nelle valutazioni quantitative devi anche considerare che quella lookup table sono sempre 200KB di cache che usi solo per il calcolo del valore assoluto, e che potrebbero essere usati per altro.

Ti ringrazio per la precisazione. Anche se prendesse 200KB di cache preferisco la velocità.

[gugoXX]

Originariamente inviato da ^TiGeRShArK^

ho fatto una semplicissima prova in ruby sul mio A64 3000+@4000+ (2520mhz e RAM 186 mhz se non sbaglio):

startTime = Time.new
for i in 0..1000000
  a = -2.abs
end
puts Time.new - startTime

risultato... 350 msec per un milione di iterazioni....
e ruby è notoriamente molto lento come implementazione (ho usato la versione 1.8.6 non la ben + veloce 1.9.0 )

Occhio, non conosco Ruby, ma il C++ in quel caso avrebbe saltato la valutazione dell'ABS.
Avrebbe messo direttamente +2 nella variabile a.
Anzi, se tutto va bene, dato che la variabile a non e' usata, avrebbe proprio saltato tutta la riga...

[gugoXX]

Originariamente inviato da Mr. X

Ti ringrazio per la precisazione. Anche se prendesse 200KB di cache preferisco la velocità.

Chiaro.
Quello che dico e' che nel complesso mangiare 200KB di cache potrebbe rallentare il sistema. Valuta bene.
Poi a me vedere un array che nella cella 1 c'e' scritto 1
nella cella 2 c'e' scritto 2
nella cella X c'e' scritto X
Mi fa irritare un po'... ma passa subito non preoccuparti.

[Mr. X]

Originariamente inviato da gugoXX

Chiaro.
Quello che dico e' che nel complesso mangiare 200KB di cache potrebbe rallentare il sistema. Valuta bene.
Poi a me vedere un array che nella cella 1 c'e' scritto 1
nella cella 2 c'e' scritto 2
nella cella X c'e' scritto X
Mi fa irritare un po'... ma passa subito non preoccuparti.