Analisi di prestazione dell'interprete tuProlog su piattaforma Java - Tesi

ALMA MATER STUDIORUM - UNIVERSITA DI BOLOGNA

FACOLTA DI INGEGNERIA

Corso di Laurea Triennale in Ingegneria Informatica

Tesi di Laurea in Fondamenti di Informatica L-B

Analisi di prestazionedell’interprete tuProlog

su piattaforma Java

CandidatoMichele Damian

RelatoreChiar.mo Prof. Enrico Denti

Anno Accademico 2007/08

Indice

Introduzione vii

1 Il motore tuProlog 1

2 Benchmarks 7

2.1 Profilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1 Il profiler HPROF . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Teorie di test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Analisi dei tempi di esecuzione 13

3.1 Metodo di profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 Tempi di esecuzione dei metodi . . . . . . . . . . . . . . . . . . . . 15

3.3 Analisi della scalabilita . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.4 Grafo delle chiamate . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Analisi dell’utilizzo della memoria 25

4.1 Metodo di profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 Allocazione degli oggetti in memoria . . . . . . . . . . . . . . . . . 26

4.3 Analisi del garbage collector . . . . . . . . . . . . . . . . . . . . . . 32

4.4 Grafo delle allocazioni . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Confronto con la versione tuProlog 1.3 39

6 Conclusioni 41

i

Elenco delle figure

1.1 Il pattern state che realizza la macchina a stati finiti . . . . . . . . 3

1.2 La macchina a stati finiti del motore tuProlog . . . . . . . . . . . . 4

3.1 Analisi delle chiamate ai metodi piu utilizzati nell’esecuzione delle

teorie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.1 Analisi delle istanziazioni degli oggetti piu allocati nell’esecuzione

delle teorie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

iii

Elenco delle tabelle

3.1 Tempi di esecuzione per cento risoluzioni e errore relativo calcolato

per una singola esecuzione. . . . . . . . . . . . . . . . . . . . . . . . 15

3.2 Tempi di lettura ed esecuzione. . . . . . . . . . . . . . . . . . . . . 16

3.3 Analisi dei metodi. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.4 Analisi dei metodi totale. . . . . . . . . . . . . . . . . . . . . . . . . 20

3.5 Analisi della scalabilita del motore tuProlog. . . . . . . . . . . . . . 21

3.6 Associazione fra il numero identificativo di un nodo nella Figura 3.1

e il metodo che esso rappresenta. . . . . . . . . . . . . . . . . . . . 23

4.1 Analisi degli oggetti utilizzati. . . . . . . . . . . . . . . . . . . . . . 30

4.2 Analisi dell’utilizzo della memoria da parte degli oggetti rispetto

all’obiettivo della teoria. . . . . . . . . . . . . . . . . . . . . . . . . 31

4.3 Analisi complessiva degli oggetti utilizzati. . . . . . . . . . . . . . . 32

4.4 Analisi del garbage collector. . . . . . . . . . . . . . . . . . . . . . . 35

4.5 Associazione fra il numero identificativo di un nodo nella Figura 4.1

e l’oggetto che esso rappresenta. . . . . . . . . . . . . . . . . . . . . 36

5.1 Comparazione dei tempi di esecuzione nelle singole teorie. . . . . . . 40

5.2 Comparazione dell’allocazione della memoria nelle singole teorie. . . 40

v

Introduzione

Il motore tuProlog e un interprete per il linguaggio Prolog, scritto interamente

in Java e interoperabile con le librerie fornite dalla piattaforma di sviluppo JDK.

Giunto recentemente alla versione 2.1, ha portato con se diversi cambiamenti dal

punto di vista strutturale. L’obiettivo del lavoro e quello di analizzare le pre-

stazioni dell’interprete in modo tale da porre delle basi utili per un suo ulteriore

miglioramento in versioni successive. Alla conclusione, all’eventuale revisore del-

l’interprete, sara chiaro su quali parti del codice dovra orientare la sua attenzione

per apportare dei miglioramenti. A questo proposito l’analisi viene scomposta in

due sezioni, con lo scopo di mettere in luce l’utilizzo della cpu e l’allocazione della

memoria heap da parte dei metodi e delle classi implementate dal motore. Per

quanto riguarda le prestazioni in termini di velocita, allo stato attuale, i dati a di-

sposizione si basano unicamente sui tempi di esecuzione di alcune teorie utilizzate

come benchmark per interpreti Prolog e considerate standard per test prestazionali

di questo tipo di motore. A causa della variazione del sistema hardware sul quale

vengono eseguiti i test, queste teorie pero non garantiscono tempi di esecuzione ab-

bastanza elevati da poter essere misurati con un apprezzabile errore sulla misura.

Per questo motivo ad esse devono essere aggiunte delle nuove teorie per ottimizzare

il benchmark. Un altro obiettivo che il lavoro si pone e quello di analizzare come

sono cambiate le prestazioni dell’interprete in seguito al passaggio dalla versione

1 alla versione 2, la quale ha introdotto alcune modifiche a livello architetturale.

In particolare viene presa come riferimento l’ultima release di ognuna delle due

versioni, le quali sono rispettivamente la release 1.3 e 2.1.

La dissertazione e strutturata in modo da rendere piu comprensibile possi-

bile il motivo delle scelte fatte durante il progetto. Il Capitolo 1 presenta il motore

vii

tuProlog, spiegando quali sono le caratteristiche principali dell’interprete e facendo

un’analisi di alto livello del suo funzionamento. Nel Capitolo 2 vengono discussi

i motivi che hanno portato alla scelta di HPROF come strumento di profiling,

nonche le sue funzionalita principali. Inoltre vengono presentate le teorie di test

che hanno permesso di ricavare le informazioni utilizzate nell’analisi di tuProlog.

Nei capitoli successivi si entra nella parte centrale del lavoro, esponendo queste

informazioni e analizzando qual e il loro significato. In particolare, nel Capitolo 3

vengono analizzati i tempi di esecuzione, mentre nel Capitolo 4 viene analizzato

l’utilizzo della memoria heap da parte di tuProlog. Nel Capitolo 5 si trova un

confronto fra la piu recente versione di tuProlog (2.1) e la versione 1.3. Questo

confronto viene fatto riferendosi ai tempi di esecuzione ed ai dati relativi all’uso

della memoria. Infine, nel Capitolo 6, vengono tratte le conclusioni, esponendo

quali sono le parti del motore che possono essere migliorate.

viii

Capitolo 1

Il motore tuProlog

L’obiettivo per cui l’interprete tuProlog venne ideato fu quello di poter disporre

di uno strumento in grado di realizzare dei componenti intelligenti da poter utiliz-

zare in un’infrastruttura internet dinamica. La base sulla quale viene costruito e il

linguaggio di programmazione logica dichiarativo Prolog. Sin dal primo interprete,

scritto nel 1972, le implementazioni dei sistemi Prolog si pongono come obiettivo

quello di ottimizzare fattori quali il tempo di esecuzione e l’utilizzo della memoria.

tuProlog, scritto interamente in Java, si discosta da questa tendenza, introducendo

nell’architettura dell’interprete i concetti legati alla programmazione orientata agli

oggetti, con lo scopo di poterne sfruttare i vantaggi. Tra questi pregi, apprezzati

quando si deve scrivere codice utilizzabile in infrastrutture intelligenti e sistemi

dinamici, vi sono: la portabilita, ovvero la facilita con cui e possibile distribuire

l’applicazione, legata solamente alla presenza della piattaforma Java; la riusabi-

lita, che permette il riutilizzo di componenti in diversi sistemi; la modularita, che

determina anche la leggerezza del core. Queste nozioni, ben note nell’ingegneria

del software, vengono realizzate implementando i pattern descritti in seguito.

In primo luogo viene considerata la riusabilita e la modularita dell’architet-

tura del motore tuProlog. Esse vengono rese possibili grazie alla separazione delle

responsabilita del sistema. Ogni responsabilita viene associata ad un singolo ma-

nager il quale controlla parte del motore tuProlog, in modo tale che le librerie e

i predicati primitivi siano indipendenti dal motore e possano essere sostituite o

1

CAPITOLO 1. IL MOTORE TUPROLOG

modificate preservando il funzionamento del sistema. Queste caratteristiche sono

rese possibili grazie al pattern Facade [2], che riduce anche il numero di oggetti

che il cliente deve utilizzare, rendendo il sistema piu semplice da gestire. Sono

presenti quattro tipi di manager per gestire diversi oggetti: il manager delle li-

brerie, il manager delle primitive, il manager delle teorie e il manager degli stati

della macchina a stati finiti. Il manager delle librerie rende possibile il caricamento

delle librerie di predicati al bisogno, anche a runtime. Questa peculiarita, oltre

a rendere estremamente configurabile tuProlog, fa si che il core metta a disposi-

zione funzionalita essenziali e quindi dia migliori prestazioni in termini di tempi

di esecuzione e utilizzo della memoria. Tuttavia esistono alcuni predicati che non

sono stati inseriti nelle librerie, ma sono stati definiti nel motore. Essi sono quei

predicati che influenzano il processo di risoluzione, come cut/0, quelli che sono

troppo basilari per essere definiti altrove, come fail/0 e quelli che per ragioni di

efficienza devono essere definiti vicino al core, come ’,’/2. A parte queste eccezioni

tutti gli altri predicati sono contenuti all’interno di librerie, le cui seguenti sono

caricate durante la fase di creazione del motore: la libreria BasicLibrary, la quale

contiene i predicati piu importanti, escludendo i predicati di I/O; la libreria IO-

Library che mette a disposizione alcuni dei predicati di input/output standard di

Prolog, come write/1, read/1 e nl/0; la libreria ISOLibrary che definisce predicati

standard ISO non definiti nelle due librerie precedenti; e JavaLibrary che definisce

