Performance Tip: Data Alignment

[DarthMoul]

Η μέγιστη δυνατή ταχύτητα ανάκτησης των δεδομένων από την μνήμη, επιτυγχάνεται όταν αυτά είναι ευθυγραμμισμένα (aligned) στην φυσική τους διεύθυνση. Τι σημαίνει αυτό; Μια μεταβλητή ακέραιου τύπου που έχει μέγεθος 4 bytes, για να είναι ευθυγραμμισμένη, θα πρέπει να βρίσκεται σε διεύθυνση που είναι ακέραιο πολλαπλάσιο του 4. Σε κάθε άλλη περίπτωση, ο χρόνος ανάκτησης της από την μνήμη αυξάνεται από 3 έως 30 φορές, ανάλογα την αρχιτεκτονική.

Ας υποθέσουμε ότι έχουμε να δηλώσουμε τρεις μεταβλητές, μία char με μέγεθος 1 byte, μία int με μέγεθος 4 bytes και μία double με μέγεθος 8 bytes. Για προσέξτε την παρακάτω δήλωση:

char c;
double d;
int i ;

Εδώ απλά την πατήσαμε! Οι μεταβλητή c βρίσκεται στην σχετική διεύθυνση 0. Εδώ κανένα πρόβλημα, αφού έχουμε μέγεθος 1 byte. Η d όμως είναι στην διεύθυνση 1. Και το i στην 9. Οι μεταβλητές d και i είναι misaligned.

Για να αποφύγουμε τα misalignments η μέθοδος είναι να δηλώνουμε τις μεταβλητές με αντίστροφη σειρά μεγέθους. Η σωστή δήλωση θα ήταν:

double d;
int i;
char c;

Τώρα η d είναι στην σχετική διεύθυνση 0, ή i στην 8 και c στην 9.

Για τα unaligned accesses το μικρότερο κόστος το έχουν οι Pentium. Στους Athlon κοστίζει, λιγάκι παραπάνω. Πάντως και στις δύο περιπτώσεις δεν είναι αμελητέο και δεν μπορούμε να το αγνοήσουμε. Δυστυχώς, η x86 αρχιτεκτονική, επιβάλλει ο χρήστης / προγραμματιστής να μένει ανενόχλητος από τα unaligned accesses, οπότε αυτά δεν προκαλούν ούτε error, ούτε warning, και οι περισσότεροι profilers τα αγνοούν. Σε νεότερες και πιο εξελιγμένες αρχιτεκτονικές πάντως, o profiler ή o compiler τα εντοπίζουν και ειδοποιούν. Σε κάποιες από αυτές, η εφαρμογή θα χτυπήσει στο πρώτο misalignment που θα συναντήσει.


Προσοχή στα misalignments. Είναι silent performance killers.

[Linos80]

Θεωρω ομως οτι ειναι αναποφευκτο μεσα στα εκατομμυρια γραμμες κωδικα απο τα εκατονταδες προγραμματα που χρησιμοποιουμε να υπαρχουν και misalignments.Παρολαυτα θα συμφωνησω οτι η ευστοχη δηλωση των μεταβλητων στο παραδειγμα που αναφερεις αλλαζει εντελως τα δεδομενα σε επιπεδο αποδωσης!!!

Υ.Γ.Θα μπορουσες να μας αναλυσεις λιγακι παραπανω αυτο το τελευταιο περι κοστους σε Intel και AMD καθως και το τι συμβαινει στις διαφορες αρχιτεκτονικες?

[DarthMoul]

Θεωρω ομως οτι ειναι αναποφευκτο μεσα στα εκατομμυρια γραμμες κωδικα απο τα εκατονταδες προγραμματα που χρησιμοποιουμε να υπαρχουν και misalignments.Παρολαυτα θα συμφωνησω οτι η ευστοχη δηλωση των μεταβλητων στο παραδειγμα που αναφερεις αλλαζει εντελως τα δεδομενα σε επιπεδο αποδωσης!!!

Υ.Γ.Θα μπορουσες να μας αναλυσεις λιγακι παραπανω αυτο το τελευταιο περι κοστους σε Intel και AMD καθως και το τι συμβαινει στις διαφορες αρχιτεκτονικες?
Στατιστικά, πάνω από το 50% του κώδικα που τρέχει σε x86 έχει τουλάχιστον ένα misalignment. Ο λόγος είναι ότι η x86 αρχιτεκτονική είναι η πλέον πεπαλαιομένη απ'όσες υπάρχουν σήμερα και οι ρίζες της ξεκινάνε από το 1976 και στα 8 bits. Τότε τα misalignments είχαν ελάχιστη επίδραση, και ήταν και δυσκολότερο να συμβούν μια και τα address και data busses ήταν πολύ "στενότερα" απ' ότι σήμερα. Στατιστικά λοιπόν, η πιθανότητα ενός misalignment ήταν κατά πολύ μικρότερη.

