نیاز به سرعت

رابطه با زبان C: ساختار

در زبان C، یک ساختار یک نوع ترکیبی است که از فیلدهای مختلف تشکیل شده است. هر فیلد نوع و اندازه‌ی خودش را دارد.

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

همترازی

همترازی یک نوع، توانی از دو و نامنفی است (۱، ۲، ۴، ۸، ...) که نشان‌دهنده‌ی الزامی روی آدرس آن است. هر شیء از آن نوع باید در آدرسی قرار بگیرد که مضربی از همترازی آن باشد.

برای یک نوع اولیه، همترازی معمولاً برابر با اندازه‌ی آن است، بنابراین، برای مثال، یک int32_t معمولاً همترازی ۴ بایتی دارد. این یعنی int32_t باید در مرزهای ۴ بایتی تخصیص داده شود.

اما همترازی یک ساختار، بیشترین همترازی میان فیلدهای آن است. پس برای مثال، struct example که در بالا تعریف شد، همترازی ۸ بایتی خواهد داشت، چون این همترازی 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 همترازی ۱ دارد و می‌تواند در هر آدرسی قرار بگیرد. چون فیلد four_byte همترازی ۴ دارد، فیلدهای داخل ساختار نیز باید مرزهای ۴ بایتی را رعایت کنند. این یعنی باید بین هر دو فیلد در ساختار، تعدادی بایت باشد که مضربی از ۴ است. چون one_byte فقط ۱ بایت را اشغال می‌کند، سپس ۳ بایت پرکننده بعد از آن درج می‌شود تا این مرز رعایت شود.

فیلدهای مجاور هرگاه ممکن باشد گروه‌بندی می‌شوند تا تعداد بایت‌های پرکننده‌ی لازم به کمینه برسد:

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'

مهم است که هرگاه به یک ساختار در اسمبلی دسترسی پیدا می‌کنید، بایت‌های پرکننده‌ی احتمالی را در نظر بگیرید.

قرارداد فراخوانی

به‌طور کلی، مقادیر همان‌طور که انتظار می‌رود به توابع ارسال و از آن‌ها بازگردانده می‌شوند:

• مقادیر صحیح، شامل آدرس‌های حافظه و enumها، در رجیسترهای همه‌منظوره (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

اگر یک ساختار فیلدهایی با مقادیر صحیح و همچنین فیلدهایی با مقادیر شناور داشته باشد، هر ۸ بایت متوالی در ساختار باید جداگانه دسته‌بندی شود:

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

اگر مقادیر صحیح و شناور در همان ۸ بایت قرار بگیرند، نوع آن صحیح است و کل ۸ بایت (شامل مقدار شناور) در یک 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

اما ساختارهایی با حجم بیش از ۱۶ بایت معمولاً در حافظه قرار می‌گیرند، صرف‌نظر از نوع هر ۸ بایت:

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 بازمی‌گرداند.