لماذا لا يمكن أن يقوم C compilers بإعادة ترتيب أعضاء البنية لإزالة حشوة المحاذاة؟




struct compiler-optimization (8)

ممكن تكرار:
لماذا لا تقوم دول مجلس التعاون الخليجي بتحسين الهياكل؟
لماذا لا يجعل C ++ الهيكل أكثر إحكاما؟

خذ بعين الاعتبار المثال التالي على جهاز 32 بت x 86:

بسبب قيود المحاذاة ، الهيكل التالي

struct s1 {
    char a;
    int b;
    char c;
    char d;
    char e;
}

يمكن تمثيل أكثر كفاءة الذاكرة (12 مقابل 8 بايت) إذا تم إعادة ترتيب الأعضاء كما في

struct s2 {
    int b;
    char a;
    char c;
    char d;
    char e;
}

وأنا أعلم أنه لا يسمح compilers C / C ++ للقيام بذلك. سؤالي هو لماذا تم تصميم اللغة بهذه الطريقة. بعد كل شيء ، قد ينتهي بنا الأمر إلى إهدار كميات هائلة من الذاكرة ، كما أن المراجع مثل struct_ref->b لن تهتم بالفرق.

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

  1. يجب علينا فقط إعادة تنظيم البنية إذا كانت ضرورية بالفعل (لا تفعل أي شيء إذا كانت البنية "ضيقة" بالفعل)
  2. تنظر القاعدة فقط إلى تعريف البنية ، وليس داخل البنى الداخلية. هذا يضمن أن نوع البنية له نفس التخطيط سواء كان داخليًا في بنية أخرى أم لا
  3. تخطيط الذاكرة المترجمة لبنية معينة يمكن التنبؤ به نظرًا لتعريفه (أي أن القاعدة ثابتة)