Για τον λόγο αυτό, η Intel δεν έκανε πρόβλεψη στα Architecture specifications για το πως θα χειρίζονται την περίπτωση του misalignment ο compiler, o profiler, και φυσικά το λειτουργικό. Λόγω αυτής της παλιάς "αμαρτίας" γράφτηκε, και ακόμα γράφεται κώδικας που περιλαμβάνει misalignments, και είναι λογικό, αφού η αρχιτεκτονική προβλέπει, ότι αφενός δεν είναι σφάλμα, και αφεταίρου ότι κανείς δεν έχει την υποχρέωση να ειδοποιήσει για κάτι τέτοιο.

Τώρα όσον αφορά το κόστος. Στους Pentium είναι 3 παραπάνω κύκλοι μηχανής για τους ακεραίους. Για τους floating point, εξαρτάται από το αν είναι 32, 64 ή 80 bits. Όσο μεγαλύτερο το εύρος, τόσο μεγαλύτερο το κόστος. Εδώ το κόστος είναι από 3 μέχρι και 7 κυκλους μηχανής, αναλόγως την περίπτωση.

Επίσης το πρόβλημα γίνεται πιο περίπλοκο όταν έχουμε μετακίνηση δεδομένων, που είναι και η πιο συνήθης περίπτωση, από μία διεύθυνση της μνήμης σε μία άλλη δηλαδή πχ a=b. Το κόστος είναι διαφορετικό όταν είναι misaligned η διεύθυνση της πηγής, και διαφορετικό όταν είναι misaligned η διεύθυνση προορισμού. Εδώ έχουν και διαφορετική συμπεριφορά οι Pentium με τους Athlon. Τα misalignment στην διεύθυνση προορισμού πάντα κοστίζουν παραπάνω.

Στους Athlon θεωρητικά, το κόστος τους misalignent είναι ένας κύκλος μηχανής. Το κόστος όμως που πληρώνει κάποιος όταν μετακινεί δεδομένα από την μία διεύθυνση στην άλλη, για την διεύθυνση πηγής είναι σημαντικό, ενώ στους Pentium αμελητέο. Γενικότερα η AMD δείχνει μια κρυψίνια σε αυτά τα ζητήματα. Για τους float πχ γράφει, ότι τα misalignments πρέπει να αποφεύγονται "γιατί μειώνουν το memory bandwidth". Παραπάνω πληροφορία, καμμία. Για να βρούμε την ακριβή συμπεριφορά του Athlon στα misalignments και σε κάθε περίπτωση, χρειάζεται λιγάκι benchmarking. Το γεγονός είναι ότι κατα βάσει κοστίζει κάτι παραπάνω, παρ'όλα όσα γράφει το optimization guide.

Η διαφορετική συμπεριφορά των δύο CPU's οφείλεται κυρίως στον τρόπο που διαχειρίζονται το cache, και στο pipeline structure. (Στο pipeline structure είναι κρυψίνους η Intel). Ειδικά για το cache θα κάνουμε άλλο thread μια και όλα τα προγράμματα είναι ενα πρόβλημα αποδοτικής διαχειρισης του.

Σε risc αρχιτεκτονικές, τα misalignments απλά γονατίζουν την μηχανή. Στο Alpha πχ που είναι και ο πιο ευαίσθητος σε αυτά τα ζητήματα, το μέσο κόστος είναι μέχρι και 30 κύκλοι μήχανής με maximum τους 67. Τα προγράμματα που αρχικά γράφτηκαν για alpha, σε x86 τρέχουν σαν όνειρο γιατί είναι overaligned. Στους πρώτους sparc ένα misalignment προκαλούσε segfault ή bus error και η εκτέλεση του προγράμματος σταματούσε.

Σε γενικές γραμμές, κυνηγάμε τα misalignments όπου τα βρούμε. Δεν κοστίζει τίποτα και αποδίδει πολύ. Αρκεί να αποκτήσουμε την καλή συνήθεια όταν γράφουμε κώδικα, να δηλώνουμε τις μεταβλητές μας σωστά, και να δομούμε σωστά τα records και structures.

