Απόδοση και μεταφερσιμότητα

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Απόδοση

Η απόδοση του λογισμικού μπορεί να εξεταστεί ως προς:

Την ταχύτητα εκτέλεσης του προγράμματος ή συγκεκριμένων λειτουργιών του.
Τη χρήση μνήμης του προγράμματος.

Και οι δύο παράγοντες εξαρτώνται από:

την αποδοτικότητα των αλγορίθμων (κύρια)
τον τρόπο υλοποίησης (γλώσσα και τεχνικές προγραμματισμού)

Επιπλέον υπάρχουν και άλλοι παράγοντες απόδοσης όπως:

Ο όγκος δεδομένων κατά τη μεταφορά τους
Η κατανάλωση ενέργειας
Η μεταβλητότητα (variability) χαρακτηριστικών της απόδοσης.

Πότε βελτιστοποιούμε

Βελτίωση της ταχύτητας ενός προγράμματος έχει αξία μόνο αν:

Το πρόγραμμα είναι πραγματικά αργό
Το ταχύτερο πρόγραμμα θα συνεχίσει να έχει σωστά αποτελέσματα (αντιπαράδειγμα, αλλαγή αριθμών κινητής υποδιαστολής με ακέραιους σε MP3 player)
Το ταχύτερο πρόγραμμα είναι ευανάγνωστο
Το ταχύτερο πρόγραμμα είναι στιβαρό (αντιπαράδειγμα έλεγχοι ορίων πινάκων στη C και στη Java)

Επίσης, υπάρχουν κατηγορίες προγραμμάτων στις οποίες συχνά δε μας ενδιαφέρει η ταχύτητα:

Ασκήσεις στο πανεπιστήμιο
Προσωπικά προγράμματα
Εργαλεία που δε χρησιμοποιούνται συχνά
Προγράμματα ελέγχου
Δοκιμαστικά προγράμματα
Αρχέτυπα

Χρήση επεξεργαστή κατά τη διόρθωση ενός προγράμματος

Χρήση επεξεργαστή κατά την αποκωδικοποίηση MP3

Χρήση επεξεργαστή κατά τον ορθογραφικό έλεγχο

Τα πρώτα δύο προγράμματα πιθανότατα δε θα κερδίσουν από βελτιστοποίηση.

Τρόποι βελτιστοποίησης

Βελτιστοποίηση ενός προγράμματος επιτυγχάνουμε με γενικές τεχνικές καθώς και με τεχνικές σχετικές με το πεδίο εφαρμογής του.

Γενικές τεχνικές είναι οι παρακάτω:

Χρήση αποδοτικότερων αλγορίθμων και δομών δεδομένων
Ανάλυση κατανομής χρόνου του προγράμματος και βελτιστοποίηση συγκεκριμένων τμημάτων
Υλοποίηση σε αποδοτικότερο περιβάλλον (π.χ. από 4GL σε C++)
Ενεργοποίηση βελτιστοποιήσεων του μεταγλωττιστή
Βελτιστοποίηση του κώδικα
(Μη επέμβαση όταν δεν είναι απαραίτητο)

Τεχνικές σχετικές με το πεδίο εφαρμογής εφαρμόζονται σε τομείς όπως:

Ενσωματωμένες συσκευές
Μεταφορά δεδομένων
Σχεσιακές βάσεις δεδομένων
Γραφικά

Ανάλυση κατανομής χρόνου

Βασικό στοιχείο για τη βελτίωση της απόδοσης είναι η μέτρηση του προγράμματος. Μπορούμε να μετρήσουμε:

Το χρόνο που κάνει το πρόγραμμα για να εκτελεστεί και την κατανομή του ανάμεσα στον κώδικα της εφαρμογής και το λειτουργικό σύστημα. Π.χ.
```
$ time fmt /usr/share/dict/words  >/dev/null

real    0m3.238s
user    0m2.527s
sys     0m0.294s
```
Την κατανάλωση πόρων του συστήματος
Το χρόνο εκτέλεσης συγκεκριμένων συναρτήσεων του προγράμματος μέσα στο πρόγραμμα (π.χ. με τη χρήση της System.currentTimeMillis() στη Java ή της time() στη C).

To χρόνο εκτέλεσης των συναρτήσεων του προγράμματος με τη χρήση ενός εργαλείου ελέγχου κατανομής χρόνου (profiler). Το παρακάτω απόσπασμα παριστάνει την κατανομή χρόνου στο πρόγραμμα συμπίεσης MP3 bladeenc:

                                  called/total       parents
