linux user group brescia

On Thu, 8 May 2003, Gabriele Villi wrote:

	Rispondo qui anche a tutte le altre, mi scuso per la malavoglia di 
distribuire il tutto in 3/4 mail diverse ;-P

> Alle 09:27, giovedì 08 maggio 2003, Maurizio Paolini ha scritto:
> > Io invece interpretavo la domanda in modo diverso: quando alloco una struct
> > con malloc, immagino sia sensato che venga allocato spazio dal gestore
> > della memoria in modo da poter poi riliberare lo spazio e/o altre
> > operazioni del tutto estranee al compilatore.

	Perfetto. Era esattamente questo. E avete risposto. Inoltre stavo 
decisamente dimenticando l'allineamento, e la frammentazione (chi mi dice 
che effettivamente il primo byte libero e' a un multiplo di 4?), ecc.

> Confermo: da quanto mi ricordo il so gestisce la memoria basandosi su una 
> lista di blocchi liberi; tuttavia, sempre se la _mia_ :) memoria non mi 
> inganna, si cerca mettere le informazioni di servizio (ad es. puntatori al 
> prox/precendente blocco libero, dimensione ecc) proprio nello spazio 
> "libero", in modo da non appesantire inutilmente lo spazio realmente allocato 
> dall'utente. 

	E penso che a questo punto quello che guadagno con una gestione 
"oculata" della memoria da parte del prog venga perso dal SO, anche in 
tempo di elaborazione...
	Questa parte di accesso e' una grossa parte del programma di 
ottimizzazione che sto scrivendo. Se ci impiega il doppio vuol dire che 
deve smacchinare per 2 settimane anziche' 1...

[snip]

> Mi sembra quindi sensato il suggerimento di allocare blocchi il piu' grandi 
> possibile se il prezzo in termini di complicazione del codice non e' 
> eccessivo. Inoltre cercherei di usare strutture e tipi che siano compatibili 
> con gli allineamenti "graditi" al processore; in parole povere, una stringa 
> di bit  non la farei lunga quanto la cardinalita' massima dell'insieme, ma 
> cercherei di accorpare piu' stringhe fino a raggiungere una dimensione 
> multipla di 4 byte (o quel che e' per il tuo processore). Chiaro che bisogna 
> vedere se il gioco vale la candela...

	Sto pensando che la soluzione migliore sia davvero un vettore di 
"unsigned" da 32 bit, ogni bit in questo vettore identifica la presenza o 
meno nell'insieme dell'elemento col suo indice.
	A questo punto se N e' l'indice dell'elemento da controllare
N>>5 e' l'intero che lo (puo') contenere
N&31 e' il bit associato in quell'intero
	Tempo di accesso \varepsilon, tempo di aggiornamento \varepsilon, 
inoltre per ogni insieme alloco UNA volta perche' gli insiemi hanno tutti 
la stessa cardinalita' massima da stabilire a priori.

	Grazie dei suggerimenti, se avessi implementato la lista linkata 
"ciecamente" mi sarei trovato con molta piu' memoria utilizzata e un 
"traffico" di operazioni di ricerca da fare ad ogni passo.
	Senza parlare dei tempi necessari per confrontare il contenuto di 
due liste linkate...

-- 
						Ciriciao
					LtC. Melkor?! B. Xapatan

PS: Dove si puo' scoprire quanto lunghe sono le parole utilizzabili dalla 
ALU del processore in un blocco (di quanti bit posso fare l'AND 
contemporaneamente) senza andare a cercare il datasheet del processore? E 
"possibilmente" usando il C standard sotto il pinguino, non ho intenzione 
di impelagarmi con l'assembler solo per passare da 32 a 64 bit!