Newsgroup: it.comp.lang.c
Titolo: Utilizzare un char come contantore

Salve,
per motivi di prestazioni, ho la necessità di utilizzare un char come
contatore. Mi spiego meglio.
Il contatore in questione parte da -1 e può arrivare al massimo a 9, e
quindi uno spreco di memoria utilizzare una variabile di tipo int. Mi
è stato suggerito ti utilizzare un char e di lavorare sulla posizione
dei bit.
Mi potete dare qualche consiglio, visto che la cosa non mi è molto
chiara?
Grazie mille


non mi e' molto chiaro...
quanti di questi contatori devi utilizzare ?
qualche decina di milioni ?
Oppure stai lavorando su un sistema embedded nel quale
devi risparmiare il singolo byte ?
Perche' altrimenti non capisco la motivazione
delle prestazioni. Fare calcoli su un singolo char spesso
non e' piu' veloce che fare calcoli su un normale int, anzi.
Comunque, anche se tu proprio volessi usare un char come contatore
non vedo che bisogno ci sia di lavorare sui bit.
Un char e' un tipo intero. Se e' un signed char puoi benissimo
rappresentare direttamente numeri tra -1 e 9.
L'uso dei bit (che farebbe peggiorare le prestazioni) ha senso
solo se hai piu' di questi contatori e li vuoi impacchettare in meno
di un char.
Ovvero il tuo contatore variando tra -1 e 9 puo' assumere esattamente
(-1,0,1,2,3,4,5,6,7,8,9)  11 valori distinti. Questi valori distinti li
puoi rappresentare con i numeri tra 0 e 10 che a loro volta possono
essere rappresentati con 4 bit (ovvero un nibble, ovvero la meta' dei
bit /normalmente/ utilizzati per un char). Quindi in teoria, usando
operazioni sui bit, puoi rappresentare due di questi contatori
in un unico char.
Ancora una volta, a meno che tu non ne abbia tantissimi e poca memoria,
rappresentarli impacchettati fara' generalmente peggiorare le
prestazioni invece di migliorarle (ci possono essere delle eccezioni,
in base al tipo di operazioni che ci devi fare sopra).
Nel caso tu debba operare sui bit, ti devi prendere un manuale e ti
studi questi operatori :   "<<"   ">>"  "&"  "|"  "^" che lavorano
bit a bit sui numeri interi (e quindi anche sui char, in quel caso
meglio se unsigned) e sono shift e operazioni AND, OR e XOR, che
usate con opportune maschere ti permettono di settare o leggere singoli
bit, se ne hai bisogno.
Casomai prova a spiegarci perche' l'uso di un char dovrebbe
migliorare le prestazioni, cioe' dicci a cosa ti servono questi
contatori.
ciao,
g.

 g.
ok, ora vi spiego
Ho un array tridimensionale, una griglia per intederci. Ogni punto
della griglia rappresenta un punto nello spazio 3d.
Per il momento ho una griglia di int che devo provare a far diventare
di char.
In ogni posizione ho salvato un contatore che mi indica se quel punto
verifica una determinata proprietà (sto effettuando degli studi sulle
proteine). Questo valore varia da -1 (punto di nessun interesse) a 9
(punto molto interessante).
I calcoli vengono fatti in parallelo su un cluster, quindi alla fine
ogni processore avrà un valore parziale del contatore.
Per tanto faccio una reduce (ossia per ogni punto nella griglia, sommo
il corrispodente risultato che ho su ogni singolo processore).
La griglia può avere anche dimensioni notevoli (tipo 300x300x300,
quindi 27.000.000 di punti) e pertanto per velocizzare i tempi di invio
della reduce tra i vari processori devo allegerire il tipo di dati
inviato (posso risparmiare anche qualche ora di calcolo).
E' chiaro il problema ora?

 E' chiaro il problema ora?
Non proprio, ma è molto interessante. In particolare i dati possono anche 
non esserci? Voglio dire, ogni punto della tua griglia contiene un valore, 
oppure il 90% della griglia è -1? In questo caso forse una struttura dati 
diversa potrebbe risolvere il problema della dimensione, a scapito -forse- 
della velocità di utilizzo della struttura da parte del singolo processore.
Per curiosità, che cosa calcola ogni processore? E quanti ne hai?
-- 
Costantino Grana 

 E' chiaro il problema ora?