index  %time    self descendents  called+self    name           index
                                  called/total       children

                                                     <spontaneous>
[1]    100.0    0.00       41.07                 main [1]
                0.03       40.93     211/211         codecEncodeChunk [2]
                0.00        0.06     106/106         updateProgressIndicator [34]
                0.00        0.02       1/1           codecInit [48]
                0.00        0.01     212/212         readSamples [61]
                0.00        0.01     212/212         fwrite [70]
                0.00        0.01      15/121         fprintf [39]
                0.00        0.00       1/1           addCommandlineJob [77]
                0.00        0.00       1/1           findConfigFile [79]
                0.00        0.00       1/3           fopen [66]
                0.00        0.00     211/211         be_kbhit [84]
                0.00        0.00       2/2           timerStart [95]
                0.00        0.00       2/2           timerStop [96]
                0.00        0.00       1/2           fclose [97]
                0.00        0.00       1/1           codecExit [101]
[...]

Τις φορές εκτέλεσης συγκεκριμένων εντολών. Παράδειγμα από πρόγραμμα μέτρησης γραμμάτων, λέξεων, γραμμών:

       1 -> gotsp = 1;                                 
   1,3,1 -> while ((len = read(fd, buf, MAXBSIZE)) > 0) {
       2 ->         charct += len;
2,6151,2 ->         for (C = buf; len--; ++C) {              
    6149 ->                 if (isspace(*C)) {
    1487 ->                         gotsp = 1;
    1487 ->                         if (*C == '\n') {
     269 ->                                 ++linect;
                                    }
    1487 ->                 } else {
    4662 ->                         if (gotsp) {
     968 ->                                 gotsp = 0;
     968 ->                                 ++wordct;
                                    }
                            }
                    }
       2 -> }
       1 -> if (len == -1) {
   ##### ->         warn("%s", file);
   ##### ->         rval = 1;

Αποδοτικότητα των αλγορίθμων

Η απόδοση ενός προγράμματος εξαρτάται κύρια από τους αλγορίθμους και τις δομές δεδομένων που χρησιμοποιεί.
Πολλές φορές μπορούμε να βελτιώσουμε την απόδοση ενός αλγορίθμου αλλάζοντας εντολές.
- Παράδειγμα 1:
  // Return the position of X in the first N elements of A; -1 if not found
  for (i = 0; i < N; i++)
  if (A[i] == X)
  return i;
  return -1;
- Παράδειγμα 2:
  A[N] = X;
  for (i = 0; A[i] != X; i++)
          ;
  if (i == N)
          return -1;
  else
          return i;
- Παρατηρήστε τη διαφορά εντολών από το πρώτο στο δεύτερο παράδειγμα.
- Μπορεί να υπάρχει αποδοτικότερος αλγόριθμος;
Για μεγάλο όγκο δεδομένων οι παραπάνω διαφορές είναι ασήμαντες.
Για να μετρήσουμε την απόδοση χρησιμοποιούμε τη σημειογραφία Ο().
Αυτή δείχνει την τάξη του χρόνου ή της μνήμης που απαιτεί ένας αλγόριθμος χωρίς να λαμβάνονται υπόψη σταθεροί (ανεξάρτητοι του ν) παράγοντες.
Παραδείγματα:
- Γραμμική ανίχνευση Ο(ν)
- Δυαδική ανίχνευση Ο(log ν)
- Διπλός βρόχος Ο(ν²)
Όταν δύο Ο() διαφέρουν μεταξύ τους θα υπάρχει πάντα κάποιος όγκος δεδομένων για τον οποίο η διαφορά θα είναι αντιληπτή και στην πράξη.
Η σημειογραφία χρησιμοποιείται για να εξετάσουμε τόσο το χρόνο, όσο και το χώρο που απαιτεί ένας αλγόριθμος.

Παράδειγμα

(Από συνέντευξη πρόσληψης στη Microsoft). Εύρεση αν υπάρχει βρόχος σε μια συνδεδεμένη λίστα (π.χ. αν έχουμε ξαναπεράσει από τον ίδιο υπάλληλο σε συναλλαγή με το δημόσιο):

Πρώτη λύση
for (i = L.begin(); i != L.end(); i++) {
        for (j = L2.begin(); j != L2.end(); j++)
                if (*j == i)
                        return true;
        L2.push_back(i);
}
return false;

Ο(ν²) χρόνος, Ο(ν) χώρος
Δεύτερη λύση
for (i = L.begin(), ci = 0; i != L.end(); i++, ci++)
        for (j = L.begin(), cj= 0; j < i; j++, cj++) {
                for (k = j + 1, ck = 0; ck < ci - cj; k++, ck++)
                        if (k == j)
                                return true;
return false;

Ο(ν³) χρόνος, Ο(1) χώρος
Τρίτη λύση
for (i = L.begin(), j = L.begin(); j != L.end(); i++, j++, j++)
if (j == i)
return true;
return false;

Ο(ν) χρόνος, Ο(1) χώρος

Τεχνικές βελτιστοποίησης του κώδικα

Αποδοτική χρήση του υλικού
- ειδικές εντολές επεξεργαστή
- συνεπεξεργαστές,
- πολλαπλοί επεξεργαστές
- σωλήνωση εντολών (instruction pipelining)
Αποφυγή κλήσης του λειτουργικού συστήματος
Οικονομία στη χρήση εξωτερικών δεδομένων (ειδικά αν το πρόγραμμα δεσμεύεται από το χρόνο εκτέλεσής τους)
Αντικατάσταση ακριβών εντολών με φθηνές
Ξετύλιγμα των βρόχων
Φύλαξη ενδιάμεσων τιμών
Ενταμίευση εισόδου και εξόδου (input / output buffering)
Ειδικός κώδικας για τις ειδικές περιπτώσεις (έτσι ώστε οι γενικές να είναι γρήγορες). (παράδειγμα: βρόχοι σε συστήματα γραφικών).
Προ-υπολογισμός αποτελεσμάτων
Χρήση χαμηλότερης ακρίβειας στους υπολογισμούς
Υλοποίηση σε γλώσσα χαμηλότερου επιπέδου (π.χ. PHP -> Java -> C -> Assembly)

Χρήση μνήμης

Η μνήμη που χρησιμοποιεί ένα πρόγραμμα χωρίζεται στις παρακάτω κατηγορίες:

Κώδικας (code): Οι εντολές του προγράμματος, τυπικά σταθερές κατά την εκτέλεσή του.
Δεδομένα (data): Τα δεδομένα που έχουν οριστεί στατικά μέσα στο πρόγραμμα (π.χ. αρχικές τιμές) καθώς και η δυναμική μνήμη που απαιτείται κατά τη λειτουργία του (εντολή new στη Java / C++, malloc στη C). Σε πολλά προγράμματα αυτή είναι η κατηγορία της μνήμης που μας ενδιαφέρει να βελτιστοποιήσουμε.
Στοίβα (stack): Τοπικές μεταβλητές, κλήση συναρτήσεων ιδίως σε αναδρομικές συναρτήσεις.

Παράδειγμα χρήσης μνήμης προγράμματος (g++):

      1906  average shared memory size (κώδικας)
      9232  average unshared data size (δεδομένα)
       195  average unshared stack size (στοίβα)

Όταν ο όγκος της κύριας μνήμης του υπολογιστή δεν επαρκεί μπορεί να χρησιμοποιηθεί:

ιδεατή μνήμη στο δίσκο (virtual memory)
εξωτερικό αρχείο υπό τον έλεγχο του προγράμματος
βάση δεδομένων

Τέλος, για οικονομία στο χώρο που απαιτεί ο κώδικας των προγραμμάτων στο δίσκο, χρησιμοποιούνται συχνά μοιρασμένες βιβλιοθήκες (shared libraries) (π.χ. .DLL, .so).

Μεταφορά δεδομένων

Η μεταφορά μεγάλου όγκου δεδομένων συχνά απαιτεί σεβαστό χρόνο, ειδικά αν γίνεται από μέσα με χαμηλό εύρος ζώνης (bandwidth). Βελτίωση του χρόνου μπορούμε να έχουμε με:

Συμπίεση των δεδομένων:
- χωρίς απώλειες (lossless) (π.χ. αλγόριθμοι Lempel-Ziv, Huffman, Burrows-Wheeler)
- με απώλειες (lossy) (π.χ. συμπίεση JPEG, MP3, MPEG)
Κατανεμημένα αντίγραφα των δεδομένων
Φύλαξη αντιγράφου των δεδομένων σε κρυφή μνήμη (cache memory).

Ενσωματωμένες συσκευές

Σε ενσωματωμένες συσκευές (κινητά τηλέφωνα, συσκευές αναπαραγωγής MP3, ηλεκτρονικά σημειωματάρια κ.λπ.) οι παράγοντες που έχουν σημασία για την απόδοση είναι συχνά διαφορετικοί. Μπορεί να πρέπει να λάβουμε υπόψη μας:

Κατανάλωση ενέργειας με
- χρήση αποδοτικών αλγορίθμων
- περιορισμένη χρήση περιφερειακών
- χρήση πόρων κατά μικρά διαστήματα
Μέγεθος κώδικα (συχνά με χρήση συμπίεσης)
Χρήση της μη ασταθούς μνήμης (non volatile memory) (συχνά είναι αργή και περιορισμένης χωρητικότητας)

Τεχνικές ΣΒΔ

Σε συστήματα που βασίζονται σε σχεσιακές βάσεις δεδομένων χρησιμοποιούμε συχνά τις παρακάτω τεχνικές για αύξηση της απόδοσης:

Ορισμός δεικτών (indexes) στα κατάλληλα πεδία.
Μη ορισμός δεικτών σε πεδία που δεν το απαιτούν.
Βελτιστοποίηση της δομής των πινάκων
Ελαχιστοποίηση των δεδομένων που μεταφέρονται από τον εξυπηρετητή στον πελάτη.
Χρήση εντολών της SQL αντί για βρόχους κώδικα. Για παράδειγμα, αντικατάσταση του κώδικα
        Do While Not tblPersons.EOF
            If tblPersons("Name") = looking Then
                MsgBox "Your number is " & tblPersons("Number")
            End If
            tblPersons.MoveNext
        Loop

με τον κώδικα
        Set qryPersons = dbsDb.OpenQuery("SELECT Number from Persons Where Name ='" & looking & "'")
        Set rstPersons = qryPersons.OpenRecordset
        If Not rstTables.EOF
            MsgBox "Your number is " & rstPersons("Number")
        End If
Χρήση πινάκων με ενδιάμεσα αποτελέσματα και αυτόματη ενημέρωσή τους σε νεκρούς χρόνους (π.χ. βράδυ), για στοιχεία που δεν απαιτούν απόλυτη ακρίβεια, ή με trigger procedures.
Χρήση εργαλείων βελτιστοποίησης της βάσης του κατασκευαστή.

Μεταφερσιμότητα

Η μεταφερσιμότητα ενός προγράμματος εμποδίζεται από:

Διαφορετικούς επεξεργαστές (όταν είναι σε εκτελέσιμη μορφή)
Διαφορετικά λειτουργικά συστήματα (όταν είναι σε εκτελέσιμη μορφή)
Τα παραπάνω και διαφορετικούς μεταγλωττιστές και βιβλιοθήκες (όταν είναι σε πηγαίο κώδικα)

Ο προγραμματισμός σύμφωνα με τις παρακάτω αρχές αυξάνει τη μεταφερσιμότητα του προγράμματος:

Να χρησιμοποιούνται μόνο στοιχεία που περιέχονται στον πρότυπο ορισμό της γλώσσας και όχι επεκτάσεις (π.χ. πίνακες με μεταβλητό μήκος στη GNU C).
Να αποφεύγεται η χρήση "εξωτικών" στοιχείων της γλώσσας προγραμματισμού (π.χ. ο τύπος complex στη C, member templates στη C++, εσωτερικές κλάσεις στη Java) αν δεν είναι απολύτως απαραίτητο.
Να μη βασίζεται ο κώδικας σε ιδιότητες της γλώσσας που δεν ορίζονται με συνέπεια (π.χ. το πρόσημο των χαρακτήρων στη C/C++).
Να μη βασίζεστε στη σειρά εκτέλεσης των πράξεων (π.χ. printf("%d, %d", x++, x++) τυπώνει 0, 0 με το μεταγλωττιστή Microsoft C και 0, 1 με το μεταγλωττιστή GNU C).
Να μη βασίζεστε στο μέγεθος των αριθμητικών τύπων. Αν και αυτό ορίζεται αυστηρά στη Java, σε άλλες γλώσσες αλλάζει συχνά ανάλογα με το μεταγλωττιστή και τον επεξεργαστή (π.χ. το μέγεθος του τύπου char * μπορεί να είναι 16, 32, ή 64 bit στη C++).
Να μη βασίζεται ο κώδικας στη σειρά φύλαξης των byte κάθε τύπου στη μνήμη, ούτε στη σειρά φύλαξης των μελών των κλάσεων και των δομών.
Να χρησιμοποιείτε μόνο τις πρότυπες βιβλιοθήκες ή μεταφέρσιμες βιβλιοθήκες λογισμικού ανοιχτού κώδικα (open source software).
Αρχεία που μεταφέρονται ανάμεσα σε υπολογιστές να περιέχουν απλό κείμενο.

Απομόνωση

Μερικές φορές θα πρέπει να χρησιμοποιήσετε μη μεταφέρσιμα στοιχεία. Τότε προσπαθήστε:

Να απομονώσετε τα μη μεταφέρσιμα στοιχεία σε ξεχωριστά αρχεία.
Να υλοποιήσετε ένα ενδιάμεσο στρώμα συμβατότητας.
Να χρησιμοποιήσετε απλές διεπαφές για να κρύψετε τα στοιχεία αυτά.

Τεχνικές μεταφερσιμότητας εφαρμογής με γραφική διεπαφή

Διεθνοποίηση και τοπική προσαρμογή

Διεθνοποίηση (internationalisation) είναι η διεργασία γενίκευσης που επιτρέπει στο λογισμικό να μπορεί εύκολα να προσαρμοστεί σε διάφορες περιοχές.
Τοπική προσαρμογή (localisation) είναι η διεργασία συγκεκριμενοποίησης που προσαρμόζει το λογισμικό για μια συγκεκριμένη περιοχή.

Στοιχεία που αφορούν τις παραπάνω ενέργειες είναι:

Εισαγωγή τοπικού κειμένου
Επεξεργασία τοπικού κειμένου (π.χ. ταξινόμηση)
Εξαγωγή τοπικού κειμένου (εμφάνιση στην οθόνη, εκτύπωση)
Προσαρμογή στον τοπικό τρόπο χρήσης
- αριθμών
- ημερομηνίας
- ώρας
- νομισμάτων
Εμφάνιση μηνυμάτων στην τοπική γλώσσα
Είσοδος εντολών στην τοπική γλώσσα

Στο παρακάτω παράδειγμα φαίνεται η αυτόματη εμφάνιση της ημερομηνίας και ώρας σε διαφορετικές γλώσσες:

en_US: Sun 05 May 2002 03:19:46 AM EEST
de_DE: Son Mai 5 03:19:46 EEST 2002
it_IT: dom 05 mag 2002 03:19:46 EEST
af_ZA: So 05 Mei 2002 03:19:46 EEST

Βιβλιογραφία

Jon Louis Bentley. Writing Efficient Programs. Prentice-Hall, 1982.
Andrew Deitsch, David Czarnecki, and Andy Deitsch. Java Internationalization. O'Reilly and Associates, Sebastopol, CA, USA, 2001.
A. Dolenc, A. Lemmke, D. Keppel, and G. V. Reilly. Notes on writing portable programs in C. Available by anonymous ftp from sauna.hut.fi:pub/CompSciLab/doc, November 1990.
David Harel. Algorithmics: the Spirit of Computing, pages 119–147. Addison-Wesley, 1987.
Nadine Kano. Developing International Software for Windows 95 Windows NT. Microsoft Press, 1995.
Brian W. Kernighan and Rob Pike. The Practice of Programming, pages 165–212. Addison-Wesley, 1999.
Sandra Martin O'Donnell. Programming for the World: How to Modify Software to Meet the Needs of the Global Market. Prentice Hall, 1994.
Roger S. Pressman. Software Engineering: A Practitioner's Approach, pages 426–428. McGraw-Hill, 1987.
Roger S. Pressman. Software Engineering: A Practitioner's Approach, pages 494–500. McGraw-Hill, fifth edition, 2000. European Adaptation. Adapted by Darrel Ince.
Henry Rabinowitz and Chaim Schaap. Portable C. Prentice Hall, 1990.
Diomidis Spinellis. Optimal peripheral access using pipe-based double-buffering (http://www.dmst.aueb.gr/dds/pubs/trade/1999-login-dd/html/dd.html). ;login:, 24(4):43–45, August 1999.
Dave Taylor. Global Software: Developing Applications for the International Market. Springer-Verlag, New York, NY, USA, 1992.

Ασκήσεις

Έχετε να επιλέξετε ανάμεσα σε αλγορίθμους που απαιτούν
- 5000 + 1000 λογ₁₀ ν,
- ν² / 1000, και
- 50 ν πράξεις.
Υπολογίστε πόσες πράξεις θα χρειαστούν για την επεξεργασία 10, 1.000, 1.000.000, 1.000.000.000 στοιχείων και εξηγήστε ποιόν αλγόριθμο θα διαλέγατε σε κάθε περίπτωση. Εκφράστε τα παραπάνω με τη χρήση της σημειογραφίας Ο().
Διαβάστε και αναλύστε πως η γλώσσα Java διευκολύνει το πρόβλημα της μεταφερσιμότητας των προγραμμάτων.
Αναλύστε τις τοπικές προσαρμογές που επιτρέπει το σύστημα Microsoft Windows.

Περιεχόμενα