Additions:
4. **Constant folding**: sì, il ##b-1## del test ##> b-1## viene precalcolato dal compilatore. Infatti, le istruzioni:
confrontano il risultato della ##cmp## direttamente con zero senza dover calcolare ##b-1## a tempo di esecuzione.
Deletions:
4. **Constant folding**: sì, il ##b-1## del test ##> b-1## viene precalcolato dal compilatore. Infatti, viene effettuato:
che confronta il risultato della ##cmp## con zero (##b-1##).
Additions:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx
Deletions:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx#
Additions:
4. **Constant folding**: sì, il ##b-1## del test ##> b-1## viene precalcolato dal compilatore. Infatti, viene effettuato:
Deletions:
~4. **Constant folding**: sì, il #b-1# del test ##> b-1## viene precalcolato dal compilatore. Infatti, viene effettuato:
Additions:
jg .L5
Deletions:
ìjg .L5
Additions:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx#
3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b##, compilata nelle istruzioni:
subl $1, %eax
testl %eax, %eax
ìjg .L5
che nel test ##> b-1##, compilato nelle istruzioni:
testl %ecx, %ecx
jg .L6
testl %ecx, %ecx
jg .L6
Deletions:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx#
3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b## compilata nelle istruzioni
che nel test ##> b-1##, compilato nelle istruzioni
Additions:
1. **Loop-invariant code motion**: no (non ci sono espressioni invarianti nel ciclo che possono essere portate fuori dal ciclo)
2. **Function inlining**: sì, infatti non ci sono istruzioni ##call## e il corpo della funzione ##cmp## è rimpiazzata dalle istruzioni:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx#
che calcolano la differenza di elementi consecutivi dell'array.
3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b## compilata nelle istruzioni
che nel test ##> b-1##, compilato nelle istruzioni
~4. **Constant folding**: sì, il #b-1# del test ##> b-1## viene precalcolato dal compilatore. Infatti, viene effettuato:
che confronta il risultato della ##cmp## con zero (##b-1##).
Deletions:
~1. **Loop-invariant code motion**: no (non ci sono espressioni invarianti nel ciclo che possono essere portate fuori dal ciclo)
~2. **Function inlining**: sì, infatti non ci sono istruzioni ##call## e il corpo della funzione ##cmp## è rimpiazzata dalle istruzioni ##movl -4(%edx,%eax,4), %ecx## e ##subl (%edx,%eax,4), %ecx## che calcolano la differenza di elementi consecutivi dell'array.
~3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b## (istruzioni ##subl $1, %eax##, ##testl %eax, %eax## e ##jg .L5##) che nel test ##> b-1## (istruzioni ##testl %ecx, %ecx##, ##jg .L6##).
~4. **Constant folding**: sì, il #b-1# del test ##> b-1## viene precalcolato dal compilatore. Infatti, viene effettuato ##testl %ecx, %ecx##, ##jg .L6##, che confronta il risultato della ##cmp## con zero (##b-1##).
Additions:
~3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b## (istruzioni ##subl $1, %eax##, ##testl %eax, %eax## e ##jg .L5##) che nel test ##> b-1## (istruzioni ##testl %ecx, %ecx##, ##jg .L6##).
Deletions:
~3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b## (istruzioni ##subl $1, %eax##, ##testl %eax, %eax## e ##jg .L5##)
) che nel test ##> b-1## (istruzioni ##testl %ecx, %ecx##, ##jg .L6##).
Additions:
==Esercizio 4 (Ottimizzazioni del compilatore)==
Il codice assembly generato da ##gcc -O1## per il programma è:
ord:
.LFB1:
.cfi_startproc
movl 4(%esp), %edx
movl 8(%esp), %eax
jmp .L3
.L5:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx
testl %ecx, %ecx
jg .L6
.L3:
subl $1, %eax
testl %eax, %eax
jg .L5
movl $1, %eax
ret
.L6:
movl $0, %eax
ret
Possiamo ignorare .LFB1: e .cfi_startproc.
~1. **Loop-invariant code motion**: no (non ci sono espressioni invarianti nel ciclo che possono essere portate fuori dal ciclo)
~2. **Function inlining**: sì, infatti non ci sono istruzioni ##call## e il corpo della funzione ##cmp## è rimpiazzata dalle istruzioni ##movl -4(%edx,%eax,4), %ecx## e ##subl (%edx,%eax,4), %ecx## che calcolano la differenza di elementi consecutivi dell'array.
~3. **Constant propagation**: sì, la costante ##b=1## viene propagata sia nell'espressione ##--n>=b## (istruzioni ##subl $1, %eax##, ##testl %eax, %eax## e ##jg .L5##)
) che nel test ##> b-1## (istruzioni ##testl %ecx, %ecx##, ##jg .L6##).
~4. **Constant folding**: sì, il #b-1# del test ##> b-1## viene precalcolato dal compilatore. Infatti, viene effettuato ##testl %ecx, %ecx##, ##jg .L6##, che confronta il risultato della ##cmp## con zero (##b-1##).
Additions:
Si noti l'opzione ##-pg## per collegare ##gprof## al programma.
Eseguire il programma con ##./es1##.
Poiché il programma è stato compilato con ##-pg##, ##./es1## effettua una esecuzione "profilata" che genera un file binario ##gmon.out##.
Deletions:
Si noti l'opzione ##-pg## per attivare ##gprof##.
Eseguire con: ##./es1##. Viene generato un file binario ##gmon.out##.
Additions:
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x. Non male... Si noti che il valore è comunque approssimato poiché il valore a denominatore è inaccurato essendo vicino alla precisione con cui il sistema usato effettua le misurazioni (millisecondi).
Deletions:
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x. Non male... Si noti che il valore è comunque approssimato poiché il valore a denominatore è impreciso essendo vicino alla precisione con cui il sistema usato effettua le misurazioni (millisecondi).
Additions:
**Domanda 5.** L'ottimizzazione del punto 1 modifica il costo asintotico del programma?
**Risposta.** Sì, il costo originale è quadratico nella lunghezza dell'array (perché?), quello ottimizzato è lineare.
Additions:
**Risposta.** L'ottimizzazione deve essere effettuata manualmente poiché il compilatore non può fare alcuna assunzione su quello che viene fatto dalla funzione ##len##. Infatti, la funzione ##len## è in un modulo diverso da quello che contiene la funzione ##ordina##. In generale, ##len## potrebbe effettuare dei side-effect che renderebbero la trasformazione di loop-invariant code motion errata. Si noti infatti che i compilatori applicano solo trasformazioni dei programmi che non ne modificano il comportamento osservabile (la semantica).
Deletions:
**Risposta.** L'ottimizzazione deve essere effettuata manualmente poiché il compilatore non può fare alcuna assunzione su quello che viene fatto dalla funzione ##len##. Infatti, la funzione ##len## è in un modulo diverso da quello che contiene la funzione ##ordina##. In generale, ##len## potrebbe effettuare dei side-effect che renderebbero la trasformazione di loop-invariant code motion errata. Si noti infatti che i compilatori applicano solo trasformazioni dei programmi che non ne modificano il comportamento (la semantica).
Additions:
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x. Non male... Si noti che il valore è comunque approssimato poiché il valore a denominatore è impreciso essendo vicino alla precisione con cui il sistema usato effettua le misurazioni (millisecondi).
**Risposta.** L'ottimizzazione deve essere effettuata manualmente poiché il compilatore non può fare alcuna assunzione su quello che viene fatto dalla funzione ##len##. Infatti, la funzione ##len## è in un modulo diverso da quello che contiene la funzione ##ordina##. In generale, ##len## potrebbe effettuare dei side-effect che renderebbero la trasformazione di loop-invariant code motion errata. Si noti infatti che i compilatori applicano solo trasformazioni dei programmi che non ne modificano il comportamento (la semantica).
Deletions:
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x. Non male...
**Risposta.** [...]
Additions:
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x. Non male...
Deletions:
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x
Additions:
**Risposta.** Compiliamo il programma vecchio con il nome ##es1## e quello ottimizzato con il nome ##es1-opt##. Misuriamo i tempi:
$ time ./es1
$ time ./es1-opt
real 0m0.002s
user 0m0.000s
sys 0m0.001s
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x
Deletions:
**Risposta.**
time ./es1
Additions:
**Risposta.** La funzione che richiede più tempo totale è ##len##. Essa viene infatti chiamata ad ogni iterazione della funzione ##ordinato## sebbene restituisca sempre lo stesso valore. Possiamo pertanto applicare la tecnica del loop-invariant code motion.
**Risposta.** Spostiamo la chiamata a ##len## fuori dal ciclo come segue:
**Risposta.**
**Risposta.** [...]
Deletions:
**Risposta 1.** La funzione che richiede più tempo totale è ##len##. Essa viene infatti chiamata ad ogni iterazione della funzione ##ordinato## sebbene restituisca sempre lo stesso valore. Possiamo pertanto applicare la tecnica del loop-invariant code motion.
**Risposta 2.** Spostiamo la chiamata a ##len## fuori dal ciclo come segue:
**Risposta 3.**
**Risposta 4.** [...]
Additions:
**Risposta 3.**
time ./es1
1 [corretto = 1]
real 0m2.815s
user 0m2.805s
sys 0m0.004s
Deletions:
**Risposta 3.** [...]
Additions:
**Domanda.** Consideriamo un programma P che richiede 10 secondi, ottimizziamo una funzione f che richiede il 30% del tempo di esecuzione totale di P, e vediamo che il tempo totale di P scende a 8 secondi. Di quante volte abbiamo velocizzato f?
**Risposta.** Lo speedup del programma è 10/8. Usando la legge di Amdahl, abbiamo:
**Domanda 1.** Che tecnica di ottimizzazione useresti per ridurre il tempo di esecuzione del programma? Perché?
Deletions:
**Domanda:** Consideriamo un programma P che richiede 10 secondi, ottimizziamo una funzione f che richiede il 30% del tempo di esecuzione totale di P, e vediamo che il tempo totale di P scende a 8 secondi. Di quante volte abbiamo velocizzato f?
**Risposta:** Lo speedup del programma è 10/8. Usando la legge di Amdahl, abbiamo:
**Domanda 1:** Che tecnica di ottimizzazione useresti per ridurre il tempo di esecuzione del programma? Perché?
Additions:
**Risposta 1.** La funzione che richiede più tempo totale è ##len##. Essa viene infatti chiamata ad ogni iterazione della funzione ##ordinato## sebbene restituisca sempre lo stesso valore. Possiamo pertanto applicare la tecnica del loop-invariant code motion.
**Domanda 2.** Applicare al programma l'ottimizzazione indicata al punto 1.
**Risposta 2.** Spostiamo la chiamata a ##len## fuori dal ciclo come segue:
**Domanda 3.** Misurare il tempo di esecuzione del programma prima e dopo l'ottimizzazione: di che fattore si è velocizzato il programma a seguito dell'ottimizzazione applicata? (es. 2x vuole dire che è due volte più veloce, cioè richiede la metà del tempo di esecuzione).
**Risposta 3.** [...]
**Domanda 4.** L'ottimizzazione applicata deve essere applicata manualmente dal programmatore, oppure possiamo aspettarci che venga effettuata in automatico dal compilatore?
**Risposta 4.** [...]
Deletions:
**Risposta 1:** La funzione che richiede più tempo totale è ##len##. Essa viene infatti chiamata ad ogni iterazione della funzione ##ordinato## sebbene restituisca sempre lo stesso valore. Possiamo pertanto applicare la tecnica del loop-invariant code motion e spostare la chiamata a ##len## fuori dal ciclo come segue:
**Domanda 2:** Applicare al programma l'ottimizzazione indicata al punto 1.
**Risposta 2:** [...]
**Domanda 3:** Misurare il tempo di esecuzione del programma prima e dopo l'ottimizzazione: di che fattore si è velocizzato il programma a seguito dell'ottimizzazione applicata? (es. 2x vuole dire che è due volte più veloce, cioè richiede la metà del tempo di esecuzione).
**Risposta 3:** [...]
**Domanda 4:** L'ottimizzazione applicata deve essere applicata manualmente dal programmatore, oppure possiamo aspettarci che venga effettuata in automatico dal compilatore?
**Risposta 4:** [...]