Επόμενο Προηγούμενο Περιεχόμενα
...και την 42η μέρα ο Θεός δημιούργησε την C. Βλέποντας
την απειλή οι δυνάμεις του Κακού αποφάσισαν να
αντεπιτεθούν... και έτσι γεννήθηκε η Java.
Η Java από τότε που δημιουργήθηκε κλήθηκε να
αντιμετωπίσει τις κυρίαρχες τότε (αλλά και σήμερα) C και
C++. Η σύγκριση ήταν αναπόφευκτη΄ η Java διαφημιζόταν ως
μια πιο κομψή και ασφαλής C++, μια γλώσσα ικανή να
χρησιμοποιηθεί σε ένα ευρύ πεδίο εφαρμογών, από
ιστοσελίδες μέχρι ενσωματωμένες συσκευές. Όπως
συνηθίζεται στον κόσμο των υπολογιστών, ένας "ιερός"
πόλεμος ξέσπασε.
Οι πολέμιοι της Java είχαν κυρίως δύο λόγους για τους
οποίους ήθελαν να την κάψουν στην πυρά. Καταρχάς υπήρχαν
εκείνοι που στο άκουσμα της λέξης "αντικειμενοστρεφής"
έβγαζαν σκόρδα και προσπαθούσαν να ξορκίσουν τα δαιμόνια.
Σε αυτούς, βέβαια, δεν άρεσε ούτε η C++, η οποία όμως
έπαιρνε άφεση διότι μπορούσε απλώς να χρησιμοποιηθεί ως
βελτιωμένη C. Ο δεύτερος και πιο καταδικαστικός λόγος
ενάντια στην Java ήταν ότι ήταν αργή. Ειδικά σε ότι είχε
σχέση με γραφικές διεπαφές (GUI) ήταν εκνευριστικά αργή
και επιπλέον είχε μια μέτριας ποιότητας (εμφανισιακά,
τουλάχιστον) βιβλιοθήκη χειριστηριών.
Σήμερα, αρκετό καιρό ύστερα από την έναρξη της διαμάχης,
τα πράγματα φαίνεται να έχουν μπει σε μια τάξη. Η Java
έχει καταφέρει να βελτιωθεί θεαματικά στο φλέγον θέμα της
απόδοσης και έτσι έχει κατακτήσει μια αρκετά υψηλή θέση
στις καρδιές των προγραμματιστών αλλά και των διοικητικών
στελεχών. Η C παραμένει κυρίαρχη στον τομέα για τον οποίο
σχεδιάστηκε, τον προγραμματισμό συστημάτων, ενώ η C++
απολαμβάνει μια σταθερή θέση σε εφαρμογές που
επωφελούνται από την αντικειμενοστρεφή προσέγγιση και
ταυτόχρονα έχουν αυξημένες απαιτήσεις απόδοσης.
Δυστυχώς στις απόψεις πολλών η Java και γενικά οι
διερμηνευόμενες (interpreted) γλώσσες έχουν στιγματιστεί
από την αργοπορία που τις χαρακτήριζε στα πρώτα τους
βήματα. Στο πείραμα που ακολουθεί θα εξετάσουμε και θα
εξηγήσουμε την απρόσμενα καλή απόδοση ενός προγράμματος
σε Java.
Στο πείραμα που ακολουθεί θα μετρήσουμε τους χρόνους
εκτέλεσης του ίδιου προγράμματος σε C (gcc 3.2.3) και σε
Java (Sun J2RE 1.4.2_01). Το πρόγραμμα είναι η αναδρομική
συνάρτηση υπολογισμού των όρων της σειράς fibonacci fn =
fn-1 + fn-2, με f0 = 0 και f1 = 1.
Σε C:
#include <stdio.h>
#include <stdlib.h>
unsigned long fib(unsigned long n)
{
if (n < 2)
return n;
else
return fib(n-1) + fib(n-2);
}
int main(int argc, char *argv[])
{
int n;
if (argc < 2)
n = 1;
else
n = atoi(argv[1]);
printf("%lu\n", fib(n));
return 0;
}
Σε Java:
public class fib {
public static void main(String args[]) {
int n;
if (args.length < 1)
n = 1;
else
n = Integer.parseInt(args[0]);
System.out.println(fib(n));
}
public static int fib(int n) {
if (n < 2)
return n;
else
return fib(n-1) + fib(n-2);
}
}
Μεταγλωττίζουμε τα δύο προγράμματα και τα εκτελούμε 3
φορές το καθένα. Το J2RE της Sun προσφέρει δύο εικονικές
μηχανές, την server και την client (default). Η πρώτη
έχει μεγαλύτερες απαιτήσεις μνήμης αλλά έχει ως
αποτέλεσμα καλύτερη ταχύτητα εκτέλεσης ενώ η δεύτερη έχει
πιο μικρές απαιτήσεις αλλά η ταχύτητα εκτέλεσης δεν είναι
η βέλτιστη. Εδώ χρησιμοποιούμε την παράμετρο "-server"
που επιλέγει την server VM (εικονική μηχανή).
$ gcc -O3 -fomit-frame-pointer -o fib.c.exe fib.c
$ time fib.c.exe 39
63245986
real 0m7.479s
user 0m7.361s
sys 0m0.017s
$ time fib.c.exe 39
63245986
real 0m7.478s
user 0m7.368s
sys 0m0.013s
$ time fib.c.exe 39
63245986
real 0m7.471s
user 0m7.366s
sys 0m0.016s
$ javac fib.java
$ time java -server fib 39
63245986
real 0m5.853s
user 0m5.618s
sys 0m0.049s
$ time java -server fib 39
63245986
real 0m5.848s
user 0m5.625s
sys 0m0.043s
$ time java -server fib 39
63245986
real 0m5.847s
user 0m5.622s
sys 0m0.044s
Η Java φαίνεται να έχει αρκετά καλύτερες επιδόσεις από τη
C!!! Είναι δυνατόν; Ευτυχώς ή δυστυχώς είναι!
Αφού περάσει το πρώτο σοκ, ανασυντασσόμαστε και
προσπαθούμε να φερθούμε όσο πιο επιστημονικά γίνεται.
Έχουμε ένα πείραμα με απροσδόκητα αποτελέσματα και
καλούμαστε να τα εξηγήσουμε.
Καταρχάς, γνωρίζουμε ότι o διερμηνευτής της Java περιέχει
JIT μεταγλωττιστή οπότε γενικά θα περιμέναμε μια καλή
απόδοση. Το βασικό ερώτημα είναι το τι έκανε ο JIT
μεταγλωττιστής, που δε μπόρεσε να κάνει ο gcc, ώστε να
βελτιώσει την απόδοση κατά 20% περίπου. Για να
απαντήσουμε σε αυτό το ερώτημα το καλύτερο που μπορούμε
να κάνουμε είναι να συγκρίνουμε τον κώδικα μηχανής που
παρήγαγε καθένας από τους δύο αντιπάλους.
Τον κώδικα μηχανής που παρήγαγε ο gcc είναι πολύ απλο να
τον εξετάσουμε χρησιμοποιώντας τον HT Editor. Βεβαίως,
μπορείτε να χρησιμοποιήσετε όποιο εργαλείο σας βολεύει.
|| ....... ! ;********************************************************
|| ....... ! ; function fib (global)
|| ....... ! ;********************************************************
|| ....... ! fib: ;xref c80483d7 c80483e4 c8048427
|| ....... ! ;xref c8048434
|| ....... ! push esi
|| 8048411 ! push ebx
|| 8048412 ! mov esi, [esp+0ch] ;; esi=n
|| 8048416 ! cmp esi, 1
|| 8048419 ! mov eax, esi
|| 804841b ! ja loc_8048420
|| 804841d !
|| ....... ! loc_804841d: ;xref j804843f
|| ....... ! pop ebx
|| 804841e ! pop esi
|| 804841f ! ret
|| 8048420 !
|| ....... ! loc_8048420: ;xref j804841b
|| ....... ! sub esp, 0ch
|| 8048423 ! lea edx, [esi-1]
|| 8048426 ! push edx
|| 8048427 ! call fib ;; fib(n-1)
|| 804842c ! lea edx, [esi-2]
|| 804842f ! mov ebx, eax
|| 8048431 ! mov [esp], edx
|| 8048434 ! call fib ;; fib(n-2)
|| 8048439 ! lea eax, [eax+ebx] ;; eax = fib(n-1) + fib(n-2)
|| 804843c ! add esp, 10h
|| 804843f ! jmp loc_804841d
Ένα πολύ χρήσιμο χαρακτηριστικό του HT editor είναι ότι
υποστηρίζει πληθώρα εκτελέσιμων αρχείων, μεταξύ αυτών και
τα .class αρχεία της Java! Έτσι είναι απλό να εξετάσουμε
και τα bytecodes στα οποία μεταφράστηκε η συνάρτηση fib:
|| ... ! ;----------------------------------------------
|| ... ! ; public static int fib::fib(int)
|| ... ! ;----------------------------------------------
|| ... ! fib_1fa:
|| ... ! iload_0 ;; Σωρός: [n]
|| 1fb ! iconst_2 ;; Σωρός: [n] [2]
|| 1fc ! if_icmpge loc_201 ;; Σωρός: -, if (n >= 2) goto loc_201
|| 1ff ! iload_0 ;; Σωρός: [n]
|| 200 ! ireturn
|| 201 !
|| ... ! loc_201: ;xref j1fc
|| ... ! iload_0 ;; Σωρός: [n]
|| 202 ! iconst_1 ;; Σωρός: [n] [1]
|| 203 ! isub ;; Σωρός: [n-1]
|| 204 ! invokestatic <int fib::fib(int)> 4 ;; Σωρός: [fib(n-1)]
|| 207 ! iload_0 ;; Σωρός: [fib(n-1)] [n]
|| 208 ! iconst_2 ;; Σωρός: [fib(n-1)] [n] [2]
|| 209 ! isub ;; Σωρός: [fib(n-1)] [n-2]
|| 20a ! invokestatic <int fib::fib(int)> 4 ;; Σωρός: [fib(n-1)] [fib(n-2)]
|| 20d ! iadd ;; Σωρός: [fib(n-1)+fib(n-2)]
|| 20e ! ireturn
Φως στο τούνελ του Java JIT μεταγλωττιστή
Η αποστολή μας, αν τη δεχθούμε, είναι να βρούμε και να
αναλύσουμε τον κώδικα μηχανής που παρήγαγε ο JIT
μεταγλωττιστής (native κώδικας). Το πρόβλημα είναι ότι δε
γνωρίζουμε καθόλου την εσωτερική λειτουργία του Sun Java
διερμηνευτή (αφού ο κώδικας είναι κλειστός). Το μόνο
σίγουρο είναι ότι ο εκτελέσιμος κώδικας μηχανής
δημιουργείται δυναμικά κάπου στο χώρο διευθύνσεων της
Java και ο έλεγχος κάποια στιγμή περνάει στο σημείο αυτό.
Αρχίζοντας την εξερεύνηση μας εκτελούμε την ltrace -i -o
fib.ltr java -server fib 10 (βλέπε προηγούμενα τεύχη).
Εξετάζοντας το fib.ltr τα αποτελέσματα δεν είναι
ιδιαίτερα ενθαρρυντικά, οπότε συνεχίζουμε με την strace
-i -o fib.str java -server fib 10. Προς το τέλος του
fib.str βρίσκουμε τα εξής:
[400379db] open("/home/alf/projects/magaz/issue3/src/fib.class", O_RDONLY|O_LARGEFILE) = 5
[401514e7] fstat64(5, {st_mode=S_IFREG|0644, st_size=561, ...}) = 0
[401512f7] stat64("/home/alf/projects/magaz/issue3/src/fib.class", ...
[40036eeb] read(5, "\312\376\272\276\0\0\0.\0$\n\0\7\0\22\n\0\23\0\24\t\0\25"..., 561) = 561
[40036f5f] close(5) = 0
[40118b71] gettimeofday({1081166745, 55282}, NULL) = 0
[40118b71] gettimeofday({1081166745, 55460}, NULL) = 0
[40118b71] gettimeofday({1081166745, 55594}, NULL) = 0
[40118b71] gettimeofday({1081166745, 56101}, NULL) = 0
[40118b71] gettimeofday({1081166745, 56241}, NULL) = 0
...
[401516d7] lstat64("/home", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf", {st_mode=S_IFDIR|0711, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects/magaz", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects/magaz/issue3", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[401516d7] lstat64("/home/alf/projects/magaz/issue3/src", {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
[40118b71] gettimeofday({1081166745, 82175}, NULL) = 0
[40118b71] gettimeofday({1081166745, 82915}, NULL) = 0
[40118b71] gettimeofday({1081166745, 83546}, NULL) = 0
[40118b71] gettimeofday({1081166745, 83719}, NULL) = 0
[40118b71] gettimeofday({1081166745, 83851}, NULL) = 0
...
[40159ac5] brk(0) = 0x80c4000
[40159ac5] brk(0x80c5000) = 0x80c5000
[40159ac5] brk(0) = 0x80c5000
[40159ac5] brk(0x80c6000) = 0x80c6000
[40036e5b] write(1, "89", 2) = 2
[40036e5b] write(1, "\n", 1) = 1
...
[400a8ac1] kill(789, SIGRTMIN) = 0
[400a8ac1] kill(789, SIGRTMIN) = 0
[40154c7d] unlink("/tmp/hsperfdata_alf/787") = 0
...
Παρατηρούμε πως η Java διαβάζει το .class αρχείο που
περιέχει τα bytecodes της εφαρμογής μας. Ύστερα αρχίζει
να διαβάζει συνεχώς την ώρα της ημέρας, μαθαίνει κάποια
πράγματα για το τρέχον directory, συνεχίζει να
δειγματοληπτεί την ώρα, αυξάνει το μέγεθος του data
segment κατά 0x2000 bytes και τελικά τυπώνει το
αποτέλεσμα (89). Ομολογουμένως οι πληροφορίες δεν είναι
ιδιαίτερα χρήσιμες.
Ένα ενδιαφέρον σημείο είναι το αρχείο
/tmp/hsperfdata_alf/787 το οποίο βλέπουμε να διαγράφεται.
Παραπάνω στο fib.str υπάρχει το σημείο που ανοίγει:
[400379b8] open("/tmp/hsperfdata_alf/787", O_RDWR|O_CREAT|O_TRUNC, 0600) = 3
[4015bd61] ftruncate(3, 16384) = 0
[4015d8ed] old_mmap(NULL, 16384, PROT_READ|PROT_WRITE, MAP_SHARED, 3, 0) = 0x4081e000
[40036f41] close(3) = 0
Το /tmp/hsperfdata_alf/787 αντιστοιχείται (mapped) στις
διευθύνσεις μνήμης 0x4081e000-0x40822000 και περαιτέρω
προσπελάσεις γίνονται μέσα από αυτές τις διευθύνσεις.
Μπορούμε να δούμε τα περιεχόμενα του αρχείου αν
φροντίσουμε ώστε να αργήσει να τελειώσει το πρόγραμμα μας
(πχ με java -server fib 100), για να μην προλάβει να
σβηστεί το προσωρινό αυτό αρχείο.
Μια σύντομη εξέταση του αρχείου μας δείχνει πως πρόκειται
για πληροφορίες που χρησιμοποιεί ο HotSpot(TM) JIT
μεταγλωττιστής της Sun. Έτσι εξηγείται και το
"hsperfdata_alf" που μάλλον σημαίνει HotSpot(TM)
Performance Data για τον χρήστη alf. Επίσης, το αρχείο
αρχίζει με τα bytes 0xCA 0xFE 0xC0 0xC0. Η αναζήτηση στο
internet για το νόημα των bytes ήταν άκαρπη, πάντως
υποψιάζομαι ότι είναι το signature των αρχείων δεδομένων
του JIT μεταγλωττιστή.
Αν και (ελπίζω) ενδιαφέρουσα, η ως τώρα περιήγηση στον
JIT μεταγλωττιστή δε μας οδήγησε πιο κοντά στη λύση.
Παραμένει το καίριο ερώτημα για τη θέση του native
κώδικα.
Ένας συλλογισμός που ίσως μας οδηγήσει στη λύση είναι ο
παρακάτω: Ο java διερμηνευτής αφού δημιουργήσει τον
native κώδικα περνάει τον έλεγχο σε αυτόν. Ο κώδικας μας
είναι αμιγώς cpu-intensive, δηλαδή χρησιμοποιεί πολύ τον
επεξεργαστή και δεν έχει I/O που μπορούν να διακόψουν τη
λειτουργία του. Αυτό σημαίνει πως αν σε μια τυχαία
χρονική στιγμή εξετάσουμε σε ποια διεύθυνση δείχνει ο
instruction pointer (IP) της διεργασίας, αυτή με πολύ
μεγάλη πιθανότητα θα βρίσκεται μέσα στις διευθύνσεις που
καταλαμβάνει ο native κώδικας.
Επομένως, το πρόβλημα μας μετασχηματίστηκε στην εύρεση
ενός τρόπου να παρακολουθούμε σε ποια διεύθυνση βρίσκεται
η εκτέλεση κάποια διεργασίας!
...Σαν να ψάχνεις διεύθυνση στα άχυρα
Μια πρώτη σκέψη είναι να εκτελέσουμε την java στο GDB, να
διακόπτουμε το πρόγραμμα κάθε λίγο και να καταγράφουμε
τις τιμές του IP. Απλό και αποτελεσματικό... μόνο που δε
φαίνεται να λειτουργεί στη δική μας περίπτωση :(
$ gdb -q java
(no debugging symbols found)...(gdb) r -server fib 10
Starting program: /usr/lib/j2sdk1.4.2_01/bin/java -server fib 10
(no debugging symbols found)...[New Thread 16384 (LWP 1536)]
(no debugging symbols found)...
(no debugging symbols found)...Cannot find user-level thread for LWP 1536: generic error
(gdb) info reg
No selected frame.
(gdb) q
The program is running. Exit anyway? (y or n) y
Cannot find thread 16384: generic error
(gdb) q
The program is running. Exit anyway? (y or n) y
Cannot find thread 16384: generic error
Όχι μόνο δεν καταφέραμε να τρέξουμε τη Java αλλά "τα
πήρε" και ο GDB. Αααργκ!!! Αν κάποιος ξέρει τι συμβαίνει
παρακαλώ να μου γράψει...
Μην απελπίζεστε! Ευτυχώς για εμάς, το πάντα χρήσιμο /proc
προσφέρει την υπηρεσία που χρειαζόμαστε (τον τρέχων IP
μιας διεργασίας). Η πληροφορία βρίσκεται καλά κρυμμένη
μέσα στο /proc/#/stat και θα χρησιμοποιήσουμε την εντολή
ps για να τη φέρουμε στην επιφάνεια. Συγκεκριμένα θα
χρησιμοποιήσουμε τη παράμετρο -ο για να ορίσουμε τις
πληροφορίες που θέλουμε να εμφανίζει η ps (βλέπε man
page).
Τώρα, λοιπόν, έχουμε όλα τα εργαλεία στα χέρια μας και
μπορούμε να αρχίσουμε δουλειά! Με τις παρακάτω εντολές
τρέχουμε τη java και κάθε 0.2 δευτερόλεπτα τυπώνουμε τον
IP της (30 δείγματα).
$ java -server fib 100 &
[1] 1390
$ for ((i=0;$i<30;i++)); do ps --pid=1390 -o eip; sleep 0.2; done
EIP
42900340
EIP
429003b8
EIP
4290033b
EIP
4290031c
EIP
4290030f
EIP
42900302
EIP
42900372
EIP
429002e0
EIP
429002e0
EIP
42900414
EIP
42900386
EIP
429003dc
EIP
429003d3
EIP
429002e0
EIP
4290044d
EIP
42900455
EIP
429003dc
EIP
429003b4
EIP
42900369
EIP
42900453
EIP
42900409
EIP
42900350
EIP
42900441
EIP
429003c4
EIP
429002e7
EIP
42900372
EIP
42900390
EIP
42900311
EIP
429003b4
EIP
429003b4
Παρατηρούμε πως ο κώδικας βρίσκεται σε ένα βρόχο με
μικρότερη διεύθυνση την 0x429002e0 και μέγιστη
0x42900453. Οι διευθύνσεις αυτές μπορεί να μην είναι τα
ακριβή άκρα του βρόχου, αφού έχουμε κάνει τυχαία
δειγματοληψία, αλλά με μεγάλη πιθανότητα είναι κάπου εκεί
κοντά.
Το μόνο που μένει τώρα είναι να διαβάσουμε τον κώδικα που
βρίσκεται σε αυτές τις θέσεις μνήμης. Για το σκοπό αυτό
θα χρησιμοποιήσουμε και πάλι το /proc και συγκεκριμένα το
"αρχείο" /proc/#/mem. Η πρόσβαση στο αρχείο γίνεται με
τις γνωστές εντολές (open/fopen, lseek/fseek, read/fread)
αλλά υπάρχουν δύο σημεία που πρέπει να προσεχθούν.
Καταρχάς, για να μας επιτραπεί να διαβάσουμε από το mem
αρχείο θα πρέπει η δική μας διεργασία να έχει "δεθεί" με
τη διεργασία της οποίας τη μνήμη σκοπεύουμε να
προσπελάσουμε. Αυτό το "δέσιμο" γίνεται μέσω της ptrace,
η οποία μας δίνει το δικαίωμα να παρακολουθούμε τη
διεργασία. Ένα δεύτερο σημείο προσοχής είναι ότι θα
πρέπει η διεργασία που μας ενδιαφέρει να μην είναι σε
κατάσταση εκτέλεσης. Αυτό επιτυγχάνεται στέλνοντάς της το
σήμα SIGSTOP.
$ kill -SIGSTOP 1390
$ memread 1390 0x429002e0 0x200 < fib.bin
Reading from Process: 1390 Address: 0x429002e0 Size: 512
Successfully read 512 bytes!
Ο αριθμός των 512 bytes επιλέχθηκε αυθαίρετα, με μόνη
προϋπόθεση να είναι μεγαλύτερος από τα όρια του βρόχου
που βρήκαμε προηγουμένως.
Ο κώδικας του memread: memread.c.gz.
Τώρα που επιτέλους έχουμε στα χέρια μας τον native κώδικα
μπορούμε να αρχίσουμε την ανάλυση. Τι μυστικά κρύβει,
άραγε, αυτό το μικρό αρχείο των 512 bytes;
Φορτώνουμε το αρχείο στον ht με ht fib.bin και επιλέγουμε
disasm/x86 mode (πατώντας space ή F6). Παρακάτω φαίνεται
ο κώδικας με κάποια σχόλια:
00000000 89842400d0ffff mov [esp-00003000], eax
00000007 81ec24000000 sub esp, 0x24
0000000d 83f902 cmp ecx, 0x2 ;; ecx=n
00000010 0f8c5d010000 jl 0x173 ;; n < 2 ?
00000016 89742414 mov [esp+0x14], esi
0000001a 896c2418 mov [esp+0x18], ebp
0000001e 897c241c mov [esp+0x1c], edi
00000022 8be9 mov ebp, ecx
00000024 4d dec ebp ;; ebp=n-1
00000025 8bd9 mov ebx, ecx
00000027 83c3fb add ebx, fffffffb ;; ebx=n-5
0000002a 8bf1 mov esi, ecx
0000002c 83c6fe add esi, fffffffe ;; esi=n-2
0000002f 8bc1 mov eax, ecx
00000031 83c0fc add eax, fffffffc ;; eax=n-4
00000034 8bd1 mov edx, ecx
00000036 83c2fd add edx, fffffffd ;; edx=n-3
00000039 83fd02 cmp ebp, 0x2
0000003c 0f8c96000000 jl 0xd8 ;; n-1 < 2 => n < 3 ?
00000042 83fe02 cmp esi, 0x2
00000045 7c40 jl 0x87 ;; n-2 < 2 => n < 4 ?
00000047 8954240c mov [esp+0xc], edx ;;
0000004b 89442408 mov [esp+0x8], eax ;; Save registers (1)
0000004f 895c2404 mov [esp+0x4], ebx ;;
00000053 890c24 mov [esp], ecx ;;
00000056 8bca mov ecx, edx
00000058 90 nop
00000059 90 nop
0000005a 90 nop
0000005b e8a0ffffff call 0x0 ;; call fib(n-3)
00000060 89442410 mov [esp+0x10], eax
00000064 8b4c2408 mov ecx, [esp+0x8]
00000068 90 nop
00000069 90 nop
0000006a 90 nop
0000006b e890ffffff call 0x0 ;; call fib(n-4)
00000070 8bf8 mov edi, eax
00000072 037c2410 add edi, [esp+0x10] ;; edi = fib(n-3)+fib(n-4)
00000076 8b0c24 mov ecx, [esp] ;;
00000079 8b5c2404 mov ebx, [esp+0x4] ;; Restore registers (1)
0000007d 8b442408 mov eax, [esp+0x8] ;;
00000081 8b54240c mov edx, [esp+0xc] ;;
00000085 eb02 jmp 0x89
00000087 8bfe mov edi, esi ;; edi = n-2
00000089 83fa02 cmp edx, 0x2
0000008c 7c26 jl 0xb4 ;; n-3 < 2 => n < 5 ?
0000008e 8954240c mov [esp+0xc], edx ;;
00000092 89442408 mov [esp+0x8], eax ;; Save registers (2)
00000096 895c2404 mov [esp+0x4], ebx ;;
0000009a 890c24 mov [esp], ecx ;;
0000009d 8bc8 mov ecx, eax
0000009f e85cffffff call 0x0 ;; call fib(n-4)
000000a4 8be8 mov ebp, eax
000000a6 8b4c2404 mov ecx, [esp+0x4]
000000aa 90 nop
000000ab e850ffffff call 0x0 ;; call fib(n-5)
000000b0 03c5 add eax, ebp ;; eax = fib(n-4) + fib(n-5)
000000b2 eb11 jmp 0xc5
000000b4 8954240c mov [esp+0xc], edx ;;
000000b8 89442408 mov [esp+0x8], eax ;; Save registers (3)
000000bc 895c2404 mov [esp+0x4], ebx ;;
000000c0 890c24 mov [esp], ecx ;;
000000c3 8bc2 mov eax, edx
000000c5 8be8 mov ebp, eax
000000c7 03ef add ebp, edi
000000c9 8b0c24 mov ecx, [esp] ;;
000000cc 8b5c2404 mov ebx, [esp+0x4] ;; Restore registers (2,3)
000000d0 8b442408 mov eax, [esp+0x8] ;;
000000d4 8b54240c mov edx, [esp+0xc] ;;
000000d8 83fe02 cmp esi, 0x2
000000db 0f8c80000000 jl 0x161 ;; n-2 < 2 => n < 4
000000e1 83fa02 cmp edx, 0x2
000000e4 7c39 jl 0x11f ;; n-3 < 2 => n < 5
000000e6 8bfa mov edi, edx
000000e8 89442408 mov [esp+0x8], eax ;;
000000ec 895c2404 mov [esp+0x4], ebx ;; Save registers (4)
000000f0 890c24 mov [esp], ecx ;;
000000f3 8bc8 mov ecx, eax
000000f5 90 nop
000000f6 90 nop
000000f7 e804ffffff call 0x0 ;; call fib(n-4)
000000fc 8944240c mov [esp+0xc], eax
00000100 8b4c2404 mov ecx, [esp+0x4]
00000104 90 nop
00000105 90 nop
00000106 90 nop
00000107 e8f4feffff call 0x0 ;; call fib(n-5)
0000010c 8bf8 mov edi, eax
0000010e 037c240c add edi, [esp+0xc] ;; edi = fib(n-4) + fib(n-5)
00000112 8b0c24 mov ecx, [esp] ;;
00000115 8b5c2404 mov ebx, [esp+0x4] ;; Restore registers (4)
00000119 8b442408 mov eax, [esp+0x8] ;;
0000011d eb02 jmp 0x121
0000011f 8bfa mov edi, edx
00000121 83f802 cmp eax, 0x2
00000124 7c37 jl 0x15d ;; n-4 < 2 => n < 6
00000126 890424 mov [esp], eax
00000129 8bf1 mov esi, ecx
0000012b 8bcb mov ecx, ebx
0000012d 90 nop
0000012e 90 nop
0000012f e8ccfeffff call 0x0 ;; call fib(n-5)
00000134 890424 mov [esp], eax
00000137 8bce mov ecx, esi
00000139 83c1fa add ecx, fffffffa ;; n' = n - 6
0000013c 90 nop
0000013d 90 nop
0000013e 90 nop
0000013f e8bcfeffff call 0x0 ;; call fib(n-6)
00000144 030424 add eax, [esp] ;; eax = fib(n-5) + fib(n-6)
00000147 eb14 jmp 0x15d
00000149 8b6c2418 mov ebp, [esp+0x18]
0000014d 8b7c241c mov edi, [esp+0x1c]
00000151 8b742414 mov esi, [esp+0x14]
00000155 83c424 add esp, 0x24
00000158 e9a377ffff jmp ffff7900
0000015d 03c7 add eax, edi
0000015f eb02 jmp 0x163
00000161 8bc6 mov eax, esi
00000163 03c5 add eax, ebp
00000165 8b6c2418 mov ebp, [esp+0x18]
00000169 8b7c241c mov edi, [esp+0x1c]
0000016d 8b742414 mov esi, [esp+0x14]
00000171 eb02 jmp 0x175
00000173 8bc1 mov eax, ecx
00000175 83c424 add esp, 0x24
00000178 c3 ret
00000179 90 nop ;; Από εδώ και κάτω είναι άχρηστος (για τους σκοπούς μας) κώδικας
0000017a 90 nop
0000017b 8bc8 mov ecx, eax
0000017d ebca jmp 0x149
0000017f 8bc8 mov ecx, eax
00000181 ebc6 jmp 0x149
00000183 8bc8 mov ecx, eax
00000185 ebc2 jmp 0x149
00000187 8bc8 mov ecx, eax
00000189 ebbe jmp 0x149
0000018b 8bc8 mov ecx, eax
0000018d ebba jmp 0x149
0000018f 8bc8 mov ecx, eax
00000191 ebb6 jmp 0x149
00000193 8bc8 mov ecx, eax
00000195 ebb2 jmp 0x149
00000197 8bc8 mov ecx, eax
00000199 ebae jmp 0x149
Το παραπάνω listing αν και μεγάλο σε μήκος είναι στην
ουσία αρκετά απλό. Οι βασικοί λόγοι για τους οποίους
φαίνεται μπερδεμένο είναι οι συνεχείς μετακινήσεις προς
και από το σωρό και οι επαναχρησιμοποίηση των καταχωρητών
για εντελώς διαφορετικό σκοπό (πχ ο ebp αρχικά εκφράζει
το n-1 ενώ αργότερα, από τη διεύθυνση 0xc7 και πέρα
περιέχει κάποιο άλλο άθροισμα).
Το πρώτο βήμα για την ανάλυση
κώδικα σε assembly είναι συνήθως η επισύναψη σχολίων πάνω
στον κώδικα όπως παραπάνω. Ένας καλός τρόπος για να
συνεχίσουμε είναι η σταδιακή μετατροπή του κώδικα σε
κάποια πιο υψηλή και γνώριμη μορφή, αγνοώντας περιττές
λεπτομέρειες. Για παράδειγμα, το κομμάτι ανάμεσα στις
διευθύνσεις 0x39 και 0x87 θα μπορούσε ως επόμενο βήμα να
γραφτεί:
if (n-1 < 2) goto 0xd8
if (n-4 < 2) goto 0x87
edi = fib(n-3) + fib(n-4)
goto 89
87: edi = n-2
89:
και ύστερα, αναγνωρίζοντας τη δομή if-else που υπάρχει:
if (n-1 < 2) goto 0xd8
if (n-4 >= 2)
edi = fib(n-3) + fib(n-4);
else
edi = n-2;
89:
Ακολουθώντας μια τέτοια διαδικασία τελικά καταλήγουμε στον παρακάτω Java/C κώδικα
που εκφράζει πιο ξεκάθαρα την λειτουργία του assembly κώδικα:
int fib_jit(int n)
{
int C,D;
if (n < 2)
return n;
if (n >= 3) {
int A,B;
if (n >= 4)
A=fib_jit(n-3)+fib_jit(n-4);
else
A=n-2;
if (n >= 5)
B=fib_jit(n-4)+fib_jit(n-5);
else
B=n-3;
C=A+B;
}
else
C=n-1;
if (n >= 4) {
int A,B;
if (n >= 5)
A=fib_jit(n-4)+fib_jit(n-5);
else
A=n-3;
if (n >= 6)
B=fib_jit(n-5)+fib_jit(n-6);
else
B=n-4;
D=A+B;
}
else
D=n-2;
return D+C;
}
Βέβαια, ακόμη και με την παραπάνω μορφή το τι ακριβώς
συμβαίνει και γιατί λειτουργεί το κατασκεύασμα του JIT
μεταγλωττιστή παραμένει κάπως μυστήριο. Για να
ανακαλύψουμε όλη την αλήθεια θα πρέπει να θυμηθούμε την
αρχική συνάρτηση fib. Αυτή μπορεί να ξαναγραφτεί ως:
public static int fib(int n) {
int R;
if (n >= 2)
R=fib(n-1) + fib(n-2);
else
R=n;
return R;
}
Σας θυμίζει τίποτα; Η δομή if-else που υπάρχει στη αρχική
fib φαίνεται να μοιάζει πολύ με τις if-else που υπάρχουν
διάσπαρτες στην fib_jit. Για την ακρίβεια, οι δομές που
υπάρχουν στην fib_jit είναι η fib() για διάφορες
παραστάσεις του n!!!
Για να γίνει πιο κατανοητό το παραπάνω θεωρήστε το:
if (n >= 4)
A = fib_jit(n-3)+fib_jit(n-4);
else
A = n-2;
το οποίο πρακτικά είναι το:
Α=fib(n-2);
Κάνοντας τις παραπάνω αντικαταστάσεις και κάποιες
απλοποιήσεις προκύπτει η εξής fib_jit1:
int fib_jit1(int n)
{
int C,D;
if (n < 2)
return n;
if (n >= 3)
C = fib(n-2) + fib(n-3);
else
C = n-1;
if (n >= 4)
D = fib(n-3) + fib(n-4);
else
D = n-2;
return D+C;
}
Χμμ, εμφανίστηκαν πάλι οι γνωστές δομές if-else. Είναι
σαν τον κώδικα της μαρμότας... ξαναζείς τον ίδιο κάθε
φορά :) Αν αντικαταστήσουμε και αυτές τις δομές με την
αντίστοιχη fib προκύπτει:
int fib_jit2(int n)
{
if (n < 2)
return n;
return fib(n-1) + fib(n-2);
}
H παραπάνω συνάρτηση δεν είναι άλλη από τη αυθεντική fib!
Επομένως φτάσαμε στο συμπέρασμα πως fib=fib_jit και άρα
όντως η fib_jit λειτουργεί σωστά, αφού στην ουσία είναι η
ίδια η fib σε άλλη μορφή.
Τώρα πιστεύω πως είναι σαφές τι "μαγικά" έκανε ο JIT
μεταγλωττιστής της Java. Ουσιαστικά έκανε inlining των
αναδρομικών κλήσεων της fib σε δύο επίπεδα βάθους! Αυτό
είχε ως αποτέλεσμα να αποφευχθεί ένα μέρος του κόστους
των κλήσεων συναρτήσεων και επομένως να αυξηθεί η
ταχύτητα εκτέλεσης.
Τελικά είναι η Java πιο γρήγορη από τη C; Θέλω να ελπίζω
πως θα συμφωνήσετε μαζί στο ότι αυτή είναι η λάθος
ερώτηση! Αυτό που πρέπει να ρωτήσουμε είναι αν ο JIT
μεταγλωττιστής παράγει πιο γρήγορο κώδικα από τον gcc. Η
απάντηση είναι πως ειδικά σε αυτή τη περίπτωση ναι και σε
γενικές γραμμές παράγει εξίσου καλό κώδικα.
Αν συνεχίσουμε το πείραμα και μεταγλωττίσουμε τη
συνάρτηση fib_jit() (σε C) με τον gcc, το τελικό
εκτελέσιμο θα έχει ελαφρώς καλύτερη απόδοση από αυτό της
Java. Το θέμα εδώ είναι ότι ο JIT μας απαλλάσσει από αυτή
τη διαδικασία. Βέβαια, για να υπερασπιστούμε λίγο και τον
gcc, o JIT μεταγλωττιστής έχει το πλεονέκτημα πως έχει
πρόσβαση και στις πληροφορίες δυναμικής εκτέλεσης του
προγράμματος ενώ ο gcc μπορεί μόνο στατικά να ελέγξει τον
κώδικα.
Ηθικό δίδαγμα: οι γλώσσες δε μπορούν να συγκριθούν με
κριτήριο την ταχύτητα, μόνο οι μεταγλωττιστές τους
μπορούν.
Επόμενο Προηγούμενο Περιεχόμενα
