[Vari] Context 1: Bitmap

[gugoXX]

Volevo aprire una serie di topic con alcuni esercizi che possono essere interessanti.
L'idea sarebbe quella di proporre una soluzione efficiente, indipendentemente dal linguaggio. Ovvero concentrandosi sugli algoritmi piuttosto che sulla implementazione nel linguaggio X.
Ovvio che poi soluzioni eleganti in ciascun linguaggio sono apprezzate.

Sia data una bitmap 1000x1000x8bit di profondita', immaginatela a toni di grigio, e codificatela come meglio vi aggrada o come il linguaggio propone.
Una matrice bidimensionale di byte e' considerata sufficiente, anche se non e' proprio una bitmap.
Si vorrebbe invertire l'ordine dei bit di ciascun byte di colore, effettuando in pratica uno specchio di ciascun byte, nel modo piu' efficiente.
Esempio 10001101 diventa 10110001, 00111101 diventa 10111100 e cosi' via.

Non e' richiesta la lettura di file o tantomeno la lettura di file tipizzati (gif, jpg, etc.), introducente l'input come meglio aggrada (certo che se si leggesse da file sarebbe meglio).

[^TiGeRShArK^]

mmm...
ma per invertire ogni byte di colore non si dovrebbe fare 255 - il valore del byte? :mbe:
perchè nel post di sopra rivolti il byte anzichè fare 255 - byte? :fagiano:

[gugoXX]

mmm...
ma per invertire ogni byte di colore non si dovrebbe fare 255 - il valore del byte? :mbe:
perchè nel post di sopra rivolti il byte anzichè fare 255 - byte? :fagiano:

Si', hai ragione, non e' il negativo. E' un inverso che non ha forse molto senso colorimetrico.

Se c'e' 10010000 diventa 00001001

Alcuni che sono gia' di natura simmetrici restano cosi' come sono:
00011000 -> 00011000

[^TiGeRShArK^]

la soluzione + veloce in assoluto mi sa che è specificare l'endianess dei byte della matrice, ma non so se è possibile nei vari linguaggi...
altirmenti la prima che viene in mente è semplicemente prendere i bit ad uno ad uno e copiarli in un'altro byte in ordine inverso.

[banryu79]

altirmenti la prima che viene in mente è semplicemente prendere i bit ad uno ad uno e copiarli in un'altro byte in ordine inverso.

Durante l'iterazione della matrice inserirei i risultati in una Hash Map dove la chiave è il byte originale e il valore il byte invertito: se il prossimo elemento da processare è già presente nell'hash map non occorre ricalcolarlo.

Probabilmente non è il massimo dell'efficienza ma potrebbe avere un senso all'aumentare delle dimensioni della matrice (della bitmap) ?

[^TiGeRShArK^]

Durante l'iterazione della matrice inserirei i risultati in una Hash Map dove la chiave è il byte originale e il valore il byte invertito: se il prossimo elemento da processare è già presente nell'hash map non occorre ricalcolarlo.

Probabilmente non è il massimo dell'efficienza ma potrebbe avere un senso all'aumentare delle dimensioni della matrice (della bitmap) ?

mmm..vero, tanto hai solo 256 valori possibili e quindi aumenteresti l'efficenza di molto :p
Chissà come fanno a i vari linguaggi a gestire l'endianess ora che ci penso :mbe:

[banryu79]

Chissà come fanno a i vari linguaggi a gestire l'endianess ora che ci penso :mbe:
Non ne so nulla :boh:

[marco.r]

Durante l'iterazione della matrice inserirei i risultati in una Hash Map dove la chiave è il byte originale e il valore il byte invertito: se il prossimo elemento da processare è già presente nell'hash map non occorre ricalcolarlo.

Probabilmente non è il massimo dell'efficienza ma potrebbe avere un senso all'aumentare delle dimensioni della matrice (della bitmap) ?

Perchè una Hash Map ? :mbe:
Ti basta un array come cache

[banryu79]

Perchè una Hash Map ? :mbe:
Ti basta un array come cache
Perchè non ci ho pensato a fondo, sono in ufficio, ho letto il post e ho scritto la prima cosa che mi è saltata in mente dopo aver letto la risposta di TigerShark.
Inoltre non ho esperienze solide con queste cose.

Inoltre stavo pensando in Java: le HashMap sono comode.

Come faresti con un unico array?

[^TiGeRShArK^]

Perchè non ci ho pensato a fondo, sono in ufficio, ho letto il post e ho scritto la prima cosa che mi è saltata in mente dopo aver letto la risposta di TigerShark.
Inoltre non ho esperienze solide con queste cose.

Inoltre stavo pensando in Java: le HashMap sono comode.

Come faresti con un unico array?

con l'array basterebbe creare un array di byte con 256 celle e mettere il byte rivoltato nella cella corrispondente al suo reciproco..

tipo se hai il byte 000000001 scriverai nell'indice 1 dell'array il byte 10000000 :p

[marco.r]

Visto che hai solo 8 bit di valori, usi un array con 256 elementi

Qualcosa come il seguente (in C++)

typedef unsigned char uchar8; // o quel che è

uchar8 b0 = 1,
b1=2,
b2=4,
b3=8,
b4=16,
b5=32,
b6=64,
b7=128;

uchar8 invert( uchar8 x )
{
return ((x&b0)<<7) + ((x&b1) << 5) + ((x&b2) << 3) + ((x&b3) << 1)
+((x&b4)>>1) + ((x&b5) >> 3) + ((x&b6) >> 5) + ((x&b7) >> 7);
}

void invertMatrix( uchar8** matrix, int rows, int cols )
{
uchar8 inverted[256];
for ( int i=0 ; i< 256 ; ++i )
{
inverted[i] = invert(i);
}
for ( int i=0 ; i<rows ; ++i )
{
for ( int j=0 ; j<cols ; ++j )
{
matrix[i][j] = inverted[ matrix[i][j] ];
}
}
}

[banryu79]

Geniale, stavo provando a rifletterci e appunto a capire come mappare l'indice dell'array con il byte originale.
Molto meglio della soluzione con l'hashmap, grazie per la spiegazione :)

OT:
se la Bitmap fosse a profondità maggiore, diciamo 16 bit, come faresti?

Non capisco bene questo:

uchar8 invert( uchar8 x )
{
return ((x&b0)<<7) + ((x&b1) << 5) + ((x&b2) << 3) + ((x&b3) << 1)
+((x&b4)>>1) + ((x&b5) >> 3) + ((x&b6) >> 5) + ((x&b7) >> 7);
}

Conosco il significato degli opertori bitwise ma non avendoli mai usati ne scritto algoritmi con essi stento a interpretare tutta l'operazione.
Se hai tempo e puoi spiegarlo mi faresti un favore, sennò me lo guardo con calma stasera.

[^TiGeRShArK^]

Geniale, stavo provando a rifletterci e appunto a capire come mappare l'indice dell'array con il byte originale.
Molto meglio della soluzione con l'hashmap, grazie per la spiegazione :)

OT:
se la Bitmap fosse a profondità maggiore, diciamo 16 bit, come faresti?

Non capisco bene questo:

Conosco il significato degli opertori bitwise ma non avendoli mai usati ne scritto algoritmi con essi stento a interpretare tutta l'operazione.
Se hai tempo e puoi spiegarlo mi faresti un favore, sennò me lo guardo con calma stasera.

ricava il bit 0 facendo un and con 1 e lo shifta di 7 a sinistra in modo da mandarlo al posto del bit + significativo, prende il bit 1 e fa la stessa cosa, ma poichè è + vicino di uno al centro e poichè lo deve spostare nella posizione del bit + significativo - 1 allora è sufficiente spostarlo di 5.
Lo stesso fa con gli altri bit e infine somma il risultato :p

[Big Bamboo]

Forse per invertire è meglio fare a gruppi di bit invece che singoli

inverto prima i 4 bit destra - sinistra
byte = (byte & 0x0F) << 4 | (byte & 0xF0) >> 4;

poi con 2 maschere sposti 2 bit per ogni lato
byte = (byte & 0x33) << 2 | (byte & 0xCC) >> 2;

ed infine i singoli bit
byte = (byte & 0x55) << 1 | (byte & 0xAA) >> 1;

Con il codice assembler si potrebbe effettivamente valutare la soluzione migliore

[gugoXX]

