New/Dispose

[luigi.altomare]

 Saluti a tutti, mi sono presentato ieri nell'apposita sezione.

 Sono un dilettante ed ho molte lacune sulla gestione dei puntatori, nondimeno piu` volte ho avuto modo di usarli copiando bovinamente parti di codice all'interno di miei programmi (che hanno un unico utente: me stesso).

 Come in questo caso: avevo la necessita` di scrivere un mio programma di sorting e come base ho utilizzato il sorgente, ad opera di tale Peter Taranto, "MergeTest" conservato nelle SWAG, vecchia raccolta di sorgenti dos ora disponibile all'url http://swag.outpostbbs.net

 Il link diretto al programma e` http://kd5col.info/swag/SORTING/0063.PAS.html

 Il programma e` immediatamente compilabile con fpc senza dover cambiare nemmeno un byte.

 L'algoritmo della funzione MergeSort e` veloce ed efficiente e non pare dare problemi. Viceversa la funzione che riempie la lista da ordinare non libera la memoria usata. Infatti dopo aver compilato il sorgente con fpc -gh, eseguendo il programma risulta:

  --------------------------------------------------
  Heap dump by heaptrc unit
  7 memory blocks allocated : 84/112
  1 memory blocks freed : 12/16
  6 unfreed memory blocks : 72
  True heap size : 98304 (64 used in System startup)
  True free heap : 97664
  Should be : 97760
  --------------------------------------------------

 Trascrivo in calce il codice che genera queste imprecisioni. Si tratta di un programma che si limita alla funzione oggetto di esame: Type/Procedure/Function sono quelle dell'autore originario, le poche linee di codice per coordinarle sono mie.

 La costante "Elementi" e` pure mia, e l'ho fissata bassa (=7) perche`, oltre alla sintesi che ho riportato, fpc -gh genera un enorme numero di informazioni proporzionale al numero di errori trovati. Con fpc -ghl restituisce anche il numero di linea del codice dove avviene l'allocazione di memoria, se disponibile. Purtroppo in questo caso non ha fornito informazioni utili.

 La funzione "RandomList" non libera tutti i blocchi di memoria ma ne lascia "Elementi-1" occupati. Ritengo che sia responsabile di cio` l'istruzione "new" (evidenziata nel sorgente sotto riportato) contenuta nel il ciclo reiterato, appunto, "Elementi-1" volte.

 Tale errore risulta anche compilando con -gh il sorgente originario. Non si tratta, quindi, di una conseguenza del mio adattamento.

 Mi pare che manchi l'istruzione "dispose" corrispondente a "new". Mettendola qua e la`, dove mi pareva corretto, ho ottenuto solo indifferenza oppure errori 216 (Access Violation). Ho inserito efficacemente l'ultima (unica "dispose" presente nell'intero codice) che infatti ha liberato un blocco di memoria in piu`.

 La domanda quindi e`: Dove va messa l'istruzione "dispose"?

 Oppure, in alternativa: Come si riempie quella lista senza lasciare indietro blocchi di memoria?

 Mi interessa molto perche` l'implementazione di MergeSort e` ottima (veloce anche con milioni di linee da ordinare, ho fatto dei test comparativi) ma e` strutturata per quel tipo di lista che deve pur essere riempita.

 Saluto e ringrazio per l'attenzione.

 Luigi Altomare

 Segue quindi il codice:

{-------------------------------------------------------------------------}
  Const Elementi=7;
{-------------------------------------------------------------------------}
  Type
    PNodeType = ^NodeType;
    NodeType = Record
      Val  : DWord;      {The Value of the node}
      Prev : PNodeType;  {The Previous Node in the List. This equals nil when first in list}
      Next : PNodeType;  {The Next Node in the List. This equals nil when last in list}
    End; // Record NodeType
{-------------------------------------------------------------------------}
  Procedure ShowList(Lst:PNodeType);
    Begin
      While Lst <> Nil Do
        Begin
          writeln(Lst^.Val:6);
          Lst:=Lst^.Next;
        End; // while
    End; // Procedure ShowList
{-------------------------------------------------------------------------}
  Function RandomList(Item:Dword):PNodeType;
    var
      Index:dword;
      TempList:PNodeType;
    begin
       new(RandomList);
       RandomList^.Val  := Random(1000000);
       RandomList^.Prev := Nil;
       TempList := RandomList;
       For Index:= 2 To Item Do // <-- ciclo for (vedi sopra)
         Begin
           new(TempList^.Next); // <-- new (vedi sopra)
           TempList^.Next^.Prev := TempList;
           TempList := TempList^.Next;
           TempList^.Val := Random(1000000);
           TempList^.next := Nil;
         End; // for
    end; // Function RandomList
{-------------------------------------------------------------------------}
    var
      NodeTest:PNodeType;
    begin
      Randomize;
      NodeTest:=RandomList(Elementi);
      writeln('------');
      ShowList(NodeTest);
      writeln('------');
      dispose(NodeTest);
    end.
{-------------------------------------------------------------------------}

[nomorelogic]

Ciao Luigi,

Il dispose è nel posto giusto però mentre la funzione RandomList alloca 7 record, la dispose ne libera solo 1.
Dovresti fare una procedura che libera tutta la catena, partendo dall'ultimo elemento e risalendo in cima (o viceversa).
Per aiutarti a capire: in RandomList la new viene richiamata 7 volte mentre la dispose 1 volta sola.

Questo è evidente se fai i seguenti calcoli:
1) la dimensione di NodeType è di 12 byte (1 DWord + 2 puntatori = 4 * 3 = 12)
2) heaptrc di dice: 6 unfreed memory blocks : 72
3) 6 blocchi (che guarda caso sarebbe 7 new - 1 dispose di cui ti dicevo sopra) * 12 = 72

Soluzione: devi fare una procedura che scansioni e liberi la lista.

Mi permetto 2 consigli.

Consiglio nr. 1
oltre a new/dispose c'è anche un altro modo per allocare la memoria ed è getmem/freemem
la differenza è che con getmem/freemem devi calcolare l'intero ammontare di byte di cui hai bisogno di modo da eseguire una unica istruzione per allocare (getmem) ed una unica per deallocare (freemem)
Dovendo fare una procedura di sort direi che bisognerebbe preservare la velocità di esecuzione. Per sortare una lista di 10000 elementi hai bisogno di 2 loop dove esegui 10000 new e poi 10000 dispose.
Con 10000 se usi il metodo getmem hai sempre e solo 2 istruzione a prescindere dalla lunghezza della lista.

Consiglio nr. 2
In pascal è possibile riferirsi al risultato di una funzione chiamandolo come la funzione stessa. E' tuttavia una metodologia di programmazione datata: oggi si dovrebbe usare la keyword "result".

[xinyiman]

Nomore sei stato più veloce di me

Comunque caro luigi se ti interessa approfondire il discorso puntatori e liste, datti un occhiata ai seguenti due tutorial.

http://www.lazaruspascal.it/index.php?page=34
http://www.lazaruspascal.it/index.php?page=18

[luigi.altomare]

Ringrazio per la risposte.
Non ho capito, pero` come si inserisca il testo a cui si risponde (una volta si diceva "quotare") in una finestra scorrevole? (BTW: come si inserisce un codice in una finestra scorrevole?) Scusate se uso il vecchio sistema anteponendo il segno ">".