[Linos80]

Σα να χτιζουμε ενα σπιτι και να μην βαριομαστε να του κανουμε σωστα και γερα θεμελια ε? ;)

[vagalati]

Με την ευκαιρία, θυμήθηκα κάτι που μου είχε συμβεί πριν απο καιρό. Είχα κάνει το εξής σε ένα πρόγραμμα C++:

struct Test
{
char c;
int i;
};


Ήθελα να σώσω κάποια structs σε ένα binary αρχείο αλλά περιέργως όταν τα διάβαζα ένα-ένα (διάβαζα ένα byte για το char και μετά 4 bytes για τον int), το πρόγραμμα μου πετούσε segmentation fault. Μετά απο ψάξιμο κατέληξα στο εξής:

Αν διάβαζα τα δεδομένα με structs (περνούσα τον δείκτη του struct και το sizeof του) όλα δούλευαν ωραία. Όταν τα διάβαζα ξεχωριστά, διάβαζε "σκουπίδια".

Στη συνέχεια απο περιέργεια τύπωσα στην οθόνη το sizeof(Test) και βρήκα τον ένοχο. Ενώ εγώ περίμενα να μου βγάλει 5 αυτό επέστρεφε 8! Όταν γράφουμε ένα struct σε αρχείο αυτό αποθηκεύεται όπως είναι στη μνήμη (αν π.χ το γράφεις σε litle endian machine και το ίδιο αρχείο το διαβάσεις σε big endian την πάτησες!). Ο gcc προσπαθούσε να αποφύγει τα missalignements και έσωζε το struct ολόκληρο στη μνήμη σε 8 bytes. Απο αυτά τα 3 bytes μετά το char έμεναν απλά *ανεκμετάλλευτα* και στη συνέχεια ακολουθούσε το int.
Τότε πρέπει να χρησιμοποιούσα τον gcc 2.x.y. Λογικά το ίδιο πρέπει να γίνεται και με τον 3.x.

[DarthMoul]

Με την ευκαιρία, θυμήθηκα κάτι που μου είχε συμβεί πριν απο καιρό. Είχα κάνει το εξής σε ένα πρόγραμμα C++:

struct Test
{
char c;
int i;
};


Ήθελα να σώσω κάποια structs σε ένα binary αρχείο αλλά περιέργως όταν τα διάβαζα ένα-ένα (διάβαζα ένα byte για το char και μετά 4 bytes για τον int), το πρόγραμμα μου πετούσε segmentation fault. Μετά απο ψάξιμο κατέληξα στο εξής:

Αν διάβαζα τα δεδομένα με structs (περνούσα τον δείκτη του struct και το sizeof του) όλα δούλευαν ωραία. Όταν τα διάβαζα ξεχωριστά, διάβαζε "σκουπίδια".

Στη συνέχεια απο περιέργεια τύπωσα στην οθόνη το sizeof(Test) και βρήκα τον ένοχο. Ενώ εγώ περίμενα να μου βγάλει 5 αυτό επέστρεφε 8! Όταν γράφουμε ένα struct σε αρχείο αυτό αποθηκεύεται όπως είναι στη μνήμη (αν π.χ το γράφεις σε litle endian machine και το ίδιο αρχείο το διαβάσεις σε big endian την πάτησες!). Ο gcc προσπαθούσε να αποφύγει τα missalignements και έσωζε το struct ολόκληρο στη μνήμη σε 8 bytes. Απο αυτά τα 3 bytes μετά το char έμεναν απλά *ανεκμετάλλευτα* και στη συνέχεια ακολουθούσε το int.
Τότε πρέπει να χρησιμοποιούσα τον gcc 2.x.y. Λογικά το ίδιο πρέπει να γίνεται και με τον 3.x.
Ο gcc έβαλε το σωστό pad πριν από τον ακέραιο, για να κρατήσει το alignment των δεδομένων σου. Πάντως μην επαναπαύεσαι ότι όλοι οι compilers θα τα κάνουν αυτά. Για PC οι μόνοι που έχουν τέτοια χαρακτηριστικά είναι οι compilers της GNU και της Intel. Microsoft, Borland, Watcom κλπ δεν είναι και πολύ έξυπνοι σε τέτοια ζητήματα. Γι αυτό καλύτερα να τα φροντίζουμε εμείς για να έχουμε το κεφάλι μας ήσυχο.

[vagalati]