tutti quei predicati idonei a permettere l’interazione fra Prolog e Java. Tutte le

altre librerie, come quelle definite dall’utente, possono essere caricate runtime. Il

manager delle primitive ha il compito di riconoscere i predicati presenti all’interno

delle teorie da quelli definiti nelle librerie o dall’utente. Questa operazione e neces-

saria in quanto i due gruppi di predicati dovranno essere trattati differentemente

durante il processo di risoluzione: i primi dovranno essere eseguiti come metodi

Java ogni qualvolta la risoluzione di una teoria preveda prima la loro risoluzione,

mentre gli altri saranno gestiti dalla macchina a stati finiti del motore tuProlog.

Il parser del motore tuProlog legge la teoria Prolog riconoscendo la corretta sin-

tassi e creando gli oggetti corrispondenti ai termini identificati. A supporto del

parser il manager delle teorie crea il database delle clausole, a cui il motore fara

riferimento durante il processo di risoluzione e riconosce le direttive che devono

essere eseguite immediatamente. Per questioni di ottimizzazione il corpo di una

2

Figura 1.1: Il pattern state che realizza la macchina a stati finiti

proposizione viene decomposto in sotto obiettivi non appena essa stessa viene rico-

nosciuta e non durante la fase di risoluzione. La proposizione viene rappresentata

in memoria tramite una struttura dati ad albero in cui ogni foglia rappresenta un

sotto obiettivo.

Infine il manager del motore si occupa di gestire i motori di risoluzione crean-

do un’istanza della macchina a stati finiti per ogni teoria che debba essere risolta

(situazione che potrebbe presentarsi nel caso le teorie siano innestate l’una nell’al-

tra). Questa macchina, nel quale ogni stato rappresenta un passo nella risoluzione

della teoria, e di fondamentale importanza in quanto realizza il motore di riso-

luzione delle teorie. Inoltre, il manager del motore permette di disaccoppiare il

motore di risoluzione tuProlog dal resto dell’architettura favorendo l’estensibilita

della macchina a stati finiti, a cui diventa possibile aggiungere nuovi stati. Per

realizzare tutto cio viene usato il pattern State [2] che permette di istanziare og-

getti il cui comportamento dipende dallo stato interno. La classe Engine mantiene

al suo interno sia lo stato attuale della macchina a stati finiti sia lo stato suc-

cessivo al quale deve transitare, mentre gli stati vengono realizzati derivando la

classe astratta State. Piu dettagliatamente il motore comprende uno stato iniziale

(Init), quattro stati rappresentanti le attivita svolte durante il processo di riso-

luzione (Goal Selection, Goal Evaluation, Rule Selection e Backtrack) e quattro

stati finali rappresentanti i modi in cui la risoluzione potrebbe terminare (HALT,

TRUE, TRUE CP e FALSE).

3

CAPITOLO 1. IL MOTORE TUPROLOG

Figura 1.2: La macchina a stati finiti del motore tuProlog

Lo stato Init e il punto di partenza e ha il compito di inizializzare il motore

di risoluzione estraendo gli obiettivi da valutare dalla teoria e creando un ogget-

to che rappresenta il contesto nella quale l’obiettivo verra valutato. Dopodiche

il controllo verra passato allo stato Goal Selection il quale seleziona l’obiettivo

da valutare da una lista di obiettivi. Se questo obiettivo non viene trovato e il

processo di esecuzione e terminato si possono presentare due casi: se esiste un

punto di scelta e quindi la teoria puo avere un’altra soluzione, lo stato finale sara

TRUE CP, altrimenti lo stato finale sara TRUE. Se invece esiste un altro obiettivo

che puo essere estratto deve essere valutato nello stato Goal Evaluation, a meno

che esso non rappresenti un numero, in qual caso la risoluzione termina nello stato

FALSE. Se l’obbiettivo valutato nello stato Goal Evaluation rappresenta un pre-

dicato primitivo allora la macchina a stati finiti transita nello stato Goal Selection

o Backtrack, a seconda se la valutazione del predicato abbia avuto esito positivo o

negativo, altrimenti transita nello stato Rule Selection e viene scelta una clausola

compatibile per la risoluzione della teoria. In qualsiasi momento venga raggiunta

una condizione di errore nello stato Goal Evaluation la macchina transita nello

stato HALT e termina l’esecuzione. Nel caso non venga trovata nessuna clausola

dal set di regole compatibili con l’attuale obiettivo allora lo stato successivo sara

quello di Backtrack. Nello stato di Rule Selection viene preparato un nuovo con-

testo di esecuzione, l’obiettivo viene unificato con la testa della clausola, il corpo

della clausola viene aggiunto al risolvente, viene creato un nuovo punto di scelta ed

il sistema transita nello stato di Goal Selection. Infine lo stato di Backtrack ha il

4

compito di trovare una clausola compatibile dal contesto creato nell’ultimo punto

di scelta aperto, se questa non viene trovata il motore termina la sua esecuzione

nello stato FAIL.

5

Capitolo 2

Benchmarks

La scelta del benchmark e un passo importante nell’analisi delle prestazioni di

un software. Le funzionalita del benchmark, il modo in cui le prestazioni vengono

da esso misurate e il modo in cui i dati finali vengono rappresentati determinano

quali parti del sistema e possibile analizzare, come e possibile analizzarle attraverso

lo strumento e come i dati possono essere interpretati e rielaborati in modo che essi

abbiano un significato concreto, tale da mettere alla luce le lacune del software esa-

minato. Il capitolo e diviso in due sezioni. La prima descrive brevemente i possibili

profiler adatti ad un’analisi di memoria e velocita di esecuzione di un’applicazione

Java. Vengono poi confrontati i vari strumenti ed esposte le ragioni che hanno por-

tato alla scelta dell’uno anziche dell’altro, soffermandosi sulle caratteristiche del

profiler HPROF, che fornisce i dati analizzati nei capitoli successivi. La seconda

sezione riguarda invece le teorie di test, essenziali per esaminare il comportamento

del sistema attraverso il profiler. La risoluzione delle clausole di Horn attraverso

l’interprete tuProlog viene infatti eseguita per una teoria ben precisa, in quanto

ogni teoria determina una successione dei cambiamenti di stato della macchina

a stati finiti diverso dalle altre e di conseguenza un diverso comportamento del

motore tuProlog. Quindi, durante la scrittura delle teorie, si considera che esse

devono testare l’interprete in modo tale da poterne analizzare le prestazioni in

tutti i possibili impieghi.

7

CAPITOLO 2. BENCHMARKS

2.1 Profilers

Il profiler e essenzialmente uno strumento in grado di misurare le performance

e analizzare il comportamento di un certo software durante la sua esecuzione. Il

modo in cui questo viene attuato ed il modo in cui i dati collezionati vengono

resi disponibili al cliente varia da profiler a profiler. La scelta dello strumento piu

adatto allo scopo e dettata non solo da quali variabili si debbano misurare durante

il profiling, ma anche dalla qualita e quantita delle informazioni che e possibile

ricavare analizzando i dati forniti. Ad esempio, la scelta di un profiler in grado

di misurare, o in grado di fornire dati dal quale sia possibile misurare, la memo-

ria allocata da metodi, anche innestati, viene privilegiata rispetto ad un profiler

che fornisce solamente i dati relativi alla memoria allocata durante l’esecuzione

dell’applicazione. La qualita delle informazioni ricavate puo anche essere definita

come la varianza dei dati misurati dallo strumento in esecuzioni diverse della stes-

sa teoria o in esecuzioni della stessa teoria su piattaforme diverse. Maggiore e la

varianza, minore sara la qualita delle informazioni in possesso. Questo problema e

reso evidente dal fatto che i dati ricavati saranno disponibili per future estensioni o

modifiche, cosa difficilmente possibile nel caso queste informazioni non siano para-

gonabili con quelle misurate su altre piattaforme. Sebbene la risoluzione di questo

quesito meriti una discussione a se e possibile ovviare al problema esprimendo i

tempi di esecuzione dei vari metodi1 con un valore relativo al tempo di esecuzione

totale della teoria, anziche come valore assoluto. In questo modo si possono avere

informazioni relative a quanto incide un metodo sul tempo di esecuzione totale e

questo dato rimane coerente fra diverse esecuzioni dell’interprete in diverse piat-

taforme2.

Dato per scontato che lo strumento con cui viene fatto il profiling debba essere

in grado di misurare la quantita di memoria heap allocata e i tempi di esecuzione

1Si vedra piu avanti che viene assunto come ipotesi il fatto che il tempo di esecuzione totaledella teoria sia dato dalla somma del tempo di esecuzione dei singoli metodi e l’ottimizzazionedi uno di essi comporta l’ottimizzazione del tempo di esecuzione totale.

2Non e escluso che alcuni sistemi operativi, o alcune implementazioni JVM diverse da quelladella Sun Microsystems, presentino ottimizzazioni che potrebbero far variare le velocita di ese-cuzione relative dei vari metodi. Queste variazioni dovrebbero comunque essere ragionevolmentepiccole.

8

2.1. PROFILERS

di un’applicazione Java, essendo tuProlog scritto interamente in Java, la scelta del

profiler viene fatta in primo luogo fra due categorie: i profiler commerciali e quelli

non commerciali3. Data la natura accademica della ricerca si opta per un profiler

con licenza di tipo non commerciale. Questa scelta e dettata dal fatto che utiliz-

zare un software commerciale porrebbe delle barriere economiche ad una futura

prosecuzione dell’analisi svolta. Un altro fattore di interesse nella scelta dello stru-

mento piu consono e, come detto in precedenza, la possibilita di misurare i tempi

di esecuzione e la quantita di memoria allocata dai vari metodi utilizzati durante

la risoluzione di una teoria. Inoltre, osservando l’architettura della macchina a

stati finiti, si puo facilmente intuire che alcuni degli stati in cui il sistema transita

vengono utilizzati in maniera predominante rispetto ad altri. E quindi opportuno

che la scelta venga indirizzata su un profiler che fornisca anche il numero di chia-

mate ad un metodo, in modo da poter analizzare meglio se il sistema spende un

certo tempo, o una certa quantita di memoria, perche effettua un numero elevato

di chiamate a questo o perche esso e computazionalmente complesso.

Una buona parte dei profiler con le caratteristiche indicate e basata sull’in-

terfaccia JVM TI (acronimo di Java Virtual Machine Tool Interface) fornita nella

piattaforma J2SE della Sun Microsystems a partire dalla versione 1.5. Questa

interfaccia provvede un accesso allo stato della JVM da parte di altri strumenti

attraverso delle API. All’atto dell’inizializzazione della VM una libreria, scritta in

C o C++, viene caricata. Questa puo invocare chiamate o registrarsi ad eventi,

secondo quanto descritto dall’interfaccia, allo scopo di interrogare la VM riguardo

al suo stato. Nei seguenti capitoli i dati sono tutti ricavati dalla libreria HPROF.

Questo agente, a differenza degli altri strumenti a disposizione, presenta i risul-

tati in maniera piuttosto grezza, senza che vengano elaborati o formattati. Quel

che puo sembrare un difetto, o una mancanza di qualita, e in realta un pregio.

Gli altri profiler infatti, presentando un output piu o meno elaborato, tendono a

mettere in risalto un aspetto del sistema anziche un altro, perdendo informazione.

Con HPROF e possibile invece elaborare i dati grezzi, in modo tale da mettere in

risalto l’aspetto desiderato.

3Per software non commerciale si intende shareware o open source.

9


2.1.1 Il profiler HPROF

HPROF genera le informazioni relative al profiling attraverso le chiamate a

JVM TI, le chiamate di ritorno dagli eventi della JVM TI e attraverso l’iniezione

di byte code nelle classi caricate dalla VM. Il metodo usato per il profiling dipende

dall’opzione con cui viene lanciato HPROF: l’opzione cpu=times inietta il byte

code all’ingresso e all’uscita di ogni metodo, l’opzione heap inietta il byte code nel

metodo <init> della classe java.lang.Object ed in ogni ‘newarray’ visto all’interno

di tutti i metodi, mentre l’opzione cpu=sample utilizza un thread che, svegliandosi

dopo un determinato intervallo di tempo, campiona lo stack. E possibile utilizzare

questo strumento attraverso il comando

java -agentlib:hprof[=opzioni] ClasseDaAnalizzare

dove la ClasseDaAnalizzare e la classe alice.tuprolog.Agent con, come primo

parametro, la teoria di test. In particolare, per fare il profiling dei tempi di ese-

cuzione e dell’uso dell’heap dell’interprete tuProlog, vengono usati i comandi con

le seguenti opzioni: hprof=cpu=times e hprof=heap=sites. Il primo presenta i

dati riguardanti al tempo effettivo speso da un metodo in millisecondi, il numero

di volte che quel metodo e stato chiamato da un altro metodo e il trace dello stack

che ha causato quella chiamata. Il secondo comando mostra gli oggetti che sono

stati creati durante l’esecuzione del programma. In particolare si possono trovare

informazioni riguardanti la memoria occupata e il numero di oggetti vivi in un

certo trace, nonche la memoria allocata e il numero di oggetti allocati durante l’e-

secuzione dell’intero programma nello stesso trace. Questo permette di analizzare

il comportamento del garbage collector durante l’esecuzione della teoria. Inoltre ad

ogni oggetto viene associato il trace dello stack che ha generato la sua allocazione

in memoria, permettendo di fatto di risalire a quale metodo lo ha istanziato. Uno

degli svantaggi di usufruire di un’analisi metodo a metodo, anche se compensato

dalla precisione delle misure, e quello di non poter sfruttare questo procedimento

per teorie il cui calcolo computazionale richieda tempi lunghi, in quanto il pro-

filer allunga, anche notevolmente, i tempi di esecuzione. Di questo e dei motivi

che hanno portato alla scelta delle opzioni descritte in precedenza viene discusso

comunque piu approfonditamente nei Capitoli 3 e 4.

10

2.2. TEORIE DI TEST

2.2 Teorie di test

Le teorie di test sono una parte del benchmark importante quanto il profiler.

Esse infatti determinano il comportamento dell’interprete durante la risoluzione

delle clausole e percio devono essere scelte con cura, in modo tale da permettere

un’analisi il piu completa possibile. In questa dissertazione vengono presentati

i risultati dei test sul core tuProlog e sulla libreria BasicLibrary, senza testare

le librerie aggiuntive come IOLibrary, JavaLibrary o ISOLibrary, anche se queste

vengono caricate automaticamente durante l’inizializzazione del motore tuProlog.

L’attenzione e anche rivolta alla scalabilita del sistema e alcune delle teorie uti-

lizzate sono scritte in modo tale da permettere vari test sulla scalabilita senza la

necessita di pesanti modifiche alla teoria stessa o l’introduzione di nuove teorie.

I risultati trovati in studi precedenti [6], con lo scopo di confrontare tuPro-

log con altri interpreti Prolog basati su Java, vennero trovati utilizzando teorie di

test note, utilizzate in benchmark atti a misurare la velocita di risoluzione delle

teorie. Per mantenere una certa continuita e per poter confrontare i risultati del

lavoro svolto in passato si e deciso di mantenere, per quanto possibile, alcune delle

teorie gia utilizzate. Si noti comunque che i sistemi hardware e software su cui

sono stati fatti i test passati e quelli qui descritti sono completamente differenti4.

Questo rende il confronto fra i risultati ottenuti solo indicativo. Tuttavia, alcune

delle teorie utilizzate devono essere omesse completamente dall’analisi dei tempi

di esecuzione totale (non dall’analisi dei tempi di esecuzione dei vari metodi) per

i motivi illustrati nel capitolo 3.

Le teorie utilizzate sono: Crypt, Poly, Qsort, Queens, Query, Tak, Einstein’s

riddle, Spanning tree e Switch square. Le prime sei fra queste sono teorie che

erano gia state usate come benchmark, mentre le altre sono state introdotte so-

lamente ora. Einstein’s riddle, Spanning tree e Switch square permettono inoltre

di ingrandire l’albero di risoluzione delle teorie modificando l’obiettivo. In questo

4Il sistema su cui sono stati ricavati i risultati antecedenti a quelli qui descritti era equipaggiatocon un processore Pentium III 800 MHz, 256 MB di RAM su Windows 2000 e J2SE 1.5.0 09. Ilsistema attuale consiste in un processore Pentium IV 2.6 GHz, con 1 GB di RAM su WindowsXP Home Edition e J2SE 1.6.0 04.

11


modo e possibile incrementare o diminuire il lavoro svolto dal motore tuProlog

senza modificare la teoria in se, consentendo di analizzare la scalabilita del siste-

ma. Esse svolgono il seguente lavoro: Crypt, data una formula matematica nota,

ne cerca la soluzione; Poly dato un polinomio nella forma 1 + x + y + z lo eleva

alla decima potenza attraverso la trasformazione simbolica della formula; Qsort

riordina una lista di numeri in modo crescente; Queens e la versione estesa a nove

regine del piu famoso problema delle 8 regine [1]; Query interroga un database

contenente per ogni nazione la rispettiva dimensione e il numero di cittadini e

restituisce, conoscendo gia il nome di una nazione, quella con la densita piu simile

ad essa; Einstein’s riddle tenta di risolvere un indovinello nel quale viene chiesto

chi e il proprietario di un certo animale data una serie di indizi riguardo a cinque

persone di diversa nazionalita, residenti in case di colore diverso e con una distinta

preferenza in termini di animali domestici, marche di sigarette e bevande; Span-

ning tree data una lista di collegamenti fra nodi, ognuno con un certo peso, trova

appunto lo spanning tree [1] di quell’albero; Switch square data una matrice 3x3,

i cui valori possono essere vero o falso, tenta di negare i valori posizionati ad una

distanza di Manhattan uguale o inferiore ad 1 da una certa cella e, attraverso una

sequenza di commutazioni delle celle, cerca di rendere tutti i valori della matrice

veri.

12

Capitolo 3

Analisi dei tempi di esecuzione

In questo capitolo vengono presentati i risultati ottenuti dal profiling delle

teorie di test esposte precedentemente. In particolare vengono mostrati quali sono

i tempi di esecuzione totali delle teorie e i tempi di esecuzione dei vari metodi

utilizzati durante la loro risoluzione. I dati ottenuti vengono poi elaborati in modo

da mettere in evidenza quali sono i punti fondamentali su cui il motore deve essere

migliorato. Per fare cio viene prima messa alla prova la scalabilita del sistema,

facendo il profiling con teorie via via piu complesse ed in secondo luogo vengono

costruiti i grafi delle chiamate ai metodi, in modo da evidenziare quali metodi

effettuano le chiamate piu costose da un punto di vista computazionale.

3.1 Metodo di profiling

Come gia detto, i dati risultanti dal profiling devono fornire il tempo di ese-

cuzione totale della teoria, il tempo di esecuzione dei metodi e, indirettamente,

per ognuno di essi, i tempi di esecuzione dei metodi innestati. Cio e possibile in

quanto il profiler HPROF mette a disposizione il trace dello stack che ha generato

la chiamata ad un particolare metodo, oltre ovviamente al tempo di esecuzione del

metodo (mostrato come percentuale sul tempo di esecuzione totale) e al numero

di volte in cui e stato chiamato. Il comando utilizzato per fare cio e il seguente

java -agentlib:hprof=cpu=times alice.tuprolog.Agent teoria.pl

13

CAPITOLO 3. ANALISI DEI TEMPI DI ESECUZIONE

dove la classe Agent, contenuta nel package alice.tuprolog, e uno strumento che

