Συζήτηση στο Memory Alignment

[gon1332]

Είχα εδώ και καιρό μία γνωστική σύγκρουση πάνω στο θέμα του Memory Alignment. Αυτή προήλθε από μία άσκηση που είχα στη σχολή στο μάθημα της Οργάνωσης Η/Υ. Η άσκηση έλεγε λοιπόν:

 

 

Ευθυγράμμιση δομών δεδομένων
Θεωρείστε την παρακάτω δομή δεδομένων σε C:

struct foo {
        char a;
        bool b; // Implement in an effective way
        int c;
        double d;
        short e;
        float f;
        double g;
        char *cptr;
        float *fptr;
        int x;
}

Ποιο είναι το μέγεθος της struct foo για έναν επεξεργαστή 32-bit; Ποιο είναι το ελάχιστο μέγεθος της struct foo υποθέτοντας ότι μπορούμε να αλλάξουμε την σειρά των πεδίων της struct foo με όποιον τρόπο θέλουμε; Επαναλάβετε τις ίδιες ερωτήσεις για έναν επεξεργαστή 64-bit.
Σημειώστε ότι εκτός από τις απαιτήσεις για ευθυγραμμισμένα πεδία μέσα σε μία struct, ή ίδια η struct πρέπει να είναι επίσης ευθυγραμμισμένη. Σημ. σκεφτείτε τι ακριβώς γίνεται όταν έχουμε για παράδειγμα έναν πίνακα από τέτοιες structs (πχ. struct foo[100]).

 

 

Η απάντησή μου είναι στην επισύναψη αρχείων.

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

Η άσκηση δεν το ζητούσε, αλλά εγώ κάθησα και δοκίμασα 3 compilers για C. Τον gcc, τον compiler του VS2012 και τον MinGW. O πρώτος σε 32 bit Ubuntu και 64 bit Ubuntu και οι άλλοι δύο σε 64 bit Windows 8.

 

Το κουλό ήταν πως σε 32 bit Ubuntu o gcc έκανε alignment ως προς 4 byte το ανώτερο. Αν είχα double μέσα στο struct, τότε τον "έσπαγε". Εντωμεταξύ κάπου είχα διαβάσει (στο ίντερνετ) πως στο linux γίνεται alignment ως προς το default pack size που στα 32 bit είναι τα 4 bytes. Το ίδιο όμως δε συνέβαινε με το Ubuntu 64bit, όπως και τους υπόλοιπους compilers. Όλοι έκαναν align το struct με βάση το μεγαλύτερο μέγεθος μέσα σε αυτό. Αν πχ έβαζα long double τότε έκαναν alignment με βάση αυτό.

 

Τι έχετε να πείτε;

[sonyxp]

.....Όλοι έκαναν align το struct με βάση το μεγαλύτερο μέγεθος μέσα σε αυτό. Αν πχ έβαζα long double τότε έκαναν alignment με βάση αυτό.

 

Τι έχετε να πείτε;

 

Δεν ήξερα ότι κάνει μόνο του alignment, νόμιζα ότι εσύ πρέπει να τα δηλώσεις έτσι ώστε να πετύχεις το alignment (χειροκίνητα δηλαδή, από το μεγαλύτερο προς το μικρότερο)

[gon1332]

Δεν ήξερα ότι κάνει μόνο του alignment, νόμιζα ότι εσύ πρέπει να τα δηλώσεις έτσι ώστε να πετύχεις το alignment (χειροκίνητα δηλαδή, από το μεγαλύτερο προς το μικρότερο)

 

Κάνει μόνο του alignment για λόγους απόδοσης. Βασικά είναι default ενεργοποιημένο. Πρέπει κάποιος να το δηλώσει ρητά ότι δε θέλει alignment με όποιες συνέπειες..

[παπι]

Τι έχετε να πείτε;

Ασχετοι.

[ChRis6]

Δεν πρέπει μονο τα πεδία μεσα στη struct να ειναι ευθυγραμμισμένα,αλλά και η ίδια η struct να είναι ευθυγραμμισμένη.Πώς αλλιώς θα κάνεις array απο foo ; Οπότε μπαίνει κι αλλο padding...

Για τα 64bit γιατί βγάζεις 56bytes ; Εγώ βγάζω 52.Μόνο το μέγεθος των pointers αλλάζει.Όλα τα υπόλοιπα είναι ίδια