قم بإدراك حججك واحدًا تلو الآخر

  • تخطيط البيانات منخفض المستوى ، "عنصر الأقل مفاجأة" : فقط اكتب البنى الخاصة بك بأسلوب ضيق بنفسك (مثل @ Perry's answer) ولم يتغير شيء (الشرط 1). إذا أردت ، لسبب غريب ، أن يكون هناك حشو داخلي ، يمكنك إدخاله يدويًا باستخدام متغيرات وهمية ، و / أو قد تكون هناك كلمات رئيسية / توجيهات.

  • اختلافات برنامج التحويل البرمجي : المتطلب 3 يزيل هذا القلق. في الواقع ، من تعليقاتDavid Heffernan ، يبدو أن لدينا هذه المشكلة اليوم لأن مختلف compilers الوسادة بشكل مختلف؟

  • التحسين : نقطة كاملة من إعادة ترتيب هو تحسين الذاكرة (الذاكرة). أرى الكثير من الإمكانات هنا. قد لا نتمكن من إزالة الحشو كله معًا ، ولكن لا أرى كيف يمكن أن تؤدي إعادة الترتيب إلى الحد من التحسين بأي طريقة.

  • نوع الصب : يبدو لي أن هذه هي أكبر مشكلة. لا يزال ، يجب أن يكون هناك طرق حول هذا الموضوع. وبما أن القواعد ثابتة في اللغة ، فإن المجمع قادر على معرفة كيفية إعادة ترتيب الأعضاء ، والاستجابة وفقًا لذلك. كما ذكر أعلاه ، سيكون من الممكن دائمًا منع إعادة الترتيب في الحالات التي تريد فيها التحكم الكامل. كذلك ، يضمن المتطلب 2 أن لا يتم كسر الشفرة الآمنة من النوع.

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

لاحظ أنني لا أتحدث عن تغيير اللغة - إلا إذا كان من الممكن (أو ينبغي) تصميمها بشكل مختلف.

أعرف أن سؤالي افتراضي ، لكنني أعتقد أن المناقشة توفر رؤية أعمق في المستويات الدنيا لتصميم الآلة واللغة.

أنا جديد هنا ، لذا لا أعرف ما إذا كان ينبغي عليّ طرح سؤال جديد لهذا الغرض. من فضلك قل لي إذا كان هذا هو الحال.


إذا كنت تقرأ / تكتب البيانات الثنائية من وإلى هياكل C ، فإن إعادة ترتيب أعضاء struct ستكون كارثة. لن يكون هناك طريقة عملية بالفعل لملء الهيكل من مخزن مؤقت ، على سبيل المثال.


إن حالتك محددة جدًا حيث أنها تتطلب إعادة ترتيب العنصر الأول من struct . هذا غير ممكن ، لأن العنصر الذي تم تعريفه أولاً في struct يجب أن يكون دائمًا عند الإزاحة 0 . الكثير من الكود (الزائف) قد ينكسر إذا كان هذا مسموحًا به.

مؤشرات أكثر عموما من subobjects التي تعيش داخل كائن أكبر يجب أن تسمح دائما للمقارنة مؤشر. يمكنني أن أتخيل أن بعض التعليمات البرمجية التي تستخدم هذه الميزة سوف تنكسر إذا ما قمت بتغيير الترتيب. ومن أجل هذه المقارنة ، لن تساعد معرفة المترجم عند نقطة التعريف: لا يحتوي مؤشر إلى كائن فرعي على "علامة" يقوم به الكائن الأكبر الذي ينتمي إليه. عند تمريرها إلى وظيفة أخرى على هذا النحو ، يتم فقدان جميع المعلومات عن سياق محتمل.


تم تصميم C ويهدف إلى تمكين كتابة التعليمات البرمجية غير المحمولة وتنسيق التعليمات البرمجية بلغة عالية المستوى. إعادة ترتيب محتويات البنية خلف الجزء الخلفي من المبرمج سوف يدمر تلك القدرة.

مراقبة هذا الرمز الفعلي من ip.h الخاص بـ NetBSD:


/*
 * Structure of an internet header, naked of options.
 */
struct ip {
#if BYTE_ORDER == LITTLE_ENDIAN
    unsigned int ip_hl:4,       /* header length */
             ip_v:4;        /* version */
#endif
#if BYTE_ORDER == BIG_ENDIAN
    unsigned int ip_v:4,        /* version */
             ip_hl:4;       /* header length */
#endif
    u_int8_t  ip_tos;       /* type of service */
    u_int16_t ip_len;       /* total length */
    u_int16_t ip_id;        /* identification */
    u_int16_t ip_off;       /* fragment offset field */
    u_int8_t  ip_ttl;       /* time to live */
    u_int8_t  ip_p;         /* protocol */
    u_int16_t ip_sum;       /* checksum */
    struct    in_addr ip_src, ip_dst; /* source and dest address */
} __packed;

هذه البنية متطابقة في التخطيط إلى رأس مخطط بيانات IP. يتم استخدامه لتفسير النقط في الذاكرة التي تم تحطيمها بواسطة وحدة تحكم Ethernet مباشرة كرؤوس كتل بيانات IP. تخيل لو أن المترجم أعاد ترتيب المحتويات بشكل عشوائي من تحت المؤلف - ستكون كارثة.

ونعم ، ليست محمولة على وجه التحديد (بل هناك توجيهات غير قابلة __packed من __packed مجلس التعاون الخليجي تعطى هناك عبر ماكرو __packed ) ولكن هذا ليس هو الهدف. تم تصميم C خصيصًا لتتيح لك كتابة التعليمات البرمجية غير المحمولة عالية المستوى لقيادة الأجهزة. هذا هو وظيفتها في الحياة.


سيؤدي ذلك إلى تغيير دلالات عمليات المؤشر لإعادة ترتيب أعضاء البنية. إذا كنت تهتم بتمثيل الذاكرة المدمجة ، فستكون مسؤوليتك كمبرمج لمعرفة بنية الهدف ، وتنظيم الهياكل وفقًا لذلك.


لا أستطيع أن أكون عضوًا في WG14 ، لا يمكنني قول أي شيء محدد ، ولكن لدي أفكاري الخاصة:

  1. من شأنه أن ينتهك مبدأ الأقل مفاجأة - قد يكون هناك سبب وجيه ملعون لأنني أرغب في وضع عناصري في ترتيب معين ، بغض النظر عما إذا كانت أكثر فعالية من حيث المساحة أم لا ، ولا أريد من المترجم إعادة ترتيب تلك العناصر

  2. لديه القدرة على كسر كمية غير عادية من الشفرات الموجودة - هناك الكثير من الشفرات القديمة التي تعتمد على أشياء مثل عنوان الهيكل هو نفسه عنوان العضو الأول (شاهد الكثير من MacOS الكلاسيكي رمز ذلك الافتراض) ؛

يعالج C99 Rationale النقطة الثانية مباشرة ("الشفرة الحالية مهمة ، التطبيقات القائمة ليست") وتعالج بشكل غير مباشر الأولى ("الوثوق بالمبرمج").


لنفترض أن لديك رأس مع

struct s1 {
    char a;
    int b;
    char c;
    char d;
    char e;
}

وهذا جزء من مكتبة منفصلة (التي لديك فقط الثنائيات المترجمة التي تم تجميعها بواسطة مترجم غير معروف) وترغب في استخدام هذه البنية للاتصال بهذه المكتبة ،

إذا سمح لل مترجم بإعادة ترتيب الأعضاء بأي طريقة يرضيها ، فسيكون هذا مستحيلاً لأن المترجم العميل لا يعرف ما إذا كان سيستخدم البنية كما هو أو محسّن (ثم يذهب من الأمام أو من الخلف) أو حتى مبطن بالكامل مع كل عضو الانحياز على فترات 4 بايت

لحل هذه المشكلة ، يمكنك تحديد خوارزمية حتمية للضغط ولكنها تتطلب أن يقوم جميع المترجمين بتنفيذها وأن الخوارزمية تكون جيدة (من حيث الكفاءة). من السهل الاتفاق على قواعد الحشو أكثر من مجرد إعادة الترتيب

من السهل إضافة #pragma التي تحظر التحسين عندما تحتاج إلى تخطيط لبنية محددة يكون بالضبط ما تحتاجه لذلك لا توجد مشكلة


هناك العديد من الأسباب التي تجعل المترجم C لا يمكنه إعادة ترتيب الحقول تلقائيًا:

  • لا يعرف المترجم C ما إذا كانت struct تمثل بنية ذاكرة كائنات تتجاوز وحدة التجميع الحالية (على سبيل المثال: مكتبة أجنبية ، ملف على القرص ، بيانات الشبكة ، جداول صفحات وحدة المعالجة المركزية ، ...). في مثل هذه الحالة ، يتم تعريف البنية الثنائية للبيانات أيضًا في مكان لا يمكن الوصول إليه من خلال المحول البرمجي ، لذلك فإن إعادة إنشاء حقول struct يؤدي إلى إنشاء نوع بيانات لا يتوافق مع التعريفات الأخرى. على سبيل المثال ، يحتوي رأس الملف في ملف ZIP على حقول 32 بت محاذاة غير صحيحة. إن إعادة ترتيب الحقول سيجعل من المستحيل على الشفرة C قراءة الرأس أو كتابته مباشرة (بافتراض أن تطبيق ZIP يرغب في الوصول إلى البيانات مباشرة):

    struct __attribute__((__packed__)) LocalFileHeader {
        uint32_t signature;
        uint16_t minVersion, flag, method, modTime, modDate;
        uint32_t crc32, compressedSize, uncompressedSize;
        uint16_t nameLength, extraLength;
    };
    

    تمنع السمة packed المحول البرمجي من محاذاة الحقول وفقًا إلى محاذاةها الطبيعية ، ولا علاقة لها بمشكلة الطلب الميداني. قد يكون من الممكن إعادة ترتيب الحقول من LocalFileHeader بحيث يحتوي بنية الحد الأدنى من حجم كافة الحقول محاذاة إلى المحاذاة الطبيعية الخاصة بهم. ومع ذلك ، لا يستطيع المترجم أن يختار إعادة ترتيب الحقول لأنه لا يعرف أن البنية محددة بالفعل بمواصفات ملف ZIP.

  • C لغة غير آمنة. لا يعرف المترجم C ما إذا كان سيتم الوصول إلى البيانات عبر نوع مختلف عن تلك التي يشاهدها المترجم ، على سبيل المثال:

    struct S {
        char a;
        int b;
        char c;
    };
    
    struct S_head {
        char a;
    };
    
    struct S_ext {
        char a;
        int b;
        char c;
        int d;
        char e;
    };
    
    struct S s;
    struct S_head *head = (struct S_head*)&s;
    fn1(head);
    
    struct S_ext ext;
    struct S *sp = (struct S*)&ext;
    fn2(sp);
    

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

  • إذا كان نوع struct مضمنًا في نوع struct آخر ، فمن المستحيل تضمين struct الداخلية:

    struct S {
        char a;
        int b;
        char c, d, e;
    };
    
    struct T {
        char a;
        struct S s; // Cannot inline S into T, 's' has to be compact in memory
        char b;
    };
    

    وهذا يعني أيضًا أن نقل بعض الحقول من S إلى بنية منفصلة يعطّل بعض التحسينات:

    // Cannot fully optimize S
    struct BC { int b; char c; };
    struct S {
        char a;
        struct BC bc;
        char d, e;
    };
    
  • نظرًا لأن معظم برامج التحويل البرمجي لـ C تعمل على تحسين برامج التحويل البرمجي ، تتطلب إعادة تنظيم حقول البنية إجراء تحسينات جديدة ليتم تنفيذها. من المشكوك فيه ما إذا كانت تلك التحسينات ستكون قادرة على القيام بما هو أفضل من المبرمجين القادرين على الكتابة. إن تصميم هياكل البيانات يدويًا أقل استهلاكا للوقت من مهام المترجم الأخرى مثل تخصيص السجلات ، التضمين الوظيفي ، الطي الثابت ، تحويل عبارة التبديل إلى البحث الثنائي ، إلخ. وهكذا ، فإن الفوائد التي يمكن اكتسابها عن طريق السماح للملقم بتحسين هياكل البيانات يبدو أقل ملموس من تحسينات المجمع التقليدي.


يتم استخدام الهياكل لتمثيل الأجهزة المادية في أدنى المستويات. على هذا النحو لا يستطيع المترجم تحريك الأشياء لتلائمها على هذا المستوى.

ومع ذلك ، لن يكون من غير المعقول وجود # pragma تسمح للمجمّع بإعادة ترتيب بنية تستند إلى الذاكرة تمامًا والتي يتم استخدامها داخليًا فقط في البرنامج. ومع ذلك أنا لا أعرف من هذا الوحش (ولكن هذا لا يعني القرفصاء - أنا خارج الاتصال مع C / C ++)





memory-alignment