Newsgroup: it.comp.lang.c
Titolo: Ottimizzazione utilizzo liste concatenate

Ciao a tutti,
stavo cercando di ottimizzare un programma per l'elaborazione di dati di
scansioni laser fotogrammetrici quando sono incappato in un comportamento
che non riesco a spiegarmi.
Dunque, una parte del codice su cui sono intervenuto consiste nella
creazione di una matrice bidimensionale di puntatori a struct che chiamerň
"struct elemento" che altro non sono che liste concatenate che rappresentano
un insieme di punti in una data cella della matrice. Quindi dalla posizione
x,y della matrice accedo al primo elemento della lista che potrň scorrere in
maniera abituale per analizzare i punti dell'insieme.
Visto che in varie parti del programma si "spendeva" parte dell'elaborazione
solo per contare i punti contenuti in queste liste (con dei cicli while che
si facevano passare tutte le liste) ho pensato che potesse portare ad un
miglioramento intervenire sulla procedura di caricamento dati aggiungendo un
membro alla "struct elemento" che contasse i punti contenuti nella lista.
Al momento dell'accesso ad una cella della matrice mi era cosě possibile
sapere quanti elementi avrei trovato nella lista semplicemente recuperando
il valore del contatore contenuto sul PRIMO elemento.
Oh, mi ero dimenticato di dirlo: la matrice consiste in almeno un milione di
queste celle da cui partono mediamente liste concatenate di una ventina di
struct elemento.
Contrariamente a quanto mi aspettavo le prestazioni del programma sono
peggiorate (quasi del doppio) invece che migliorare.
Visto che il mio bilancio era qualcosa di simile:
FATTORI NEGATIVI:
struct elemento piů grossa
aggiunta un'operazione di somma per incrementare il contatore nella
procedura di caricamento dati
FATTORI POSITIVI:
eliminati cicli while per contare i punti su ogni cella della matrice
non riesco a spiegarmi questo comportamento: forse il fatto di avere le
struct piů grosse č la spiegazione?
Chi sa darmi qualche indizio?
Grazie
Bye
John


Se puoi crea una variabile, e ogni volta che viene creato un nuovo nodo, 
la incrementi.
Cosě in ogni momento sai la dimensione della lista.
Le prestazioni sono peggiorate perchč hai aggiunto una nuova var ad ogni 
nodo, causando un'appesantimento
sia nella allocazione della memoria per ogni nodo che nella sua 
gestione. Ovviamente č peggiorato perchč sicuramente
si parla di migliaia o forse piů di nodi.

 si parla di migliaia o forse più di nodi.
Come già detto la matrice conta circa un milione di puntatori a struct
elemento e da ogni struct partono mediamente una venita di nodi, quindi le
malloc coinvolte sono: una iniziale con un milione di elementi e le
successive per la creazione dei singoli elementi.
Bye
John


Cerca di posizionare la var solo nei nodi principali e non in tutti. Ho 
capito il problema,
ma senza sapere di che si tratta, vedendo il codice, è difficile 
ottimizzarlo.
Prova una variabile contatore *esterna alla struttura elemento* che 
conta ogni "elemento" che viene allocato
per le struct che partono da elemento, se conosci già il num o non ti 
interessa saperlo, hai risolto; se ti interessa
potresti inserire una var nella struct dipendenti da elemento, ma le 
prestazioni in questo caso peggiorano anche se
di poco essendo poche pendenze.

 di poco essendo poche pendenze.
Ok grazie, ora ho capito cosa intendevi.
Farò qualche prova.
Ciao
John

 spesso il S.O. ad intervenire per caricare nuove pagine in memoria?
Quest'ultima mi pare l'ipotesi più plausibile. Se ho ben capito, la tua
struttura dati, già pesante di suo, s'è ingrandita di almeno 20 milioni di
byte (nell'ipotesi che il contatore sia un char, altrimenti anche il
doppio o il quadruplo). È più che abbastanza per mettere in ginocchio la
memoria virtuale di molti sistemi.
Così in astratto, senza sapere i dettagli, mi vengono in mente un paio di
possibili ottimizzazioni. Se siano applicabili o no lo devi vedere tu.
1) La matrice ha grandi aree "vuote"? Per vuote intendo che contengono un
puntatore NULL o comunque che contengono un valore estremamente ricorrente
che potrebbe essere considerato "il default". Se la risposta è sì,
potresti provare a trasformare la matrice in una lista (sorted array, hash
table, ecc.) in cui le coordinate (x,y) fungono da chiave. In questo modo
elimini non solo la memoria sprecata per le caselle "vuote" ma potresti
anche velocizzare notevolmente il codice che scandisce la matrice, perché
il cicli solo sulle caselle "piene".
2) Ci sono tante caselle che contengono una catena identica a quella
contenuta in un'altra casella, o anche solo identica alla parte finale
della catena di un'altra casella? Se sì, potresti ottimizzare la routine
di caricamento. Prima di inserire una catena in una casella, si ripassa
tutte le caselle precedentemente inserite alla ricerca di una catena con
la coda identica: se la trova riutilizza lo stesso puntatore, anziché
allocare una catena nuova. Ovviamente, la routine di caricamento diventa
così molto più complicata (e lenta), ma ci guadagni in memoria.
I due approcci non si escludono a vicenda, e non escludono (soprattutto il
primo, che già prevede una nuova struttura di "testa" per contenente la
chiave x,y) la tua idea di tenere un contatore della lunghezza delle
catene.
--
Cingar
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it


Grazie dei consigli anche se temo che nessuno dei due scenari da ipotizzati
si adegui alla mia situazione: la matrice ha abbastanza uniforme e presenta
poche celle vuote e le catene sono tutte le une diverse dalle altre.
Comunque mi interessava capire cosa avesse tanto peggiorato la situazione
con la mia modifica, credo di aver avuto qualche conferma da parte vostra.
Bye
John