Σημείωση: Σε ορισμένες αρχιτεκτονικές αν τα δεδομένα δεν είναι ευθυγραμμισμένα,απλά δεν τρέχει το πρόγραμμα.Keep that in mind!

[gon1332]

Για τα 64bit γιατί βγάζεις 56bytes ; Εγώ βγάζω 52.Μόνο το μέγεθος των pointers αλλάζει.Όλα τα υπόλοιπα είναι ίδια

 

Για το λόγο που είπες μου βγάζει 56 bytes. Για να είναι ευθυγραμμισμένο και ως στοιχείο ενός πίνακα από structs.

Αν προσέξεις χρειάζονται άλλα 4 dummy bytes στο τέλος για να επιτευχθεί αυτό. Μάλλον εσύ το τρέχεις με gcc

με την έκδοση με την οποία έτρεχα εγω στο Ubuntu 32 bits. Εκεί ακριβώς είναι ο προβληματισμός μου. Γιατί σε

όλα τα παραδείγματα με άλλους compilers και στα παραδείγματα που υπάρχουν στο internet ΔΕ συμβαίνει αυτό

και συμβαίνει το απολύτως λογικό να γίνεται η ευθυγράμμιση στο μεγαλύτερο μέγεθος τύπου μέσα στο struct;

 

Αν το δοκίμασες με gcc, ποια έκδοση τρέχεις; (gcc --version)

[ChRis6]

Και εμένα  με gcc 4.7.3 μου βγάζει 56 που ειναι και το σωστό.Νόμιζα στο πινακάκι έχεις απλά το μέγεθος του struct με βαση τα πεδια.

Padding  γίνεται με βάση τον αριθμό  των bytes που χρειάζονται  για να γίνει η ευθυγράμμιση στο κοντινότερο πολλαπλάσιο

edit: Εφόσον το μάθημα Λέγεται οργάνωση Η/Υ και όχι compilers,δεν κοιτάς τι σου βγάζει ο κάθε compiler.Μπορεί να βρεις έναν compiler που βάζει 256bits στον int γιατί έτσι ξύπνησαν εκείνη τη μέρα οι σχεδιαστές.

Σε ποια αρχιτεκτονική βασίζεστε ;

[imitheos]

Είχα εδώ και καιρό μία γνωστική σύγκρουση πάνω στο θέμα του Memory Alignment. Αυτή προήλθε από μία άσκηση που είχα στη σχολή στο μάθημα της Οργάνωσης Η/Υ. Η άσκηση έλεγε λοιπόν:

 

 

Ευθυγράμμιση δομών δεδομένων

Θεωρείστε την παρακάτω δομή δεδομένων σε C:

Ποιο είναι το μέγεθος της struct foo για έναν επεξεργαστή 32-bit; Ποιο είναι το ελάχιστο μέγεθος της struct foo υποθέτοντας ότι μπορούμε να αλλάξουμε την σειρά των πεδίων της struct foo με όποιον τρόπο θέλουμε; Επαναλάβετε τις ίδιες ερωτήσεις για έναν επεξεργαστή 64-bit.

Σημειώστε ότι εκτός από τις απαιτήσεις για ευθυγραμμισμένα πεδία μέσα σε μία struct, ή ίδια η struct πρέπει να είναι επίσης ευθυγραμμισμένη. Σημ. σκεφτείτε τι ακριβώς γίνεται όταν έχουμε για παράδειγμα έναν πίνακα από τέτοιες structs (πχ. struct foo[100]).

 

 

Η απάντησή μου είναι στην επισύναψη αρχείων.

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

Η άσκηση δεν το ζητούσε, αλλά εγώ κάθησα και δοκίμασα 3 compilers για C. Τον gcc, τον compiler του VS2012 και τον MinGW. O πρώτος σε 32 bit Ubuntu και 64 bit Ubuntu και οι άλλοι δύο σε 64 bit Windows 8.

 