Dai vabbene.
Questo era il riscaldamento e ovviamente abbiamo trovato la soluzione ottima (ovviamente O(N) dove N e' il numero di pixel), e anche l'algoritmo corretto, ovvero usare un array.

Direi che si puo' riassumere con
Quando vangono utilizzati molti se non tutti i valori possibili di un range di dominio, allora e' bene usare un array, altrimenti una hastable.

Ottimo anche l'algoritmo per trovare lo speculare di un byte, che con una manciata di istruzioni senza cicli e senza salti ottiene subito il risultato.

Passiamo oltre.

[^TiGeRShArK^]

Dai vabbene.
Questo era il riscaldamento e ovviamente abbiamo trovato la soluzione ottima (ovviamente O(N) dove N e' il numero di pixel), e anche l'algoritmo corretto, ovvero usare un array.

Direi che si puo' riassumere con
Quando vangono utilizzati molti se non tutti i valori possibili di un range di dominio, allora e' bene usare un array, altrimenti una hastable.

Ottimo anche l'algoritmo per trovare lo speculare di un byte, che con una manciata di istruzioni senza cicli e senza salti ottiene subito il risultato.

Passiamo oltre.

:D

Bene, avanti così! :D

:asd:

[Oceans11]

mmm...
ma per invertire ogni byte di colore non si dovrebbe fare 255 - il valore del byte? :mbe:
perchè nel post di sopra rivolti il byte anzichè fare 255 - byte? :fagiano:

ehm...scusate raga....ma dove fate 255-byte????
scrivere il byte da destra verso sinistra mica funziona!?!

Non ci vuole: byte XOR 0xFF???

Premetto che la soluzione con gli shift mi ha ingrippato parecchio....:muro:

[marco.r]

Geniale, stavo provando a rifletterci e appunto a capire come mappare l'indice dell'array con il byte originale.
Molto meglio della soluzione con l'hashmap, grazie per la spiegazione :)

OT:
se la Bitmap fosse a profondità maggiore, diciamo 16 bit, come faresti?

Con 16 bit ancora ti conviene usare la stessa tecnica 2^16 = 65k byte di memoria per l'array, praticamente niente. Ovviamente se l'array e' piu' grande, altrimenti non serve a niente :D.
Se i valori sono maggiori penso abbia senso utilizzare comunque una tabella piu' piccola e "cachare" a pezzi.
Ad esempio usando qualcosa tipo

makeUint32( uchar8 x3, uchar8 x2, uchar8 x1, uchar8 x0 )
{
return (x3<<24) + (x2<<16) + (x1<<8) + x0;
}

uchar8 byte(int n,uint32 x)
{
return (x & (0xff << (n*8))) >> (n*8);
}

/* ... prepara la tabella inverted come sopra ... */

uint32 invert32( uint32 x)
{
return makeUint32( inverted[byte(3,x)], inverted[byte(2,x)], inverted[byte(1,x)], inverted[byte(0,x)]);
}

O qualcosa del genere (disclaimer: non ho provato il codice :p).
Magari si puo' scrivere lo smistamento dei vari bit in modo piu' veloce (non e' una cosa di cui mi occupo abitualmente), ma l'idea e' comunque quella.

[^TiGeRShArK^]

ehm...scusate raga....ma dove fate 255-byte????
scrivere il byte da destra verso sinistra mica funziona!?!

Non ci vuole: byte XOR 0xFF???

Premetto che la soluzione con gli shift mi ha ingrippato parecchio....:muro:

infatti non lo facciamo in nessun posto :p
gugoxx intendeva che bisognava invertire il byte NON in senso colorimetrico (che si ottiene con 255 - byte), ma bisognava fare un mirror del byte attorno all'asse centrale...
ad esempio 10000000 diventa 00000001, 01000000 diventa 00000010 e così via :p

[Vincenzo1968]

È ancora valido questo contest? Posso postare la mia soluzione?

Ciao

[Furla]

#dichiarazione nel sorgente .cpp: extern "C" char invert(char);
#file .s:
.global _invert
_invert:
push %EBP
mov %ESP, %EBP

mov 8(%EBP),%AH
mov $7,%CL
c: rcl $1,%AH
rcr $1,%AL
dec %CL
jge c

mov %EBP, %ESP
pop %EBP
ret

più ottimizzato di così non esiste, assembly powah!

[Vincenzo1968]

Con una matrice 1000x1000 ottengo un tempo di 0ms. Con una di 10000x10000 il tempo è 250ms


#include <stdio.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

#define BITS_PER_CHAR 8

BYTE ReverseBits(BYTE b)
{
BYTE ret = b;
int s = sizeof(b) * BITS_PER_CHAR - 1;

for (b >>= 1; b; b >>= 1)
{
ret <<= 1;
ret |= b & 1;
s--;
}
ret <<= s;

return ret;
}

int main()
{
int r, c;
int x;

DWORD ms1, ms2;

BYTE **a;

r = RIGHE;
c = COLONNE;

a = (BYTE**)malloc(sizeof(BYTE*)*r);
if ( a != NULL )
{
for ( x = 0; x < r; x++ )
{
a[x] = (BYTE*)malloc(sizeof(BYTE)*c);
if ( a[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return -1;
}

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = 1;

printf("\nbyte -> %d\n", a[RIGHE - 1][COLONNE - 1]);
ms1 = GetTickCount();
for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = ReverseBits(a[r][c]);
ms2 = GetTickCount();
printf("byte -> %d\n", a[RIGHE - 1][COLONNE - 1]);
printf("Temp impiegato -> %d\n\n", ms2 - ms1);

for ( x = 0; x < r; x++ )
free(a[x]);
free(a);

return 0;
}

[Vincenzo1968]

Chissà come fanno a i vari linguaggi a gestire l'endianess ora che ci penso :mbe:

in C è semplice:


#include <stdio.h>

typedef unsigned char BYTE;
typedef unsigned short WORD;

typedef int BOOL;

#define TRUE 1
#define FALSE 0

BOOL IsLittleEndian()
{
WORD wParola = 0x0001;
BYTE *b = (BYTE*)&wParola;

return (b[0] ? TRUE : FALSE);
}

WORD SwapTwoBytes(WORD w)
{
register WORD tmp;

tmp = (w & 0x00FF);
tmp = ((w & 0xFF00) >> 0x08) | (tmp << 0x08);

return tmp;
}

int main()
{
WORD wParola = 0x0001;
BYTE *b = (BYTE*)&wParola;

short in;
short swapped;

// Utilizziamo la funzione IsLittleEndian per verificare se
// la macchina nella quale gira questo programma adotta il
// formato little-endian o big-endian.
printf("Questa macchina adotta il formato %s-endian\n\n",
IsLittleEndian() ? "little" : "big");

printf("Il numero esadecimale 0x0001, e' cosi' rappresentato: %02X%02X\n\n", b[0], b[1]);

wParola = 0x3412;
printf("Il numero esadecimale 0x3412, e' cosi' rappresentato: %02X%02X\n\n", b[0], b[1]);

wParola = SwapTwoBytes(wParola);
printf("Il numero dopo lo scambio -> %02X%02X\n\n", b[0], b[1]);

return 0;
}

[Vincenzo1968]

Lo stesso algoritmo, in C#, impiega 875ms.
Questo è il codice:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Contest1
{
class Program
{
static private int Righe = 10000;
static private int Colonne = 10000;

static private byte ReverseBits(byte b)
{
byte ret = b;
int s = 7;

for (b >>= 1; b > 0; b >>= 1)
{
ret <<= 1;
ret |= (byte)(b & 1);
s--;
}
ret <<= s;

return ret;
}

static void Main(string[] args)
{
int r, c;
byte[,] a = new byte[Righe, Colonne];

r = Righe;
c = Colonne;

for (r = 0; r < Righe; r++)
for (c = 0; c < Colonne; c++)
a[r,c] = 1;

Console.WriteLine("byte -> {0}", a[Righe - 1, Colonne - 1]);
Stopwatch watch = new Stopwatch();
watch.Start();

for (r = 0; r < Righe; r++)
for (c = 0; c < Colonne; c++)
a[r,c] = ReverseBits(a[r,c]);

watch.Stop();
Console.WriteLine("byte -> {0}", a[Righe - 1, Colonne - 1]);
Console.WriteLine("Tempo impiegato -> {0}", watch.ElapsedMilliseconds);
}
}
}

[VICIUS]

#dichiarazione nel sorgente .cpp: extern "C" char invert(char);
#file .s:
.global _invert
_invert:
push %EBP
mov %ESP, %EBP

mov 8(%EBP),%AH
mov $7,%CL
c: rcl $1,%AH
rcr $1,%AL
dec %CL
jge c

mov %EBP, %ESP
pop %EBP
ret

più ottimizzato di così non esiste, assembly powah!
Prova a dare un occhiata a sse. Con registri a 128bit dovresti riuscire ad invertire 16 pixel per volta.

[cdimauro]

Mi sono perso questo interessante thread. :muro:

Rispondo soltanto a questo:

#dichiarazione nel sorgente .cpp: extern "C" char invert(char);
#file .s:
.global _invert
_invert:
push %EBP
mov %ESP, %EBP

mov 8(%EBP),%AH
mov $7,%CL
c: rcl $1,%AH
rcr $1,%AL
dec %CL
jge c

mov %EBP, %ESP
pop %EBP
ret

più ottimizzato di così non esiste, assembly powah!
Certo che esiste: basta usare il loop unrolling:

#dichiarazione nel sorgente .cpp: extern "C" char invert(char);
#file .s:
.global _invert
_invert:
push %EBP
mov %ESP, %EBP

mov 8(%EBP),%AH
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL
rcl $1,%AH
rcr $1,%AL

mov %EBP, %ESP
pop %EBP
ret
In questo modo eviti di stallare la pipeline del processore.

Comunque a questa soluzione che esegue tante istruzioni interdipendenti preferisco sempre la LUT (LookUp Table): 256 byte (meglio se allineati a 128 o 256 bit, a seconda dell'architettura della CPU) stanno sempre nella cache dati di primo livello, per cui in pochi cicli si ottiene il risultato.

Per il resto concordo con Marco: per questo tipo di problemi generalmente le LUT rappresentano un'ottima ed efficiente soluzione.

E concordo pure con VICIUS: con le SSE si possono convertire blocchi di 16 byte alla volta. ;)

[Furla]

#dichiarazione nel sorgente .cpp: extern "C" short int invert(short int);
#file .s:
.global _invert
_invert:
.global _inv #extern "C" int _inv(int)
_inv:
mov 4(%ESP),%EBX
mov $31,%CL
c: rcl $1,%EBX
rcr $1,%EAX
dec %CL
jge c

rol $8,%AX # xchg %AL,%AH
rol $16,%EAX # xchg %AX,%AY dove %AY è la metà alta di %EAX
rol $8,%AX # xchg %AL,%AH

ret

ok dai, divertiamoci a fare gli estremi :D
lasciamo perdere %EBP tanto non lo usiamo, e ribaltiamo 4 byte alla volta, con lo stesso sistema si possono macinare 8 byte a botta usando le istruzioni a 64 bit (che ancora non conosco -.-); non conosco nemmeno le sse, cmq ora vado a documentarmi...
ovviamente srotolando si guadagna un po', in questo caso sono 64 istruzioni, non so se conviene già un unroll parziale e farne 8 o 16 alla volta (non mi intendo né di pipeline né di prefetch, ancora^^)
per la lookup non saprei, bisognerebbe fare delle prove, ma per fare in modo che siano attendibili bisognerebbe allinearla... come si fa a dirlo al compilatore? :D

[Vincenzo1968]

A me la versione con lookup table risulta un po' piu lenta(360ms contro 250ms) anche spostando la costruzione della tabella al di fuori della funzione invertMatrix:


#include <stdio.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

typedef unsigned char uchar8; // o quel che è

uchar8 b0 = 1,
b1=2,
b2=4,
b3=8,
b4=16,
b5=32,
b6=64,
b7=128;

uchar8 invert( uchar8 x )
{
return ((x&b0)<<7) + ((x&b1) << 5) + ((x&b2) << 3) + ((x&b3) << 1)
+((x&b4)>>1) + ((x&b5) >> 3) + ((x&b6) >> 5) + ((x&b7) >> 7);
}

void invertMatrix( uchar8** matrix, uchar8* inverted, int rows, int cols )
{
int i, j;
for ( i=0 ; i<rows ; ++i )
{
for ( j=0 ; j<cols ; ++j )
{
matrix[i][j] = inverted[ matrix[i][j] ];
}
}
}

int main()
{
int r, c;
int x;

DWORD ms1, ms2;

uchar8 inverted[256];
BYTE **a;

r = RIGHE;
c = COLONNE;

for ( x = 0; x < 256; ++x )
inverted[x] = invert(x);

a = (BYTE**)malloc(sizeof(BYTE*)*r);
if ( a != NULL )
{
for ( x = 0; x < r; x++ )
{
a[x] = (BYTE*)malloc(sizeof(BYTE)*c);
if ( a[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return -1;
}

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = 1;

printf("\nbyte -> %d\n", a[RIGHE - 1][COLONNE - 1]);
ms1 = GetTickCount();
invertMatrix(a, inverted, RIGHE, COLONNE);
ms2 = GetTickCount();
printf("byte -> %d\n", a[RIGHE - 1][COLONNE - 1]);
printf("Temp impiegato -> %d\n\n", ms2 - ms1);

for ( x = 0; x < r; x++ )
free(a[x]);
free(a);

return 0;
}

[cdimauro]

#dichiarazione nel sorgente .cpp: extern "C" short int invert(short int);
#file .s:
.global _invert
_invert:
.global _inv #extern "C" int _inv(int)
_inv:
mov 4(%ESP),%EBX
mov $31,%CL
c: rcl $1,%EBX
rcr $1,%EAX
dec %CL
jge c

rol $8,%AX # xchg %AL,%AH
rol $16,%EAX # xchg %AX,%AY dove %AY è la metà alta di %EAX
rol $8,%AX # xchg %AL,%AH

ret

ok dai, divertiamoci a fare gli estremi :D
lasciamo perdere %EBP tanto non lo usiamo, e ribaltiamo 4 byte alla volta,
Se vogliamo "ottimizzare a tutti i costi", allora le 3 ROL alla fine per eseguire il byte-swap le puoi benissimo sostituire con la sola istruzione BSWAP EAX. :cool:
con lo stesso sistema si possono macinare 8 byte a botta usando le istruzioni a 64 bit (che ancora non conosco -.-);
Non ti preoccupare: sono le stesse, a parte che i registri li chiami RAX, RBX, ecc., oppure R0, R1, ..., R15. :D
non conosco nemmeno le sse, cmq ora vado a documentarmi...
Per questo tipo di applicazione non dovrai perderci tanto tempo per studiarti le SSE.
ovviamente srotolando si guadagna un po', in questo caso sono 64 istruzioni, non so se conviene già un unroll parziale e farne 8 o 16 alla volta (non mi intendo né di pipeline né di prefetch, ancora^^)
Puoi provare entrambe le versioni. :)
per la lookup non saprei, bisognerebbe fare delle prove, ma per fare in modo che siano attendibili bisognerebbe allinearla... come si fa a dirlo al compilatore? :D
Dipende dal compilatore: alcuni hanno apposite direttive, altri no e devi fare a manina.

In quest'ultimo caso puoi provare così (per allinearlo a 128 bit = 16 byte):
uchar8 *p;
(uchar8 *) p = malloc(256 + 16);
p = (uchar8 *) ((((int) p + 16) & ~15);
Convertire un puntatore in intero, lavorarci, e poi riconvertirlo in puntatore è una cosa che personalmente ODIO (a proposito: si potrebbe sprecare meno memoria allocando 256 + 15 byte, ma poi ci sono dei controlli in più da fare per allineare il puntatore a 16 byte).
A me la versione con lookup table risulta un po' piu lenta(360ms contro 250ms) anche spostando la costruzione della tabella al di fuori della funzione invertMatrix:
E' una cosa che onestamente mi sorprende.

Potresti provare ad allocare la LUT allineandola a 128 bit, come ho suggerito sopra?

Guardando le soluzioni proposte finora mi sono accorto di una banale ottimizzazione applicabile a tutti gli esempi: per il tipo di problema non è necessario considerare l'immagine come matrice bidimensionale, ma la si può trattare tranquillamente come un vettore, risparmiando quindi il codice per eseguire righe e colonne. ;)

[rеpne scasb]

Direi di utilizzare questo (linguaggio C):


#include <stdio.h>

void main(void)

{
unsigned char lut[256],*bitmap;
int i,j,bitmap_len;

/*
Il vettore 'bitmap' risulta riempito con i valori della bitmap
La variabile 'bitmap_len' riporta la lunghezza in byte della bitmap
*/

for(i=0;i<256;i++)
{
for(lut[i]=j=0;j<8;j++)
{
if(i&(1<<j))
lut[i]|=1<<(7-j);
}
}

for(i=0;i<bitmap_len;i++)
bitmap[i]=lut[bitmap[i]];

}


Per l'assembly x86-32 curiosamente, su architettura Intel-Core, questo codice:


cld
mov esi,OFFSET bitmap
mov edi,esi
mov ebx,OFFSET lut
mov ecx,[bitmap_len]
loop_bitmap:
lodsb
xlatb
stosb
loop loop_bitmap


risulta piu' veloce di questo:


mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
mov [esi],dl
inc esi
dec ecx
jne loop_bitmap

[rеpne scasb]

Guardando le soluzioni proposte finora mi sono accorto di una banale ottimizzazione applicabile a tutti gli esempi: per il tipo di problema non è necessario considerare l'immagine come matrice bidimensionale, ma la si può trattare tranquillamente come un vettore, risparmiando quindi il codice per eseguire righe e colonne. ;)

Giuro che quanto ho proposto il mio esempio in C, non avevo ancora guardato il tuo intervento ;)

[cdimauro]

Per l'assembly x86-32 curiosamente, su architettura Intel-Core, questo codice:


cld
mov esi,OFFSET bitmap
mov edi,esi
mov ebx,OFFSET lut
mov ecx,[bitmap_len]
loop_bitmap:
lodsb
xlatb
stosb
loop loop_bitmap


risulta piu' veloce di questo:


mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
mov [esi],dl
inc esi
dec ecx
jne loop_bitmap

E' un risultato assolutamente controintuivo, per quanto mi riguarda: il primo codice è pieno di istruzioni "legacy" - che fanno uso di micro-op "lunghe" e, suppongo, microcodice. :stordita:

[rеpne scasb]

E' un risultato assolutamente controintuivo, per quanto mi riguarda: il primo codice è pieno di istruzioni "legacy" - che fanno uso di micro-op "lunghe" e, suppongo, microcodice. :stordita:

Esatto. Ed infatti non me lo spiego. Il primo codice, l'ho scritto proprio per vedere quanto fosse piu' lento rispetto al secondo. Sto comunque riarrangiando il secondo codice per vedere se riesco a rosicchiare qualcosa.

UPDATE: Questo nuovo codice 2 e' piu' veloce del codice 1:


mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
inc esi
dec ecx
mov [esi-1],dl
jne loop_bitmap

[^TiGeRShArK^]

E' un risultato assolutamente controintuivo, per quanto mi riguarda: il primo codice è pieno di istruzioni "legacy" - che fanno uso di micro-op "lunghe" e, suppongo, microcodice. :stordita:

ecco.
questa discussione la linkerei a peppepz così finalmente capisce perchè un profiler è essenziale e scrivere codice basato su una supposizione del programmatore rischia di essere addirittura controproducente :D

[Vincenzo1968]

E' una cosa che onestamente mi sorprende.

Potresti provare ad allocare la LUT allineandola a 128 bit, come ho suggerito sopra?



Ciao cdimauro,

in effetti la funzione che utilizzo è più veloce solo se il byte contiene pochi bit impostati a 1. Inizializzando per esempio l'array non col valore 1(in binario = 00000001) ma col valore 229(in binario = 11100101) la mia versione risulta molto più lenta rispetto a quella con lookup table.

Questa è la mia versione con lookup table:


#include <stdio.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

static const BYTE BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

int main()
{
int r, c;
int x;

DWORD ms1, ms2;

BYTE **a;

r = RIGHE;
c = COLONNE;

a = (BYTE**)malloc(sizeof(BYTE*)*r);
if ( a != NULL )
{
for ( x = 0; x < r; x++ )
{
a[x] = (BYTE*)malloc(sizeof(BYTE)*c);
if ( a[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return -1;
}

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = 229; /* in binario = 11100101 */

printf("\nbyte -> %d\n", a[RIGHE - 1][COLONNE - 1]);

ms1 = GetTickCount();

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = BitReverseTable[a[r][c]];

ms2 = GetTickCount();

/* Restituisce 167, in binario = 10100111 */
printf("byte -> %d\n", a[RIGHE - 1][COLONNE - 1]);

printf("Temp impiegato -> %d\n\n", ms2 - ms1);

for ( x = 0; x < r; x++ )
free(a[x]);
free(a);

return 0;
}


Ottengo un tempo di 266ms

Ciao.

[rеpne scasb]

Questa è la mia versione con lookup table:...[CUT]

Stai utilizzando una matrice bidimensionale. Per la cache del processore, nelle operzioni di lettura/scrittura, quando "salti" da una riga ad un'altra, avrai che la testa del vettore k(n), non e' fisicamente contigua con la coda del vettore k(n-1). Ossia l'accesso della matrice m[x][y] e' assai piu' lento dell'accesso del vettore m[x*y]. Utilizza un vettore ad un unica-dimensione.

[Vincenzo1968]

Stai utilizzando una matrice bidimensionale. Per la cache del processore, nelle operzioni di lettura/scrittura, quando "salti" da una riga ad un'altra, avrai che la testa del vettore k(n), non e' fisicamente contigua con la coda del vettore k(n-1). Ossia l'accesso della matrice m[x][y] e' assai piu' lento dell'accesso del vettore m[x*y]. Utilizza un vettore ad un unica-dimensione.

Ciao repne,

l'ho fatto ma il tempo peggiora: 360ms.

Questo è il codice:


#include <stdio.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

static const BYTE BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

int main()
{
int r, c;

DWORD ms1, ms2;

BYTE *a;

r = RIGHE;
c = COLONNE;

a = (BYTE*)malloc(sizeof(BYTE)*(r*c));
if ( !a )
{
printf("Memoria insufficiente.\n");
return -1;
}

for(r = 0; r < RIGHE * COLONNE; r++)
a[r] = 229; // in binario = 11100101

printf("\nbyte -> %d\n", a[(RIGHE * COLONNE) - 1]);

ms1 = GetTickCount();

for (r = 0; r < RIGHE * COLONNE; r++)
a[r] = BitReverseTable[a[r]];

ms2 = GetTickCount();

// Restituisce 167, in binario = 10100111
printf("byte -> %d\n", a[(RIGHE * COLONNE) - 1]);

printf("Temp impiegato -> %d\n\n", ms2 - ms1);

free(a);

return 0;
}

[cdimauro]

Esatto. Ed infatti non me lo spiego. Il primo codice, l'ho scritto proprio per vedere quanto fosse piu' lento rispetto al secondo. Sto comunque riarrangiando il secondo codice per vedere se riesco a rosicchiare qualcosa.

UPDATE: Questo nuovo codice 2 e' piu' veloce del codice 1:


mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
inc esi
dec ecx
mov [esi-1],dl
jne loop_bitmap

Mumble. Le cause potrebbero essere due: c'è uno stallo dovuto alla scrittura a [esi] troppo vicina alla lettura dello stesso (mi pare poco probabile, ma a questo punto... ogni ipotesi è lecita :D) oppure all'utilizzo del registro dl subito dopo che è stato modificato.

Potresti provare questo:

mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
dec ecx
mov [esi],dl
inc esi
jcxnz loop_bitmap

Così, tanto per vedere se otteniamo qualche altro risultato anomalo. :p
ecco.
questa discussione la linkerei a peppepz così finalmente capisce perchè un profiler è essenziale e scrivere codice basato su una supposizione del programmatore rischia di essere addirittura controproducente :D
Vero. Penso che in generale sia meglio lasciare al profiler questo compito. :D
Ciao cdimauro,

in effetti la funzione che utilizzo è più veloce solo se il byte contiene pochi bit impostati a 1. Inizializzando per esempio l'array non col valore 1(in binario = 00000001) ma col valore 229(in binario = 11100101) la mia versione risulta molto più lenta rispetto a quella con lookup table.
Potresti provare a riempire la bitmap di valori casuali?
Ciao repne,

l'ho fatto ma il tempo peggiora: 360ms.

Questo è il codice:
Azz. Un altro risultato controintuitivo. :p

Puoi provare ad allocare sia la LUT che la bitmap allineandole a 128 bit?

[Vincenzo1968]

Puoi provare ad allocare sia la LUT che la bitmap allineandole a 128 bit?

La LUT posso allinearla:


#define CACHE_LINE 16
#define CACHE_ALIGN __declspec(align(CACHE_LINE))

typedef CACHE_ALIGN struct { BYTE a; } S;

S BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};


ma con la bitmap come faccio, dato che la alloco dinamicamente?

[cdimauro]

Così:
BYTE *a;
a = (BYTE *) malloc(sizeof(BYTE) * (r * c) + 16);
a = (BYTE *) ((((int) a + 16) & ~15);

[Vincenzo1968]

I risultati non cambiano neanche inserendo valori casuali.

Questo e il codice per l'array bidimensionale:

#include <stdio.h>
#include <time.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

static const BYTE BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

void InitMatrix(int min, int max, BYTE **p)
{
int r, c;

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
p[r][c] = (BYTE)((double)rand() / (RAND_MAX + 1) * (max - min) + min);
}

int main()
{
int r, c;
int x;

clock_t start, end;

BYTE **a;
r = RIGHE;
c = COLONNE;

a = (BYTE**)malloc(sizeof(BYTE*)*r);
if ( a != NULL )
{
for ( x = 0; x < r; x++ )
{
a[x] = (BYTE*)malloc(sizeof(BYTE)*c);
if ( a[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return -1;
}

srand( (unsigned)time( NULL ) );
InitMatrix(0, 255, a);

printf("\nMatrice bidimensionale:\n\n");

printf("\nbyte -> %d\n", a[RIGHE - 1][COLONNE - 1]);

start = clock();

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = BitReverseTable[a[r][c]];

end = clock();

printf("byte -> %d\n", a[RIGHE - 1][COLONNE- 1]);

printf("Temp impiegato -> %2.5f secondi\n\n", (double)(end - start) / CLOCKS_PER_SEC);

for ( x = 0; x < r; x++ )
free(a[x]);
free(a);

return 0;
}


e questo è il risultato:
http://www.guidealgoritmi.it/images/ImgForums/Matrice01.jpg


Questo è il codice per l'array monodimensionale con allineamento a 128 bit:

#include <stdio.h>
#include <time.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

#define CACHE_LINE 16
#define CACHE_ALIGN __declspec(align(CACHE_LINE))

typedef CACHE_ALIGN struct { BYTE a; } S_BYTE;

S_BYTE BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

void InitMatrix(int min, int max, BYTE *p)
{
int r;
int x = RIGHE * COLONNE;

for(r = 0; r < x; r++)
p[r] = (BYTE)((double)rand() / (RAND_MAX + 1) * (max - min) + min);
}

int main()
{
int r, x;

clock_t start, end;

BYTE *a;

x = RIGHE * COLONNE;

a = (BYTE *) malloc(sizeof(BYTE) * x + 16);
if ( !a )
{
printf("Memoria insufficiente.\n");
return -1;
}
a = (BYTE *) (((int) a + 16) & ~15);

srand( (unsigned)time( NULL ) );
InitMatrix(0, 255, a);

printf("\nMatrice monodimensionale, allineamento a 16 byte:\n\n");

printf("\nbyte -> %d\n", a[x - 1]);

start = clock();

for (r = 0; r < x; r++)
a[r] = BitReverseTable[a[r]].a;

end = clock();

printf("byte -> %d\n", a[x - 1]);

printf("Temp impiegato -> %2.5f secondi\n\n", (double)(end - start) / CLOCKS_PER_SEC);

free(a);

return 0;
}


e questo è il risultato
http://www.guidealgoritmi.it/images/ImgForums/Matrice02.jpg

Ho eseguito le prove una ventina di volte per ogni versione; quella con array bidimensionale risulta sempre (e inspiegabilmente :eek: ) più veloce.

[cdimauro]

Forse il problema sta nella dichiarazione di
typedef CACHE_ALIGN struct { BYTE a; } S_BYTE;

S_BYTE BitReverseTable[] = {...}
Non dovresti definire il singolo elemento del vettore BitReverseTable come struttura allineata a 16 byte, ma dovrebbe essere l'intero vettore a essere allineato a 16 byte.

Qualcosa del tipo:
CACHE_ALIGN BYTE BitReverseTable[] = {...}
Ho il sospetto che la dichiazione che usavi vengano allocati 16 byte (allineati a 128 bit) per ogni elemento dell'array, anziché uno soltanto.

[Vincenzo1968]

Ho seguito il tuo suggerimento e adesso i tempi sono uguali per entrambe le versioni.


#include <stdio.h>
#include <time.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

#define CACHE_LINE 1
#define CACHE_ALIGN __declspec(align(CACHE_LINE))

CACHE_ALIGN BYTE BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

void InitMatrix(int min, int max, BYTE *p)
{
int r;
int x = RIGHE * COLONNE;

for(r = 0; r < x; r++)
p[r] = (BYTE)((double)rand() / (RAND_MAX + 1) * (max - min) + min);
}

int main()
{
int r, x;

clock_t start, end;

BYTE *a;

x = RIGHE * COLONNE;

a = (BYTE *) malloc(sizeof(BYTE) * x + CACHE_LINE);
if ( !a )
{
printf("Memoria insufficiente.\n");
return -1;
}
a = (BYTE *) (((int) a + CACHE_LINE) & ~(CACHE_LINE - 1));

srand( (unsigned)time( NULL ) );
InitMatrix(0, 255, a);

printf("\nMatrice monodimensionale, allineamento a 16 byte:\n\n");

printf("\nsizeof(a[0]) -> %d\n\n", sizeof(a[0]));
printf("\nsizeof(BitReverseTable[0]) -> %d\n\n", sizeof(BitReverseTable[0]));

printf("\nbyte -> %d\n", a[x - 1]);

start = clock();

for (r = 0; r < x; r++)
a[r] = BitReverseTable[a[r]];

end = clock();

printf("byte -> %d\n", a[x - 1]);

printf("Temp impiegato -> %2.5f secondi\n\n", (double)(end - start) / CLOCKS_PER_SEC);

free(a);

return 0;
}


La versione con array monodimensionale non dovrebbe essere comunque più veloce? :confused:

[cdimauro]

Sì, dovrebbe esserlo. Probabilmente la dimensione della bitmap non è abbastanza grande da mostrare risultati diversi (si potrebbe provare a ingrandire la bitmap, o a ripetere n volte l'operazione).

Comunque rimane ancora strano che la versione con la LUT sia veloce tanto quanto quella con la funzione che esegue i calcoli. :p

[rеpne scasb]

La versione con array monodimensionale non dovrebbe essere comunque più veloce? :confused:

Ed infatti e' circa il 35% piu' veloce. Anch'ho ho fatto qualche prova:

Ho usato questa tua versione per array bidimensionali:


#include <stdio.h>
#include <time.h>
#include <windows.h>

#define RIGHE 10000
#define COLONNE 10000

static const BYTE BitReverseTable[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

void InitMatrix(int min, int max, BYTE **p)
{
int r, c;

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
p[r][c] = (BYTE)((double)rand() / (RAND_MAX + 1) * (max - min) + min);
}

int main()
{
int r, c;
int x;

clock_t start, end;

BYTE **a;
r = RIGHE;
c = COLONNE;

a = (BYTE**)malloc(sizeof(BYTE*)*r);
if ( a != NULL )
{
for ( x = 0; x < r; x++ )
{
a[x] = (BYTE*)malloc(sizeof(BYTE)*c);
if ( a[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return -1;
}

srand( (unsigned)time( NULL ) );
InitMatrix(0, 255, a);

printf("\nMatrice bidimensionale:\n\n");

printf("\nbyte -> %d\n", a[RIGHE - 1][COLONNE - 1]);

start = clock();

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = BitReverseTable[a[r][c]];

end = clock();

printf("byte -> %d\n", a[RIGHE - 1][COLONNE- 1]);

printf("Temp impiegato -> %2.5f secondi\n\n", (double)(end - start) / CLOCKS_PER_SEC);

for ( x = 0; x < r; x++ )
free(a[x]);
free(a);

return 0;
}


Questo e' l'output sulla mia macchina:



Matrice bidimensionale:


byte -> 177
byte -> 141
Temp impiegato -> 0.40600 secondi


Ho quindi sviluppato una versione per array monodimensionali:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define BITMAP_LEN 100000000

int main(void)

{
unsigned char lut[256],*bitmap;
long i,j;
clock_t start,end;
time_t t;

if((bitmap=malloc(BITMAP_LEN*sizeof(char)))==NULL)
{
fprintf(stderr,"Memoria insufficiente");
return 1;
}

srand((unsigned)time(&t));

for(i=0;i<BITMAP_LEN;i++)
bitmap[i]=((double)rand()*256.)/(RAND_MAX+1.);

for(i=0;i<256;i++)
{
for(lut[i]=j=0;j<8;j++)
{
if(i&(1<<j))
lut[i]|=1<<(7-j);
}
}

start=clock();

for(i=0;i<BITMAP_LEN;i++)
bitmap[i]=lut[bitmap[i]];

end=clock();

printf("Tempo di esecuzione: %7.3f secondi\n",(double)(end-start)/CLK_TCK);

return 0;
}


Questo e' l'output generato:


Tempo di esecuzione: 0.296 secondi


Per avere dei tempi piu' attendibili ho anche sviluppato due versioni che eseguissero 10 volte la trasformazione della bitmap. I risultati sono:

Versione monodimensionale: 2.875 secondi
Versione bidimensionale: 3.937 secondi.

Tutto come previsto.

[cdimauro]

Finalmente. :p

[rеpne scasb]

Potresti provare questo:

mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
dec ecx
mov [esi],dl
inc esi
jcxnz loop_bitmap


Alcune considerazioni sull'esecuzione della lut (architettura Intel X86-32/Core):

1) La versione in C per ogni iterazione prende circa 10.3 cicli di clock, con array monodimensionale.
2) La versione in C per ogni iterazione prende circa 14.1 cicli di clock, con array bidimensionale.

3) Questa versione in assembly richiede 4.5 cicli di clock

cld
mov esi,OFFSET bitmap
mov edi,esi
mov ebx,OFFSET lut
mov ecx,[bitmap_len]
loop_bitmap:
lodsb
xlatb
stosb
loop loop_bitmap

4) Questa versione in assembly richiede 5.0 cicli di clock

mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
mov [esi],dl
inc esi
dec ecx
jne loop_bitmap

5) Questa versione in assembly richiede 4.1 cicli di clock

mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
inc esi
dec ecx
mov [esi-1],dl
jne loop_bitmap


Per quanto riguarda l'esempio da te proposto, non e' corretto, in quanto in assembly x86-32 non esiste l'istruzione jcxnz (salta se CX/ECX e' diverso da zero), ma esiste solo l'istruzione jcxz/jecxz (salta se CX/ECX e' uguale a zero). Probabilmente devi aver visto quest'istruzione da qualche parte di un codice asm, ma probabilmente era una macro che l'assemblatore trasformava in un jcxz/jecxz + jmp.

Un'ultima considerazione sui compilatori C: ne devono ancora fare di strada, per arrivare al livello di un 'discreto' programmatore assembly.

[rеpne scasb]

Finalmente. :p

Giusto per completezza ho preso anche la versione che non utilzza la lut ma una funzione di trasformazione (l'ho leggermente modoficata):


#include <stdio.h>
#include <windows.h>
#include <time.h>

#define RIGHE 10000
#define COLONNE 10000

#define BITS_PER_CHAR 8

BYTE ReverseBits(BYTE b)
{
BYTE ret = b;
int s = sizeof(b) * BITS_PER_CHAR - 1;

for (b >>= 1; b; b >>= 1)
{
ret <<= 1;
ret |= b & 1;
s--;
}
ret <<= s;

return ret;
}

int main()
{
clock_t start,end;
int r, c;
int x;

DWORD ms1, ms2;

BYTE **a;

r = RIGHE;
c = COLONNE;

a = (BYTE**)malloc(sizeof(BYTE*)*r);
if ( a != NULL )
{
for ( x = 0; x < r; x++ )
{
a[x] = (BYTE*)malloc(sizeof(BYTE)*c);
if ( a[x] == NULL )
{
printf("Memoria insufficiente.\n");
return -1;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return -1;
}

for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = 1;

printf("\nbyte -> %d\n", a[RIGHE - 1][COLONNE - 1]);
start = clock();
for(r = 0; r < RIGHE; r++)
for(c = 0; c < COLONNE; c++)
a[r][c] = ReverseBits(a[r][c]);
end = clock();
printf("byte -> %d\n", a[RIGHE - 1][COLONNE - 1]);
printf("Temp impiegato -> %7.3f\n\n", (double)(end-start)/CLK_TCK);

for ( x = 0; x < r; x++ )
free(a[x]);
free(a);

return 0;
}


Questa versione eseguita 10 volte prende 35.567 secondi ossia 128 cicli di clock per iterazione (circa 12 volte piu' lenta della versione con array monodimensionale).

[cdimauro]

Alcune considerazioni sull'esecuzione della lut (architettura Intel X86-32/Core):

1) La versione in C per ogni iterazione prende circa 10.3 cicli di clock, con array monodimensionale.
2) La versione in C per ogni iterazione prende circa 14.1 cicli di clock, con array bidimensionale.
Ottimo. Sono risultati in linea con le mie aspettative.
3) Questa versione in assembly richiede 4.5 cicli di clock

cld
mov esi,OFFSET bitmap
mov edi,esi
mov ebx,OFFSET lut
mov ecx,[bitmap_len]
loop_bitmap:
lodsb
xlatb
stosb
loop loop_bitmap

4) Questa versione in assembly richiede 5.0 cicli di clock

mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
mov [esi],dl
inc esi
dec ecx
jne loop_bitmap

5) Questa versione in assembly richiede 4.1 cicli di clock

mov esi,OFFSET bitmap
mov ebx,OFFSET lut
xor eax,eax
mov ecx,[bitmap_len]
loop_bitmap:
mov al,[esi]
mov dl,[eax+ebx]
inc esi
dec ecx
mov [esi-1],dl
jne loop_bitmap

Qui rimango in ogni caso sopreso dalla velocità del codice che fa uso di istruzioni "legacy" che dovrebbero far ricorso al microcodice. Impressionante.

Complimenti alla Intel perché ha fatto un eccellente lavoro.
Per quanto riguarda l'esempio da te proposto, non e' corretto, in quanto in assembly x86-32 non esiste l'istruzione jcxnz (salta se CX/ECX e' diverso da zero), ma esiste solo l'istruzione jcxz/jecxz (salta se CX/ECX e' uguale a zero). Probabilmente devi aver visto quest'istruzione da qualche parte di un codice asm, ma probabilmente era una macro che l'assemblatore trasformava in un jcxz/jecxz + jmp.
Sì, è possibile. E' da diverso tempo che non metto mano all'assembly x86 e ricordavo male (non mi sono premunito neppure di controllare, per cui semplicemente... ho sbagliato :p).
Un'ultima considerazione sui compilatori C: ne devono ancora fare di strada, per arrivare al livello di un 'discreto' programmatore assembly.
Indubbiamente. Il fattore discriminante, al solito, è il tempo per implementare la soluzione nei rispettivi linguaggi.
Giusto per completezza ho preso anche la versione che non utilzza la lut ma una funzione di trasformazione (l'ho leggermente modoficata):
[...]
Questa versione eseguita 10 volte prende 35.567 secondi ossia 128 cicli di clock per iterazione (circa 12 volte piu' lenta della versione con array monodimensionale).
Perfetto. Quindi le previsioni, almeno in questi casi (uso di LUT e vettori VS funzione di calcolo e matrice) si sono rivelate poi corrette. :)

[Vincenzo1968]

Questo è il risultato con matrice bidimensionale:
http://www.guidealgoritmi.it/images/ImgForums/Matrice03.jpg

Questo è il risultato con matrice monodimensionale:
http://www.guidealgoritmi.it/images/ImgForums/Matrice04.jpg

E questa è la mia macchina:
http://www.guidealgoritmi.it/images/ImgForums/Matrice05.jpg

Pre la matrice monodimensionale ho utilizzato il tuo codice. Ho aggiunto soltanto un paio di printf:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define BITMAP_LEN 100000000

int main(void)

{
unsigned char lut[256],*bitmap;
long i,j;
clock_t start, end;
time_t t;

if((bitmap = malloc(BITMAP_LEN*sizeof(char))) == NULL)
{
fprintf(stderr,"Memoria insufficiente");
return 1;
}

srand((unsigned)time(&t));

for( i = 0; i < BITMAP_LEN; i++ )
bitmap[i] = ((double)rand()*256.)/(RAND_MAX+1.);

printf("\nMatrice monodimensionale:\n\n");

printf("byte -> %d\n", bitmap[BITMAP_LEN - 1]);

for(i=0;i<256;i++)
{
for(lut[i]=j=0;j<8;j++)
{
if(i&(1<<j))
lut[i]|=1<<(7-j);
}
}

start=clock();

for(i=0;i<BITMAP_LEN;i++)
bitmap[i]=lut[bitmap[i]];

end=clock();

printf("byte -> %d\n", bitmap[BITMAP_LEN - 1]);

printf("\nTempo di esecuzione: %7.3f secondi\n",(double)(end-start)/CLK_TCK);

return 0;
}


Ho provato a dare una piccola scossa al pc(come si faceva un tempo con i vecchi televisori quando non funzionavano bene :D ) ma niente da fare.
Certo che è strano: con array monodimensionale dovrebbe risultarmi più veloce. Boh :cry:

[rеpne scasb]

Qui rimango in ogni caso sopreso dalla velocità del codice che fa uso di istruzioni "legacy" che dovrebbero far ricorso al microcodice. Impressionante.

Impressionante sicuramente. L'Intel con il Core ha fatto un lavoro a dir poco incredibile, probabilmente queste istruzioni legacy non sono in microcodice, ma vengono eseguite secondo uno schema ottimizzato nonostante siano raramente utilizzare all'interno di un software.

[rеpne scasb]

Ho provato a dare una piccola scossa al pc(come si faceva un tempo con i vecchi televisori quando non funzionavano bene :D ) ma niente da fare.
Certo che è strano: con array monodimensionale dovrebbe risultarmi più veloce. Boh :cry:

Non me lo spiego. Dovrei quanto meno conoscere il compilatore che stai utilizzando, o magari, se puoi, allegare i due eseguibili cosi' da andare a vedere il codice assembly che ha generato il tuo compilatore tramite un debugger.

[rеpne scasb]

Sì, è possibile. E' da diverso tempo che non metto mano all'assembly x86 e ricordavo male (non mi sono premunito neppure di controllare, per cui semplicemente... ho sbagliato :p).

Ahhhhhhhhhhhh, questo non l'avevo visto!!!!!!!! cdimauro che si sbaglia e' talmente raro che quasi non ci credo! Meglio quotare prima che cancelli tutto! :p :p :p :p :p

[Vincenzo1968]

Non me lo spiego. Dovrei quanto meno conoscere il compilatore che stai utilizzando, o magari, se puoi, allegare i due eseguibili cosi' da andare a vedere il codice assembly che ha generato il tuo compilatore tramite un debugger.

Utilizzo il Visual Studio 2008. Se vuoi ti posso postare l'assembly generato dal compilatore.

Ciao

[rеpne scasb]

Utilizzo il Visual Studio 2008. Se vuoi ti posso postare l'assembly generato dal compilatore.

Ciao

Ok, mi interessano i due pezzi di codice assembly, presenti tra le due chiamate alla funzione clock(). Grazie.

[Vincenzo1968]

Questo è l'assembly per la matrice bidimensionale:


; Listing generated by Microsoft (R) Optimizing Compiler Version 15.00.21022.08

TITLE c:\Progetti Visual Studio\Progetti visual Studio 2008\C++\MyProjects\Bitmap\Bitmap\Bitmap.c
.686P
.XMM
include listing.inc
.model flat

INCLUDELIB OLDNAMES

PUBLIC ??_C@_0BI@HEOAEDLG@Memoria?5insufficiente?4?6?$AA@ ; `string'
PUBLIC ??_C@_0BL@FMGMLAME@?6Matrice?5bidimensionale?3?6?6?$AA@ ; `string'
PUBLIC ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@ ; `string'
PUBLIC ??_C@_0CD@IDBDLGEF@Tempo?5impiegato?5?9?$DO?5?$CF2?45f?5secondi@ ; `string'
EXTRN @__security_check_cookie@4:PROC
EXTRN __imp__rand:PROC
EXTRN __imp__printf:PROC
EXTRN __imp__clock:PROC
EXTRN __imp___time64:PROC
EXTRN __imp__srand:PROC
EXTRN __imp__free:PROC
EXTRN __imp__malloc:PROC
; COMDAT ??_C@_0CD@IDBDLGEF@Tempo?5impiegato?5?9?$DO?5?$CF2?45f?5secondi@
CONST SEGMENT
??_C@_0CD@IDBDLGEF@Tempo?5impiegato?5?9?$DO?5?$CF2?45f?5secondi@ DB 'Temp'
DB 'o impiegato -> %2.5f secondi', 0aH, 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@
CONST SEGMENT
??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@ DB 'byte -> %d', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0BL@FMGMLAME@?6Matrice?5bidimensionale?3?6?6?$AA@
CONST SEGMENT
??_C@_0BL@FMGMLAME@?6Matrice?5bidimensionale?3?6?6?$AA@ DB 0aH, 'Matrice '
DB 'bidimensionale:', 0aH, 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0BI@HEOAEDLG@Memoria?5insufficiente?4?6?$AA@
CONST SEGMENT
??_C@_0BI@HEOAEDLG@Memoria?5insufficiente?4?6?$AA@ DB 'Memoria insufficie'
DB 'nte.', 0aH, 00H ; `string'
_BitReverseTable DB 00H
DB 080H
DB 040H
DB 0c0H
DB 020H
DB 0a0H
DB 060H
DB 0e0H
DB 010H
DB 090H
DB 050H
DB 0d0H
DB 030H
DB 0b0H
DB 070H
DB 0f0H
DB 08H
DB 088H
DB 048H
DB 0c8H
DB 028H
DB 0a8H
DB 068H
DB 0e8H
DB 018H
DB 098H
DB 058H
DB 0d8H
DB 038H
DB 0b8H
DB 078H
DB 0f8H
DB 04H
DB 084H
DB 044H
DB 0c4H
DB 024H
DB 0a4H
DB 064H
DB 0e4H
DB 014H
DB 094H
DB 054H
DB 0d4H
DB 034H
DB 0b4H
DB 074H
DB 0f4H
DB 0cH
DB 08cH
DB 04cH
DB 0ccH
DB 02cH
DB 0acH
DB 06cH
DB 0ecH
DB 01cH
DB 09cH
DB 05cH
DB 0dcH
DB 03cH
DB 0bcH
DB 07cH
DB 0fcH
DB 02H
DB 082H
DB 042H
DB 0c2H
DB 022H
DB 0a2H
DB 062H
DB 0e2H
DB 012H
DB 092H
DB 052H
DB 0d2H
DB 032H
DB 0b2H
DB 072H
DB 0f2H
DB 0aH
DB 08aH
DB 04aH
DB 0caH
DB 02aH
DB 0aaH
DB 06aH
DB 0eaH
DB 01aH
DB 09aH
DB 05aH
DB 0daH
DB 03aH
DB 0baH
DB 07aH
DB 0faH
DB 06H
DB 086H
DB 046H
DB 0c6H
DB 026H
DB 0a6H
DB 066H
DB 0e6H
DB 016H
DB 096H
DB 056H
DB 0d6H
DB 036H
DB 0b6H
DB 076H
DB 0f6H
DB 0eH
DB 08eH
DB 04eH
DB 0ceH
DB 02eH
DB 0aeH
DB 06eH
DB 0eeH
DB 01eH
DB 09eH
DB 05eH
DB 0deH
DB 03eH
DB 0beH
DB 07eH
DB 0feH
DB 01H
DB 081H
DB 041H
DB 0c1H
DB 021H
DB 0a1H
DB 061H
DB 0e1H
DB 011H
DB 091H
DB 051H
DB 0d1H
DB 031H
DB 0b1H
DB 071H
DB 0f1H
DB 09H
DB 089H
DB 049H
DB 0c9H
DB 029H
DB 0a9H
DB 069H
DB 0e9H
DB 019H
DB 099H
DB 059H
DB 0d9H
DB 039H
DB 0b9H
DB 079H
DB 0f9H
DB 05H
DB 085H
DB 045H
DB 0c5H
DB 025H
DB 0a5H
DB 065H
DB 0e5H
DB 015H
DB 095H
DB 055H
DB 0d5H
DB 035H
DB 0b5H
DB 075H
DB 0f5H
DB 0dH
DB 08dH
DB 04dH
DB 0cdH
DB 02dH
DB 0adH
DB 06dH
DB 0edH
DB 01dH
DB 09dH
DB 05dH
DB 0ddH
DB 03dH
DB 0bdH
DB 07dH
DB 0fdH
DB 03H
DB 083H
DB 043H
DB 0c3H
DB 023H
DB 0a3H
DB 063H
DB 0e3H
DB 013H
DB 093H
DB 053H
DB 0d3H
DB 033H
DB 0b3H
DB 073H
DB 0f3H
DB 0bH
DB 08bH
DB 04bH
DB 0cbH
DB 02bH
DB 0abH
DB 06bH
DB 0ebH
DB 01bH
DB 09bH
DB 05bH
DB 0dbH
DB 03bH
DB 0bbH
DB 07bH
DB 0fbH
DB 07H
DB 087H
DB 047H
DB 0c7H
DB 027H
DB 0a7H
DB 067H
DB 0e7H
DB 017H
DB 097H
DB 057H
DB 0d7H
DB 037H
DB 0b7H
DB 077H
DB 0f7H
DB 0fH
DB 08fH
DB 04fH
DB 0cfH
DB 02fH
DB 0afH
DB 06fH
DB 0efH
DB 01fH
DB 09fH
DB 05fH
DB 0dfH
DB 03fH
DB 0bfH
DB 07fH
DB 0ffH
PUBLIC __real@0000000000000000
PUBLIC __real@406fe00000000000
PUBLIC __real@3f00000000000000
PUBLIC _InitMatrix
EXTRN __fltused:DWORD
; COMDAT __real@0000000000000000
; File c:\progetti visual studio\progetti visual studio 2008\c++\myprojects\sfidehw\bitmap\bitmap\bitmap.c
CONST SEGMENT
__real@0000000000000000 DQ 00000000000000000r ; 0
CONST ENDS
; COMDAT __real@406fe00000000000
CONST SEGMENT
__real@406fe00000000000 DQ 0406fe00000000000r ; 255
CONST ENDS
; COMDAT __real@3f00000000000000
CONST SEGMENT
__real@3f00000000000000 DQ 03f00000000000000r ; 3.05176e-005
; Function compile flags: /Ogtpy
CONST ENDS
; COMDAT _InitMatrix
_TEXT SEGMENT
tv200 = -8 ; size = 4
tv198 = -8 ; size = 2
tv195 = -4 ; size = 4
tv193 = -4 ; size = 4
_InitMatrix PROC ; COMDAT
; _p$ = eax
; Line 88
sub esp, 8
push ebx
; Line 91
mov ebx, DWORD PTR __imp__rand
push ebp
push esi
push edi
mov edi, eax
mov ebp, 10000 ; 00002710H
$LL6@InitMatrix:
; Line 92
xor esi, esi
$LL3@InitMatrix:
; Line 93
call ebx
mov ecx, DWORD PTR [edi]
mov DWORD PTR tv200[esp+24], eax
fild DWORD PTR tv200[esp+24]
inc esi
fnstcw WORD PTR tv198[esp+24]
fmul QWORD PTR __real@3f00000000000000
movzx eax, WORD PTR tv198[esp+24]
or eax, 3072 ; 00000c00H
cmp esi, 10000 ; 00002710H
mov DWORD PTR tv195[esp+24], eax
fmul QWORD PTR __real@406fe00000000000
fadd QWORD PTR __real@0000000000000000
fldcw WORD PTR tv195[esp+24]
fistp DWORD PTR tv193[esp+24]
mov al, BYTE PTR tv193[esp+24]
mov BYTE PTR [esi+ecx-1], al
fldcw WORD PTR tv198[esp+24]
jl SHORT $LL3@InitMatrix
add edi, 4
sub ebp, 1
jne SHORT $LL6@InitMatrix
pop edi
pop esi
pop ebp
pop ebx
; Line 94
add esp, 8
ret 0
_InitMatrix ENDP
; Function compile flags: /Ogtpy
_TEXT ENDS
; COMDAT _time
_TEXT SEGMENT
_time PROC ; COMDAT
; File c:\programmi\microsoft visual studio 9.0\vc\include\time.inl
; Line 135
push 0
call DWORD PTR __imp___time64
add esp, 4
; Line 136
ret 0
_time ENDP
_TEXT ENDS
PUBLIC __real@408f400000000000
PUBLIC _main
; COMDAT __real@408f400000000000
CONST SEGMENT
__real@408f400000000000 DQ 0408f400000000000r ; 1000
; Function compile flags: /Ogtpy
CONST ENDS
; COMDAT _main
_TEXT SEGMENT
tv795 = -4 ; size = 4
_start$ = -4 ; size = 4
_main PROC ; COMDAT
; File c:\progetti visual studio\progetti visual studio 2008\c++\myprojects\sfidehw\bitmap\bitmap\bitmap.c
; Line 97
push ecx
push ebx
push edi
; Line 107
mov edi, DWORD PTR __imp__malloc
push 40000 ; 00009c40H
call edi
mov ebx, eax
add esp, 4
; Line 108
test ebx, ebx
je $LN15@main
push esi
; Line 110
xor esi, esi
$LL14@main:
; Line 112
push 10000 ; 00002710H
call edi
add esp, 4
mov DWORD PTR [ebx+esi*4], eax
; Line 113
test eax, eax
je $LN24@main
inc esi
cmp esi, 10000 ; 00002710H
jl SHORT $LL14@main
push ebp
; Line 126
push 0
call DWORD PTR __imp___time64
push eax
call DWORD PTR __imp__srand
; Line 127
mov eax, ebx
call _InitMatrix
; Line 129
mov ebp, DWORD PTR __imp__printf
push OFFSET ??_C@_0BL@FMGMLAME@?6Matrice?5bidimensionale?3?6?6?$AA@
call ebp
; Line 131
mov eax, DWORD PTR [ebx+39996]
movzx eax, BYTE PTR [eax+9999]
push eax
push OFFSET ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@
call ebp
add esp, 20 ; 00000014H
; Line 133
call DWORD PTR __imp__clock
mov DWORD PTR _start$[esp+20], eax
; Line 135
xor esi, esi
npad 10
$LL9@main:
; Line 136
mov eax, DWORD PTR [ebx+esi*4]
add eax, 2
mov edi, 2000 ; 000007d0H
npad 5
$LL6@main:
; Line 137
movzx ecx, BYTE PTR [eax-2]
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax-1]
mov BYTE PTR [eax-2], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax]
mov BYTE PTR [eax-1], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax+1]
mov BYTE PTR [eax], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax+2]
mov BYTE PTR [eax+1], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
mov BYTE PTR [eax+2], dl
add eax, 5
sub edi, 1
jne SHORT $LL6@main
inc esi
cmp esi, 10000 ; 00002710H
jl SHORT $LL9@main
; Line 139
call DWORD PTR __imp__clock
mov edi, eax
; Line 141
mov eax, DWORD PTR [ebx+39996]
movzx eax, BYTE PTR [eax+9999]
push eax
push OFFSET ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@
call ebp
; Line 143
sub edi, DWORD PTR _start$[esp+28]
mov DWORD PTR tv795[esp+28], edi
fild DWORD PTR tv795[esp+28]
fdiv QWORD PTR __real@408f400000000000
fstp QWORD PTR [esp]
push OFFSET ??_C@_0CD@IDBDLGEF@Tempo?5impiegato?5?9?$DO?5?$CF2?45f?5secondi@
call ebp
; Line 145
mov ebp, DWORD PTR __imp__free
add esp, 12 ; 0000000cH
xor edi, edi
test esi, esi
jle SHORT $LN1@main
npad 3
$LL3@main:
; Line 146
mov ecx, DWORD PTR [ebx+edi*4]
push ecx
call ebp
inc edi
add esp, 4
cmp edi, esi
jl SHORT $LL3@main
$LN1@main:
; Line 147
push ebx
call ebp
add esp, 4
pop ebp
pop esi
pop edi
; Line 149
xor eax, eax
pop ebx
; Line 150
pop ecx
ret 0
$LN24@main:
; Line 115
push OFFSET ??_C@_0BI@HEOAEDLG@Memoria?5insufficiente?4?6?$AA@
call DWORD PTR __imp__printf
add esp, 4
pop esi
pop edi
; Line 116
or eax, -1
pop ebx
; Line 150
pop ecx
ret 0
$LN15@main:
; Line 122
push OFFSET ??_C@_0BI@HEOAEDLG@Memoria?5insufficiente?4?6?$AA@
call DWORD PTR __imp__printf
add esp, 4
pop edi
; Line 123
or eax, -1
pop ebx
; Line 150
pop ecx
ret 0
_main ENDP
_TEXT ENDS
END


E questo è quello generato col tuo codice:


; Listing generated by Microsoft (R) Optimizing Compiler Version 15.00.21022.08

TITLE c:\Progetti Visual Studio\Progetti visual Studio 2008\C++\MyProjects\Bitmap3\Bitmap3\Bitmap3.c
.686P
.XMM
include listing.inc
.model flat

INCLUDELIB OLDNAMES

PUBLIC ??_C@_0BG@JDPKLEPE@Memoria?5insufficiente?$AA@ ; `string'
PUBLIC ??_C@_0BN@EKOOMNHE@?6Matrice?5monodimensionale?3?6?6?$AA@ ; `string'
PUBLIC ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@ ; `string'
PUBLIC ??_C@_0CF@HGCADOJO@?6Tempo?5di?5esecuzione?3?5?$CF7?43f?5seco@ ; `string'
EXTRN @__security_check_cookie@4:PROC
EXTRN __imp____iob_func:PROC
EXTRN __imp__fprintf:PROC
EXTRN __imp__printf:PROC
EXTRN __imp__rand:PROC
EXTRN __imp__srand:PROC
EXTRN __imp__malloc:PROC
EXTRN __imp__clock:PROC
EXTRN __imp___time64:PROC
; COMDAT ??_C@_0CF@HGCADOJO@?6Tempo?5di?5esecuzione?3?5?$CF7?43f?5seco@
CONST SEGMENT
??_C@_0CF@HGCADOJO@?6Tempo?5di?5esecuzione?3?5?$CF7?43f?5seco@ DB 0aH, 'T'
DB 'empo di esecuzione: %7.3f secondi', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@
CONST SEGMENT
??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@ DB 'byte -> %d', 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0BN@EKOOMNHE@?6Matrice?5monodimensionale?3?6?6?$AA@
CONST SEGMENT
??_C@_0BN@EKOOMNHE@?6Matrice?5monodimensionale?3?6?6?$AA@ DB 0aH, 'Matric'
DB 'e monodimensionale:', 0aH, 0aH, 00H ; `string'
CONST ENDS
; COMDAT ??_C@_0BG@JDPKLEPE@Memoria?5insufficiente?$AA@
CONST SEGMENT
??_C@_0BG@JDPKLEPE@Memoria?5insufficiente?$AA@ DB 'Memoria insufficiente', 00H ; `string'
; Function compile flags: /Ogtpy
CONST ENDS
; COMDAT _time
_TEXT SEGMENT
_time PROC ; COMDAT
; __Time$ = eax
; File c:\programmi\microsoft visual studio 9.0\vc\include\time.inl
; Line 135
push eax
call DWORD PTR __imp___time64
add esp, 4
; Line 136
ret 0
_time ENDP
_TEXT ENDS
PUBLIC __real@408f400000000000
PUBLIC __real@3f00000000000000
PUBLIC __real@4070000000000000
PUBLIC __$ArrayPad$
PUBLIC _main
EXTRN ___security_cookie:DWORD
EXTRN __fltused:DWORD
; COMDAT __real@408f400000000000
CONST SEGMENT
__real@408f400000000000 DQ 0408f400000000000r ; 1000
CONST ENDS
; COMDAT __real@3f00000000000000
CONST SEGMENT
__real@3f00000000000000 DQ 03f00000000000000r ; 3.05176e-005
CONST ENDS
; COMDAT __real@4070000000000000
CONST SEGMENT
__real@4070000000000000 DQ 04070000000000000r ; 256
; Function compile flags: /Ogtpy
CONST ENDS
; COMDAT _main
_TEXT SEGMENT
tv681 = -276 ; size = 4
tv679 = -276 ; size = 4
tv639 = -276 ; size = 4
tv686 = -272 ; size = 4
tv684 = -272 ; size = 2
_t$ = -268 ; size = 8
_lut$ = -260 ; size = 256
__$ArrayPad$ = -4 ; size = 4
_main PROC ; COMDAT
; File c:\progetti visual studio\progetti visual studio 2008\c++\myprojects\sfidehw\bitmap3\bitmap3\bitmap3.c
; Line 9
sub esp, 276 ; 00000114H
mov eax, DWORD PTR ___security_cookie
xor eax, esp
mov DWORD PTR __$ArrayPad$[esp+276], eax
push ebp
; Line 15
push 100000000 ; 05f5e100H
call DWORD PTR __imp__malloc
mov ebp, eax
add esp, 4
test ebp, ebp
jne SHORT $LN14@main
; Line 17
push OFFSET ??_C@_0BG@JDPKLEPE@Memoria?5insufficiente?$AA@
call DWORD PTR __imp____iob_func
add eax, 64 ; 00000040H
push eax
call DWORD PTR __imp__fprintf
add esp, 8
; Line 18
lea eax, DWORD PTR [ebp+1]
pop ebp
; Line 51
mov ecx, DWORD PTR __$ArrayPad$[esp+276]
xor ecx, esp
call @__security_check_cookie@4
add esp, 276 ; 00000114H
ret 0
$LN14@main:
push ebx
push esi
; Line 21
lea eax, DWORD PTR _t$[esp+288]
push edi
push eax
call DWORD PTR __imp___time64
push eax
call DWORD PTR __imp__srand
; Line 23
mov edi, DWORD PTR __imp__rand
add esp, 8
xor esi, esi
npad 6
$LL13@main:
; Line 24
call edi
mov DWORD PTR tv686[esp+292], eax
fild DWORD PTR tv686[esp+292]
inc esi
fnstcw WORD PTR tv684[esp+292]
movzx eax, WORD PTR tv684[esp+292]
fmul QWORD PTR __real@4070000000000000
or eax, 3072 ; 00000c00H
cmp esi, 100000000 ; 05f5e100H
mov DWORD PTR tv681[esp+292], eax
fmul QWORD PTR __real@3f00000000000000
fldcw WORD PTR tv681[esp+292]
fistp DWORD PTR tv679[esp+292]
mov cl, BYTE PTR tv679[esp+292]
mov BYTE PTR [esi+ebp-1], cl
fldcw WORD PTR tv684[esp+292]
jl SHORT $LL13@main
; Line 26
mov ebx, DWORD PTR __imp__printf
push OFFSET ??_C@_0BN@EKOOMNHE@?6Matrice?5monodimensionale?3?6?6?$AA@
call ebx
; Line 28
movzx edx, BYTE PTR [ebp+99999999]
push edx
push OFFSET ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@
call ebx
add esp, 12 ; 0000000cH
; Line 30
xor edi, edi
$LL28@main:
; Line 32
xor esi, esi
mov BYTE PTR _lut$[esp+edi+292], 0
lea eax, DWORD PTR [esi+7]
$LL7@main:
; Line 34
mov edx, 1
mov ecx, esi
shl edx, cl
test edx, edi
je SHORT $LN6@main
; Line 35
mov dl, 1
mov ecx, eax
shl dl, cl
or BYTE PTR _lut$[esp+edi+292], dl
$LN6@main:
dec eax
inc esi
cmp eax, -1
jg SHORT $LL7@main
inc edi
cmp edi, 256 ; 00000100H
jl SHORT $LL28@main
; Line 39
mov esi, DWORD PTR __imp__clock
call esi
mov edi, eax
lea eax, DWORD PTR [ebp+1]
mov ecx, 20000000 ; 01312d00H
npad 7
$LL3@main:
; Line 42
movzx edx, BYTE PTR [eax-1]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax-1], dl
movzx edx, BYTE PTR [eax]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax], dl
movzx edx, BYTE PTR [eax+1]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax+1], dl
movzx edx, BYTE PTR [eax+2]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax+2], dl
movzx edx, BYTE PTR [eax+3]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax+3], dl
add eax, 5
sub ecx, 1
jne SHORT $LL3@main
; Line 44
call esi
mov esi, eax
; Line 46
movzx eax, BYTE PTR [ebp+99999999]
push eax
push OFFSET ??_C@_0M@KGAKOBNB@byte?5?9?$DO?5?$CFd?6?$AA@
call ebx
; Line 48
sub esi, edi
mov DWORD PTR tv639[esp+300], esi
fild DWORD PTR tv639[esp+300]
fdiv QWORD PTR __real@408f400000000000
fstp QWORD PTR [esp]
push OFFSET ??_C@_0CF@HGCADOJO@?6Tempo?5di?5esecuzione?3?5?$CF7?43f?5seco@
call ebx
; Line 51
mov ecx, DWORD PTR __$ArrayPad$[esp+304]
add esp, 12 ; 0000000cH
pop edi
pop esi
pop ebx
pop ebp
xor ecx, esp
xor eax, eax
call @__security_check_cookie@4
add esp, 276 ; 00000114H
ret 0
_main ENDP
_TEXT ENDS
END

[rеpne scasb]

Questo...[CUT]

Ora guardo, e poi ti faccio sapere. Grazie.

[Vincenzo1968]

Ora guardo, e poi ti faccio sapere. Grazie.

Grazie a te :)

Ci sto impazzendo su questa cosa.
Se ti dovesse prendere troppo tempo, lascia perdere, non preoccuparti.

Ciao.

[rеpne scasb]

Ora guardo, e poi ti faccio sapere. Grazie.

Allora ho isolato i due codici generati. Questo e' per l'array monodimensionale:

lea eax, DWORD PTR [ebp+1]
mov ecx, 20000000 ; 01312d00H
npad 7
$LL3@main:
; Line 42
movzx edx, BYTE PTR [eax-1]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax-1], dl
movzx edx, BYTE PTR [eax]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax], dl
movzx edx, BYTE PTR [eax+1]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax+1], dl
movzx edx, BYTE PTR [eax+2]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax+2], dl
movzx edx, BYTE PTR [eax+3]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax+3], dl
add eax, 5
sub ecx, 1
jne SHORT $LL3@main

e questo per l'array bidimensionale:

; Line 135
xor esi, esi
npad 10
$LL9@main:
; Line 136
mov eax, DWORD PTR [ebx+esi*4]
add eax, 2
mov edi, 2000 ; 000007d0H
npad 5
$LL6@main:
; Line 137
movzx ecx, BYTE PTR [eax-2]
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax-1]
mov BYTE PTR [eax-2], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax]
mov BYTE PTR [eax-1], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax+1]
mov BYTE PTR [eax], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax+2]
mov BYTE PTR [eax+1], dl
movzx edx, BYTE PTR _BitReverseTable[ecx]
mov BYTE PTR [eax+2], dl
add eax, 5
sub edi, 1
jne SHORT $LL6@main
inc esi
cmp esi, 10000 ; 00002710H
jl SHORT $LL9@main
; Line 139


Alla luce del codice generato, "SECONDO ME", sarebbe da prendere "a palare sulle gengive" chi ha sviluppato Visual Studio 2008.

Questi sono i pezzi di codice da verificare:


movzx edx, BYTE PTR [eax-1]
movzx edx, BYTE PTR _lut$[esp+edx+292]
mov BYTE PTR [eax-1], dl



movzx edx, BYTE PTR _BitReverseTable[ecx]
movzx ecx, BYTE PTR [eax-1]
mov BYTE PTR [eax-2], dl


Non solo il codice per array monodimensionali risulta il 50% piu' grande come estensione, ma presenta per il registro edx una doppia dipendenza, oltre ad utilizzare un offset piu' complesso. Di fatto il pregio di avere la memoria tutta allocata in un unico blocco, viene perso a causa della non ottimale generazione del codice per la routine per un array monodimensionale. Di fatto quello che era semplice e' stato tradotto in assembly in modo complesso, quello che era complesso, e' stato tradotto in modo semplice.

[Vincenzo1968]

Alla luce del codice generato, "SECONDO ME", sarebbe da prendere "a palare sulle gengive" chi ha sviluppato Visual Studio 2008.



Seguirei volentieri il tuo consiglio...
Tu che compilatore usi?

[rеpne scasb]

Seguirei volentieri il tuo consiglio...
Tu che compilatore usi?

Forse sono stata fraintesa. Per quel poco che l'ho utilizzato, Visual studio e' secondo me uno strumento adatto a chi vuol programmare in C. "A palate sulle gengive" solo per la generazione di questo particolare codice, ed in queste particolari condizioni. In generale, a me sembra un prodotto valido, continua quindi ad utilizzarlo, tranne essere smetita da chi conosce Visual Studio in modo approfondito e molto meglio di me.

Io utilizzo il Watcom C http://www.openwatcom.org/index.php/Main_Page solo perche' lo uso da anni e conosco bene i suoi pregi (pochi), ed i suoi difetti (molti): ftp://openwatcom.mirrors.skynet.be/pub/ftp.openwatcom.org/open-watcom-c-win32-1.7a.exe

[gugoXX]

Cesare, quando hai tempo potresti profilarmi questo? A me viene un risultato inattendibile, pero' dovrebbe essere buono (sono su una macchina virtuale ora)


__asm{
mov esi,bitmap
lea ebx,lut
xor eax,eax
mov ecx,[bitmap_len]
dec esi
loop_bitmap:
jcxz avanti
mov al,[esi+ecx]
mov dl,[ebx+eax]
mov [esi+ecx],dl
dec ecx
jmp loop_bitmap
avanti:
}

[cdimauro]

Dovresti chiedere a Lyane, che finora s'è occupata di profilare i pezzi di codice assembly. :)

P.S. A naso mi sembra una buona soluzione: si risparmia uno stallo dovuto alla modifica del registro ESI. :)

[cdimauro]

Mumble. E perché non questa:

__asm{
mov esi,bitmap
lea ebx,lut
xor eax,eax
mov ecx,[bitmap_len]
dec esi
jcxz avanti
loop_bitmap:
mov al,[esi+ecx]
mov dl,[ebx+eax]
mov [esi+ecx],dl
dec ecx
jnz loop_bitmap
avanti:
}
? :D

Ci stiamo sbizzarrendo. :p

[DanieleC88]

Cioè ma fatemi capire, appena mi manca l'occasione di connettermi voi subito cacciate questi contest? Arrrgh!! :muro:

[rеpne scasb]

Ci stiamo sbizzarrendo. :p

Guarda, io ho anche pensato ad una cosa del genere:


mov ebx,OFFSET bitmap
mov ecx,OFFSET start_jmp
mov edx,bitmap_len-1
xor eax,eax
loop_bitmap:
mov al,byte [ebx+edx]
lea esi,[8*eax+ebx]
jmp esi

ALIGN 8d

start_jmp:
mov byte [ebx+edx],0h
jmp exit_switch

ALIGN 8d

mov [ebx+edx],80h
jmp exit_switch

ALIGN 8d

mov [ebx+edx],40h
jmp exit_switch

ALIGN 8d

mov [ebx+edx],0C0h
jmp exit_switch

...

...

exit_switch:
sub edx,1h
jnc loop_bitmap


Non ho il tempo di verificare se e' veloce, ma con i processori di oggi tutta la routine stara' completamente in cache istruzioni (la routine dovrebbe essere grande 2 KiB circa).

[cdimauro]

Lo credo bene: è l'equivalente di uno switch "unrolled". :D

[gugoXX]

Questo, questo. Ho liberato i flag


__asm{
mov esi,bitmap
lea ebx,lut
xor eax,eax
mov ecx,bitmap_len
dec esi
loop_bitmap:
jcxz avanti
mov al,[esi+ecx]
mov dl,[ebx+eax]
mov [esi+ecx],dl
lea ecx,[ecx-1]
jmp loop_bitmap
avanti:
}


Che bambini.

[rеpne scasb]

Questo, questo. Ho liberato i flag


__asm{
mov esi,bitmap
lea ebx,lut
xor eax,eax
mov ecx,bitmap_len
dec esi
loop_bitmap:
jcxz avanti
mov al,[esi+ecx]
mov dl,[ebx+eax]
mov [esi+ecx],dl
lea ecx,[ecx-1]
jmp loop_bitmap
avanti:
}


Che bambini.

Ecco questo e' interessante: "Il fatto di non aver alterato flags all'interno della routine, puo' migliorare le prestazioni? Ossia, quanto pesano, in termini di prestazioni, le alterazioni dei flags in una routine?"

Non lo so. Chi lo sa?

P.S. L'istruzione jcxz salta se CX=0, a te serve la jecxz che salta se ECX=0.

[gugoXX]

Ecco questo e' interessante: "Il fatto di non aver alterato flags all'interno della routine, puo' migliorare le prestazioni? Ossia, quanto pesano, in termini di prestazioni, le alterazioni dei flags in una routine?"

Non lo so. Chi lo sa?

P.S. L'istruzione jcxz salta se CX=0, a te serve la jecxz che salta se ECX=0.

Vero, erroraccio.
Ma tanto non avevo ancora mai eseguito...

Penso che liberare i flag, ovvero non settarli ne utilizzarli, possa essere di effettivo aiuto nelle ottimizzazioni.
Provo a fare un po' di test e vediamo.

[Vincenzo1968]

up

:bimbo: