Specializzazione automatica di programmi per Java

Pietro Cappellazzo, 809652

Alvise Costa, 810114

2

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

3

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.

4

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.

5

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.

6

Esempio (1)

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)

Il diagramma ad oggetti del programma e una generica interazione con l’oggetto Power (calcolo di x3).

7

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.

8

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

9

Partial Evaluation

Binding - time AnalysisL’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.

10

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.

11

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.

12

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).

13

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, …

14

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

15

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

16

L’esempio Power rivisitato

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.

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

17

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?

18

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.

19

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.

20

EsempioLa 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

21

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.

22

Esempio

L’oggetto x viene stampato prima di essere passato come argomento del metodo dotP.

Non vogliamo che avvenga la stampa durante la specializzaizone: x deve essere disponibile nel programma residuo e quindi avere b. t. dinamico.

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.

23

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.

24

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.

25

Specializzazione VS Compilazione

26

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.

27

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 ).

28

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.

29

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.

30

JSpec

31

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.

32

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.

33

TempoCODICE IN INPUT:/* Programma originale in linguaggio C */

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++;

}

}

CODICE DOPO LA FASE DI ANALISI:/* 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++;

}

}

34

Tempo• La specializzazione basandosi su questo codice “annotato” e sugli

input conosciuti genera un programma specializzato.

CODICE DOPO LA FASE DI ANALISI:/* 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++;

}

}

CODICE DOPO LA FASE DI SPECIALIZZAZIONE:/*Specializzazione con char *fmt = “<%d|%d>” */

miniprintf_1(int val[])

{

putchar( '<' );

putint ( val[0] );

putchar( '|' );

putint ( val[1] );

putchar( '>' );

}

35

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.

36

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 Op { int f_0(int i){throw new JSpekExn();}}introduction Add { int f_0(int i){return i+0;}}introduction Mul { int f_0(int i){return i*0;}}introduction Use { int apply_0(OP p, int x){return p.f_0(x);}}

}

37

JSpec – esempi praticiPROGRAMMA GENERICO:interface IxI2I{ int f(int x, int y);}class Add implements IxI2I { int f(int x, int y){return x+y;}}class Mul implements IxI2I { int f(int x, int y){return x*y;}}class Use {int apply(IxI2I 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);}}}

38

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.

39

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:

40

JSpec – Visitor Design PatternCODICE 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);}}DIAGRAMMA DELLE ITERAZIONI:

class FoldBinOp extends TreeVisitor {

…

int visitNode(Node n) {return this.op.eval(n.getLeft().accept(this),n.getRight().accept(this) ); }}

41

JSpec – Visitor Design Pattern

• 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.

Specclass FoldPlus specializes Client{@specialize: int processTree (Tree t, TreeVisitor v),Where v: FoldWithPlus;}

Specclass FoldWithPlus specializes FoldBinOp {Op: Plus;}

42

JSpec – Visitor Design PatternCODICE 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:

43

JSpec – Visitor Design Pattern

44

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/