Το κουλό ήταν πως σε 32 bit Ubuntu o gcc έκανε alignment ως προς 4 byte το ανώτερο. Αν είχα double μέσα στο struct, τότε τον "έσπαγε". Εντωμεταξύ κάπου είχα διαβάσει (στο ίντερνετ) πως στο linux γίνεται alignment ως προς το default pack size που στα 32 bit είναι τα 4 bytes. Το ίδιο όμως δε συνέβαινε με το Ubuntu 64bit, όπως και τους υπόλοιπους compilers. Όλοι έκαναν align το struct με βάση το μεγαλύτερο μέγεθος μέσα σε αυτό. Αν πχ έβαζα long double τότε έκαναν alignment με βάση αυτό.

 

Τι έχετε να πείτε;

Το alignment εξαρτάται από τον compiler (σε συνδυασμό με οποιαδήποτε φράγματα ίσως βάζει το ABI του επεξεργαστή). Σε κάθε αρχιτεκτονική ο compiler γνωρίζει ποια προσπέλαση τίνος μεγέθους είναι πιο γρήγορη (ή τίνος μεγέθους επιτρέπεται γιατί εκτός x86 πολλοί επεξεργαστές θα βαρέσουν fault αν δεν υπάρχει το σωστό alignment) και ευθυγραμμίζει σε αυτό. Με βάση αυτά τα δεδομένα ο compiler επιλέγει ένα alignment για τον κάθε τύπο.

 

Συχνά βλέπουμε να γίνονται δύο λάθη όσον αφορά την περιγραφή της λειτουργίας της ευθυγράμμισης:

 

α) Οι κανόνες ευθυγράμμισης ορίζονται μεν με βάση την αρχιτεκτονική αλλά από εκεί και πέρα παίζει ρόλο μόνο ο τύπος της μεταβλητής. Δηλαδή, δεν γίνεται πάντα ευθυγράμμιση σε 4 σε 32bit και σε 8 σε 64bit όπως θα περιμέναμε. Ο τύπος char για παράδειγμα έχει ευθυγράμμιση 1 οπότε μια δομή με 2 chars σε 32bit (το πιο πιθανό είναι πως) θα έχει μέγεθος 2 και όχι 4.

 

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

 

Ας δούμε δύο χαζά παραδείγματα των α και β.

 

#include <stdio.h>

struct foo {
	char a;
	char b;
};

struct bar {
	char a;
	short b;
	short c;
};

int main(void)
{
	printf("size: foo = %zu - bar = %zu\n\n", sizeof(struct foo),
	       sizeof(struct bar));

	return 0;
}

Έξοδος:

% cc -Wall tmp.c 
% ./a.out 
size: foo = 2 - bar = 6

% cc -Wall -m32 tmp.c 
% ./a.out 
size: foo = 2 - bar = 6

Όπως βλέπουμε, και σε 32bit και σε 64bit η δομή με τους 2 chars έχει μέγεθος 2 (και όχι 4 ή 8) και η δομή με τον char και τους δύο short έχει μέγεθος 6 (και όχι 8).

 

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>

struct foo {
        char a;
        bool b; // Implement in an effective way
        double d;  // Ebala ton double prin ton int
        int c;
        short e;
        float f;
        double g;
        char *cptr;
        float *fptr;
        int x;
};

