Ανάγκη για ταχύτητα

Διεπαφή με τη γλώσσα C: Structs

Στη γλώσσα C, μια struct είναι ένας σύνθετος τύπος, που αποτελείται από διαφορετικά πεδία. Κάθε πεδίο έχει τον δικό του τύπο και μέγεθος.

Για παράδειγμα, αυτό ορίζει έναν τύπο που αποτελείται από τρεις ακέραιους, δύο των 4 byte και έναν των 8 byte:

struct example {
    int32_t first_four_byte_integer;
    uint32_t second_four_byte_integer;
    uint64_t eight_byte_integer;
};

Μια struct μπορεί επίσης να περιέχει άλλες structs:

struct example_2 {
    struct example first;
    struct example second;
};

Αν ένα από τα πεδία της struct είναι ένας πίνακας, όλα τα byte που δεσμεύονται για τον πίνακα είναι μέρος της struct. Ωστόσο, αν το πεδίο είναι μόνο ένας δείκτης προς τον πίνακα, τότε ο πίνακας πρέπει να αποθηκευτεί κάπου αλλού:

struct with_array {
    char string[20];
};
// all 20 bytes of string are inside struct with_array

struct with_pointer {
    const char *string;
};
// only the 8-byte pointer to the string is inside struct with_pointer

Ευθυγράμμιση

Η ευθυγράμμιση ενός τύπου είναι μια μη αρνητική δύναμη του δύο (1, 2, 4, 8, ...) που αντιπροσωπεύει μια απαίτηση για τη διεύθυνσή του. Κάθε αντικείμενο αυτού του τύπου πρέπει να βρίσκεται σε μια διεύθυνση που είναι πολλαπλάσιο της ευθυγράμμισής του.

Για έναν αρχέγονο τύπο, η ευθυγράμμιση είναι συνήθως ίση με το μέγεθός του, έτσι, για παράδειγμα, ένα int32_t έχει συνήθως ευθυγράμμιση 4 byte. Αυτό σημαίνει ότι το int32_t πρέπει να δεσμεύεται σε όρια 4 byte.

Η ευθυγράμμιση μιας struct, ωστόσο, είναι η μέγιστη ευθυγράμμιση οποιουδήποτε από τα πεδία της. Έτσι, για παράδειγμα, η struct example, που ορίστηκε παραπάνω, θα είχε ευθυγράμμιση 8 byte, αφού αυτή είναι η ευθυγράμμιση του uint64_t.

Αν η ευθυγράμμιση ενός πεδίου μιας struct είναι μικρότερη από αυτή της struct, μπορεί να εισαχθούν bytes padding μετά από αυτό το πεδίο. Αυτό διασφαλίζει ότι τα επόμενα πεδία και η struct στο σύνολό της πληρούν τις απαιτήσεις ευθυγράμμισης. Στην πράξη, αυτό σημαίνει ότι παρόλο που αυτά τα bytes padding συμβάλλουν στο μέγεθος της struct, δε χρησιμοποιούνται στην τιμή της struct:

struct example_3 {
    char one_byte; // alignment of 1
    int four_byte; // alignment of 4
};
// example_3 has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one_byte'
// 3 padding bytes (with undefined value)
// 4 bytes for field 'four_byte'

Σημείωσε ότι στη struct που ορίστηκε παραπάνω, το πεδίο 'one_byte' έχει ευθυγράμμιση 1 και μπορεί να τοποθετηθεί σε οποιαδήποτε διεύθυνση. Εφόσον το πεδίο 'four_byte' έχει ευθυγράμμιση 4, τα πεδία στη struct πρέπει επίσης να τηρούν τα όρια των 4 byte. Αυτό σημαίνει ότι πρέπει να υπάρχει ένας αριθμός byte που είναι πολλαπλάσιο του 4 ανάμεσα σε οποιαδήποτε δύο πεδία στη struct. Εφόσον το 'one_byte' καταλαμβάνει μόνο 1 byte, τότε 3 bytes padding εισάγονται μετά από αυτό για να τηρηθεί αυτό το όριο.

Τα γειτονικά πεδία ομαδοποιούνται όποτε είναι δυνατόν, ώστε να ελαχιστοποιηθεί ο αριθμός των απαραίτητων bytes padding:

struct two_padding {
    char one; // alignment of 1
    char two; // alignment of 1
    int three; // alignment of 4
};
// struct two_padding has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one'
// 1 byte for field 'two'
// 2 padding bytes
// 4 bytes for field 'three'

Αυτή η ομαδοποίηση πρέπει επίσης να τηρεί την ευθυγράμμιση κάθε πεδίου:

struct one_padding {
    char one; // alignment of 1
    int16_t two; // alignment of 2
    int three; // alignment of 4
};
// struct one_padding has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one'
// 1 padding byte
// 2 bytes for field 'two'
// 4 bytes for field 'three'
// Since 'two' has alignment of 2, it must be placed in a 2-byte boundary
// So, there must be 1 padding byte between 'one' and 'two'

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

struct example_4 {
    int64_t one;
    short two;
    int32_t three;
};
// example_4 has alignment of 8 (the same as int64_t)
// it occupies 16 bytes in space:
// 8 bytes for field 'one'
// 2 bytes for field 'two'
// 2 padding bytes
// 4 bytes for field 'three'
// two' and 'three' are adjacent and can be grouped to sum up 8 bytes with only 2 bytes of padding