accetta come parametro una teoria Prolog scritta in un file di testo e, dopo aver

tentato di risolverla, stampa sullo standard output il risultato della valutazione.

tuProlog permette di valutare una teoria in altri tre modi: lanciando un’interfaccia

grafica ed inserendo la teoria in un’apposita TextBox, in un ambiente interattivo

attraverso la classe alice.tuprologx.ide.CUIConsole oppure istanziando un oggetto

Prolog in una classe Java. Il metodo utilizzato, a differenza degli altri, permette

pero di isolare il motore tuProlog, in modo da non dover estromettere dal profiling

i dati non dovuti alla risoluzione, come ad esempio l’istanziazione della GUI.

Per misurare il tempo di esecuzione in modo ottimale il file teoria.pl viene

costruito in modo da separare tre diversi processi che avvengono durante la riso-

luzione della teoria: l’inizializzazione del motore e il caricamento delle librerie1,

la lettura delle clausole di Horn e la risoluzione vera e propria. Vengono quin-

di dapprima misurati i tempi di esecuzione della lettura della teoria assieme alla

sua risoluzione risolvendo un certo obiettivo2. Successivamente lo stesso obiet-

tivo viene risolto per undici volte e viene sottratto il tempo di esecuzione pre-

cedentemente trovato. Questo e equivalente a misurare undici volte il tempo di

esecuzione dell’obiettivo piu una volta il tempo di lettura della teoria per poi sot-

trarlo. E inoltre necessario evitare di misurare il tempo di creazione della JVM

e per fare cio viene scritta un’ulteriore teoria in cui viene usato il metodo Ja-

va java.lang.System.currentTimeMillis prima e dopo l’esecuzione dell’obiettivo. Il

codice Prolog della teoria indicata risulta il seguente:

time(T) :- class(’java.lang.System’) <- currentTimeMillis returns T.

go(File) :- time(A), consult(File), time(B), C is B-A, print(C).

dove File rappresenta il nome completo del file di testo in cui e contenuta la

teoria da valutare. All’interno di questo file sono contenute le seguenti clausole, le

quali permettono di valutare il tempo di lettura ed esecuzione:

1I tempi in cui questi processi avvengono sono dovuti alla JVM e non al motore tuProlog inse.

2Per diminuire la dispersione delle misure e stato misurato dodici volte il tempo di esecuzionedell’obiettivo e sottratto il valore massimo e minimo trovato. Il tempo di esecuzione e la mediadei valori rimanenti.

14

3.2. TEMPI DI ESECUZIONE DEI METODI

:- solve(goAndRepeat).

:- solve(go).

goAndRepeat :- goN(11).

go :- goal().

goN(0).

goN(Z) :- goal(), W is Z-1, goN(W).

dove goAndRepeat risolve undici volte l’obiettivo goal().

3.2 Tempi di esecuzione dei metodi

Nonostante il metodo java.lang.System.currentTimeInMillis restituisca un tem-

po in millisecondi, la granularita del valore dipende dal sistema in cui e ospitata

la JVM e potrebbe essere maggiore di 1 ms. Nel sistema in cui sono avvenute le

misure non e stato possibile misurare intervalli di tempo minori a 15 ms, il che

fa pensare che lo stesso valore corrisponda alla granularita del sistema. Questo

ha reso impossibile un’apprezzabile misurazione delle teorie Crypt, Poly, Qsort,

Queens e Query in quanto i tempi misurati contengono un errore sulla misura

troppo elevato.

Teoria Tempo di esecuzione (ms) Errore relativo %Crypt 1669 179,75Einstein’s riddle 114598 2,62Poly 31 9677,42Qsort 671 447,09Queens 2574 116,55Query 312 961,54Spanning tree 18034 16,64Switch square 93787 3,20Tak 105721 2,84

Tabella 3.1: Tempi di esecuzione per cento risoluzioni e errore relativo calcolatoper una singola esecuzione.

Dalla Tabella 3.1 si evince chiaramente che la misurazione dei tempi di let-

tura della teoria e risoluzione dell’obiettivo non possono essere misurati con una

15


buona precisione. Nella Tabella 3.2 vengono quindi illustrati i tempi delle teorie

Einstein’s riddle, Spanning tree, Switch square e Tak i quali hanno errori relativi

ragionevolmente contenuti. La distinzione fra le due modalita di esecuzione ha

lo scopo di mettere in luce quali sono le parti del motore tuProlog che possono

causare una degradazione delle performance.

Teoria Lettura esec (ms) Esec (ms) Esec/Lettura esec %Einstein’s riddle 13807 13331 96,6Spanning tree 2216 1868 84,3Switch square 10110 9628 95,2Tak 11373 10797 94,9

Tabella 3.2: Tempi di lettura ed esecuzione.

Si puo quindi affermare che il tempo di lettura risulta essere all’incirca costante al

variare della teoria3. I metodi coinvolti nella risoluzione dell’obiettivo occuperan-

no la maggior parte del tempo di esecuzione totale e questo permette un profiling

senza distinguere fra lettura ed esecuzione, come e stato fatto fin d’ora, dato che

non valutare i metodi coinvolti durante la prima fase non comporta una perdita

di informazione significativa.

Di seguito, nella Tabella 3.3, vengono presentati i risultati del profiling, ese-

guiti nei modi descritti precedentemente. Per ogni teoria ci si limita a presentare

i risultati di quei metodi il cui tempo impiegato a terminare4 e superiore o uguale

al 2% del tempo di esecuzione totale.

3Nel caso di Spanning tree, la teoria piu lunga, il numero di righe che il motore deve leggeree 186, mentre nel caso di Tak, quella piu corta, il numero di righe e 29.

4Il tempo impiegato ad un metodo per terminare non comprende il tempo impiegato ai metodiinnestati in esso ad essere eseguiti.

16


Teoria Nome metodo Tempo esec % N. chiamate

Cryptjava.lang.Object.wait 41,65 2

java.lang.AbstractStringBuilder.append 2,27 60583

E.’s riddle

alice.tuprolog.Var.occurCheck 21,35 14909053

alice.tuprolog.Struct.getTerm 14,24 30803506

alice.tuprolog.Var.free 6,01 4676006

java.util.AbstractList$Itr.next 4,60 4251755

alice.tuprolog.Struct.getArity 3,9 14871224

java.util.ArrayList.get 3,82 5599360

alice.tuprolog.Var.unify 3,59 2488524

alice.tuprolog.Struct.unify 3,54 2482605

java.util.AbstractList$Itr.hasNext 3,49 4998320

java.util.ArrayList.add 3,27 5000191

alice.tuprolog.Var.getTerm 2,53 9374073

Poly


java.io.StringReader.read 3,59 24662

alice.tuprolog.Tokenizer.readNextToken 3,12 8815

java.lang.StringBuffer.append 2,96 32544

alice.tuprolog.Tokenizer.readToken 2,92 21835

java.io.StreamTokenizer.nextToken 2,21 17063

alice.tuprolog.Struct.toString 2,21 1986

java.io.StreamTokenizer.read 2,12 24662

Qsort






Queens java.lang.Object.wait 36,27 2

Query



alice.tuprolog.Tokenizer.readNextToken 2,29 8534

alice.tuprolog.Tokenizer.readToken 2,23 21002

17



S. tree

java.lang.Object.wait 28,19 6





java.util.ArrayList.<init> 2,57 732603



alice.tuprolog.Term.match 2,01 128442

S. square






alice.tuprolog.Int.unify 3,42 1849876

alice.tuprolog.Struct.copy 3,39 1492772





alice.tuprolog.Var.copy 2,77 1118445

java.util.IdentityHashMap.get 2,35 1118445

alice.tuprolog.Var.rename 2,18 561971


Tak



java.util.ArrayList.<init> 3,25 3259113






18


alice.tuprolog.Var.copy 2,47 1193928

java.util.AbstractList$Itr.<init> 2,35 3388196


alice.tuprolog.Var.rename 2,13 645368

alice.tuprolog.Int.unify 2,12 1355254

Tabella 3.3: Analisi dei metodi.

Come si puo notare, in tre delle nove teorie, il metodo che impiega piu tempo a

terminare e java.lang.Object.wait. Questo metodo viene lanciato dalla JVM (nel

caso si tratti del client HotSpot della JVM e l’algoritmo usato sia seriale) e per-

mette al garbage collector di ripulire parte dell’heap quando non e piu possibile

promuovere oggetti dallo young generation all’old generation [4]. Una spiegazione

piu approfondita a riguardo viene data nel capitolo seguente. Per tutti gli altri

metodi risulta difficile fare una ragionevole analisi basata su di una singola teo-

ria e, come detto nei capitoli precedenti, si deve ricercare un approccio che possa

mettere in luce i miglioramenti in un ambito di utilizzo il piu eterogeneo possibile.

Nella Tabella 3.4 vengono sommati i tempi di esecuzione relativi di tutti i metodi

(anche quelli non inclusi nella Tabella 3.3). Nell’aggregare i risultati delle varie

teorie e stato scelto di sommare semplicemente i risultati parziali senza dare alcun

peso ai tempi di esecuzione delle teorie. Infatti, come si puo vedere nell’analisi

della scalabilita, modificando l’obiettivo di una teoria, in modo da allungare o ac-

corciare l’albero di ricerca di una soluzione, il tempo per ottenere una risposta,

rispettivamente, cresce o diminuisce linearmente con il numero di foglie dell’albero

visitate dalla macchina a stati finiti. Tuttavia i tempi di esecuzione relativi dei

vari metodi rimangono costanti. Per questo motivo dare un peso a questi tem-

pi significherebbe sbilanciare l’analisi complessiva a favore di una teoria anziche

un’altra. Per la stessa ragione nella Tabella 3.4 viene omesso il numero di chiamate

ai metodi.