----------------------------------------------------------------
per nomorelogic:

>Il dispose e` nel posto giusto pero` mentre la funzione RandomList alloca 7 record, la dispose ne libera solo 1.
>Dovresti fare una procedura che libera tutta la catena, partendo dall'ultimo elemento e risalendo in cima (o viceversa).
>Per aiutarti a capire: in RandomList la new viene richiamata 7 volte mentre la dispose 1 volta sola.

Questo l'avevo intuito, e l'ho anche scritto nel post. Anzi mi e` venuto lo schiribizzo di provare heaptrc proprio perche` avevo notato l'assenza di "dispose", l'unica che c'e` l'avevo messa io.

>Soluzione: devi fare una procedura che scansioni e liberi la lista.

Questo, invece, non lo intuisco. Cioe` non saprei da che parte iniziare. Quando e` cosi` faccio un po` di prove e qualcosa esce fuori. In questo caso invece non sono riuscito a combinare niente.

>Consiglio nr. 1
>oltre a new/dispose c'e` anche un altro modo per allocare la memoria ed e` getmem/freemem
>la differenza e` che con getmem/freemem devi calcolare l'intero ammontare di byte di cui hai bisogno di modo da eseguire >una unica istruzione per allocare (getmem) ed una unica per deallocare (freemem)

Vedro` di trovare il modo di riempire quella lista con getmem/freemem. Per ora non ne ho idea, provero`. Ti sarei grato se potessi darmi qualche hint.

>Dovendo fare una procedura di sort direi che bisognerebbe preservare la velocita` di esecuzione. Per sortare una lista di >10000 elementi hai bisogno di 2 loop dove esegui 10000 new e poi 10000 dispose.
>Con 10000 se usi il metodo getmem hai sempre e solo 2 istruzione a prescindere dalla lunghezza della lista.