int main(void)
{
	struct foo foo;

	printf("char   a has offset %zu and size %zu\n",
	       offsetof(struct foo, a), sizeof(foo.a));
	printf("bool   b has offset %zu and size %zu\n",
	       offsetof(struct foo, , sizeof(foo.);
	printf("double d has offset %zu and size %zu\n",
	       offsetof(struct foo, d), sizeof(foo.d));
	printf("int    c has offset %zu and size %zu\n",
	       offsetof(struct foo, c), sizeof(foo.c));
	printf("short  e has offset %zu and size %zu\n",
	       offsetof(struct foo, e), sizeof(foo.e));
	printf("float  f has offset %zu and size %zu\n",
	       offsetof(struct foo, f), sizeof(foo.f));
	printf("double g has offset %zu and size %zu\n",
	       offsetof(struct foo, g), sizeof(foo.g));
	printf("char ptr has offset %zu and size %zu\n",
	       offsetof(struct foo, cptr), sizeof(foo.cptr));
	printf("flt  ptr has offset %zu and size %zu\n",
	       offsetof(struct foo, fptr), sizeof(foo.fptr));
	printf("int    x has offset %zu and size %zu\n",
	       offsetof(struct foo, x), sizeof(foo.x));

	return 0;
}

Εδώ βλέπουμε την δομή που έδωσες αλλά με μία αλλαγή. Έβαλα τον double πριν τον int για να φανεί αυτό που είπα ότι το μέγεθος δεν έχει σχέση με την ευθυγράμμιση.

% gcc -Wall tmp2.c -m32 -malign-double -o 32a   
% gcc -Wall tmp2.c -m32 -o 32 
Έξοδος:

% ./32
char   a has offset 0 and size 1
bool   b has offset 1 and size 1
double d has offset 4 and size 8
int    c has offset 12 and size 4
short  e has offset 16 and size 2
float  f has offset 20 and size 4
double g has offset 24 and size 8
char ptr has offset 32 and size 4
flt  ptr has offset 36 and size 4
int    x has offset 40 and size 4

% ./32a 
char   a has offset 0 and size 1
bool   b has offset 1 and size 1
double d has offset 8 and size 8
int    c has offset 16 and size 4
short  e has offset 20 and size 2
float  f has offset 24 and size 4
double g has offset 32 and size 8
char ptr has offset 40 and size 4
flt  ptr has offset 44 and size 4
int    x has offset 48 and size 4

Όπως βλέπουμε, ενώ ο double έχει μέγεθος 8 δεν ευθυγραμμίζεται σε 8 αλλά έχει offset 4 από τη μάνα του και μόνο αν ενεργοποιήσουμε την επιλογή -malign-double, ο gcc τον ευθυγραμμίζει σε 8. Αυτά φυσικά για τον gcc σε x86 linux. Ένας άλλος compiler μπορεί να κάνει κάτι τελείως διαφορετικό.

[παπι]

Ειναι θεμα compiler, για αυτο και εγραψα ασχετοι. (εννοωντας τους συντακτες της ασκησης)

[ChRis6]

Ο compiler απλα ακολουθεί την αρχιτεκτονική.

Αν η αρχιτεκτονική ορίσει π.χ μέγεθος λέξης = 4bytes,ο compiler πρεπει να το σεβαστεί και να το ακουλουθήσει με ευλάβεια.Διαφορετικά δεν θα είναι καλός compiler.Τα υπόλοιπα είναι ραπανάκια για την όρεξη !

[gon1332]

 

 

α) Οι κανόνες ευθυγράμμισης ορίζονται μεν με βάση την αρχιτεκτονική αλλά από εκεί και πέρα παίζει ρόλο μόνο ο τύπος της μεταβλητής. Δηλαδή, δεν γίνεται πάντα ευθυγράμμιση σε 4 σε 32bit και σε 8 σε 64bit όπως θα περιμέναμε. Ο τύπος char για παράδειγμα έχει ευθυγράμμιση 1 οπότε μια δομή με 2 chars σε 32bit (το πιο πιθανό είναι πως) θα έχει μέγεθος 2 και όχι 4.

 

Πολύ σωστά! Γι'αυτό και ειπά ότι για x86 μου κάνει ευθυγράμμιση το πολύ 4 bytes.

 

 

 

Όπως βλέπουμε, ενώ ο double έχει μέγεθος 8 δεν ευθυγραμμίζεται σε 8 αλλά έχει offset 4 από τη μάνα του και μόνο αν ενεργοποιήσουμε την επιλογή -malign-double, ο gcc τον ευθυγραμμίζει σε 8. Αυτά φυσικά για τον gcc σε x86 linux. Ένας άλλος compiler μπορεί να κάνει κάτι τελείως διαφορετικό. 

 

Μπράβο! Λογικά αυτή θα είναι η λύση στο ζήτημα. Σε linux x86 πρέπει να είναι ενεργοποιημένα κάποια flags για να λειτουργήσει όπως θέλουμε. Σε άλλους compilers θα υπάρχουν κάποιες άλλες επιλογές ως default.

 

 

 

edit: Εφόσον το μάθημα Λέγεται οργάνωση Η/Υ και όχι compilers,δεν κοιτάς τι σου βγάζει ο κάθε compiler.Μπορεί να βρεις έναν compiler που βάζει 256bits στον int γιατί έτσι ξύπνησαν εκείνη τη μέρα οι σχεδιαστές.

 

Σε ποια αρχιτεκτονική βασίζεστε ;

 

Η άσκηση αυτή δεν ήταν η μοναδική. Ήταν η μόνη που ξέφευγε λιγάκι. Μάλλον εγώ της έδωσα περισσότερη σημασία απ' ότι έπρεπε.

 

Στο μάθημα εξετάζουμε την αρχιτεκτονική του MIPS, αλλά αυτό δεν έχει κάποια σχέση όπως είπε και ο imitheos με αυτή. Το καλό είναι που το πρόσεξα τώρα, οπότε ΝΑ τι μαθαίνει κανείς με τους πειραματισμούς!

Ο compiler απλα ακολουθεί την αρχιτεκτονική.

 

Αν η αρχιτεκτονική ορίσει π.χ μέγεθος λέξης = 4bytes,ο compiler πρεπει να το σεβαστεί και να το ακουλουθήσει με ευλάβεια.Διαφορετικά δεν θα είναι καλός compiler.Τα υπόλοιπα είναι ραπανάκια για την όρεξη !

 

EDIT

Μάλλον γράφαμε μαζί.

 

Αυτό που λες όπως είχα γράψει και στο αρχικό μου post το είχα βρει κάπου. Ποιο είναι το μέγεθος λέξης του x86; Τα 4 bytes; Ωραία, ο gcc σε x86 κάνει alignment με το πολύ 4 bytes (μπορεί να κάνει με 1, με 2, αλλά όχι πάνω από 4). Σε 64 bit τι συμβαίνει;

 

Μάλλον όπως είπε και ο imitheos έχει σχέση με τις επιλογές που θα δώσεις στον compiler.

[παπι]

 

Αυτό που λες όπως είχα γράψει και στο αρχικό μου post το είχα βρει κάπου. Ποιο είναι το μέγεθος λέξης του x86; Τα 4 bytes;

Σημερα, 16 

[imitheos]

Αυτό που λες όπως είχα γράψει και στο αρχικό μου post το είχα βρει κάπου. Ποιο είναι το μέγεθος λέξης του x86; Τα 4 bytes; Ωραία, ο gcc σε x86 κάνει alignment με το πολύ 4 bytes (μπορεί να κάνει με 1, με 2, αλλά όχι πάνω από 4). Σε 64 bit τι συμβαίνει;

 

Μάλλον όπως είπε και ο imitheos έχει σχέση με τις επιλογές που θα δώσεις στον compiler.

Δες τι είπαμε πριν στο α) κομμάτι. Ο compiler δεν θα κάνει "το πολύ 4 bytes" ούτε "τουλάχιστον 4 bytes" αλλά θα κάνει όση ευθυγράμμιση πρέπει

 

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>