Έστω ότι θέλω να φτιάξω ένα struct σαν το παραπάνω που είχα αναφέρει. Και στη συνέχεια θέλω να ορίσω έναν πίνακα με (π.χ 10) instances αυτού του struct. Πως αποφευγουμε τα misalignments;
Το να βάζουμε πρώτα όλα τα ints και μετά όλα τα chars δεν είναι λύση γιατί έτσι καταργούμε την έννοια του struct (και της τάξης, αν χρησιμοποιώ τάξεις και αντικείμενα).
Σκέφτηκα ότι ίσως ότι θα ήταν φρόνιμο να ορίσουμε δεδομένα μέσα στο structs τα οποία θα κάνουν ότι έκανε και ο gcc. Δηλ.
struct
{
int a;
char b;
char unused[3]; // ποτέ δεν θα χρησιμοποιηθούν,
//υπάρχουν για να δίνουν ευθυγράμιση των δεδομένων στον πίνακα
}

Η παραπάνω τεχνική όμως τρώει μνήμη. Υπάρχει κάτι καλύτερο;

[DarthMoul]

Έστω ότι θέλω να φτιάξω ένα struct σαν το παραπάνω που είχα αναφέρει. Και στη συνέχεια θέλω να ορίσω έναν πίνακα με (π.χ 10) instances αυτού του struct. Πως αποφευγουμε τα misalignments;
Το να βάζουμε πρώτα όλα τα ints και μετά όλα τα chars δεν είναι λύση γιατί έτσι καταργούμε την έννοια του struct (και της τάξης, αν χρησιμοποιώ τάξεις και αντικείμενα).
Σκέφτηκα ότι ίσως ότι θα ήταν φρόνιμο να ορίσουμε δεδομένα μέσα στο structs τα οποία θα κάνουν ότι έκανε και ο gcc. Δηλ.
struct
{
int a;
char b;
char unused[3]; // ποτέ δεν θα χρησιμοποιηθούν,
//υπάρχουν για να δίνουν ευθυγράμιση των δεδομένων στον πίνακα
}

Η παραπάνω τεχνική όμως τρώει μνήμη. Υπάρχει κάτι καλύτερο;
Δεν υπάρχει κάτι καλύτερο. Σχεδόν καθε τεχική βελτιστοποίησης ταχύτητας, είναι εχθρός της μνήμης. Είναι το κόστος που πληρώνεις για να πας γρήγορα.
Δεν καταργείς καμμία έννοια του struct αν τα δηλώσεις όπως σου είπα. Εκτός αν καταργούν την έννοια του struct το Intel Architecture Optimization Manual, το Optimization for AMD Processors Manual και το The Alpha Architecture Handbook που έχω δίπλα μου. Και τα τρία αυτήν την τεχνική προτείνουν. Δήλωσε τον πίνακα σου μαζί με τους υπόλοιπους ακέραιους και είσαι μια χαρούλα

[spinner]

Aυτο που εχω παρατηρησει, αν τελικα ο γενικος κανονας ειναι να δηλωνουμε τις μεταβλητες με φθινουσα σειρα μεγεθους τοτε μπορω να πω οτι δεν το βλεπω συχνα...
Π.χ. το σκεφτομουν τις προαλλες που κοιτουσα τον example κωδικα στο
/usr/src/linux-2.6.15.2/Documentation/rtc.txt

Ειχε ενα παραδειγμα και οι μεταβλητες ηταν misallinged αν δεν κανω λαθος..
Γενικα παντως σε κωδικα για x86 που κοιταω πολυ συχνα δεν βλεπω το σωστο allingment..
Aφου ειναι silent performance killers γιατι δεν τα προσεχουν ?
Μαλλον πρεπει να δωσω ενα link στο παρον topic :D

[DarthMoul]

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

Η δήλωση των μεταβλητών με φθίνουσα τάξη μεγέθους διασφαλίζει ότι δεν θα υπάρξει misalignment. Αν οι μεταβλητές δεν δηλωθούν έτσι, δεν σημαίνει πως είναι και misaligned.

Ούτως η άλλως το κομμάτι του κώδικα που έδωσες είναι για 32 bit συστήματα όπου και οι int και οι long είναι 4 bytes. Τα structures είναι πάντα aligned από τον gcc.

Επειδή τρέχω linux σε alpha που τα misalignments προκαλούν πολύ θόρυβο αυτό που έχω δει είναι πως ο kernel 2.4 είχε ένα misalignment και ο 2.6 κανένα.