Si ed e' anche piu' interessante.
Mi sembra di capire pero' che il problema sta piu'
nella trasmissione dei dati tra una macchina
e una altre che non nel tempo di calcolo.
In ogni caso e' difficile prevedere a priori
quale soluzione di impacchettamento sia la
piu' efficente per quel che riguarda il calcolo.
Molto puo' dipendere dall'ordine col quale
accedi al megaarray, e quindi da quanto sfrutti
la cache e da tanti altri fattori.
Se il collo di bottiglia e' la trasmissione,
puoi effettivamente compattare due valori
in un unico byte e poi scompattarli a destinazione:
supponendo di avere due valori interi x,y tra -1 e 9
li puoi "comprimere" in un singolo byte cosi':
z = (x+1) + ((y+1)<<4);
oppure
z = (x+1) | ((y+1)<<4);
ovvero, aggiungo sia a x che a y la costante 1 per riportarmi
nel range piu "umano" 0-10, poi prendo il valore di (y+1) e lo
moltiplico per 16, cioe' lo shifto a sinistra di 4 bit e lo
sommo o lo metto in OR con il valore di (x+1).
per tornare indietro:
prendo gli ultimi 4 bit di z e tolgo 1
x = (z & 15) - 1;
prendo i primi 4 bit di z (facendolo scorrere a destra) e
tolgo 1
y = (z >> 4) -1;
Questo per quanto riguarda la velocizzazione
della trasmissione.
Per quanto riguarda i dati sarebbe facilissimo
utilizzare lo stesso sistema per memorizzare i
contatori e farci i calcoli sopra, ma non
sono poi cosi' sicuro che la cosa
velocizzerebbe i calcoli. In ogni
caso non dovresti metterci molto
a modificare il programma per provare
almeno signed char, signed short int, e int.
Quello che magari perdi in maggiori accessi alla memoria,
lo guadagni magari in accessi piu' "allineati".
Nel caso tu volessi usare i contatori impacchettati,
allora dovresti magari definire la matrice come
qualcosa tipo M[300][300][300/2], poi codificare
i valori implicitamente aumentati di 1, per poter
lavorare nel range 0 ... 10.
A quel punto per incrementare un contatore di posto
(i,j,k) di 1 basterebbe fare una cosa tipo
M[i][j][k>>1] += (k&1?16:1);
cioe' incremento di 1 se k e' dispari oppure
incremento di 16 (quindi il nibble alto) se k e' pari.
O qualcosa di simile, tipo
M[i][j][k>>1] += (1-(k&1))<<4+(k&1);
per evitare il condizionale.
Insomma se c'e' bisogno si puo' pensare a qualche giochetto...
ciao,
g.

 Costantino Grana

 e una altre che non nel tempo di calcolo.
esatto...ecco il perchè dell'utilizzo del unsigned char
[cut]
le tue considerazioni sono molto interessanti....devo fare alcune
valutazioni di prestazioni per vedere se sono applicabili e cercare di
prevedere che aumento di performance mi possono portare
Ti ringrazio molto

 Ti ringrazio molto
Figurati, mi sono tornati in mente i bei vecchi
tempi in cui ho programmato un pochino sulla
Connection Machine e successivamente sul Cray T3D.
Anzi sarei curioso di sapere alla fine
quale tipo di intero ti da le migliori prestazioni.
ciao,
g.

 quale tipo di intero ti da le migliori prestazioni.
poi ti mando una copia della mia tesi, quando la finirò allora! :D

 poi ti mando una copia della mia tesi, quando la finirņ allora! :D
va bene! io sono g.resta chiocciola 
iit.cnr.it
(Un tempo ho lavorato un pochino sul protein folding,
ma poi non se ne e' fatto piu' nulla.)
ciao,
g.

 utilizzo tutti,ne ho usati al momento al massimo 30.
[..]
sicuro che il collo di bottiglia sia il trasporto dei valori? in fondo 27
milioni di char li puoi trasportare in circa 3 secondi su una rete normale
e in una frazione di secondo (credo nemmeno mezzo) su quel sistema..
ma forse dovrei conoscere meglio il tuo problema (se puoi, puoi mandare la
tesi completata anche a me, sembra molto interessante, qualsiasi indirizzo
di 
iuz-lab.info
)
-- 
www.iuz-lab.info

 
www.iuz-lab.info