struct foo {
        char a;
        long double d;
};

int main(void)
{
	struct foo foo;

	printf("char   a has offset %zu and size %zu\n",
	       offsetof(struct foo, a), sizeof(foo.a));
	printf("ldbl   d has offset %zu and size %zu\n",
	       offsetof(struct foo, d), sizeof(foo.d));

	return 0;
}

Δοκίμασε αυτό σε 32bit Visual Studio να δούμε θα κάνει σε το πολύ 4 bytes ?

[gon1332]

Δοκίμασε αυτό σε 32bit Visual Studio να δούμε θα κάνει σε το πολύ 4 bytes ? 

 

Δε θα κάνει! Το έχω δοκιμάσει. Και αυτό είναι το λογικό!!

Θα κάνει align στο μεγαλύτερο μέγεθος. Τελικά το μέγεθος του struct θα είναι 32 bits.

Άλλα βγάζει το VS, άλλα έβγαζε ο gcc. Πλέον με τον gcc 4.8.1 δεν παρατήρησα

σπάσιμο του double σε 4 bytes. Απλά δε θυμάμαι αν είχα όντως παλιά έκδοση gcc

(υπήρξε και ένα format στο μεσοδιάστημα) ή κάτι άλλο.

 

Το θα κάνει το πολύ σε 4 bytes ήταν ο πραγμαικός προβληματισμός μου.

Σας ευχαριστώ για το ξεκαθάρισμα!

 

 

EDIT

 

Από GNU C Reference Manual:

 

http://www.gnu.org/software/gnu-c-manual/gnu-c-manual.html#Size-of-Structures

[ChRis6]

Στον x86 μπορείς να διαβάσεις και χωρις ευθυγράμμιση.Στον MIPS αν τα δεδομενα δεν ειναι ευθυγραμμισμενα,δεν τσουλάει ο κωδικας