struct example_5 {
    int16_t one;
    int64_t two;
    unsigned int three;
};
// example_5 also has alignment of 8 (the same as int64_t)
// however, it occupies 24 bytes in space:
// 2 bytes for field 'one'
// 6 bytes for padding
// 8 bytes for field 'two'
// 4 bytes for field 'three'
// 4 padding bytes
// 'one' can't be grouped with 'two' because their sum would be higher than the struct's alignment
// 'two' and 'three' also can't be grouped, for the same reason
// so padding bytes must be inserted in full after each field with less than 8 bytes in alignment

Σημείωσε ότι η ευθυγράμμιση ενός πίνακα είναι ίδια με την ευθυγράμμιση του υποκείμενου τύπου του:

struct array_example {
    char string[10]; // alignment of 1
};
// array_example has alignment of 1 (it can be placed at any address)
// it occupies 10 bytes in space, one for each char in 'string'

Τα στοιχεία ενός πίνακα μπορούν να ομαδοποιηθούν με τον ίδιο τρόπο όπως αν δεν ήταν μέρος ενός πίνακα:

struct group_array {
    int16_t arr[3];
    int8_t one_byte;
    int32_t four_byte;
};
// group_array has alignment of 4 because this is the alignment of 'four_byte'
// it occupies 12 bytes in space:
// 4 bytes for arr[0] and arr[1]
// 2 bytes for arr[2]
// 1 byte for 'one_byte'
// 1 padding byte (arr[2] is grouped with 'one_byte')
// 4 bytes for 'four_byte'

Είναι σημαντικό να λαμβάνεις υπόψη τυχόν πιθανά bytes padding κάθε φορά που προσπελαύνεις μια struct σε assembly.

Σύμβαση κλήσης

Σε γενικές γραμμές, οι τιμές περνούν σε συναρτήσεις και επιστρέφονται από αυτές όπως θα περίμενε κανείς:

• Οι ακέραιες τιμές, συμπεριλαμβανομένων των διευθύνσεων μνήμης και των enums, περνούν σε Γενικούς Καταχωρητές Γενικού Σκοπού (GPR).
• Οι τιμές κινητής υποδιαστολής περνούν σε καταχωρητές xmm.

Οι structs, ωστόσο, αποτελούν ειδική περίπτωση. Κατά κανόνα, όλα τα πεδία σε μια struct καταλαμβάνουν γειτονικό χώρο στη μνήμη και θα πρέπει να τοποθετούνται σε έναν μόνο καταχωρητή όποτε είναι δυνατόν:

struct single_type {
    int16_t first;
    int16_t second;
    int16_t third;
    int16_t fourth;
};
// this struct occupies 8 bytes
// it is entirely passed in the same GPR register:
// the field 'first' is passed on the lowest 2 bytes
// each subsequent field is passed in the following 2 bytes

Αν μια struct έχει πεδία με ακέραιες τιμές και επίσης πεδία με τιμές κινητής υποδιαστολής, κάθε διαδοχικό 8-byte στη struct θα πρέπει να ταξινομείται ξεχωριστά:

struct mixed_types {
    double first;
    int second;
    int third;
};
// this struct occupies 16 bytes
// the field 'first' is passed in the first 8 bytes of a xmm register
// the fields 'second' and 'third' are passed in the same GPR register:
// the field 'second' is passed on the lowest 4 bytes
// the field 'third' is passed in the next 4 bytes

Σε περίπτωση που ακέραιοι και τιμές κινητής υποδιαστολής βρίσκονται στο ίδιο 8-byte, ο τύπος είναι ακέραιος και ολόκληρο το 8-byte (συμπεριλαμβανομένης της τιμής κινητής υποδιαστολής) τοποθετείται σε έναν GPR:

struct mixed_types {
    int32_t integer;
    float floating_point;
};
// this struct occupies 8 bytes
// it is entirely passed in the same GPR register:
// the field 'integer' is passed on the lowest 4 bytes
// the field 'floating_point' is passed on the next 4 bytes

Ωστόσο, οι structs με μέγεθος μεγαλύτερο από 16 byte τοποθετούνται συνήθως στη μνήμη, ανεξάρτητα από τον τύπο κάθε 8-byte:

struct big_struct {
    uint8_t first;
    double second;
    int64_t third;
};
// this struct occupies 24 bytes, including 7 padding bytes between 'first' and 'second'
// it is entirely passed in memory

Όταν μια struct περνά ως όρισμα σε μια συνάρτηση, χρησιμοποιεί όσους καταχωρητές χρειάζεται. Αν τοποθετηθεί στη μνήμη, χρησιμοποιείται αντ' αυτού η στοίβα.

Παρόμοιοι κανόνες ισχύουν για structs που επιστρέφονται από μια συνάρτηση. Συνήθως επιστρέφονται πρώτα στους rax και rdx (αν είναι ακέραιας τιμής) ή στους xmm0 και xmm1 (αν είναι τιμής κινητής υποδιαστολής). Αν τοποθετηθεί στη μνήμη, ωστόσο, ο καλών πρέπει να δεσμεύσει χώρο για αυτό και να περάσει τη διεύθυνση αυτής της θέσης μνήμης ως ένα σιωπηρό πρώτο όρισμα στη συνάρτηση (στον rdi). Στη συνέχεια, η συνάρτηση αποθηκεύει τη struct σε αυτόν τον χώρο και επιστρέφει τη διεύθυνσή της στον rax.