الحاجة إلى السرعة

التعامل مع لغة C: البنى

في لغة C، البنية هي نوع مركب، مكوّن من حقول مختلفة. كل حقل له نوعه وحجمه الخاص.

على سبيل المثال، يعرّف هذا نوعًا مكوّنًا من ثلاثة أعداد صحيحة، اثنان بحجم 4 بايت وواحد بحجم 8 بايت:

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

يمكن أن تحتوي البنية أيضًا على بنى أخرى:

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

إذا كان أحد حقول البنية مصفوفة، فإن كل البايتات المخصصة للمصفوفة تكون جزءًا من البنية. ولكن، إذا كان الحقل مجرد مؤشر إلى المصفوفة، فيجب تخزين المصفوفة في مكان آخر:

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 بايت. هذا يعني أنه يجب تخصيص int32_t عند حدود 4 بايت.

أما محاذاة البنية، فهي المحاذاة القصوى لأي من حقولها. لذا، على سبيل المثال، سيكون للـ struct example، المعرّف أعلاه، محاذاة 8 بايت، لأن هذه هي محاذاة uint64_t.

إذا كانت محاذاة حقل في البنية أصغر من محاذاة البنية، فقد يتم إدراج بايتات حشو بعد ذلك الحقل. يضمن هذا أن الحقول التالية والبنية ككل تستوفي متطلبات المحاذاة. عمليًا، هذا يعني أنه على الرغم من أن بايتات الحشو تلك تساهم في حجم البنية، إلا أنها لا تُستخدم في قيمة البنية:

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'

لاحظ أنه في البنية المعرّفة أعلاه، الحقل 'one_byte' له محاذاة 1 ويمكن وضعه في أي عنوان. بما أن الحقل 'four_byte' له محاذاة 4، يجب أن تحترم الحقول في البنية أيضًا حدود 4 بايت. هذا يعني أنه يجب أن يكون عدد البايتات بين أي حقلين في البنية من مضاعفات 4. بما أن 'one_byte' يشغل بايتًا واحدًا فقط، يتم إدراج 3 بايتات حشو بعده لاحترام هذا الحد.

يتم تجميع الحقول المتجاورة كلما أمكن ذلك لتقليل عدد بايتات الحشو اللازمة:

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 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'

من المهم مراعاة أي بايتات حشو محتملة عند الوصول إلى بنية في لغة التجميع.

اصطلاح الاستدعاء

بشكل عام، يتم تمرير القيم إلى الدوال وإرجاعها منها كما هو متوقع:

• يتم تمرير قيم الأعداد الصحيحة، بما في ذلك عناوين الذاكرة والتعدادات، في السجلات العامة (GPR).
• يتم تمرير قيم الفاصلة العائمة في سجلات xmm.

لكن البنى هي حالة خاصة. كقاعدة عامة، تشغل جميع الحقول في البنية مساحة متجاورة في الذاكرة ويجب وضعها في سجل واحد كلما أمكن ذلك:

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

إذا كانت البنية تحتوي على حقول بقيم عدد صحيح وأيضًا حقول بقيم فاصلة عائمة، فيجب تصنيف كل 8 بايت متتالية في البنية بشكل منفصل:

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 بايت، يكون النوع عددًا صحيحًا ويتم وضع 8 البايتات بأكملها (بما في ذلك قيمة الفاصلة العائمة) في سجل عام:

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

ومع ذلك، عادةً ما يتم وضع البنى التي يزيد حجمها عن 16 بايت في الذاكرة، بغض النظر عن نوع كل 8 بايت:

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

عند تمرير بنية كوسيط إلى دالة، فإنها تستخدم أكبر عدد ممكن من السجلات حسب الحاجة. إذا تم وضعها في الذاكرة، يتم استخدام المكدس بدلاً من ذلك.

تنطبق قواعد مماثلة على البنى المُرجعة من دالة. عادةً ما يتم إرجاعها أولاً في rax و rdx (إذا كانت ذات قيمة عدد صحيح) أو xmm0 و xmm1 (إذا كانت ذات قيمة فاصلة عائمة). إذا تم وضعها في الذاكرة، ومع ذلك، يجب على المستدعي حجز مساحة لها وتمرير عنوان موقع الذاكرة هذا كوسيط أول ضمني للدالة (في rdi). ثم تخزّن الدالة البنية في هذه المساحة وتُرجع عنوانها في rax.