La maggiort parte dei punti ha una valore basso compreso tra 0 e 2.
Sfruttando il fatto che i valori non sono equiprobabili
si può tentare un approccio probabilistico.
Poniamo che i valori 0,1,2 abbiano le seguenti probabilità di
trovarsi nella griglia:
Prob(0) = 0.30
Prob(1) = 0.30
Prob(2) = 0.30
Consideriamo ora la seguente codifica:
/* 1,2 o 3 bit per dato */
/* lsb --> msb */
0 --> 0
1 --> 10
2 --> 110
/* 6 bit per dato */
/* lsb --> msb */
-1 --> 111000
 3 --> 111001
 4 --> 111010
 5 --> 111011
 6 --> 111100
 7 --> 111101
 8 --> 111110
 9 --> 111111
Il valore medio di bit/valore è dato da:
n = 1 * 0.30 + 2 * 0.30 + 3 * 0.30 + 6 * 0.1 = 2.4
migliore quindi del 4 canonico della codifica usando
sempre un nibble.
Se il valore '0' ha una probabilità maggiore
si ottengono risultati ancora migliori.
Dipende dalla frequenza del singolo valore.
La codifica naturalmente sarà un pò più complessa.
Considerando l'input un  unico flusso di bit, visto
come un array di "unsigned char" si potrebbe avere
questo esempio di decodifica dei dati:
#include <stdio.h>
enum {
        STATE_0,
        STATE_1,
        STATE_2,
        LOOPSTATE3,
        LOOPSTATE4,
        MAX_STATE
};
#define RS(v)\
        do { ret = (v); state = STATE_0; } while (0)
/*
 * bit = 0 o 1
 * torna il valore o -1 se non ha
 * ancora decodificato
 *
 * occorre anche una routine di
 * "impacchettamento" da fare ... :-)
 */
int decode_input(int bit)
{
        static int tab[] =  {-1,3,4,5,6,7,8,9,};
        static int tab2[] = {0,1,2};
        static int state = STATE_0;
        static int v;
        int ret;
        ret = -1;
        switch (state) {
                case STATE_0:
                case STATE_1:
                case STATE_2:
                        if (bit) {
                                ++state;
                        } else {
                                RS(tab2[state]);
                        }
                        break;
                case LOOPSTATE3:
                case LOOPSTATE4:
                case MAX_STATE:
                        v |= bit << (MAX_STATE - state);
                        if (MAX_STATE == state) {
                                RS(tab[v]);
                                v = 0;
                        } else {
                                ++state;
                        }
                        break;
                default:
                        break;
        }
        return ret;
}
int main (void)
{
        printf("%d\n",decode_input(1)); /* LSB */
        printf("%d\n",decode_input(1));
        printf("%d\n",decode_input(1));
        printf("%d\n",decode_input(1));
        printf("%d\n",decode_input(1));
        printf("%d\n",decode_input(0)); /* '8' */
        printf("%d\n",decode_input(0)); /* '0' */
        printf("%d\n",decode_input(0)); /* '0' */
        return 0;
}
Come ulteriore spunto:
http://it.wikipedia.org/wiki/Codifica_di_Huffman
--
Giorgio Silvestri
DSP/Embedded/Real Time OS   Software Engineer

 questo esempio di decodifica dei dati:
...visto che non hai voluto farci una demo completa, :)
l'ho 'razzolata' giu' una io (e' solo una veloce prova).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SOGLIA_6BITS	3
/* ...ma si', mettiamo 'ste variabili globali! sono pigro :) */
static const int lvaTab[] = {0,1,2,-1,3,4,5,6,7,8,9};
unsigned char *get_convtab(void)
{
	static unsigned char conv_tab[11];
	size_t x;
	for(x = 0; x < sizeof(conv_tab); x++)
	{	if(x < SOGLIA_6BITS)
		{	int i;
			for(i = 0; i < x; i++)
				conv_tab[x] |= 1 << i;
			conv_tab[x] <<= 1;
		}
		else	conv_tab[x] = 0x38 | (x - SOGLIA_6BITS);
	}
	return conv_tab;
}
int encode_input_bits(int nVal, unsigned char *ucRet)
{
	static unsigned char *conv_tab = NULL;
	size_t x, uLen;
	*ucRet = 0;
	if(!conv_tab)
		conv_tab = get_convtab();
	uLen = sizeof(lvaTab) / sizeof(lvaTab[0]);
	for(x = 0; x < uLen; x++)
		if(nVal == lvaTab[x])
			break;
	if(x >= uLen)
		return -1;
 
	*ucRet = conv_tab[x];
	return x < SOGLIA_6BITS ? x + 1 : 6;
}
/*
  * bit = 0 o 1
  * torna il valore o -1 se non ha
  * ancora decodificato
  *
  * occorre anche una routine di
  * "impacchettamento" da fare ...  :-)
  */
#define RS(v)\
	do { ret = (v); state = STATE_0; } while (0)
int decode_input(int bit)
{
	enum {
		STATE_0, STATE_1, STATE_2,
		LOOPSTATE3, LOOPSTATE4, MAX_STATE
	};
	static int state = STATE_0;
	static int v;
	int ret;
	ret = -2;
	switch (state) {
		case STATE_0:
		case STATE_1:
		case STATE_2:
			if (bit) {
				++state;
			} else {
				RS(lvaTab[state]);
			}
			break;
		case LOOPSTATE3:
		case LOOPSTATE4:
		case MAX_STATE:
			v |= bit << (MAX_STATE - state);
			if (MAX_STATE == state) {
				RS(lvaTab[v + SOGLIA_6BITS]);
				v = 0;
			} else {
				++state;
			}
			break;
		default:
			break;
	}
	return ret;
}
int main (void)
{
	int aInpValues[] = 
{1,2,5,-1,0,0,1,0,4,5,9,3,1,2,7,9,1,-1,4,6,0,1,8,2,1,0,1,1};
	unsigned char bfOut[1024];
	int i, nRes, nBits;
	unsigned long uInd = 0, uIndBfOut = 0, uBitTot = 0;
	unsigned long uInpLen = sizeof(aInpValues) / sizeof(aInpValues[0]);
	unsigned char uc = 0;
	memset(bfOut, 0, sizeof(bfOut));
	puts("CODIFICA NUMERI...");
	for(uInd = 0; uInd < uInpLen; uInd++)
	{	uc = 0;
		printf("%d ", aInpValues[uInd]);
		if(!(nBits = encode_input_bits(aInpValues[uInd], &uc)))
		{	printf("** Errore di codifica\n");
			return EXIT_FAILURE;
		}
		uc <<= 8 - nBits;
		if(uIndBfOut >= (sizeof(bfOut)-1))
		{	printf("** Errore: array temp troppo piccolo\n");
			return EXIT_FAILURE;
		}
 
		for(i = 0; i < nBits; i++, uBitTot++)
		{	uIndBfOut = uBitTot >> 3; /* uBitTot / 8 */
			if(uc & 0x80)
				bfOut[uIndBfOut] |= 1 << (~uBitTot & 0x7);
			uc <<= 1;
		}
	}
	puts("\n");
	puts("DUMP BYTES COMPRESSI:");
	for(uInd = 0; uInd < uIndBfOut; uInd++)
		printf("0x%02X ", bfOut[uInd]);
	printf("\nNumeri in input = %lu - bit utilizzati = %lu (%lu 
bytes)\n\n", uInpLen, uBitTot, uIndBfOut);
	puts("DECODIFICA...");
	for(uInd = 0; uInd < uBitTot; uInd++)
	{	uIndBfOut = uInd >> 3; /* uInd / 8 */
		nRes = decode_input( (bfOut[uIndBfOut] >> (~uInd & 0x7)) & 0x1 );
		if(nRes >= -1)
			printf("%d ", nRes);
	}
	puts("");
	return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- 
Cybertoldo
Per rispondermi via email, sostituisci moc.liamg con 
gmail.com

 
http://it.wikipedia.org/wiki/Codifica_di_Huffman
ci stavo appunto pensando anche io ieri sera! Mi avrai mandato qualche
onda....
ciao


 }
...cmq, riscriviamola meglio (forse):
unsigned char *get_convtab(void)
{
	static unsigned char conv_tab[11];
	static int bInit = 0;
	size_t x;
	if(!bInit)	
	{	for(x = 0; x < sizeof(conv_tab); x++)
		{	if(x < SOGLIA_6BITS)
			{	int i;
				conv_tab[x] = 0;
				for(i = 0; i < x; i++)
					conv_tab[x] |= 1 << i;
				conv_tab[x] <<= 1;
			}
			else	conv_tab[x] = 0x38 | (x - SOGLIA_6BITS);
		}
		bInit = 1;
	}
	return conv_tab;
}
Ciao





 altrimenti non hai il numero corretto di byte di output!
...visto che bischerata! :)
di questa me ne ero gia' accorto, stavo per postare un piu' grezzo
uIndBfOut = (uBitTot + 7) / 8;
come correzione.
Ciao


 ......