Sempre dalla Tabella 3.4 si evince che il metodo java.lang.Object.wait e ancora

quello che occupa la maggior parte del tempo di esecuzione del motore tuProlog.

19


Nome metodo Tempo esec %java.lang.Object.wait 12,15alice.tuprolog.Var.occurCheck 3,70alice.tuprolog.Struct.getTerm 3,06alice.tuprolog.Var.unify 3,05java.lang.AbstractStringBuilder.append 2,82alice.tuprolog.Var.free 2,61alice.tuprolog.Struct.unify 2,25java.util.AbstractList$Itr.next 1,88java.util.AbstractList$Itr.hasNext 1,80alice.tuprolog.Var.getTerm 1,72java.util.ArrayList.get 1,72java.lang.StringBuffer.append 1,67java.util.ArrayList.<init> 1,49java.util.ArrayList.add 1,37java.io.StringReader.read 1,16java.util.AbstractList$Itr.<init> 1,08alice.tuprolog.Tokenizer.readNextToken 1,01alice.tuprolog.Var.copy 1,01

Tabella 3.4: Analisi dei metodi totale.

Eliminando, o limitando, il numero di chiamate ad esso comporterebbe un miglio-

ramento del tempo di esecuzione di circa il 12% sul tempo totale5. Purtroppo,

escludendo il metodo Java gia citato, non esistono situazioni in cui l’utilizzo di

una funzione e predominante rispetto alle altre, anche se i metodi nella Tabel-

la 3.4 rappresentano circa la meta del tempo di esecuzione totale. Questo dato

indirizza sicuramente ad una piu attenta analisi di questi metodi.

3.3 Analisi della scalabilita

In questa parte della dissertazione viene data una dimostrazione di come la

relazione fra numero di stati visitati nell’albero di ricerca e numero di chiamate ai

metodi utilizzati sia lineare. Per fare cio e opportuno prendere come teoria di rife-

5Questa ipotesi, se pur plausibile, non e del tutto veritiera. A causa della lentezza del profilerHPROF non e stato infatti possibile analizzare teorie di una certa complessita computazionale eil valore di miglioramento potrebbe essere sottostimato.

20

3.3. ANALISI DELLA SCALABILITA

rimento la teoria Switch square che permette di ingrandire o rimpicciolire l’albero

di ricerca solamente modificando l’obiettivo e calcolare anche il numero di stati in

cui si deve transitare per trovare una soluzione. La Tabella 3.5 mostra per ogni

obiettivo valutato il tempo di esecuzione della teoria6 e i cinque metodi con tempo

di esecuzione piu elevato con il relativo numero di chiamate per quel metodo.

N. stati e Tempo esec (ms) Nome metodo N. chiamate

3 + 6! 247837

alice.tuprolog.Struct.unify 1947041alice.tuprolog.Var.unify 2584249alice.tuprolog.Var.free 1802505java.util.ArrayList.get 2639270java.util.AbstractList$Itr.next 1725777

3 + 2 ∗ 6! 488623

alice.tuprolog.Struct.unify 3876572alice.tuprolog.Var.unify 5181011alice.tuprolog.Var.free 3601750java.util.AbstractList$Itr.next 3449996java.util.ArrayList.get 5276156

3 + 3 ∗ 6! 1898223

java.lang.Object.wait 2java.lang.ref.ReferenceQueue.remove 4alice.tuprolog.Struct.unify 5813154alice.tuprolog.Var.unify 7768221alice.tuprolog.Var.free 5398379java.util.AbstractList$Itr.next 5173233java.util.ArrayList.get 7911406

Tabella 3.5: Analisi della scalabilita del motore tuProlog.

La Tabella 3.5, oltre a mostrare la linearita fra stati visitati e numero di chia-

mate ad un metodo, mostra anche come il tempo di esecuzione risulti lineare in

rapporto all’aumentare dei nodi nell’albero di risoluzione. Questo dimostra una

buona scalabilita del sistema fino alla risoluzione dell’obiettivo con 3 + 2 ∗ 6! stati,

mentre le prestazioni degradano nella risoluzione dell’obiettivo con 3 + 3 ∗ 6! stati

a causa dell’intervento del garbage collector.

6Si tenga in considerazione che il tempo di esecuzione e pregiudicato dal profiler HPROF cherallenta l’esecuzione di tuProlog. Per questo motivo non deve essere confrontato con quello dellaTabella 3.3, ma solamente con quello degli altri obiettivi.

21


3.4 Grafo delle chiamate

Con lo scopo di analizzare piu in dettaglio i singoli metodi con i tempi di esecu-

zione piu elevati (si veda la Tabella 3.4) vengono esaminate le chiamate ad ognuno

dei metodi stessi. Dai risultati di questa analisi e possibile comprendere se l’elevato

tempo di esecuzione di una funzione e dovuto all’implementazione della funzione

stessa oppure all’uso troppo intenso della funzione da parte di altri metodi. Di

conseguenza e possibile orientare la riscrittura del codice in una delle due dire-

zioni. Per lo stesso principio che ha portato all’aggregazione dei risultati parziali

delle varie teorie ed esposto durante la discussione sull’analisi della scalabilita, lo

studio e stato realizzato esaminando le chiamate complessivamente piu utilizzate,

senza dare peso ai tempi di esecuzione delle singole teorie. Per ogni singolo metodo

presente nella Tabella 3.4 e stato esplorato lo stack allo scopo di trovare quale fu

la prima funzione del package alice a generarne l’esecuzione. Questo accorgimento

e dovuto al fatto che solamente il codice dei metodi del package alice puo essere

riscritto, quindi le chiamate fra metodi java (senza tenere conto del fatto che sono

da considerarsi gia ottimizzate) non aggiungono informazione all’analisi7.

Il risultato dello studio e la Figura 3.1, la quale mostra per ogni metodo,

rappresentato come nodo nel grafo (si faccia riferimento alla Tabella 3.6 per cono-

scere a quale metodo corrisponde ogni nodo), quali sono i suoi chiamanti attraverso

una freccia entrante. Una freccia uscente ed entrante nello stesso nodo indica una

chiamata ricorsiva e per ognuna delle frecce viene indicata in quale percentuale

un determinato metodo viene eseguito per causa del chiamante sul totale delle

chiamate8.

7L’unico metodo, inserito nella Figura 3.1, il cui chiamante fa parte del package java ejava.lang.Object.wait.

8Vengono visualizzati i chiamanti con percentuali uguali o superiori al 5%.

22

3.4. GRAFO DELLE CHIAMATE

N. nodo Nome metodo0 java.io.StringReader.read1 alice.tuprolog.Var.unify2 java.util.ArrayList.add3 alice.tuprolog.Var.getTerm4 alice.tuprolog.Struct.unify5 alice.tuprolog.Var.occurCheck6 alice.tuprolog.Var.copy7 alice.tuprolog.Struct.getTerm8 alice.tuprolog.Tokenizer.readNextToken9 java.util.AbstractList$Itr.hasNext

10 alice.tuprolog.Var.free11 java.lang.Object.wait12 java.util.ArrayList.get13 java.util.AbstractList$Itr.<init>14 java.util.AbstractList$Itr.next15 java.lang.StringBuffer.append16 java.lang.AbstractStringBuilder.append17 java.util.ArrayList.<init>

Tabella 3.6: Associazione fra il numero identificativo di un nodo nella Figura 3.1e il metodo che esso rappresenta.

23


0100

218

60

11

9

Cla

use

Sto

re.d

eun

ify

SubGoalTree.addChild1

36

Int.u

nify

61

34013

24

11

Int.u

nify

448

7 25

18

Term.matchStateRuleSelection.doJob5

14

85

699Struct.copy

713

10 68

899 Tokenizer.readToken

971

9

15ClauseStore.deunify

Stru

ct.c

op

y

10

75

714

Term

.mat

ch

StateBacktrack.dojob11

100 java

1250

68

13

18

ClauseInfo.bodyCopy

SubGoalTree.getChild

ClauseSto

re.d

eunify

ClauseStore.reunify

13

6

12

15

7

5ClauseStore.deunify

ClauseSto

re.re

unifyTerm

.match

java

1475

12

9

ClauseIn

fo.b

odyCopy

ClauseStore.deunify

15

45

27 7

10

Var.r

enam

e

Struct.toString PrimitiveManager.identify

Stru

ct.<

init

>

16

Var.r

enam

e

42

Struct.<init>11

Struct.toString 28

5

Operato

rManager$

Operato

rRegist

er.getO

perato

r

7Prim

itiveManager.identify

17

Term

.matc

h

54

SubGoalTree.<init>

Term

.un

ify

6

15

17

6

ClauseStore.deunify

StateRuleSelection.doJob

Figura 3.1: Analisi delle chiamate ai metodi piu utilizzati nell’esecuzione delleteorie.

24

Capitolo 4

Analisi dell’utilizzo della memoria

Le stesse teorie presentate nel Capitolo 2 vengono ora utilizzate nel profiling

del motore con lo scopo di analizzare in quale modo tuProlog sfrutta la memoria

heap. Ad una prima discussione sulle modalita di studio dell’interprete segue la

presentazione dei dati ottenuti, ricavati con il proposito di mettere in evidenza

quali sono gli oggetti la cui istanziazione alloca in modo piu consistente questa

risorsa. A questo fine viene valutata la memoria complessivamente allocata du-

rante la risoluzione di una teoria, senza considerare il fatto che il garbage collector

libera lo spazio occupato da quegli oggetti non referenziati in un certo momento

dell’esecuzione. Infine, come nel capitolo precedente, vengono analizzati quali so-

no i metodi che sfruttano maggiormente la memoria, con lo scopo di rendere la

riscrittura del codice del motore il piu circoscritta e proficua possibile.

4.1 Metodo di profiling

Il profiling del motore tuProlog fornisce i dati riguardanti l’utilizzo della memo-

