Specializzazione automatica
di programmi per Java
Pietro Cappellazzo, 809652
Alvise Costa, 810114
L’efficienza dei linguaggi OO (1)
• Caratteristiche d’interesse
– Encapsulation: aumenta le possibilità di recupero
e riutilizzo del codice
– Method invocation: permette la comunicazione tra
componenti in maniera indipendente da una
specifica implementazione
• Pro e Contro
– Facilita l’adattamento dei programmi
– Accresce la genericità dei programmi
– Diminuisce l’efficienza
2
L’efficienza dei linguaggi OO (2)
La proprietà di encapsultion isola singole parti
del porgramma aumentando così il costo di
accesso ai dati.
L’ invocazione di metodi è implementata
traminte il dispatch virtuale, in questo modo il
flusso di controllo del programma viene
nascosto.
Le ottimizzazioni tradizionali (hw / sw) eliminano
solo alcuni di questi costi generali.
3
Program Specialization (1)
È una tecnica per adattare un programma ad
uno specifico contesto di esecuzione.
Lo scopo è quello di semplificare le interazioni
tra gli oggetti di un programma eliminando le
chiamate virtuali, aggirando l’encapsulation e
semplificando il calcolo delle invarianti.
4
Program Specialization (2)
Si consideri un programma P che prende in ingresso due
argomenti S e D e produce un risultato R:
run P(S,D) = R
Una specializzazione di P, rispetto a S, è un programma PS tale
che:
run PS(D) = run P(S,D) = R
L’input S è detto statico ed è noto a tempo di specializzazione.
L’input D è detto dinamico ed è noto solo a tempo di esecuzione.
5
Esempio (1)
Il diagramma ad oggetti del programma
e una generica interazione con l’oggetto
Power (calcolo di x3).
Una collezione di quattro classi:
Binary, Add, Mult e Power. La
classe Power può essere utilizzata
per applicare un operatore Binary
un certo numero di volte su un valore
base:
(new Power(y, new Mult())).raise(x)
6
Esempio (2)
• Considerando il calcolo di x3 si nota che l’invocazione del
metodo raise(x) dell’oggetto Power dà luogo ad una
serie di interazioni con l’oggetto Mult e ritorna il valore
x*x*x.
• Per ottimizzare si può aggiungere alla classe Power un
metodo raise_cube(x) che ritorni direttamente x*x*x.
7
Automatic Program Specialization
• La partial evaluation è un approccio alla specializzazione
che adatta un programma alle informazioni note (statiche)
sul suo contesto di esecuzione, così come sono fornite
dall’utente.
• Propagazione inter - procedurale di valori di qualsiasi tipo
di dato, semplificazione del flusso di controllo e constant folding basato su informazioni di contesto.
• Nella partial evaluation di tipo off - line, la specializzazione
è divisa in due passi:
– Binding - time analysis
– Produzione di codice specializzato
8
Partial Evaluation
Binding - time Analysis
L’utente specifica quali argomenti (incluse le variabili
globali) sono statici (noti) e quali sono dinamici (non
ancora noti) nel contesto di esecuzione.
L’informazione (statico / dinamico) viene propagata
attraverso il codice al fine di identificare quali istruzioni
(espressioni) sono statiche e quali dinamiche.
Un programma può essere specializzato rispetto qualsiasi
contesto concreto che fornisca valori per gli input statici.
9
Partial evaluation: terminazione
• La partial evaluation non impone alcun limite alla
quantità di computazioni che possono essere
eseguite per ottimizzare un programma, perciò
non è garantita la terminazione del processo di
specializzazione.
• L’utente deve indirizzare il processo verso le parti
del programma che hanno maggiori opportunità di
specializzazione.
• P. E. eseguita su “fette” di programma.
10
Specializzazione di programmi O. O.
• L’esecuzione di un programma O. O.
può essere vista come una sequenza di
interazioni tra oggetti.
• L’obbiettivo della specializzazione è
quello di semplificare le interazioni tra
gli oggetti.
11
Invocazione di metodi (1)
• L’interazione tra gli oggetti avviene
attraverso l’invocazione di metodi quindi
la specializzazione si concentra su
questo aspetto.
• La specializzazione dell’invocazione dei
metodi ottimizza le chiamate basate su
argomenti statici (incluso this).
12
Invocazione di metodi (2)
La specializzazione dei metodi ottimizza l’uso di encapsulation,
virtual dispatch e computazione imperativa.
– Encapsulation: i dati statici vengono propagati dove necessario in
modo da ridurre le operazioni che utilizzano tali dati. Vengono
ridotte le referenze di memoria indirette al dato.
– Virtual Dispatch: decisione basata sul tipo dell’argomento this.
• this è statico: il metodo chiamante viene specializzato in base alle
informazioni sul contesto di chiamata.
• this è dinamico: ogni metodo che potrebbe essere chiamato viene
specializzato su un qualsiasi argomento statico.
– Computazione imperatva: utilizzo di constant propagation, constant
folding, loop unrolling, …
13
Il Programma Specializzato
Per completare il processo bisogna
reintegrare i metodi specializzati, nella
gerarchia della classi.
– Primo approccio: aggiungere ogni metodo
specializzato alla propria classe originaria.
• I metodi specializzati sono accessibili al resto
della classe
• Può venire rotta l’invariante di incapsulamento
• Complicazione del codice sorgente
14
Il Programma Specializzato
– Secondo approccio: metodi specializzati separati
da metodi originali
• I metodi specializzati derivanti da un’unica classe,
vengono collezionati in una uova sottoclasse
• Tutti i metodi specializzati vengono definiti come metodi
di una nuova classe
– Terzo approccio: esprimere i programmi
specializzati come programmi di tipo aspect oriented
• Permette alle unità logiche che “attraversano” il
programma di essere separate dalle altre parti del
programma stesso ed essere incapsulate in moduli
separati chiamati aspect
15
L’esempio Power rivisitato
L’oggetto Power è statico, possiamo
dichiarare questo contesto usando
una classe di specializzazione che
indica quali sono gli argomenti di
Power statici e dinamici e che
metodi specializzare
La classe di specializzazione Cube dichiara che i campi di Power
sono statici, fornisce specifici valori per questi campi e indica che il
metodo raise deve essere specializzato.
La specializzazione valuta l’invocazione del metodo neutral,
esegue un loop unrolling all’interno del metodo raise e riduce i
dispatch virtuali del metodo eval.
16
Aspetti essenziali di uno
Specializzatore
• Nell’analisi binding time, l’insieme dei costrutti
considerati statici determina direttamente i
benefici raggiunti dalla partial evaluation.
• È necessario decidere che grado di
precisione deve essere adottato affinché
l’analisi risulti utile.
• Un aspetto della precisione dell’analisi è la
sua granularità: a che tipi di valori devono
essere assegnati binding time individuali?
17
Granularità dell’analisi b. t.
• Non è possibile (per un’analisi statica)
distinguere tutti gli oggetti a run - time, perciò è
necessaria un’approssimazione.
• Un’opzione grossolana è quella di assegnare lo
stesso b. t. a tutte le istanze di una stessa classe
(poca precisione).
• Una soluzione adeguata è quella di assegnare
un’unica descrizione all’insieme degli oggetti
creati nello stesso punto. Un aspetto chiamato
class polyvariance.
18
Class & Method Polyvariance
• Un oggetto contiene tipicamente diversi valori di dati
e questi valori giocano ruoli diversi all’interno del
programma.
• Viene usato un binding time composto che contiene
una descrizione diversa per ogni campo dell’oggetto.
• La class polyvariance implica che un dato parametro
di un certo metodo può essere associato ad oggetti
con binding time diversi.
• Ogni invocazione di metodo dovrebbe, quindi, essere
analizzata singolarmente: method polyvariance.
19
Esempio
La classe Vec definisce un vettore di numeri
FP.
La classe VecOp definisce il metodo dotP
che esegue il prodotto scalare tra due
oggetti della classe Vec.
Il vettore x è inizializzato usando
informazioni statiche, il vettore y usando
informazioni dinamiche.
È possibile sfruttare l’informazione statica di
x, durante la specializzazione, solo se alle
due istanze (x e y) della classe Vec
vengono assegnati binding - time diversi.
Inoltre il metodo get, che accede ai dati del
vettore, deve essere analizzato
indipendentemente ad ogni invocazione
20
Use Sensitivity
Un altro aspetto della precisione dell’analisi è
il numero di descrizioni assegnate ad ogni
valore analizzato.
Un singolo oggetto può essere usato in
entrambi i contesti - statico e dinamico - di un
programma.
La soluzione è ancora quella di assegnare
all’oggetto un binding time composto statico –
e – dinamico.
21
Esempio
L’oggetto x viene stampato prima di
essere passato come argomento del
metodo dotP.
Considerando l’oggetto x come
statico – e – dinamico, l’analisi b. t.
può assegnare ad ogni utilizzo di x
un b. t. statico o dinamico, come
richiesto.
Non vogliamo che avvenga la stampa
durante la specializzaizone: x deve
essere disponibile nel programma
residuo e quindi avere b. t. dinamico.
22
Specializzazione VS Compilazione
• La specializzazione e le ottimizzazioni compiute
durante la compilazione sono tecniche simili, che
possono diventare complementari.
• Uso delle informazioni sui tipi per l’eliminazione del
“virtual dispatch” come le tecniche di customization
e di selective argument specializzation tipiche dei
compilatori.
• La specializzazione crea nuovi metodi specializzati
per propagare queste informazioni lungo tutto il
programma, e introduce questi metodi specializzati
nelle classi dei relativi metodi non specializzati.
23
Specializzazione VS Compilazione
• L’ottimizzazione data dalla specializzazione riguarda
solo alcuni aspetti del programma (dipendenti dalle
parti statiche) e riproducono l’intero codice sorgente,
mentre le tecniche di compilazione coinvolgono tutto il
programma, spesso modificando il codice.
• La specializzazione dipende dalle ottimizzazioni
eseguite dai compilatori come copy propagation,
common subexpression elimination, o loop invariant
removal, importanti per le prestazioni.
• Inoltre la specializzazione non può gestire
ottimizzazioni indipendenti dal codice, come
l’allocazione dei registri, oppure ad esempio in Java,
l’array bounds check elimination, che devono essere
fatti dal compilatore.
24
Specializzazione VS Compilazione
25
Vantaggi della Specializzazione
• La specializzazione propaga valori conosciuti di ogni
tipo (anche relativi ad oggetti conosciuti parzialmente)
lungo il programma, garantendo una maggiore
precisione.
• La specializzazione riduce ogni computazione basata
solamente su informazioni conosciute, non ponendo di
fatto limiti alle semplificazioni possibili, garantendo
quindi più aggressività di altre tecniche.
• La specializzazione è più dominante delle tecniche
aggressive usate dai compilatori, infatti usa conoscenze
globali riguardanti la struttura degli oggetti, in modo da
propagare informazioni globali e ridurre le
computazioni.
26
JSpec - Overview
• JSpec è un off-line partial evaluator che tratta l’intero
linguaggio Java, escluse le eccezioni, e le regioni finally.
• Input: codice sorgente Java, Java bytecode.
Output: codice sorgente Java, codice C.
• Il tempo per l’analisi compiuta da JSpec dipende dal
contesto, variabile a seconda delle classi (ogni creazione
di oggetto, ha un tempo di analisi individuale), dall’uso e
dal flusso del processo.
• Il codice specializzato in C attraverso l’ambiente Harissa
incorpora più ottimizzazioni low-level (es. l’array bounds
check elimination ).
27
JSpec - Overview
• JSpec sfrutta le opportunità date dalla specializzazione
di linguaggi ad oggetti (es. propagazione dei tipi,
eliminazione virtual dispatch, ecc..).
• JSpec inoltre esegue le ottimizzazioni standard della
specializzazione (es. propagazione globale delle
costanti, riduzione delle computazioni,ecc..).
• JSpec raccoglie quindi in un unico framework le
opportunità date sia dai linguaggi ad oggetti che da quelli
standard.
28
JSpec - Overview
• JSpec è basato su tecnologia esistente e matura, il
processo di specializzazione è basato su Tempo
(specializzatore per C).
• JSpec è stato progettato per essere utilizzato anche solo
in un ristretto insieme di classi di un intero programma.
• Le parti specializzate vengono racchiuse in aspect
immessi nel codice originale.
29
JSpec
30
Harissa
• Harissa è un compilatore dal bytecode Java a
C con una JVM integrata.
• Harissa è stata scritta in C con l’obbiettivo di
rendere efficienti e flessibili le esecuzioni di
programmi java.
• Harissa produce un codice C non fortemente
ottimizzato (questo sarà poi fatto dal
compilatore C) ma privo di tutti quei costrutti
dovuti alla JVM.
31
Tempo
• Tempo è un off-line partial evaluator per i
programmi C.
• Il processo si divide in 2 fasi, l’analisi e la
specializzazione.
• L’analisi propaga le informazioni riguardanti
costrutti statici e dinamici lungo il codice.
32
Tempo
CODICE IN INPUT:
CODICE DOPO LA FASE DI ANALISI:
/* Programma originale in linguaggio C */
/* Legenda: STATIC DYNAMIC */
miniprintf(char fmt[], int val[])
{
int i = 0;
while( *fmt != ‘\0' ) {
if( *fmt != '%' )
putchar(*fmt);
else
switch(*++fmt) {
case 'd' : putint(val[i++]); break;
case '%' : putchar('%');
break;
default : prterror(*fmt);
break;
}
fmt++;
}
}
miniprintf(char fmt[], int val[])
{
int i = 0;
while( *fmt != '/0' ) {
if( *fmt != '%' )
putchar(*fmt);
else
switch(*++fmt) {
case 'd' : putint(val[i++]); break;
case '%' : putchar('%');
break;
default : prterror(*fmt);
break;
}
fmt++;
}
}
33
Tempo
• La specializzazione basandosi su questo codice “annotato”
e sugli input conosciuti genera un programma specializzato.
CODICE DOPO LA FASE DI ANALISI:
CODICE DOPO LA FASE DI SPECIALIZZAZIONE:
/* Legenda: STATIC DYNAMIC */
miniprintf(char fmt[], int val[])
{
int i = 0;
while( *fmt != '/0' ) {
if( *fmt != '%' )
putchar(*fmt);
else
switch(*++fmt) {
case 'd' : putint(val[i++]); break;
case '%' : putchar('%');
break;
default : prterror(*fmt);
break;
}
fmt++;
}
}
/*Specializzazione con char *fmt = “<%d|%d>” */
miniprintf_1(int
{
putchar( '<'
putint ( val[0]
putchar( '|'
putint ( val[1]
putchar( '>'
}
val[])
);
);
);
);
);
34
AspectJ
• AspectJ è un linguaggio basato su Java
per avvalersi del Aspect Oriented
Programming.
• Aspetti usati per evitare ridondanza nel
codice e modellare problemi trasversali al
codice stesso.
• Nel caso di JSpec le parti specializzate
sono inserite in aspect.
35
JSpec – esempi pratici
• Negli esempi che seguono si vede come JSpec
viene applicato alle classi astratte e alle
interfacce
• In entrambi i casi si considera l’input con y=0
PROGRAMMA GENERICO:
abstract class Op {abstract int f(int i, int j); }
class Add extends Op {int f(int i, int j){return i+j; } }
class Mul extends Op {int f(int i, int j){return i*j; } }
class Use {int apply(Op p, int x, int y) {return p.f(x,y);}}
PROGRAMMA SPECIALIZZATO:
aspect ZeroArgument {
introduction
introduction
introduction
introduction
}
Op { int f_0(int i){throw new JSpekExn();}}
Add { int f_0(int i){return i+0;}}
Mul { int f_0(int i){return i*0;}}
Use { int apply_0(OP p, int x){return p.f_0(x);}}
36
JSpec – esempi pratici
PROGRAMMA GENERICO:
interface
class Add
class Mul
class Use
IxI2I{ int f(int
implements IxI2I
implements IxI2I
{int apply(IxI2I
x, int y);}
{ int f(int x, int y){return x+y;}}
{ int f(int x, int y){return x*y;}}
p, int x, int y){return p.f(x,y);}}
PROGRAMMA SPECIALIZZATO:
aspect ZeroArgument {
interface IxI2I_0 extends IxI2I{ int f_0(int x);}
introduction Add {
Implements IxI2I_0; int f_0(int x) {return x+0;}
}
introduction Mul {
Implements IxI2I_0; int f_0(int x) {return x*0;}
}
introduction Use {
int apply_0(IxI2I p, int x) {return ((IxI2I_0)p).f_0(x);}
}
}
37
JSpec – Visitor Design Pattern
• Il visitor design pattern è un metodo per
specificare un operazione in un elemento della
struttura di un oggetto esternamente alla classe
che implementa la struttura stessa.
• Nell’esempio viene utilizzato per implementare
delle operazioni su una semplice struttura ad
albero binario.
38
JSpec – Visitor Design Pattern
• La classe Tree è la superclasse astratta della classe Leaf e Node.
• La classe TreeVisitor è la superclasse astratta dei visitor che
operano nell’albero (nell’esempio FoldBinOp)
Diagramma della classe:
39
JSpec – Visitor Design Pattern
CODICE SORGENTE:
class Client {
int processTree (Tree t, TreeVisitor
v)
{
return t.accept(v);
}
}
class Node extends Tree {
…
int accept(TreeVisitor v) {
return v.visitNode(this);
}}
class FoldBinOp extends TreeVisitor {
…
int visitNode(Node n) {
return this.op.eval(
n.getLeft().accept(this),
n.getRight().accept(this) );
}
}
DIAGRAMMA DELLE ITERAZIONI:
40
JSpec – Visitor Design Pattern
Specclass FoldPlus specializes Client{
@specialize: int processTree (Tree t, TreeVisitor v),
Where v: FoldWithPlus;
}
Specclass FoldWithPlus specializes FoldBinOp {
Op: Plus;
}
• La classe specializzata FoldPlus dichiara
che la specializzazione inizia nel metodo
processTree della classe Client.
• La specializzazione semplifica i virtual
dispatches dei metodi accept dentro alle
classi node e leaf in chiamate dirette.
41
JSpec – Visitor Design Pattern
CODICE SPECIALIZZATO:
aspect FoldPlus {
introduction Client {
… t.accept_bp() …
}
…
introduction Node {
int accept_bp(){
return this.left.accept_bp() + this.right.accept_bp();
}}
}
DIAGRAMMA DELLE ITERAZIONI SPECIALIZZATE:
42
JSpec – Visitor Design Pattern
43
Bibliografia
•
U. P. Schultz, J. L. Lawall, C. Consell “Automatic Program Specialization for
Java” ACM Transactions on Programming Languages and Systems, Vol. 25,
N°4, p.p. 452-499 [July 2003]
•
C. Consel, L. Hornof, J. Noyé, F. Noel, E.N. Volanschi “A Uniform Approach
for Compile-Time and Run-Time Specialization” Research Report 2775,
INRIA. [January 1996]
•
G. Muller, U. P. Schultz “Harissa: A hybrid approach to dynamic optimization
in run-time specialization” IEEE Software 16,2 p.p. 44-51 [March 1999]
•
http://compose.labri.fr/
44