L'ho aggiornato con le modifiche che mi hai indicato (spero di averle 
+/- inserite tutte). Pero' ho forti dubbi che una parametrizzazione 
troppo spinta, in un caso di codifica cosi' speciale, possa essere di 
grande aiuto...
Essendo cmq una demo, a questo punto penso che possa anche andar bene 
cosi'...
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
enum {
                 STATE_0,
                 STATE_1,
                 STATE_2,
                 LOOPSTATE3,
                 LOOPSTATE4,
                 MAX_STATE,
                 MAX_BITS
         };
#define VLEN_BITS_THRESH	LOOPSTATE3
#define NC(X)	(sizeof (X) / sizeof (X)[0])
static const int lvaTab[] = {0,1,2,-1,3,4,5,6,7,8,9};
unsigned char *get_convtab(void)
{
	static unsigned char conv_tab[NC(lvaTab)];
	static int bInit = 0;
	size_t x;
	if(!bInit)
	{	for(x = 0; x < sizeof(conv_tab); x++)
		{	if(x < VLEN_BITS_THRESH)
			{	int i;
				conv_tab[x] = 0;
				for(i = 0; i < x; i++)
					conv_tab[x] |= 1 << i;
				conv_tab[x] <<= 1;
			}
			else	conv_tab[x] = 0x38 | (x - VLEN_BITS_THRESH);
		}
		bInit = 1;
	}
	return conv_tab;
}
int encode_input_bits(int nVal, unsigned char *ucRet)
{
	static unsigned char *conv_tab = NULL;
	size_t x, uLen;
	*ucRet = 0;
	if(!conv_tab)
		conv_tab = get_convtab();
	uLen = sizeof(lvaTab) / sizeof(lvaTab[0]);
	for(x = 0; x < uLen; x++)
		if(nVal == lvaTab[x])
			break;
	if(x >= uLen)
		return 0;
 
	*ucRet = conv_tab[x];
	return x < VLEN_BITS_THRESH ? x + 1 : 6;
}
int decode_input(int bit, int *pnRetVal)
{
	static int state = STATE_0;
	static int v;
	int bRet = 0;
	switch (state)
	{
		case STATE_0:
		case STATE_1:
		case STATE_2:
			if (bit)
				++state;
			else
			{	*pnRetVal = lvaTab[state];
				bRet = 1;
				state = STATE_0;
			}
			break;
		case LOOPSTATE3:
		case LOOPSTATE4:
		case MAX_STATE:
			v |= bit << (MAX_STATE - state);
			if (MAX_STATE == state)
			{	*pnRetVal = lvaTab[v + VLEN_BITS_THRESH];
				bRet = 1;
				state = STATE_0;
				v = 0;
			}
			else	++state;
			break;
		default:
			break;
	}
	return bRet;
}
int main (void)
{
	int aInpValues[] = 
{1,2,5,-1,0,0,1,0,4,5,9,3,1,2,7,9,1,-1,4,6,0,1,8,2,1,0,1,1};
	unsigned char bfOut[(NC(aInpValues) * MAX_BITS) / CHAR_BIT + 1];
	int i, nRes, nBits;
	unsigned long ulInd = 0ul, ulIndBfOut = 0ul, ulBitTot = 0ul;
	unsigned long ulInpLen = sizeof(aInpValues) / sizeof(aInpValues[0]);
	unsigned char uc = 0u;
	memset(bfOut, 0, sizeof(bfOut));
	puts("CODIFICA NUMERI...");
	for(ulInd = 0ul; ulInd < ulInpLen; ulInd++)
	{
		printf("%d ", aInpValues[ulInd]);
		if(!(nBits = encode_input_bits(aInpValues[ulInd], &uc)))
		{	printf("** Errore di codifica\n");
			return EXIT_FAILURE;
		}
		uc <<= CHAR_BIT - nBits;
		for(i = 0; i < nBits; i++, ulBitTot++)
		{	ulIndBfOut = ulBitTot / CHAR_BIT;
			if(uc & (1u << (CHAR_BIT - 1)))
				bfOut[ulIndBfOut] |= 1 << (~ulBitTot % CHAR_BIT);
			uc <<= 1;
		}
	}
	ulIndBfOut = (ulBitTot + CHAR_BIT - 1) / CHAR_BIT;
	puts("\n");
	puts("DUMP BYTES COMPRESSI:");
	for(ulInd = 0ul; ulInd < ulIndBfOut; ulInd++)
		printf("0x%02X ", bfOut[ulInd]);
	printf("\nNumeri in input = %lu - bit utilizzati = %lu (%lu 
bytes)\n\n", ulInpLen, ulBitTot, ulIndBfOut);
	puts("DECODIFICA...");
	for(ulInd = 0ul; ulInd < ulBitTot; ulInd++)
	{	ulIndBfOut = ulInd / CHAR_BIT;
		if(decode_input( (bfOut[ulIndBfOut] >> (~ulInd % CHAR_BIT)) & 0x1, &nRes))
			printf("%d ", nRes);
	}
	puts("");
	return 0;
}
Per quanto riguarda il flusso dei dati in uscita dopo la codifica, pare 
evidente che dovrebbe essere 'anche' inviata (al computer che fara' la 
decodifica) la lunghezza in bit dello stream (eg. sopra si chiama 
ulBitTot) - ovvero: non e' possibile usare un byte con un particolare 
valore (inutilizzato) che possa indicare uno stop dei dati.
Dividendo il flusso in chunk discreti potrebbe anche essere piu' agevole 
passare, prima della trasmissione dei dati, un header che abbia almeno 
riportata la lunghezza in bit del flusso. In un header minimo che 
contenga solo la lunghezza, un valore di 0 potrebbe indicare che la 
trasmissione delle sequenze di chunks e' terminata...
In ogni caso, imho, il tutto dovrebbe essere relativamente semplice...
Ciao