ria ed in particolare, per permettere il tipo di analisi introdotta precedentemente,

deve mettere a disposizione, per ogni oggetto, i dati relativi alla memoria com-

plessiva da esso allocata e il metodo che alloca quel oggetto. Il profiler HPROF

permette di ricavare queste informazioni attraverso il seguente comando:

java -agentlib:hprof=heap=sites,depth=16 alice.tuprolog.Agent tr.pl

25

CAPITOLO 4. ANALISI DELL’UTILIZZO DELLA MEMORIA

dove l’opzione hprof=heap=sites visualizza, per ogni metodo incluso in un

certo trace dello stack e per ogni oggetto da esso istanziato, i seguenti dati: il tra-

ce dello stack che ha generato la chiamata al metodo; la quantita di memoria totale

istanziata da quel determinato trace insieme al numero totale di istanze create del-

l’oggetto in questione. Si deve precisare che HPROF non fornisce la quantita di

memoria totale occupata da un oggetto, ma bensı la quantita di memoria occupata

da esso escludendo lo spazio utilizzato dalle istanze di oggetti generati al suo in-

terno. In questo modo e possibile affrontare un’analisi classe per classe, separando

ognuna di esse da parte del suo contenuto. Se si volesse studiare quanto una classe

sfrutta complessivamente la memoria sarebbe sempre possibile farlo analizzando lo

stack. L’opzione depth=16 serve invece ad aumentare la profondita dello stack vi-

sualizzato in output. Dato che si vogliono studiare quali sono i metodi del package

alice che causano l’istanziazione di un oggetto, anche indirettamente, e ragione-

vole impostare una profondita del trace uguale a sedici per intercettare tutte le

chiamate, se pur a scapito di un profiling piu lento. Come spiegato nell’analisi dei

tempi di esecuzione la classe Agent accetta tr.pl come parametro (in questo caso

e il file di testo contente una delle nove teorie gia presentate) e viene preferita alle

altre modalita di esecuzione di tuProlog in quanto permette di analizzare solo la

parte del motore che ha il compito di risolvere la teoria.

4.2 Allocazione degli oggetti in memoria

L’allocazione degli oggetti, oltre ad incrementare la quantita di memoria di cui

tuProlog deve disporre per risolvere una teoria, porta anche ad un aumento dei

tempi di esecuzione. Questo avviene sia a causa del tempo necessario alla JVM a

creare una nuova istanza di un oggetto in memoria, sia a causa del tempo neces-

sario al garbage collector per ripulire lo spazio non referenziato da alcun oggetto.

Inoltre l’uso improprio di questa risorsa puo causare il lancio dell’errore OutOf-

MemoryError1, interrompendo la risoluzione della teoria.

La Tabella 4.1 e stata costruita sommando le quantita di memoria istanzia-

1Questo errore viene lanciato da parte della virtual machine nel momento in cui, a causa dellamancanza di spazio in memoria, non e piu possibile allocare un certo oggetto.

26

4.2. ALLOCAZIONE DEGLI OGGETTI IN MEMORIA

te dai vari trace per lo stesso oggetto durante l’esecuzione di tuProlog. In questo

modo e possibile valutare complessivamente quanto un determinato oggetto viene

istanziato. Inoltre vengono omessi quegli oggetti che occupano uno spazio in me-

moria inferiore al 2% dello spazio totale allocato.

Teoria Nome oggetto M. allocata % M. allocata Byte

Crypt

java.lang.Object[] 26,09 1631496

char[] 15,44 965728

java.util.ArrayList 8,54 534280

java.util.AbstractList$Itr 7,68 480040

alice.tuprolog.Struct 5,80 362712

java.lang.String 4,83 302128

alice.tuprolog.Term[] 4,37 273128

alice.tuprolog.Var 3,85 240728

byte[] 3,71 231960

java.lang.StringBuffer 2,32 145080

E.’s riddle


char[] 10,15 21423200





java.util.AbstractList$ListItr 3,22 6787896


java.util.LinkedList$Entry 2,68 5652544


Poly

char[] 33,16 798736


byte[] 12,04 290000


int[] 4,02 96728

alice.tuprolog.Token 3,17 76312

27


java.util.regex.Matcher 2,36 56824


Qsort


char[] 15,02 421856

byte[] 8,63 242384








Queens


char[] 10,43 1156760









alice.tuprolog.ExecutionContext 2,16 239552

byte[] 2,09 231960

Query


char[] 11,27 274544

byte[] 9,52 231960






28


alice.util.OneWayList 2,39 58264

S. tree




char[] 7,57 5262592




alice.util.OneWayList 2,67 1856008




S. square



char[] 16,87 45410744







Tak


char[] 12,92 51823792










29


alice.tuprolog.ExecutionContext 2,03 8132024

Tabella 4.1: Analisi degli oggetti utilizzati.

Come si puo osservare, in otto delle nove teorie, l’oggetto piu utilizzato e un

array di Object. Esso viene utilizzato principalmente nella classe ArrayList per

mantenere un buffer nel quale viene memorizzata la lista in questione. Un altro

oggetto che compare vistosamente nella tabella e l’array char[], che viene utilizzato

prevalentemente per memorizzare delle stringhe nelle classi String e StringBuilder

(o nella sua versione synchronized StringBuffer). Nel grafo delle allocazioni si puo

vedere in modo piu specifico quali sono i metodi che istanziano questi oggetti.

Nella Tabella 4.3 vengono mostrati quali sono gli oggetti complessivamente

piu utilizzati durante la risoluzione delle teorie. Per le stesse ragioni esposte nel-

l’analisi della scalabilita le varie percentuali di utilizzo della memoria degli oggetti

vengono sommate dando lo stesso peso alle varie teorie, sebbene la quantita di

memoria totale istanziata da una di esse possa essere diversa da quella istanziata

dalle altre. A sostegno di questa tesi, nella Tabella 4.2, vengono elencati i sei og-

getti che hanno fatto misurare le percentuali di utilizzo della memoria piu elevate

durante la risoluzione della teoria Switch square. Le misurazioni sono state fatte

per ognuno dei tre obiettivi utilizzati nell’analisi dei metodi, i quali permettono

di cercare in 3 + 6!, in 3 + 2 ∗ 6! oppure in 3 + 3 ∗ 6! diversi stati prima di tro-

vare la soluzione della teoria. Anche se la precisione dei risultati non rispecchia

quella avuta nell’analisi dei tempi di esecuzione, si puo comunque assumere, con

buona approssimazione, che al variare dell’obiettivo e del numero di stati visitati

nell’albero di ricerca la percentuale di spazio allocato in memoria da ogni oggetto,

rispetto allo spazio totale allocato, rimane costante. Come detto precedentemente,

questo permette di analizzare l’utilizzo della memoria semplicemente sommando i

dati contenuti nella Tabella 4.1.

30


N. stati Nome oggetto M. allocata %

3 + 6!

java.lang.Object[] 24,74alice.tuprolog.Struct 17,78char[] 16,87alice.tuprolog.Term[] 12,56alice.tuprolog.Var 6,66java.lang.String 5,05

3 + 2 ∗ 6!

alice.tuprolog.Struct 23,23char[] 17,80alice.tuprolog.Term[] 17,31alice.tuprolog.Var 12,60java.lang.String 10,97java.lang.Object[] 8,87

3 + 3 ∗ 6!

alice.tuprolog.Struct 19,12char[] 18,37alice.tuprolog.Term[] 13,94java.lang.Object[] 9,97java.lang.String 9,78alice.tuprolog.Var 9,37

Tabella 4.2: Analisi dell’utilizzo della memoria da parte degli oggetti rispettoall’obiettivo della teoria.

Infine, nella Tabella 4.3, vengono esposti i risultati di questa operazione omet-

tendo gli oggetti che allocano meno dell’1% della memoria totale istanziata. L’a-

nalisi conferma quanto detto precedentemente. Gli oggetti Object[] e char[] sono

ancora i piu utilizzati da parte di tuProlog occupando il 42,11% della memoria

totale impiegata. Inoltre, ricordando che il profiler HPROF non ingloba nella mi-

sura della memoria allocata da un oggetto lo spazio occupato da oggetti innestati,

e possibile considerare questi due oggetti istanziati solamente dalle classi Array-

List, String e StringBuffer. Seguendo questa ipotesi le classi String e StringBuffer

allocano complessivamente il 20,68% della memoria, mentre la classe ArrayList ne

alloca il 35,30%. Sara quindi importante, al momento di una futura implemen-

tezione del codice, considerare queste tre classi, le quali occupano nell’insieme il

55,98% della memoria totale.

31


Nome oggetto M. allocata %java.lang.Object[] 27,40char[] 14,71java.util.ArrayList 7,90java.util.AbstractList$Itr 6,95alice.tuprolog.Struct 5,37java.lang.String 4,15byte[] 4,05java.util.LinkedList$Entry 3,82alice.tuprolog.Term[] 3,82alice.tuprolog.Var 3,50java.util.AbstractList$ListItr 1,94java.lang.StringBuffer 1,82alice.util.OneWayList 1,43alice.tuprolog.ExecutionContext 1,35

Tabella 4.3: Analisi complessiva degli oggetti utilizzati.

4.3 Analisi del garbage collector

Come si e gia accennato precedentemente in questo capitolo e nell’analisi della

scalabilita il garbage collector influisce, anche pesantemente, sul tempo di esecu-

zione del motore tuProlog. Di seguito si espone piu in dettaglio quali sono le cause

del degrado delle prestazioni eseguendo alcuni test tramite le teorie Spanning tree

e Switch square, le quali permettono di istanziare un numero elevato di oggetti in

memoria e, di conseguenza, causare frequentemente l’intervento del garbage col-

lector.

Il sistema su cui viene studiato tuProlog viene definito dalla Sun Microsystems