Non ho scritto il nucleo della procedura di sort ma l'ho trovato in rete (vedi il post iniziale per i riferimenti). L'ho adottato subito: ho fatto dei test comparativi ed e` piu` veloce del sort di Windows (poco piu` veloce, ma mooolto piu` veloce, ad esempio, di sort delle CoreUtility di GnuWin32, scritto, credo, in C).

Ordina un file di testo di 6,5 milioni di linee in 35 secondi (compresa la lettura dei dati), mentre il sort di Windows ne impiega 50. La cosa buffa e` che compilato a 32 bit e` piu` veloce di quello a 64 bit (nel caso in specie 35 sec a 64 bit, 31 sec a 32 bit), pero` quello a 32 bit va in crisi (cioe` esce con overflow) per 6,8 milioni di linee, mentre a 64 bit ha ordinato in 80 secondi un file di 7 milioni di linee. Non ho provato oltre. Inutile sottolineare che il file era sempre lo stesso. La velocita` di sort dipende molto dalle condizioni iniziali del file.

Considerando pero` il topic di questo thread, cioe` la liberazione della memoria, significa che il programma ha lasciato in giro "orfani" 7 milioni di blocchi di memoria. E non e` successo niente. Se e` successo non me ne sono accorto. Quando sono liberati questi blocchi? Quando si spegne il computer? Quando il programma finisce?

>In pascal e` possibile riferirsi al risultato di una funzione chiamandolo come la funzione stessa. E' tuttavia una metodologia >di programmazione datata: oggi si dovrebbe usare la keyword "result".

Per "result" occorre compilare con Delphi Mode ON? Oppure c'e` qualche altro modo? La compilazione "liscia" mi da` errore.

----------------------------------------------------------------

per xinyiman

>Comunque caro luigi se ti interessa approfondire il discorso puntatori e liste, datti un occhiata ai seguenti due tutorial.
>http://www.lazaruspascal.it/index.php?page=34
>http://www.lazaruspascal.it/index.php?page=18

Spero di avere il tempo per farlo. Ho provato varie volte a studiare i puntatori ma non ho mai cavato un ragno dal buco.

----------------------------------------------------------------

Saluti a tutti e grazie per l'attenzione.

Luigi Altomare

[Stilgar]

Ciao Luigi.
Quello che suggeriva nomore è una cosa del genere ... a spanne ...

Codice: [Seleziona]

var p : PNodeType;
while p^.next<> nil do
begin
   p := p^.next;
end;
while (p <> NodeTest) do
begin
  if assigned(p^.next) then dispose(p^.next);  // Evita casini sull'ultimo nodo.
  p := p^.prev;
  p^.next := nil;
end;

Questo codice libera tutti gli elementi ecluso il primo. Ma quello lo liberavi già tu.

Per i puntatori .. nulla di strano o fastidioso. Sono solo numeri. Tanta gente si spaventa ... l'idea della gestione della memoria spaventa tante persone.

Vista la fonte, credo che ti possa essere d'aiuto ad imparare parecchie cosine, non solo sui puntatori.
Se trovi scritture all'indirizzo 0800:0000 (se ricordo bene), stanno scrivendo direttamete sulla scheda video in modo testo.
Non credo che quei sorgenti possano produrre eseguibili che riescano a girare sotto windows o linux.
Può essere interessante studiarli come "archeologia" software

Stilgar

[luigi.altomare]

 Rigrazio Stilgar per la soluzione che si e` incrociata con una che ho provato in seguito agli spunti che ho letto in questo forum, senza i quali non sarei riuscito a trovarla.

 Le soluzioni mi sembrano simili, ma non identiche. Provero` anche quella. Avevo praparato un post che invio comunque. L'avevo intitolato: Fu vera gloria?

 Eccolo:

 Dunque ... dalli e dalli qualcosa sono riuscito a fare. Non so come pero`: prova questo, prova quello, scopiazza di qua, scopiazza di la` e` venuta fuori una procedura, alla quale non sarei mai arrivato senza aver letto le parole di nomorelogic, che quindi ringrazio.

 >Dovresti fare una procedura che libera tutta la catena,
 >partendo dall'ultimo elemento e risalendo in cima

 Ribadisco che mi sfugge il funzionamento esatto di questa procedura. C'era una discussione di argomento simile in un forum in inglese. L'unico merito che mi attribuisco e' di aver capito che poteva essere quello il ciclo di cui parlava nomorelogic. Quanti ne ho provati inutilmente, pero`. Comunque eccola qua:

 {--------------------------------------}
  procedure DeleteNode(Targ:PNodeType);
    var
      pNode:PNodeType;
    begin
      while Targ<>nil do
        begin
          pNode:=Targ;
          Targ:=Targ^.Next;
          Dispose(pNode);
        end; // while
    end; // procedure DeleteNode
 {--------------------------------------}

 Inserita nel codice che ho postato ieri, ed inserita la relativa chiamata "DeleteNode(NodeTest)" in luogo dell'unica istruzione dispose che era presente, ha risolto la questione della deallocazione della memoria. Ho provato con milioni di elementi ed heaptrc e` sempre rimasto contento.

 Bene, si dovrebbe dire, ed invece no. Ho sempre quel dubbio: serve liberare la memoria?

 Se si libera da se` all'uscita del programma scervellarsi per liberarla un millisecondo prima non ha molto senso.

 Non solo: ma il ciclo di deallocazione porta via tempo ed infatti il programma di sorting che ho scritto, dopo l'introduzione della modifica, lo ha reso formalmente corretto (esce sempre con zero memory blocks) ma piu` lento. Il tempo per il sorting si e` allungato di circa il 10%. C'e' quindi da chiedersi se convenga avere un codice sporco e guadagnare il 10% di tempo oppure il contrario.

 Ancora: girando in rete alla ricerca di spunti ho visto molti sorgenti nei quali spesso il problema della deallocazione non e` molto sentito.

 Ad esempio: http://spir.wikidot.com/pascal-doubly-linked-list c'e` un codice che fpc compila al volo, e pare funzionare. A differenza di altri per i quali la compilazione spesso si inceppa da qualche parte. Il sito appare ben fatto. Invece se compilato con fpc -gh, heaptrc tira fuori una caterva di allocazioni non risolte.

 Quindi c'e` veramente da chiedersi se sia utile preoccuparsi di deallocare la memoria, cioe` se fu vera gloria l'essere riuscito a trovare la procedura per liberarla.

 Pervero nel mio programma la deallocazione non e` proprio l'ultima cosa. La presenza di memoria inutilmente allocata quali inconvenienti _pratici_ da`?

 Inoltre nomorelogic aveva parlato di GetMem/FreeMem senza cicli, tutto in un colpo solo. Negli esempi che ho trovato in giro pare che queste istruzioni siano state fatte lavorare su singoli puntatori come New/Dispose. Qualche suggerimento per modificare il codice che ho postato nel senso indicato da nomorelogic?

 Saluto e ringrazio per l'attenzione.

 Luigi Altomare

[Stilgar]

Luigi ...
La versione che ho preparato al volo era quella che suggeriva nomore.
Dalla fine all'inizio.
Tu ha preparato quella che parte dall'inizio e arriva alla fine.

Luigi .. allocazione e deallocazione della memoria sono il PANE del programmatore.
Quelli che non si preoccupano di questi dettaglio possiamo definirli degli smanettorni?

In altre parole .. scenario (esasperato)
"va lento il cluster di 200 nodi con milioni di tera di ram con un esercito di processori in parallelo?
Colpa di java ... o di oracle, io ho solo scritto la count".
Pian e ben .. non è che mi stai usando Hibernate e stai caricando tutto il datawarehouse per fare una select count?

Si parte del non voler controllare la memoria e si passa a non voler pensare a nulla ... perchè ci si deve concentrare sull'algoritmo

La esaspero per strappare un sorriso.

Il fatto di avere memoria allecata "inutilmente" a tendere la occupi tutta. Credo possa essere sconveniente

Stilgar

[nomorelogic]

ciao e scusate la latitanza, a volte torno nella vita reale ;P

Inserita nel codice che ho postato ieri, ed inserita la relativa chiamata "DeleteNode(NodeTest)" in luogo dell'unica istruzione dispose che era presente, ha risolto la questione della deallocazione della memoria. Ho provato con milioni di elementi ed heaptrc e` sempre rimasto contento.

 Bene, si dovrebbe dire, ed invece no. Ho sempre quel dubbio: serve liberare la memoria?

 Se si libera da se` all'uscita del programma scervellarsi per liberarla un millisecondo prima non ha molto senso.

Stilgar ti ha già risposto ed anche molto bene

comunque, è vero che i moderni sistemi operativi isolano i programmi in un'area di memoria ed al momento dell'uscita liberano la memoria utilizzata ma:
- fpc non compila solo per i moderni sistemi operativi
- una piattaforma target potrebbe essere un dispositivo android dove le applicazioni rimangono sempre in memoria
- se il progamma esce a causa di un errore... dipende
- se il leak of memory lo hai su un loop che gira su una applicazione di un server, pianti tutto il server
- se il tuo programma non viene chiuso (molti utenti non spengono il pc che dopo un paio di settimane), occupi risorse
- se il tuo leak of memory è in una libreria, tutti i programmi che usano la libreria avranno questo problema (non ti fai un buon nome nel caso )

Senza contare che, almeno in teoria, un algoritmo dovrebbe essere efficace (deve funzionare) ed efficiente (deve occupare meno tempo e risorse possibili).
Last but not least: il pascal è un linguaggio di programmazione e non di scripting (con tutto il rispetto di chi scrive script ma in quel caso non hanno questo problema perché lo script viene eseguito da un interprete che è un programma che non deve avere leak of memory).

Inoltre nomorelogic aveva parlato di GetMem/FreeMem senza cicli, tutto in un colpo solo. Negli esempi che ho trovato in giro pare che queste istruzioni siano state fatte lavorare su singoli puntatori come New/Dispose. Qualche suggerimento per modificare il codice che ho postato nel senso indicato da nomorelogic?

getmem ti permette un uso a basso livello della memoria, solitamente è meglio usare new/dispose ma per i casi dove devi allocare qualche milione di record allora bisogna usare le maniere forti.
Per usare getmem devi inoltre afferrare il concetto di aritmetica del puntatore, questo ti serve per spostarti all'interno dell'area di memoria allocata.

"aritimetica dei puntatori for dummies"
spostare un puntatore al primo byte del prossimo record vuol dire spostarlo di tanti byte quanti sono quelli necessari per contenere il record corrente.


Nell'esempio sotto trovi uno spunto per capire sia come usare getmem che come muoversi con i puntatori.
http://www.delphibasics.co.uk/RTL.asp?Name=GetMem
Tra l'altro noto che nell'esempio NON hanno liberato la memoria...

Non solo: ma il ciclo di deallocazione porta via tempo ed infatti il programma di sorting che ho scritto, dopo l'introduzione della modifica, lo ha reso formalmente corretto (esce sempre con zero memory blocks) ma piu` lento. Il tempo per il sorting si e` allungato di circa il 10%. C'e' quindi da chiedersi se convenga avere un codice sporco e guadagnare il 10% di tempo oppure il contrario.

Si ma tu devi cronometrare il tempo del sort mica pure del loading e della liberazione delle risorse...
Se i 7 milioni di record sono su un nastro, guardando i tempi, emergerebbe un algoritmo pessimo.

Edit:
per ottimizzare tutto il programma devi fare con getmem