"Cybertoldo" <cyber...@moc.liamg> ha scritto nel messaggio
news:ep13n7$me6$1...@registered.motzarella.org...

Il fatto di focalizzare sull'eliminazione di numeri "magici" o
la parametrizzazione del codice potrebbe non essere
di evidente utilità in un esempio così limitato.
Ma secondo me bisognerebbe farci l'abitudine.
Ne so qualcosa quando mi capita di lavorare su progetto
di centinaia di file (per la maggioranza non scritti da me)
dove proliferano numeri a destra e a manca.
Si diventa matti vedendo cose del tipo:
for (i=44; i<3455; ++i) {
    j += 466;
    /* ... */
}
in un file, e magari:
for (i=43; i<3454; ++i) {
    j += 266;
    /* ... */
}
in un altro file.
E scoprire poi che
44 non è correlato con 43,
3455 non è correlato con 3454
e
266 non è correlato con 466.
E' solo un esempio naturalmente ma vedere invece:
for (i=START_N_PIXEL; i<NPIX*FCT+GAP; ++i) {
    j += TOT_RANGE_M;
    /* ... */
}
e
for (i=NBIT - TOT_X; i<N_ITEMS; ++i) {
    j += SOME_OFFSET + BIT * C_F;
    /* ... */
}
porta ad una più facile manutenibilià e leggibilità
e a capire che due frammenti non sono in realtà
correlati (oppure lo sono in modo imprevisto!).
Non servono neppure i commenti con un codice
scritto in questo modo.
Inoltre per fare un variante dovrebbe essere
sufficiente modificare una o due macro e poco altro.
Quello della "fattorizzazione/parametrizzazione" del codice è
uno dei miei pallini ... :-)