un client-class machine [4]. Questo implica che il garbage collector utilizzato sia di

tipo seriale, la dimensione iniziale dell’heap disponibile sia di 4 MB e la sua dimen-

sione massima possa essere di 64 MB2. Il garbage collector seriale viene eseguito

su di una singola cpu, bloccando l’esecuzione dell’applicazione per tutto il tempo

necessario a marcare gli oggetti non referenziati e liberare la memoria. Al contra-

2La dimensione dell’heap allocabile dalla JVM viene incrementata ogni qualvolta non ci siapiu spazio per allocare un determinato oggetto. Nel caso la dimensione sia gia quella massimaprevista l’allocazione non e possibile e viene lanciato l’errore OutOfMemoryError.

32

4.3. ANALISI DEL GARBAGE COLLECTOR

rio il garbage collector parallelo utilizza piu cpu per eseguire la stessa operazione

riducendo il tempo di esecuzione. Questa seconda tipologia e particolarmente utile

quando la memoria da deallocare e piuttosto elevata3 ed, in seguito, il confronto

fra i due garbage collector viene utilizzato per stimare quanto la deallocazione

degli oggetti non referenziati incide sui tempi di esecuzione di tuProlog. Inoltre,

il garbage collector seriale utilizza a sua volta due differenti algoritmi di default:

il copying collector per lo young generation e il mark-compact collector per l’old

generation4 [3,4]. Entrambi gli algoritmi agiscono dopo aver bloccato l’esecuzione

dell’applicazione ma, mentre il primo deve agire su di una parte del heap di dimen-

sioni contenute, il secondo agisce su di una porzione piu vasta, causando un au-

mento consistente del tempo di esecuzione. In dettaglio l’algoritmo mark-compact

agisce in due fasi: nella prima marca tutti gli oggetti raggiungibili partendo dalla

radice; nella seconda gli oggetti marcati vengono compattati all’inizio del heap pre-

servandone l’ordine. Questa ultima fase, sebbene richieda un ulteriore intervallo

di tempo per essere completata, assicura un tempo d’allocazione del heap minore.

Inoltre, per garantire la consistenza degli oggetti marcati nell’old generation, l’e-

secuzione del programma deve essere interrotta in ambedue le fasi. In particolar

modo il degrado delle prestazioni di tuProlog avviene a causa di due metodi. Il

metodo Object.wait della classe java.lang.ref.Reference$ReferenceHandler5, dove

Object e un oggetto usato dal garbage collector per bloccare l’esecuzione del pro-

gramma mentre questo ultimo identifica gli oggetti che hanno cambiato stato. E

il metodo java.lang.ref.ReferenceQueue.remove, il quale viene chiamato dal meto-

do java.lang.ref.Finalizer$FinalizerThread.run quando il garbage collector rimuove

dal heap quegli oggetti che implementano il metodo finalize [5]. Nonostante questo

metodo sia altrettanto dispendioso, come si puo vedere dalla Tabella 3.3, a dif-

ferenza del metodo java.lang.ref.Reference$ReferenceHandler, non viene eseguito

altrettanto frequentemente.

3Si noti che la creazione di thread da parte del garbage collector introduce overhead.4Insieme alla permanent generation, la old generation e la young generation sono le tre sezioni

in cui viene divisa la memoria heap. Ognuna di queste ha il compito di mantenere oggetti didiverse eta (escludendo la permanent generation nel quale vengono allocati oggetti vitali perl’esecuzione dell’applicazione) in modo da rendere piu efficiente il lavoro del garbage collector.

5Essa estende java.lang.Thread ed esegue il suo codice nel metodo chiamato run chesovrascrive quello ereditato dalla classe madre.

33


Con l’obiettivo di causare una o piu volte l’intervento del garbage collector

sono state eseguite le teorie Spanning tree e Switch square. In particolar modo la

Spanning tree e stata eseguita con l’intenzione di trovare uno spanning tree per un

albero formato da 64 nodi, mentre Switch square e stata eseguita con l’obiettivo di

visitare 1+2∗8! stati prima di risolvere la teoria. tuProlog e stato successivamente

eseguito attraverso il comando

java -XX:+PrintGCTimeStamps alice.tuprolog.Agent teoria.pl

dove -XX:+PrintGCTimeStamps e un’opzione del HotSpot6 della JVM che, per

ogni garbage collection, stampa: la memoria allocata prima e dopo il collecting;

dove il collecting e stato effettuato (nello young heap, nell’old heap o entrambi);

il tempo impiegato per essere eseguito. Al fine di valutare quanto l’utilizzo del

garbage collector della client-class machine incida sui tempi di esecuzione i risultati

vengono ora confrontati con quelli ottenuti eseguendo le stesse teorie su di una

server-class machine. Il comando utilizzato per eseguire il server HotSpot e

java -server -XX:+PrintGCTimeStamps alice.tuprolog.Agent teoria.pl

Sul sistema7 su cui vengono eseguiti i test la memoria heap minima a dispo-

sizione della JVM e di 48 MB, mentre quella massima e di 768 MB. Il garbage

collector di default e di tipo parallelo [4]. La Tabella 4.4 riassume, per ognuna delle

teorie, i risultati ottenuti per i due tipi di garbage collector, assieme al numero di

collecting dello young generation, dell’old generation e i tempi di esecuzione.

Dalla Tabella 4.4 si puo notare che la differenza fra i tempi di esecuzione dei

due tipi di JVM HotSpot risulta in poco piu di 800 ms per ogni garbage collecting

dell’old generation. La Sun Microsystems stima in meno di 500 ms il tempo di

esecuzione del garbage collector seriale sull’intero heap nel caso peggiore [4].

6HotSpot e il nome della java virtual machine implementata dalla Sun Microsystems. Esso,oltre a realizzare le funzionalita di base della JVM, provvede due diversi tipi di implementazionecon diverse ottimizzazioni: un HotSpot chiamato client e l’altro chiamato server.

7Il sistema e differente da quello utilizzato nell’analisi dei tempi di esecuzione e dell’utilizzodella memoria. In questo caso consiste in un processore Intel Core 2 Duo 2,4 GHz, con 3 GB diRAM su Windows Vista Home Premium.

34

4.4. GRAFO DELLE ALLOCAZIONI

Nome teoria HotSpot N. Young gc N. Old gc Tempo (ms)

Spanning treeclient 4910 5 10599server 105 0 6393

Switch squareclient 23753 49 75285server 609 0 35573

Tabella 4.4: Analisi del garbage collector.

4.4 Grafo delle allocazioni

In modo simile a quanto fatto nell’analisi dei tempi di esecuzione viene creato

un grafo raffigurante i metodi che causano l’allocazione degli oggetti maggiormente

istanziati in memoria. L’obiettivo di questo studio e quindi quello di mettere alla

luce quali sono i metodi che fanno uso della memoria in modo piu consistente e

che, causando l’intervento del garbage collector, provocano un aumento dei tempi

di esecuzione. Con l’intenzione di valutare, non solamente gli oggetti attivi, ma

tutta la memoria allocata durante l’esecuzione delle teorie, vengono analizzati gli

oggetti presenti nella Tabella 4.3. In particolare per ognuno di questi oggetti viene

attraversato lo stack, nel tentativo di trovare qual e il primo metodo del packa-

ge alice nell’albero delle chiamate ad aver causato l’allocazione di quel oggetto8.

Per ognuno dei metodi trovati viene successivamente considerata la quantita di

memoria che essi hanno allocato per l’oggetto valutato. Questo valore viene suc-

cessivamente trasformato in percentuale sulla memoria complessivamente allocata

per il medesimo oggetto.

Il risultato viene esposto nella Figura 4.1 la quale mostra per ogni oggetto

(per conoscere l’oggetto rappresentato da un certo nodo si veda la Tabella 4.5) i

metodi che allocano una percentuale uguale o maggiore al 5% della memoria to-

tale allocata dallo stesso oggetto. I nodi le cui frecce provengono da altri oggetti

indicano che quel nodo e stato istanziato dal costruttore dell’oggetto o, nel caso

l’oggetto sia un array, dal costruttore di una delle istanze dell’array.

8Ovviamente vengono escluse dall’analisi le istanziazioni da parte di metodi rilasciati insiemealla piattaforma java in quanto questi non sono implementabili.

35


N. nodo Nome oggetto0 java.lang.Object[]1 char[]2 java.util.AbstractList$Itr3 java.lang.String4 java.lang.StringBuffer5 java.util.AbstractList$ListItr6 alice.tuprolog.Struct7 alice.tuprolog.Term[]8 alice.tuprolog.Var9 java.util.ArrayList

10 alice.tuprolog.ExecutionContext11 java.util.LinkedList$Entry12 alice.util.OneWayList13 byte[]

Tabella 4.5: Associazione fra il numero identificativo di un nodo nella Figura 4.1e l’oggetto che esso rappresenta.

36

4.4. GRAFO DELLE ALLOCAZIONI

0Var.unify5

30

23

14

ClauseInfo.performCopy

Term

.mat

chC

lau

seSt

ore

.deu

nify

2

21

61

7

9

Cla

use

Sto

re.d

eun

ify

Var.free

Term

.un

ify

SubGoalTree.iterator

1

Var.r

enam

e

98

397Var.rename

499Var.rename

5ClauseStore.reunify 99

699

799

899

9

50

18

167

7

Term

.mat

ch

ClauseStore.deunify

SubGoalTree.<init>

Term

.unify

StateRuleSelection.doJob10

99

11ClauseDatabase.getPredicates 98

12

99

13StateRuleSelection.doJob

PrimitiveInfo.evalAsPredicate

5

10

Eng

ineM

anag

er.s

olv

e

25

Tokenizer.<init> 16

Libra

ryM

anager.loadLib

rary

27

Figura 4.1: Analisi delle istanziazioni degli oggetti piu allocati nell’esecuzione delleteorie.

37


E facile notare dalla Figura 4.1 che il metodo alice.tuprolog.Var.rename compa-

re come metodo predominante nelle istanziazioni delle classi String, StringBuffer

e char[] causando, come detto in precedenza, l’allocazione del 20,68% della me-

moria totale. Inoltre questo metodo compare in uno dei costruttori della classe

alice.tuprolog.Var, la quale e fra le classi piu utilizzate. Questo porta ad un utilizzo

complessivo della memoria da parte di questo componente al 24,18%. Osservan-

do il grafo e possibile vedere che questa classe e a sua volta parte di un array

di oggetti di tipo alice.tuprolog.Term. In aggiunta Term implementa il metodo

match, responsabile del 50% delle allocazioni totali della classe java.util.ArrayList

e il 30% della classe java.lang.Object[]. Si comprende quindi quanto la struttura

delle classi formata dalla classe Term e le due classi Var e Struct che la estendono

sia molto delicata ed abbia bisogno di una sostanziale reimplementazione al fine di

migliorare le prestazioni di tuProlog per quanto riguarda l’utilizzo della memoria.

38

Capitolo 5

Confronto con la versione

tuProlog 1.3

In questo capitolo vengono confrontate la versione 2.1 di tuProlog con la 1.3,

le quali sono rispettivamente le ultime due release delle versioni 2 e 1 del moto-

re. Nella piu recente fra loro sono stati introdotti diversi cambiamenti a livello

architetturale che potrebbero averne influenzato le performance. Il fine di questo

confronto e proprio quello di mettere in evidenza le differenze prestazionali fra i

due interpreti, comparando i dati ricavati dal profiling di ognuno di essi. Il pro-

filer utilizzato e sempre HPROF: ovviamente, per rendere uniforme il confronto,

vengono utilizzate per la release 1.3 le stesse impostazioni adottate nei test dei

capitoli precedenti.

Di seguito, nella Tabella 5.1, vengono esposti i tempi di esecuzione misura-

ti nell’esecuzione delle teorie utilizzate come benchmark, sia per la versione 2.1

che per la versione 1.3 di tuProlog. Per gli stessi motivi discussi nel Capitolo 3

non vengono inseriti nella tabella i dati relativi alle teorie Crypt, Poly, Qsort,

Queens e Query in quanto hanno tempi di esecuzione troppo bassi.

Si puo osservare che la nuova architettura ha portato ad un aumento dei tempi di

esecuzione piuttosto pronunciato in tre delle quattro teorie sottoposte a verifica.

L’unica eccezione riguarda la teoria Tak, che e invece risultata circa il 37% piu

39

CAPITOLO 5. CONFRONTO CON LA VERSIONE TUPROLOG 1.3

Nome teoria tuProlog 1.3 (ms) tuProlog 2.1 (ms)Einstein’s riddle 10359 13807Spanning tree 1670 2216Switch square 6675 10110Tak 18158 11373

Tabella 5.1: Comparazione dei tempi di esecuzione nelle singole teorie.

veloce nella release 2.1 rispetto alla release 1.3.

Per quanto riguarda la memoria totale allocata dalle due versioni dell’inter-

prete l’analisi viene invece effettuata sommando lo spazio del heap allocato da

tutti i singoli metodi utilizzati nella risoluzione di ogni teoria. Nella Tabella 5.2

vengono quindi esposti i dati ricavati in KByte.

Nome teoria tuProlog 1.3 (KB) tuProlog 2.1 (KB)Crypt 4988 6106Einstein’s riddle 90576 206040Poly 3510 2351Queens 20201 10832Qsort 4334 2742Query 3410 2378Spanning tree 27928 67885Switch square 199696 262795Tak 343402 391710

Tabella 5.2: Comparazione dell’allocazione della memoria nelle singole teorie.

Anche in questo caso e possibile vedere come la piu’ recente release di tuProlog

utilizzi mediamente piu’ memoria. In special modo si puo notare la differenza

maggiore fra i due interpreti nelle teorie Einstein’s riddle, Spanning tree, Switch

square e Tak, le quali sono anche le quattro teorie con i tempi di esecuzione piu

lunghi. Le teorie Crypt, Poly, Qsort e Queens, che hanno utilizzi della memoria

relativamente contenuti, risultano allocare meno spazio nell heap nella versione

piu recente del motore.

40

Capitolo 6

Conclusioni

Il lavoro di profiling del motore tuProlog ha messo in luce diverse sezioni del

codice su cui porre l’attenzione in una futura reimplementazione dello stesso. Sia

per quanto riguarda i tempi di esecuzione, sia per l’utilizzo della memoria, si e visto

che e plausibile ottenere dei buoni miglioramenti agendo su parti dell’interprete

piuttosto circoscritte. In questo modo e possibile limitare la quantita di lavoro da

dedicare alla sua riscrittura. In aggiunta si e potuto constatare che l’allocazione

della memoria incide visibilmente sui tempi di esecuzione del motore: percio, an-

che la velocita di tuProlog beneficerebbe da un piu oculato utilizzo della medesima.

In particolare le classi che rappresentano i termini della teoria sono quelle

che provocano il piu alto consumo di memoria e di tempo. La classe Term e

le sue specializzazioni Struct e Var sono la fonte principale dell’allocazione della

memoria. Studiando il loro comportamento dettagliatamente si e visto che il me-

todo Var.rename e la causa principale dell’allocazione degli oggetti char[], String e

StringBuffer. Questi occupano circa il 20% della memoria totale istanziata durante

l’esecuzione di tuProlog. Term.match, insieme al ClauseStore.deunify, e invece il

metodo che istanzia piu frequentemente gli oggetti Object[], ArrayList e Abstrac-

tList$Itr, producendo il 42% della memoria totale allocata. Anche nell’analisi dei

tempi di esecuzione queste classi risultano fra le piu costose. Infatti, escludendo il

metodo Object.wait, i sette metodi con i tempi di esecuzione piu lunghi apparten-

gono, oppure ricevono la maggior parte delle chiamate, da una di queste tre classi.

41

CAPITOLO 6. CONCLUSIONI

Uno dei punti fondamentali del lavoro e stato quello di valutare l’effetto del gar-

bage collector sui tempi di esecuzione. A questo proposito si e visto che la pulizia

della memoria grava anche pesantemente sulla velocita di risoluzione delle teorie.

Questo risulta essere particolarmente vero quando il sistema che ospita tuProlog

ha una quantita di memoria limitata. La conseguenza a questo problema e l’impos-

sibilita nell’avere performance scalabili all’aumentare della complessita delle teorie.

Oltre all’analisi delle prestazioni di tuProlog, il progetto ha avuto lo scopo

di mettere a confronto i tempi di esecuzione e l’utilizzo della memoria allocata da

parte delle versioni 2.1 e 1.3 dell’interprete. Il fine di questa comparazione e stato

quello di esaminare quali siano state le conseguenze in termini di performance in

seguito allo sviluppo dell’architettura del motore. A questo proposito si e visto che

la piu recente delle due versioni ha subito un aumento sia dei tempi di esecuzione

che della memoria allocata.

Un primo indirizzo che puo interessare il revisore di tuProlog riguarda il metodo

Var.rename. Questo metodo viene utilizzato dal costruttore della classe Var e, al

suo interno, compie delle concatenazioni fra oggetti String. I tempi di esecuzione,

come l’allocazione della memoria, potrebbero migliorare se, al posto di una classe

immutabile la quale crea nuovi oggetti char[] ad ogni operazione, venisse utilizzata

StringBuilder. Anche Term.match puo essere facilmente migliorato impostando

una capacita iniziale diversa da quella di default. Gli ArrayList creano infatti un

oggetto Object[] ogni volta che la capacita della lista diventi insufficiente ad acco-

gliere altri oggetti. Aumentando ragionevolmente le dimensioni iniziali della lista

e possibile diminuire il numero di volte che questa operazione viene effettuata e,

di conseguenza, le allocazioni di Object[].

Infine, per quanto riguarda gli sviluppi futuri, e ragionevole approfondire l’a-

nalisi della memoria. Il profiler HPROF non permette infatti di analizzare quali

sono gli oggetti live in un certo istante dell’esecuzione dell’applicazione, ma sem-

plicemente gli oggetti allocati. Conoscere la quantita di memoria live nel tempo

potrebbe rivelarsi utile, in quanto il valore massimo di questa funzione corrispon-

42

de alla quantita di memoria che deve essere a disposizione dell’applicazione per

eseguire correttamente1. Percio, individuare i metodi che causano eventuali pic-

chi nell’utilizzo della memoria, migliorerebbe l’utilizzo di tuProlog su sistemi con

risorse limitate.

1In qualsiasi istante della risoluzione della teoria la quantita di memoria live non puo esseresuperiore alla memoria heap a disposizione, in quanto questo causerebbe un OutOfMemoryError.

43

Bibliografia

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Introduction to algorithms. MIT Press, 2008.

[2] Erich Gamma, Richard Helm, Ralph Johnson, and John M. Vlissides. Design

patterns: elements of reusable object-oriented software. Addison-Wesley, 1994.

[3] Richard Jones and Rafael D. Lins. Garbage collection: algorithms for automatic

dynamic memory management. Wiley, 1996.

[4] Sun Microsystems. Memory management in the java hotspot virtual machine.

Technical report, Sun Microsystems, 2006.

[5] Monica Pawlan. Reference objects and garbage collection. 1998.

[6] Alessandro Ricci, Alex Benini, Andrea Omicini, and Giulio Piancastelli. The

architecture and design of a malleable object-oriented prolog engine. Technical

report, DEIS - Universita di Bologna, 2008.

45

Analisi di prestazione dell'interprete tuProlog su piattaforma Java - Tesi

Technology

Transcript of Analisi di prestazione dell'interprete tuProlog su piattaforma Java - Tesi